一本通
树堆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;
}
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);
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}