首页 > 代码库 > 2016弱校联萌十一专场10.3 遗憾题合集
2016弱校联萌十一专场10.3 遗憾题合集
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"); } 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.\n"); } } 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.\n"); } else { tmp=*se2.begin(); se2.erase(tmp); se1.insert(tmp); se2.insert(a[i]); cout<<a[i].s; printf(" is not working now.\n"); cout<<tmp.s; printf(" is working hard now.\n"); } 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.\n"); cout<<tmp.s; printf(" is not working now.\n"); } else { se2.insert(a[i]); // se2.erase(tmp); //se1.insert(tmp); cout<<a[i].s; printf(" is not working now.\n"); //cout<<tmp.s; //printf(" is working hard now.\n"); /// } } 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.\n"); } else { se2.erase(tmp); se2.insert(a[i]); se1.insert(tmp); cout<<a[i].s; printf(" is not working now.\n"); cout<<tmp.s; printf(" is working hard now.\n"); } } else { se2.insert(a[i]); cout<<a[i].s; printf(" is not working now.\n"); } } } 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\n",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?
2016弱校联萌十一专场10.3 遗憾题合集