首页 > 代码库 > 8.13联考题解
8.13联考题解
最长上升子串
时间限制: 2 Sec 内存限制: 64 MB
样例输入
7 2 3 1 5 6
样例输出
题解
刚一读题觉得和昨天T3相似度极高，只不过是久违的子串。还是想动归思路，f[i][1/0]表示到第i位是/否已经改变过序列的值，然后大概就是个择优转移的思路；受到昨天那题局限用一个辅助数组记录了一下改变后的值，贪心策略把它设为a[i-1][0]+1,。开始上手打，代码倒是很短，怎么想怎么觉得不对劲，自己凭着感觉开始刻意造数据卡这个做法。试了几组数之后成功用123745678卡掉了这个做法，然后开始调，但是发现这种思路好像先天不足根本调不过，想再加一种状态也没想通，虽然时间还早但是思路整个有点混乱。想着NOIP模拟，冷静一下T1肯定没问题，就直接放在那去做后两道题了。T2一样看不出来放下，做完码量相对较大的T3回来已经10:00了，但是T3比较稳心里轻松不少。换个思路，直接去掉辅助的a数组，只改变一个不就是可以跳过一位的子串吗，然后直接从满足条件的f[i-2][0]+2或f[i-1][1]+1转移到f[i][1]，整数的问题还是用昨天的a[i]-i解决。把原来用来卡第一种做法的数据都拿过来，一个一个都测过了。这时候时间不多了，就去做T2，用这种做法成功A掉了T1。第二次做T1从想到实现只用了不到半个小时，但是如果一开始就卡在这不去做后面的题，能不能做出来尚且不一定，更不要说对心理状态的影响了；今天这种对T1的处理方法大概算是挺成功吧。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int sj=300010; int n,a[sj],f[sj][2],jg; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]-=i; f[i][0]=1; f[i][1]=2; } f[1][1]=1; for(int i=2;i<=n;i++) { if(a[i]>=a[i-1]) f[i][0]=f[i-1][0]+1; if(a[i]>=a[i-2]&&f[i][1]<f[i-2][0]+2) f[i][1]=f[i-2][0]+2; if(a[i]>=a[i-1]&&f[i][1]<f[i-1][1]+1) f[i][1]=f[i-1][1]+1; if(f[i][0]>jg) jg=f[i][0]; if(f[i][1]>jg) jg=f[i][1]; } printf("%d",jg); return 0; }
中值滤波
时间限制: 2 Sec 内存限制: 128 MB
题解
一道规律题，看上去就很高大上……做的时间不多，没有推出来规律，不过暴力模拟也拿了50。题目中提到一个“-1”的事，刚开始就很好奇在什么情况下会出-1，然后开始自己模拟，一连试了十几组，就连刻意想让它出循环之类的都没有用，还是几步之内就结束了。满心怀疑，这道题不会是没有-1吧？（刚才看题解,出题人写了一句“骗分技巧：一般对于有-1的题目，假如题目没有给出一个答案为-1的样例，则说明不可能出现无解的情况”，说的好有道理啊，真是宝贵的生活经验23333）没有-1就放心了许多，放心模拟，也不担心骗不着分。后来想了想连续的是不会改变的，用链表稍微优化一下，但是实质上没有太大改变。
正解是把每两个连续的数字都断开。现在每一段一定是01相间的，它变稳定的时间为(len-1)>>1，两端点是同一个数的整段都会变为这个数，不是一个数的各分一半。这样简单地把整个序列遍历一遍就既得出了时间又得出了最终的序列。或许是因为在手写序列的时候注意力都放在-1上，也是因为没有清楚的找规律的意识。今年夏天栽在规律题上也不知道是第几次了，过了这一个集训，看到完全没有思路的题之后推规律想贪心的想法终于是有了(全都是拿分换来的QAQ)。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int sj=500010; int n,a[sj],b[sj],a1,zd,yd,len,miao; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); zd=1; b[1]=a[1],b[n]=a[n]; for(int i=2;i<=n;i++) if(a[i]==a[i-1]) { yd=i-1; len=yd-zd; miao=len+1; miao>>=1; len>>=1; if(len>a1) a1=len; if(a[yd]==a[zd]) for(int j=zd;j<=yd;j++) b[j]=a[zd]; else { for(int j=0;j<miao;j++) b[j+zd]=a[zd]; for(int j=miao;j<(miao<<1);j++) b[j+zd]=a[yd]; } zd=yd+1; } if(yd!=n) { yd=n; len=yd-zd; miao=len+1; miao>>=1; len>>=1; if(len>a1) a1=len; if(a[yd]==a[zd]) for(int j=zd;j<=yd;j++) b[j]=a[zd]; else { for(int j=0;j<miao;j++) b[j+zd]=a[zd]; for(int j=miao;j<(miao<<1);j++) b[j+zd]=a[yd]; } } printf("%d\n",a1); for(int i=1;i<n;i++) printf("%d ",b[i]); printf("%d\n",b[n]); return 0; }
约会
时间限制: 2 Sec 内存限制: 256 MB
样例输入
4
1 2
1 3
2 4
1
2 3
样例输出
1
题解
考试的时候接连被前两题打击，第三题居然是唯一一道看了就有思路的题，毕竟考场上图论题向来比较友好。树上路径唯一，这个性质还是用得很多的，想暴力的时候打算直接枚举，但是只问种类数的话似乎没有必要细化到每一个点。反正LCA是一定要求的，刚好昨天才打过《松鼠的新家》，一道LCA+树上差分，离线tarjan的做法熟得很没过多久就打出来了(这里我其实给自己挖了个坑)。然后开始分情况讨论，刚开始考虑到了和两点都不是LCA，和LCA距离相等的情况可以取LCA及以上和LCA的兄弟之类的点；而其中一点是LCA的话则要看他们之间的距离是奇数还是偶数。后来发现情况可以并一并拆一拆，就变成了两点等深度和不等深度的情况。自己造了一棵十几个节点的非二叉树画一画，发现情况还漏了不少，然后边补坑边调，总结到最后就是：如果两点间距离是奇数，无解；是偶数，如果LCA不是这两点，要从树根的size去除询问的两个点所在LCA的子树的size；如果LCA是其中一个，要找它们之间的中间点，再求中间点的size减去询问中较深的点所在子树的size。实现的过程中发现一个问题，需要频繁地求这个点属于一个很高的祖先的哪一个子树，一开始就用倍增应该比较方便，然而我用的是离线算法这要怎么办啊……还有不到两个小时，前两个题还没做，倍增打得不熟也没有时间，于是硬着头皮一层一层抬。这样倒是很准确，也不过T了20%的随机数据。这道题虽然看起来复杂，但是毕竟基本上是个板子题，思路很容易想，敲代码的过程中心情也平静了很多，实在是考场上调整节奏的好选择。如果今天T3出个数学题或者状压什么的，可能成绩会完全不一样吧。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int sj=100010; int n,m,a1,a2,h[sj],e,dep[sj],p[sj][30],jg; int fa[sj],size[sj],ans; bool r[sj]; int re() { int jg=0,jk; jk=getchar()-‘0‘; if(jk>0&&jk<=9) jg=jk; jk=getchar()-‘0‘; while(jk<=9&&jk>=0) jg=jg*10+jk,jk=getchar()-‘0‘; return jg; } struct B { int ne,v; }b[sj<<1]; void add(int x,int y) { b[e].ne=h[x]; b[e].v=y; h[x]=e++; } void init() { n=re(); memset(h,-1,sizeof(h)); for(int i=1;i<n;i++) { a1=re(),a2=re(); add(a1,a2); add(a2,a1); } m=re(); } void dfs(int x) { size[x]=1; for(int i=h[x];i!=-1;i=b[i].ne) if(b[i].v!=fa[x]) { fa[b[i].v]=x; dep[b[i].v]=dep[x]+1; dfs(b[i].v); size[x]+=size[b[i].v]; } } void fx() { for(int j=0;(1<<j)<=n;j++) for(int i=1;i<=n;i++) p[i][j]=-1; for(int i=1;i<=n;i++) p[i][0]=fa[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++) if(p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1]; } int lca(int x,int y) { if(dep[x]<dep[y]) return lca(y,x); int i; for(i=0;(1<<i)<=dep[x];i++); i--; for(int j=i;j>=0;j--) if(dep[x]-(1<<j)>=dep[y]) x=p[x][j]; if(x==y) return x; for(int j=i;j>=0;j--) if(p[x][j]!=-1&&p[x][j]!=p[y][j]) x=p[x][j],y=p[y][j]; return fa[x]; } void sole() { int l; fa[1]=1; for(int i=1;i<=m;i++) { scanf("%d%d",&a1,&a2); if(a1==0||a2==0) { printf("1\n"); continue; } if(a1==a2) { printf("%d\n",n); continue; } jg=lca(a1,a2); if(dep[a1]==dep[a2]) { ans=n-size[jg]; for(l=0;(1<<l)<=dep[a1];l++); l--; for(int j=l;j>=0;j--) if(dep[a1]-(1<<j)>dep[jg]) a1=p[a1][j]; for(l=0;(1<<l)<=dep[a2];l++); l--; for(int j=l;j>=0;j--) if(dep[a2]-(1<<j)>dep[jg]) a2=p[a2][j]; ans+=size[jg]-size[a2]-size[a1]; printf("%d\n",ans); } else { ans=dep[a1]+dep[a2]-2*dep[jg]; if(ans&1) printf("0\n"); else { ans=ans>>1; if(dep[a1]<dep[a2]) swap(a1,a2); for(l=0;(1<<l)<=dep[a1];l++); l--; for(int j=l;j>=0;j--) if((1<<j)<ans) { a1=p[a1][j]; ans-=(1<<j); } ans=(size[fa[a1]]-size[a1]); printf("%d\n",ans); } } } } int main() { init(); dfs(1); fx(); sole(); return 0; }
PS：下午终于学会了对拍……感觉不会对拍考了这么一夏天的试没有天天翻车也是不容易……虽然说翻车频率其实挺高的。不过自己手造一些有坑的数据也很有用，以后考试又多了一种方法确保骗分拿分成功了。
8.13联考题解