首页 > 代码库 > 8.10联考题解
8.10联考题解
早上起来莫名困，天天晚上十点睡为什么会困我也不是很懂……然后就迷迷瞪瞪做题，一直都不大清醒。因为一点智障的知识漏洞T3完全挂，然后T2炸内存T1做了两个多小时没做出来~但是也只能说明自己弱，好在现在发现这些坑总比联赛之后发现好得多吧。
Evensgn 剪树枝
出题人：Vincent
时间限制：1s 空间限制：128MB
题目描述
繁华中学有一棵苹果树。苹果树有 n 个节点（也就是苹果），n ? 1 条边（也就是树枝）。调皮的 Evensgn 爬到苹果树上。他发现这棵苹果树上的苹果有两种：一种是黑苹果，一种是红苹果。Evensgn 想要剪掉 k 条树枝，将整棵树分成 k + 1 个部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝的方案？
输入格式
第一行一个数字 n，表示苹果树的节点（苹果）个数。
第二行一共 n ? 1 个数字 p0, p1, p2, p3, ..., pn?2，pi 表示第 i + 1 个节点和 pi 节
点之间有一条边。注意，点的编号是 0 到 n ? 1。
第三行一共 n 个数字 x0, x1, x2, x3, ..., xn?1。如果 xi 是 1，表示 i 号节点是黑
苹果；如果 xi 是 0，表示 i 号节点是红苹果。
输出格式
输出一个数字，表示总方案数。答案对 109 + 7 取模。
样例输入 1
3
0 0
0 1 1
6
样例输出 1
2
样例输入 2
6
0 1 1 0 4
1 1 0 0 1 0
样例输出 2
1
样例输入 3
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
样例输出 3
27
数据范围
对于 30% 的数据，1 ≤ n ≤ 10。
对于 60% 的数据，1 ≤ n ≤ 100。
对于 80% 的数据，1 ≤ n ≤ 1000。
对于 100% 的数据，1 ≤ n ≤ 105。
对于所有数据点，都有 0 ≤ pi ≤ n ? 1，xi = 0 或 xi = 1。
特别地，60% 中、80% 中、100% 中各有一个点，树的形态是一条链。
题解
想不出来这题除了树归还能怎么做了……然而树归想了一个多小时也没把思路捋清楚。f[i][1/0]代表i节点是/否在一个有黑苹果的联通块里，需要按照这个含义状态转移。取模倒不是什么问题，毕竟只有乘法和加法。问题在于需要求的是方案数，子节点选与不选都是一种情况，就算把子节点断开，子节点的子树方案数也需要被计入总结果 。然后呢……然后我就被绕死了，虽然说状态数组f[][2]并没有什么问题 。一方面是因为乘法计数原理和加法计数原理绕得乱七八糟，另一方面是因为不知道应该如何选择，按颜色应该断开的好像按方案还是要计入。有一段时间是写出了差不多的状态转移方程的，又因为初值不知道应该怎么设再次凌乱 。一个统计方案数的问题，做得不确定性像概率期望一样QAQ。在演草纸上写了又写，分情况一条一条写了好几遍，还是不知道应该怎么办。最后已经快十一点了，非常不甘心地把链的情况特殊处理了一下，真正的树归一直到交卷都没调出样例3。
看到标程的那一刻感觉自己不管是思维能力还是代码能力都受到了深深的鄙视。不管一个苹果是红还是黑，都当做红苹果来计算。1的情况可以选一个子节点为1，0的情况全部选子节点为0。处理完本节点与子节点的关系之后再来讨论颜色；如果是一个黑苹果，上面处理的0的状态实际上是1 ；如果是一个红苹果，0的值应该是0+1，因为把黑色的子节点断开，黑色子树里的情况也包含在总的方案数中。这样先做切与不切的选择，再做红与黑的判断，很轻松地解决了我在考场上遇到的种种矛盾。hyy大佬的做法增加了一维表示切与不切，其实也很有助于理清思路，但是我在考场上只是单纯地不敢再加一维。为什么呢？大概是怕自己更绕不出来吧。对于分类讨论的事一直不擅长，然而世界上的所有事总不能都只用一种方法解决。再遇到这种情况，分析的时候要更加冷静。如果实在条理不清晰，也该变通一下思路。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int mod=1000000007; const int sj=100005; int n,a1,h[sj],e,fa[sj],son[sj]; bool hs[sj]; long long f[sj][2],ans; struct B { int ne,v; }b[sj*2]; void dfs(int x) { for(int i=h[x];i!=-1;i=b[i].ne) if(b[i].v!=fa[x]) { fa[b[i].v]=x; son[x]++; dfs(b[i].v); } } void add(int x,int y) { b[e].v=y; b[e].ne=h[x]; h[x]=e++; } void dp(int x,int fx) { f[x][1]=0; f[x][0]=1; for(int i=h[x];i!=-1;i=b[i].ne) if(b[i].v!=fx)//当做红苹果来计算 { dp(b[i].v,x); f[x][1]=(f[x][1]*f[b[i].v][0])%mod; f[x][1]=(f[x][1]+f[x][0]*f[b[i].v][1])%mod;//1的情况可以选一个黑色子节点 f[x][0]=(f[x][0]*f[b[i].v][0])%mod;//0的情况所有子节点都必须为0 } if(hs[x]) f[x][1]=f[x][0];//如果是一个黑苹果，上面计算的0情况相当于1 else f[x][0]=(f[x][0]+f[x][1])%mod;//如果是一个红苹果，需要把1中选中的子节点断开， //但是方案数是一样的，这就很好地解决了选与不选的矛盾 //换种方式来表达，虽然子节点在一个黑色块里，但是切断它不就行了吗？ } int main() { //freopen("tree1.in","r",stdin); scanf("%d",&n); n--; memset(h,-1,sizeof(h)); for(int i=1;i<=n;i++) { scanf("%d",&a1); add(i,a1); add(a1,i); } for(int i=0;i<=n;i++) { scanf("%d",&a1); if(a1) hs[i]=1; } fa[0]=-1; dfs(0); for(int i=0;i<=n;i++) { if(son[i]>1) { dp(0,-1); ans=(f[0][1])%mod; break; } if(son[i]==0) a1=i; if(i==n) { ans=1; e=-0x7fffffff; for(int i=a1;i!=-1;i=fa[i]) { if(!hs[i]) e++; else { if(e>0) ans*=(e+1); ans%=mod; e=0; } } } } printf("%lld",ans); //while(1); return 0; }
公主的朋友
出题人：Wulala
时间限制：1s 空间限制：256MB
由于 Wulala 在上个问题中的精彩表现，公主认为 Wulala 是一个很棒的人，就把 Wulala 留在了 X国。这时正好公主的一位传教士朋友来拜访公主，于是想找 wulala 帮忙X 国如同一条直线，其中有n 个城市,从东向西分别编号为 1~n。而他的国家中有 m 种宗教，每个城市一定会有一种信仰的宗教。
有时候有些城市为了获得更多的认可，会派出信仰本城市宗教的传教士前往其他国家。X 国的传教士都十分厉害，只要是他途经的地方都会改信他所传播的宗教。
传教士们在路上碰到自己宗教的城市自然就不用传教了，可以停下来看看里番啥的，所以每一个传教士在旅行前都会计算自己可以在多少城市停下来(不包括起始的城市)。
而传教士们都是文科僧，数学是很差的，所以他希望 Wulala 能帮他计算。可 Wulala 数学也不好，但他又不想在公主面前丢脸，你能帮帮他吗？
Input
第一行两个整数 n，m
第二行 n 个整数第 i 个整数代表第 i 各城市信仰的宗教
第三行一个整数 T 代表传教士的个数
接下来 T 行每行两个整数 x，y 代表 x 城向 y 城派遣了一个传教士(保证 x < y)
Output
输出 T 行，第 i 行代表第 i 个传教士询问的答案
Simple Input
2 2
1 2
2
1 2
1 2
Simple Output
0
1
Hint
对于 30%的数据 n <= 100000, m <= 10, T <= 100
对于 60%的数据 n <= 100000, m <= 10, T <= 100000
对于 100%的数据 n <= 100000, m <= 300, T <= 100000
题解
读完了题，明显是个区间标记与查询。10^5，zzh讲课的时候说的分块大概能做范围。而且这个题总体的趋势是越走越统一，分块其实相当可行。但是当时就莫名有点顾虑，万一出题人最大的数据强行卡分块呢？总是觉得数据结构的做法更稳妥，慢慢偏向了线段树。要做线段树，区间需要维护的东西很迷，时间复杂度也悬。万万没想到(其实是因为我太蒻，不算空间复杂度)，真正的问题出现在内存上。每个线段树开300的数组，或者300棵线段树，都是完全不可行的，内存炸得毫无疑虑(wxh：你不炸谁炸啊)。
正解其实相当简单，正如同cogs那个分类介绍“分块之后随便搞”。给整块统一的打标记，没有打上标记的整块也按散点来算。不管是思维难度还是编程难度都不算高，然而还是那句话：考试的时候没打出来，啥都没用。正解未必难，部分分也未必简单，想到了简单的做法不妨先打一打，毕竟不会花太多时间。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int sj=100005; int n,m,zj[sj],ca,a1,a2,qc,ss[sj],ans,bj[sj]; int main() { scanf("%d%d",&n,&m); memset(bj,-1,sizeof(bj)); qc=sqrt(n); for(int i=1;i<=n;i++) { scanf("%d",&zj[i]); ss[i]=(i-1)/qc+1; } scanf("%d",&ca); for(int l=1;l<=ca;l++) { scanf("%d%d",&a1,&a2); ans=0; if(bj[ss[a1]]!=-1) zj[a1]=bj[ss[a1]]; if(ss[a1]==ss[a2]) { if(bj[ss[a1]]==-1) for(int i=a1+1;i<=a2;i++) { if(zj[i]==zj[a1]) ans++; else zj[i]=zj[a1]; } if(bj[ss[a1]]!=-1) ans=a2-a1; printf("%d\n",ans); continue; } if(bj[ss[a1]]==-1) for(int i=a1+1;i<=ss[a1]*qc;i++) { if(zj[i]==zj[a1]) ans++; else zj[i]=zj[a1]; } if(bj[ss[a1]]!=-1) ans+=ss[a1]*qc-a1; if(bj[ss[a2]]==-1) for(int i=(ss[a2]-1)*qc+1;i<=a2;i++) { if(zj[i]==zj[a1]) ans++; else zj[i]=zj[a1]; } if(bj[ss[a2]]!=-1) { if(bj[ss[a2]]!=zj[a1]) { for(int i=(ss[a2]-1)*qc+1;i<=a2;i++) zj[i]=zj[a1]; for(int i=a2+1;i<=ss[a2]*qc;i++) zj[i]=bj[ss[a2]]; bj[ss[a2]]=-1; } if(bj[ss[a2]]==zj[a1]) ans+=a2-(ss[a2]-1)*qc; } for(int i=ss[a1]+1;i<ss[a2];i++) { if(bj[i]==-1) for(int j=(i-1)*qc+1;j<=i*qc;j++) if(zj[j]==zj[a1]) ans++; if(bj[i]==zj[a1]) ans+=qc; bj[i]=zj[a1]; } printf("%d\n",ans); } return 0; }
Function
出题人：Gromah
时间限制：2s 空间限制：512MB
题解
计算机一秒能运行10^8次
计算机一秒能运行10^8次
计算机一秒能运行10^8次
重要的事情说三遍。所以说我在过去的一年里一直记的是10^9！所以说我一直以来算的时间复杂度都只是玩玩而已！所以说我判断的会不会超时完全不准确！感觉自己是个假OIer……拿到题目看到数据范围就觉得有些诡异，1sec真能运行10^9这题还有什么意义啊！然后随便打了个n*q的程序放着，基本上这题就和没做一样。稍微想了想求交点，二次函数虽然能消去二次项但是解出来也肯定一堆double，以我的能力很难做到准确；况且直线的扫描线我都没做过，何谈抛物线？暴力也是能A的，不过比我机智多了。因为对数据范围理解不到位，没有注意到它的询问一定有重复。yzh大佬的离线做法外网低空水过，内网轻松A掉，用一个bool数组标记一下会更快。至于正解，打出了人生中第一棵估值线段树，学长讲过之后一直觉得机智无比，其实实现起来也不算困难。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int xf=500001; struct hs { long long a,b,c; }hs[1010]; int n,q,que[500005],mi,ma; long long u,ans,temp,jg[1000005]; bool yz[1000005]; int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&hs[i].a,&hs[i].b,&hs[i].c); ma=-0x7fffffff; mi=0x7fffffff; for(int i=1;i<=q;i++) { scanf("%lld",&que[i]); yz[que[i]+xf]=1; if(que[i]>ma) ma=que[i]; if(que[i]<mi) mi=que[i]; } for(int i=mi;i<=ma;i++) { if(!yz[xf+i]) continue; ans=-0x7fffffff; for(int j=1;j<=n;j++) { temp=hs[j].a*i*i+hs[j].b*i+hs[j].c; if(temp>ans) ans=temp; } jg[xf+i]=ans; } for(int i=1;i<=q;i++) printf("%lld\n",jg[que[i]+xf]); return 0; }
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int xf=500001; struct hs { long long a,b,c; }hs[1010]; int n,q; long long u,ans,temp,que[500005],jg[1000005],mi,ma; bool yz[1000005]; struct tree { long long a,b1,b2,c; int l,r; }t[1005*4]; long long bj(long long x,long long y) { return x>y?x:y; } void build(int x,int z,int y) { t[x].l=z; t[x].r=y; if(z==y) { t[x].a=hs[z].a; t[x].b1=t[x].b2=hs[z].b; t[x].c=hs[z].c; return; } int mid=(z+y)>>1,ls=x<<1,rs=(x<<1)|1; build(ls,z,mid); build(rs,mid+1,y); t[x].a=bj(t[ls].a,t[rs].a); t[x].b1=bj(t[ls].b1,t[rs].b1); t[x].c=bj(t[ls].c,t[rs].c); if(t[ls].b2<t[rs].b2) t[x].b2=t[ls].b2; else t[x].b2=t[rs].b2; } long long query(int x,long long u) { if(t[x].l==t[x].r) { if(u>0) return t[x].a*u*u+t[x].b1*u+t[x].c; else return t[x].a*u*u+t[x].b2*u+t[x].c; } int ls=x<<1,rs=(x<<1)|1; long long ans1,ans2; if(u>=0) { ans1=t[ls].a*u*u+t[ls].b1*u+t[ls].c; ans2=t[rs].a*u*u+t[rs].b1*u+t[rs].c; } else { ans1=t[ls].a*u*u+t[ls].b2*u+t[ls].c; ans2=t[rs].a*u*u+t[rs].b2*u+t[rs].c; } if(ans1<=ans2) { ans2=query(rs,u); if(ans2>=ans1) return ans2; else { ans1=query(ls,u); return bj(ans1,ans2); } } if(ans2<ans1) { ans1=query(ls,u); if(ans1>=ans2) return ans1; else { ans2=query(rs,u); return bj(ans1,ans2); } } } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&hs[i].a,&hs[i].b,&hs[i].c); ma=-0x7fffffff; mi=0x7fffffff; for(int i=1;i<=q;i++) { scanf("%lld",&que[i]); yz[que[i]+xf]=1; if(que[i]>ma) ma=que[i]; if(que[i]<mi) mi=que[i]; } build(1,1,n); for(long long i=mi;i<=ma;i++) { if(!yz[xf+i]) continue; ans=query(1,i); jg[xf+i]=ans; } for(int i=1;i<=q;i++) printf("%lld\n",jg[que[i]+xf]); return 0; }
8.10联考题解