http://acm-icpc.aitea.net/index.php?2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95
C.We don't wanna work!
@siludose 你要的代码，做好了参考看
SB模拟，xjb模拟
#include <iostream> #include <algorithm> #include <stdio.h> #include <cstring> #include <queue> #include <bitset> #include <set> #include <map> using namespace std; typedef long long LL; const int MAXN = 1e6+5; struct Node { string s; int time; int d; } a[MAXN]; bool cmp(Node a, Node b) { if(a.d == b.d) return a.time > b.time; return a.d > b.d; } struct cmp2 { bool operator()(const Node a, const Node b)const { if(a.d == b.d) return a.time > b.time; return a.d > b.d; } }; struct cmp1 { bool operator()(const Node a, const Node b)const { if(a.d == b.d) return a.time < b.time; return a.d < b.d; } }; set<Node,cmp1>se1; set<Node,cmp2>se2; map<string,Node>mp; string s; int main() { int n, m; while(~scanf("%d",&n)) { se1.clear(); se2.clear(); mp.clear(); double tp = 1.0*n*0.2; int nn = (int)tp; int tn = n; for(int i=1; i<=tn; i++) { a[i].time = i; cin>>a[i].s>>a[i].d; mp[a[i].s] = a[i]; } sort(a+1, a+1+tn, cmp); for(int i=1; i<=nn; i++) se1.insert(a[i]); for(int i=nn+1; i<=n; i++) se2.insert(a[i]); scanf("%d",&m); Node tmp; for(int i=tn+1; i<=tn+m; i++) { char op; cin>>op; if(op == '-') { cin>>s; tmp = mp[s]; if(se1.erase(tmp)) nn--; se2.erase(tmp); if(nn>(int)(1.0*(n-1)*0.2)) { nn--; tmp=*se1.begin(); se1.erase(tmp); se2.insert(tmp); cout<<tmp.s; printf(" is not working now. "); } n--; if(nn<(int)(1.0*(n)*0.2)) { nn++; tmp=*se2.begin(); se1.insert(tmp); se2.erase(tmp); cout<<tmp.s; printf(" is working hard now. "); } } else///++ { cin>>a[i].s>>a[i].d; a[i].time=i; mp[a[i].s]=a[i]; //cout<<nn<<" "<<n<<endl; if(nn<(int)(1.0*(n+1)*0.2))///+0.2 { if(a[i].d>(*se2.begin()).d||a[i].d==(*se2.begin()).d&&a[i].time>(*se2.begin()).time) { se1.insert(a[i]); cout<<a[i].s; printf(" is working hard now. "); } else { tmp=*se2.begin(); se2.erase(tmp); se1.insert(tmp); se2.insert(a[i]); cout<<a[i].s; printf(" is not working now. "); cout<<tmp.s; printf(" is working hard now. "); } nn++; //cout<<"nn"<<nn<<endl; } else///=0.2 { if(nn!=0) { tmp=*se1.begin(); if(a[i].d>tmp.d||a[i].d==tmp.d&&a[i].time>tmp.time) { se1.erase(tmp); se1.insert(a[i]); se2.insert(tmp); cout<<a[i].s; printf(" is working hard now. "); cout<<tmp.s; printf(" is not working now. "); } else { se2.insert(a[i]); // se2.erase(tmp); //se1.insert(tmp); cout<<a[i].s; printf(" is not working now. "); //cout<<tmp.s; //printf(" is working hard now. "); /// } } else { tmp=*se2.begin(); if((int)(1.0*(n+1)*0.2)>0) { if(a[i].d>tmp.d||a[i].d==tmp.d&&a[i].time>tmp.time) { se1.insert(a[i]); cout<<a[i].s; printf(" is working hard now. "); } else { se2.erase(tmp); se2.insert(a[i]); se1.insert(tmp); cout<<a[i].s; printf(" is not working now. "); cout<<tmp.s; printf(" is working hard now. "); } } else { se2.insert(a[i]); cout<<a[i].s; printf(" is not working now. "); } } } n++; }///++ } } return 0; }
E.Similarity of Subtrees
真心佩服那帮用递归栈都能不爆栈的大神。。。不说了，伤心题
题目要求求出相似点对对数，相似指2对子树在不同且对应深度的结点都一样
可以看做可加的向量：(d0,d1, ... ,dn)其中dk是指深度为k的结点个数
父结点的向量是其本身(1,0,0, ... )+(0,所有子结点的向量之和)
不过要是直接向量上会o(n^2)滚粗
所以搞成hash值:d0*a^0+d1*a^1+d2*a^2+...
然后发现数字太大了，要模
a>100000就可以，没有哪个向量分量超过100000
对结果模的数m>1000000000，且必须是素数，感觉不设这么大会有hash冲突
可以map搞o(nlogn)或者hash_map搞o(n)
比赛中要注意要是这种数据都能爆栈，就用非递归+stack<int>硬杠
此题还可以bfs硬撑
#include <iostream> #include <stdio.h> #include <queue> #include <string.h> #include <vector> #include <map> #include <string> #include <set> using namespace std; typedef long long LL; const LL maxn=1e6+10,p=9901,mod=1e9+7; vector<LL>G[maxn]; LL hash_v[maxn]; map<LL,LL>mp; map<LL,LL>::iterator it; void dfs(LL u) { hash_v[u]=1; for(LL i=0; i<G[u].size(); i++) { LL v=G[u][i]; dfs(v); hash_v[u]=(hash_v[u]+hash_v[v]*p)%mod; } mp[hash_v[u]]++; } int main() { ///freopen("in.txt","r",stdin); LL n; LL u,v; while(scanf("%lld",&n)!=-1) { for(LL i=0; i<=n; i++) G[i].clear(); mp.clear(); for(LL i=1; i<n; i++) { scanf("%lld%lld",&u,&v); G[u].push_back(v); } dfs(1); LL ans=0; for(it=mp.begin(); it!=mp.end(); it++) ans+=it->second*(it->second-1)/2; printf("%lld ",ans); } return 0; }
F.Escape from the Hell
题意：有人在悬崖上的1条绳子上，
有n罐能量饮料，喝的当天可以向上爬ai米，但是若没有爬到顶点，之后会下滑bi米，不喝则不会动
与此同时，有只蜘蛛第i天会不下滑地向上ci米，且上升到人身上就会致死
问人能否逃离，第几天逃离
题解：枚举最后1天喝哪种饮料，并从饮料集合去除
把其他饮料按照a(i)-b(i)的大小排序，负数的一定没用
设sdis(i)=sdis(i-1)+c(i) pdis(i)=pdis(i)+a(i)-b(i)
找到最小的x使得
任何i<x都是pdis(i)>sdis(i)并且pdis(x-1)+a(x)>=L，就是逃离成功
枚举过的那个元素不用再重复枚举
G.Shere the Ruins Presevation
题意：把点集以1条平行于y轴且不相切任何点的直线分成2个点集，然后用栅栏把2个点集围成最小面积
题解：感觉就是对整个点集以凸包的围法画边，把整条x轴按照点集在x上的分量离散化
把整个图形按顺序分割出三角形，再把那些三角形根据占用x轴的区间把面积写在树状数组
查询时相邻区间查询因为分割而少掉的面积，最大的那个减去总面积就是解
andrew's monotone chain?
J.compressed formula
题意：把不同ri字符串重复si次之后前后连接，表达式就按平常的计算顺序做，问字符串对应表达式结果模1000000007
题解：还是有规律的，从左向右遇乘则预存左乘数s1，右乘数s2归0；遇加/减则把当前2个乘数乘了往左边s0加，2个乘数s1,s2初始化，s1看前面符号设1或-1
字符串的排布
1.只有数字，像68，则就是68686868..... 这样循环，s2=s2*10^字符串长度+字符串对应数字，矩阵乘法可以归并大量重复运算
2.数字和乘，像68*233，则就是68*23368*23368*233..... 这样循环，s2=s2*10^左字符串长度+左字符串对应数字
s1=s1*s2*右左连接的字符串对应数字^(重复次数-1)*右字符串
有多个乘？把中间的乘数独立出来，跟上述乘数一样快速幂
3.数字、乘和加/减，像3*4+5*6+7*8，则就是3*4+5*6+7*83*4+5*6+7*83*4+5*6+7*8......
中间的乘数计算结果独立出来，第1个左乘法公式和最后1个右乘法公式独立出来，其他的都快速幂
K.non-redundent drive
一棵无向树，有一定加油量加油站n个，一定距离的路，越长耗油越多，不能在半路耗完油，但可以在到达加油站时油正好到0再加油，一条路最多走1次，问最多走过多少个点
把答案分割为2部分：从一个点出发耗油量，到达一个点的余油量，用树分治的话可以覆盖所有点对，故使用
至于边对有顺序之分的问题，可以正着遍历子树1次，反着遍历子树1次，每次记录dp[i]，深度为i的点向上走时到根最多剩多少油
dp[i]序号从小到大，值是递增的，所以其实取最深的最大值是可以的。
如何得到这个位置？直接遍历dp数组，到最深的非-1值处向浅处刷，查询从上到下的路线时对每个点2分求答案
#include <cstdio> #include <iostream> #include <algorithm> #include <set> #include <stack> #include <map> #include <vector> #include <deque> #include <string.h> #include <bitset> #define lson l,m,ls[rt] #define rson m+1,r,rs[rt] #define inf 1e9 using namespace std; #define ll long long const int maxn = 203000; vector<pair<int,int> >G[maxn]; int done[maxn] , sum[maxn] , fN; int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int dfs1(int u,int pa){ sum[u] = 1; for(int i=0;i<G[u].size();i++){ int v = G[u][i].first , w = G[u][i].second; if( done[v] || pa == v ) continue; sum[u] += dfs1(v,u); } return sum[u]; } int dfs2(int u,int pa){ for(int i=0;i<G[u].size();i++){ int v = G[u][i].first , w = G[u][i].second; if( done[v] || pa == v ) continue; if( sum[v] * 2 >= fN ) return dfs2(v,u); } return u; } int ans; int val[maxn]; int dp[maxn] , len; //vector<pair<int,int> >p; void dfs4(int u,int pa,int d,int co,int mi){ mi = min( mi , co ); co += val[u]; int l = 1, r = len; while( l <= r ){ int m=((l+r)>>1); if( dp[m] + mi >= 0 ){ ans = max(ans,d + m); l = m+1; }else r = m-1; } for(int i=0;i<G[u].size();i++){ int v = G[u][i].first , w = G[u][i].second; if( done[v] || pa == v ) continue; dfs4(v,u,d+1,co-w,mi); } } int maxlen; void dfs3(int u,int pa,int d,int co,int mi){ co += val[u]; mi += val[u]; if( mi >= 0 ){ if( len < d ){ for(int i=len+1;i<=d;i++) dp[i] = -inf; len = d; } dp[d] = max( dp[d] , co ); maxlen = max(maxlen,d); mi = 0; } for(int i=0;i<G[u].size();i++){ int v = G[u][i].first , w = G[u][i].second; if( done[v] || pa == v ) continue; dfs3(v,u,d+1,co-w,mi-w); } } void sol(int u){ len = 1; dp[1] = val[u]; int i,j; for(i=0;i<G[u].size();i++){ int v = G[u][i].first , w = G[u][i].second; if( done[v] ) continue; dfs4(v,u,1,-w,-w); maxlen = -1; dfs3(v,u,2,val[u]-w,-w); for(j=maxlen-1;j>=0;j--) dp[j] = max(dp[j],dp[j+1]); } len = 1; dp[1] = val[u]; for(i=G[u].size()-1;i>=0;i--){ int v = G[u][i].first , w = G[u][i].second; if( done[v] ) continue; dfs4(v,u,1,-w,-w); maxlen = -1; dfs3(v,u,2,val[u]-w,-w); for(j=maxlen-1;j>=0;j--) dp[j] = max(dp[j],dp[j+1]); } ans = max( ans , len ); // printf("u %d ans %d len %d ",u,ans,len); } void dfs(int u){ fN = dfs1(u,-1); int r = dfs2(u,-1); sol(r); done[r] = 1; for(int i=0;i<G[r].size();i++){ int v = G[r][i].first; if( !done[v] ) dfs(v); } } void solve(){ ans = -1; memset(done,0,sizeof done); dfs(1); } int n; int main() { int i; // freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++){ scanf("%d",&val[i]); G[i].clear(); } int a,b,c; for(i=0;i<n-1;i++){ scanf("%d%d%d",&a,&b,&c); G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } solve(); printf("%d ",ans); } return 0; }