第二题一直没过，但是的确是用数组模拟的，不知道有没有大佬出点数据hack一下帮我排排错
题目链接：http://oj.csen.org.cn/contest/9
A 水杯
直接按照操作模拟即可，每个操作都是O(1)复杂度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include<bits/stdc++.h> using namespace std; int n,L,A,B,T=-274,V; int main() { int opt,x; scanf("%d%d%d%d",&n,&L,&A,&B); while (n--) { scanf("%d",&opt); if (opt==1) scanf("%d",&x),T=x; if (opt==2) scanf("%d",&x),V=x; if (opt==3) if (T>=A && T<=B && V>=L) printf("%d\n",T); else printf("GG\n"); } return 0; } |
B 鳖
官方给的题解是用队列模拟，这里我直接用的数组模拟，其他满分做法 也有数组模拟的，不知道我的哪里有问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<bits/stdc++.h> using namespace std; #define N 100010 int n,a[N<<2],A[N],B[N],totA,totB,flagA[N],flagB[N],cnt; int main() { scanf("%d",&n); for (int i=1;i<=4*n-2;++i) scanf("%d",&a[i]); for (int i=1;i<=4*n-2;i+=2) { ++flagA[a[i]]; if (flagA[a[i]]==1) A[++totA]=a[i]; if (flagA[a[i]]==2) --totA,flagA[a[i]]=0; } for (int i=2;i<=4*n-2;i+=2) { ++flagB[a[i]]; if (flagB[a[i]]==1) B[++totB]=a[i]; if (flagB[a[i]]==2) --totB,flagB[a[i]]=0; } int headA=1,headB=1; while (1) { while (!flagB[B[headB]] && headB<totB) ++headB; while (!flagA[A[headA]] && headA<totA) ++headA; if (headA>totA || headB>totB) { printf("%d",cnt); break; } ++cnt; if (cnt&1) { ++flagA[B[headB]]; if (flagA[B[headB]]==1) A[++totA]=B[headB]; if (flagA[B[headB]]==2) --totA,flagA[B[headB]]=0; --flagB[B[headB]],++headB,--totB; } else { ++flagB[A[headA]]; if (flagB[A[headA]]==1) B[++totB]=A[headA]; if (flagB[A[headA]]==2) --totB,flagB[A[headA]]=0; --flagA[A[headA]],++headA,--totA; } } return 0; } |
C 顺序安排
在考场上其实想出来正解了，但是没时间写了
其实通过手玩发现按照dfs序的序列最终的值是最小的，然而dfs序不唯一，如果子树大的排在前面可能导致子树小的产生更大的值，所以应该把子树小的排在前面，用vector存储树，然后根据子树大小排序即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define N 600010 int n,k,cnt,h[N],father[N],size[N],pos[N],tot; vector<int>G[N]; LL ans; void dfs1(int x) { size[x]=1; for (int i=0;i<G[x].size();++i) dfs1(G[x][i]),size[x]+=size[G[x][i]]; } bool cmp(int x,int y) { return size[x]<size[y]; } void dfs2(int x) { pos[x]=++tot,sort(G[x].begin(),G[x].end(),cmp); for (int i=0;i<G[x].size();++i) dfs2(G[x][i]); } int main() { scanf("%d%d",&n,&k); for (int i=2;i<=n;++i) scanf("%d",&father[i]),G[father[i]].push_back(i); dfs1(1),dfs2(1); for (int i=2;i<=n;++i) ans+=(LL)(pos[i]-pos[father[i]])*(LL)k; ans+=(LL)k; return printf("%lld",ans),0; } |