一本通刷题

一本通
树堆part
1
http://ybt.ssoier.cn:8088/problem_show.php?pid=1336
树的遍历

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=1e5+52; 
int n,m,x,y;
int tr[N];

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,1,m+1) x=read(),y=read(),tr[y]=x;
	int root;
	rep(i,1,n+1) if(!tr[i]) {root=i;break;}
	int maxn=-INF,maxroot;
	rep(i,1,n+1) 
	{
		int sum=0;
		rep(j,1,n+1) if(tr[j]==i) sum++;
		if(maxn<sum)maxn=sum,maxroot=i; 
	} 
	printf("%d\n%d\n",root,maxroot);
	rep(i,1,n+1) if(tr[i]==maxroot) printf("%d ",i);
	puts("");
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


2

http://ybt.ssoier.cn:8088/problem_show.php?pid=1337

trie,建立26个tr,然后没有建点,有的话,记录以此为结尾的单词的数目

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=1e6+52;
int tr[N][26];//字典树 
string s;
int val[N];
int tot=0;
void insert(string s)
{
	int len =s.size();
	int root=0;
	rep(i,0,len)
	{
		int id=s[i]-'0';
		if(tr[root][id]==0)tr[root][id]=++tot;
		root=tr[root][id];
	}	 
} 

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	while(cin>>s) insert(s);
	printf("%d\n",tot+1);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);

3

http://ybt.ssoier.cn:8088/problem_show.php?pid=1338
一个图论题,就是把关系读进来,然后floyd得到所有点之间的距离,然后到最后再把所有的点,到每个点的距离和比较得到最大值。

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=1e4+52;
int a[N][N],sum[N],b[N];
int n;
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read();
	rep(i,1,n+1) rep(j,1,n+1) a[i][j]=INF;
	rep(i,1,n+1) a[i][i]=0;
	rep(i,1,n+1) 
	{
		int left,right;
		b[i]=read(),left=read(),right=read();
		if(left!=0) a[i][left]=a[left][i]=1;
		if(right!=0) a[i][right]=a[right][i]=1;	
	} 
	rep(k,1,n+1)
		rep(i,1,n+1) 
			rep(j,1,n+1) 
				if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j];
	int minn=INF;
	rep(i,1,n+1)
	{
		rep(j,1,n+1) sum[i]+=a[i][j]*b[j];
		if(sum[i]<minn) minn=sum[i];
	}
	printf("%d\n",minn);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


4

http://ybt.ssoier.cn:8088/problem_show.php?pid=1339
前序遍历和中序遍历,首先中序遍历确定哪里是左,哪里是右,然后前序遍历或者后序遍历确定哪里是根,通过不断的确定左右子树和根,不断递归,最终可以实现对整个二叉树的结构得到

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
string s1,s2;
void print(int l1,int r1,int l2,int r2)
{
	int m=s2.find(s1[l1]);//通过此来求第三种遍历的方法就是索引法,中序遍历确定哪些属于左,哪些属于右,前序遍历或者后序遍历确定哪里是根节点。对应匹配即可找到位置 
	if(m>l2) print(l1+1,l1+m-l2,l2,m-1);//打印左子树 
	if(m<r2) print(l1+m-l2+1,r1,m+1,r2);//打印右子树 
	cout<<s1[l1];//打印完了,出结点,后续遍历 
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	cin>>s1>>s2;
	print(0,s1.size()-1,0,s2.size()-1);
	puts("");
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


5

dfs处理掉后续的工作,所以你只要知道现在怎么做即可。按顺序来

http://ybt.ssoier.cn:8088/problem_show.php?pid=1340

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("²âÊÔµã#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1Ãë
//        {
//            printf("²âÊÔµã#%d Time Limited Exceeded ÓÃʱ %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("²âÊÔµã#%d Accepted ÓÃʱ%.0lfms\n", i, t);
//            ok++; //ACÊýÁ¿+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("¹² %d ×é²âÊÔÊý¾Ý£¬ACÊý¾Ý %d ×é¡£ µÃ·Ö%.1lf¡£", n, ok, res);
//
//    Sleep(1000); //ÐÝÃß1Ã룬ΪÁ˽ÚÔ¼¶ÔÅÄ´ÎÊý¡£
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=1e6;
struct node
{
	char data;
	int l=-1,r=-1;
}a[N]; 
int i=-1;
string s;
int tot;
void build(int u)
{
	if(s[++i]!='.')
	{
		a[u].data=s[i];
		a[u].l=++tot;
		a[u].r=++tot; 
		build(a[u].l);
		build(a[u].r);	
	}
}
void inorder(int tot)
{
	if(a[tot].l!=-1&&a[tot].r!=-1) 
	{
		inorder(a[tot].l);
		cout<<a[tot].data;
		inorder(a[tot].r);	
	}
}
void postorder(int tot)
{
	if(a[tot].l!=-1&&a[tot].r!=-1)
	{
		postorder(a[tot].l);
		postorder(a[tot].r);
		cout<<a[tot].data;
	}
}
void dfs()
{
	char ch=pre[k++];
	if(ch=='.') return;
	dfs();
	in+=ch;
	dfs();
	post+=ch;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //һֱѭ»·£¬Ö±µ½ÕÒµ½²»Ò»ÑùµÄÊý¾Ý
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //µ± fc ·µ»Ø1ʱ£¬ËµÃ÷ÕâʱÊý¾Ý²»Ò»Ñù
            break;                          //²»Ò»Ñù¾ÍÌø³öÑ­»·
    }
#endif
	clock_t start,end;
    start=clock();
	cin>>s;
	build(0);
	inorder(0);
	puts("");
	postorder(0);
	puts("");
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


6

http://ybt.ssoier.cn:8088/problem_show.php?pid=1370

node类型的优先队列

点击查看代码
#include<bits/stdc++.h>
#include<iostream>
#include<queue>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
struct node{
    int ans,a,b,c,d;
    bool operator <(const node &n) const{
        return ans>n.ans;
    }
};

priority_queue<node> q;
int n,m;
int f(int a,int b,int c,int x){
    return a*x*x+b*x+c;    
}

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,1,n+1)
	{
		int a,b,c;a=read(),b=read(),c=read();
		int d=1;
		q.push({f(a,b,c,d),a,b,c,d});
	}
	while(m--)
	{
		node t=q.top();q.pop();
		q.push({f(t.a,t.b,t.c,t.d+1),t.a,t.b,t.c,t.d+1});
		printf("%d ",t.ans);
	} 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


7

http://ybt.ssoier.cn:8088/problem_show.php?pid=1371

priority_queue 取出当前权值最大的

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
struct peo
{
	string name;
	int value;
	bool operator <(const peo & w) const 
	{
		return value<w.value;
	}//priority_queue取出当前权值最大的 
};
priority_queue<peo> q;
int n;

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read();
	while(n--)
	{
		string tmp;
		cin>>tmp;
		int x;
		if(tmp=="pop") 
		{
			if(!q.size()) puts("none");
			else 
			{
				peo t=q.top();q.pop();
				cout<<t.name<<" "<<t.value<<'\n';
			}
		}
		else 
		{
			cin>>tmp>>x;
			q.push({tmp,x});
		}
	}
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


8

http://ybt.ssoier.cn:8088/problem_show.php?pid=1372

优先队列不好用,因为你无法同时删除用过的元素;比如第一次只输入两个最小的。
用multiset保留重复的同时,可以有序删除

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
priority_queue<int,vector<int> ,greater<int> >q1; 
priority_queue<int> q2; 
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	int n;n=read();
//	int ans=0;
//	while(n--)
//	{
//		int m;m=read();
//		if(m)
//		{
//			while(m--)
//			{
//				int x;x=read();
//				ans++;
//				q1.push(x),q2.push(x);
//			}
//			int x1=q1.top(),x2=q2.top();q1.pop(),q2.pop();
//			printf("%d %d\n",x1,x2);
//			ans-=2;			
//		}
//	}
//	while(ans)
//	{
//		int x1=q1.top(),x2=q2.top();q1.pop(),q2.pop();
//		printf("%d %d\n",x1,x2);
//		ans-=2;
//	}
//出了很大的问题,如果说输入的两个,那么输出两个,而pop也是两个,但是在两个优先队列里面其实是只删除了一个,所以开两个优先队列你不好把用过的删除掉	
//开multiset
	multiset<int> st;
	st.clear();
	rep(i,1,n+1)
	{
		int m;m=read();
		rep(j,1,m+1)
		{
			int a;a=read();
			st.insert(a);
		}
		printf("%d ",*st.begin());
		st.erase(st.begin());
		printf("%d\n",*(--st.end()));
		st.erase(--st.end());
	 } 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


9

http://ybt.ssoier.cn:8088/problem_show.php?pid=1373

很好的一道题,对于n个鱼塘,选前几个鱼塘,减去跑步时间,剩下的就是鱼塘分配,在之后用优先队列每次选取最大的。

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=1e6+52;
int num[N],d[N],t[N]; 
int n;
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read();
	rep(i,1,n+1) num[i]=read();
	rep(i,1,n+1) d[i]=read();
	rep(i,2,n+1) t[i]=read(),t[i]+=t[i-1];
	int time;time=read();
	int ans=-1;
	rep(k,1,n+1) 
	{
		int fish_time=time-t[k];
		priority_queue<PII> q;
		rep(i,1,k+1) q.push({num[i],i});
		int fish=0;
		while(q.size()&&fish_time>0)
		{
			PII t=q.top();q.pop();
			int var=t.y;
			fish+=t.x;
			fish_time--;
			t.x-=d[var];
			if(t.x>0) q.push({t.x,var});
		}
		ans=max(ans,fish);//理解上的错误,是在一个鱼塘钓鱼多长时间才会减去多少的鱼,把赶路时间减去,剩下的就是分配时间钓鱼,大根堆即可。 
	} 
	printf("%d\n",ans);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


上一篇:Lesson4


下一篇:计算机网络五层协议(TCP/IP)与七层协议(OSI)的关系与区别【计算机网络】