寒假了，bupt大佬们给2017级的萌新（包括我）搞了一些题，并组成了一个比赛——BUPT Winter Training。和CF一样，分div1和div2。div2我都做不完 里面有一些题非常有意思，现在在这里写一下。
还有，好像wordpress迁移过来之后发生了一些不稳定的情况，代码高亮也出现了一些问题。。代码中如果出现了一些奇怪字符的话，请不要在意并且无视。。。
第一类：我有特殊的A题技巧
HDU-2072 单词数
给一长串英文句子，问里面含有几个不同的单词。
这题，不应该是随便水嘛？？然后随手写了个set交上去，然后一直WA到怀疑人生。
两个坑点：空格数不定，有可能句子长度为零。
然后，有一个叫istringstream的东西，类似sprintf一样的东西，完美解决这个问题，用法如下：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<set> #include<sstream> using namespace std; set<string>s; int main() { string a,t; while(getline(cin,a)) { if(a[0]=='#')break; istringstream stream(a); while(stream>>t)s.insert(t); cout< <s.size()<<endl; s.clear(); } return 0; }
再次跪拜在STL之下….不过据说string.h头文件里的strtok函数（类似python的split）也能起到很好的效果
HDU2057A+B again
16进制a+b problem 要是模拟很麻烦。然后有以下骚操作：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<set> using namespace std; int main() { long long a,b; while(scanf("%llX%llX",&a,&b)!=EOF) { long long c=a+b; if(c<0)printf("-%llX\n",-c); else printf("%llX\n",c); } } </set></string></cstdio></algorithm></cstring></iostream>
很强 很骚 记住一定要%llX 或%I64X X大写
HDU1713 相遇周期
题意转化一下，就成了求两个分数的最小公倍数
然后有个小学奥数的结论：两个分数的最小公倍数是：分母的最小公倍数/分子的最大公约数。
这个玩意证明有点困难，还在搞。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<set> using namespace std; long long gcd(long long a,long long b) {return b==0?a:gcd(b,a%b);} long long lcm(long long a,long long b) {return a*b/gcd(a,b);} long long a,b,c,d; int n; int main() { scanf("%d",&n); while(n--) { scanf("%lld/%lld %lld/%lld",&a,&b,&c,&d); // cout< <a<<" "<<b<<" "<<c<<" "<<d<<endl; long long g1=gcd(a,b),g2=gcd(c,d); a/=g1,b/=g1,c/=g2,d/=g2; long long t1=lcm(a,c),t2=gcd(b,d),g; g=gcd(t1,t2);t1/=g,t2/=g; if(t2==1)printf("%lld\n",t1); else printf("%lld/%lld\n",t1,t2); } return 0; }
等我想出完整严格证明再来更新。。。
CodeChef – PRTITION
给出一个数x，一个数N，要求把1-N中除去x之外的其它数平均分成两堆，也就是使得两堆数的和相等。 n<=10^6
看到这题时是contest结束后第二天了。。。然后就懵了。。难道要dp?暴力？
正解是暴力。。。dfs，从大到小，哪堆小就把当前数放到哪堆。题解上有一个神奇的证明，他证明了暴力的复杂度是O(N+2^5)。
感性理解的话，首先，对于去除x之后的数的和sum，如果sum是奇数，肯定不行。
如果sum是偶数，那么在N很大的时候，有很多很多答案，所以你直接暴力，基本不会回溯，直接O(N)到底。
如果N很小，那么暴力肯定不会挂，而且在N<=5的时候dfs才会出现回溯。
所以，这个题告诉我们，写完暴力之后，要胆大一点！
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<set> using namespace std; const int N=1000005; int ans[N],n,x; bool dfs(int t,long long l,long long r) { if(t==0)return l==r; if(t==x)return dfs(t-1,l,r); //cout< <t<<" "<<l<<" "<<r<<endl; if(l<r) { ans[t]=1; if(dfs(t-1,l+t,r))return 1; ans[t]=0; if(dfs(t-1,l,r+t))return 1; return 0; } else { ans[t]=0; if(dfs(t-1,l,r+t))return 1; ans[t]=1; if(dfs(t-1,l+t,r))return 1; return 0; } } int main() { int t=0; scanf("%d",&t); while(t--) { scanf("%d%d",&x,&n); long long p=((long long)n*(n+1ll))/(long long)2-(long long)x; if(p%2){puts("impossible");continue;} if(dfs(n,0,0)) { for(int i=1;i<=n;i++) if(i==x)printf("2"); else printf("%d",ans[i]); puts(""); } else puts("impossible"); } return 0; }
据说 这个题随机化搞一下也能过。。。因为方案有很多。。
第二类：有一些特殊性质的经典题目
HDU1701Binary Tree Traversals
给出一棵二叉树的前序和中序遍历，求其后序遍历。n<1000
前序遍历：根左右。
中序遍历：左根右。
后序遍历：左右根。
前序遍历特点：第一个点是根结点，后面是子树。
中序：中间某个点是根结点，左右是子树。
后序：前面是叶子，最后是根结点。
所以，我们从前序遍历中取出一个根结点，然后在中序遍历找到他，划清左右子树。
如果存在左右子树，那么输出，如果不存在，把结果压入栈中。注意，要先dfs右子树，再dfs左子树。因为在后序遍历中，左子树在右子树前，即左子树出栈早于右子树，所以右子树进栈早！
最后弹栈输出就行了。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=1005; int tot,ans[N],cnt,root,n; int a[N],b[N],c[N]; void make(int l1,int r1,int l2,int r2) { ans[++cnt]=a[l1];int q; for(int i=l2;i< =r2;i++) if(b[i]==a[l1]){q=i;break;} int p=l1+(q-l2+1); if(r2>=q+1)make(p,r1,q+1,r2); if(l2< =q-1)make(l1+1,p-1,l2,q-1); } int main() { while(scanf("%d",&n)!=EOF) { root=tot=cnt=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); make(1,n,1,n); for(int i=cnt;i>1;i--)printf("%d ",ans[i]); printf("%d\n",ans[1]); } return 0; } </algorithm></cstring></cstdlib></cstdio></iostream>
给出后序和中序找前序同理。但是给出前序和后序是无法确定二叉树的，但是我们可以找到符合这种前序和后序遍历的二叉树数目：
我们不能确定二叉树的原因是因为：如果某一个非叶子节点只有一个儿子，根据前序和后序是不能确定这个儿子是左儿子还是右儿子的，所以这里出现了多解。
所以，我们只要看一下前序遍历的第一个儿子是不是后序遍历的第一个儿子（刚刚说过了，前序的第一个儿子是左儿子，后序遍历中，从后往前数第一个儿子是右儿子），就能知道这里是不是存在多解了。
给出后序和前序，求方案：
neuq oj 1022 二叉树
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=10000; char s1[N],s2[N]; long long ans; void dfs(int l1,int r1,int l2,int r2) { int f=0; if(l1+1< =r1) { for(int i=l2;i<=r2-1;i++) { if(s1[l1+1]==s2[i]) { if(i==r2-1)ans*=2; f=i;break; } } } if(l1+1<l1+1+(f-l2))dfs(l1+1,l1+1+(f-l2),l2,f); if(f+1<r2-1)dfs(l1+1+(f-l2)+1,r1,f+1,r2-1); } int main() { while(scanf("%s%s",s1+1,s2+1)!=EOF) { int n=strlen(s1+1); ans=1; dfs(1,n,1,n); printf("%lld\n",ans); } return 0; }
bzoj3714 Kuglarz
魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？
这个题比较神。。我们根据很久之前的一道并查集的题可以知道，每次询问[i,j]，我们便可以知道sum[i-1]和sum[j]的奇偶性是否一致。如果我们得知了sum[a],sum[b]的奇偶性是否一致，又知道sum[b]和sum[c]的奇偶性是否一致(an<bn<c)，也就知道了sum[a]和sum[c]的奇偶性是否一致。所以，如果我们知道任意的sum[i-1],sum[j]的奇偶性是都一致的话，我们就能根据sum[i],sum[i+1]的奇偶性是否一致，就能知道i杯子里有没有球了！
所以，我们要用c[i][j]的代价把所有的0-n号点都连起来，最少需要n条边。。这！最小生成树！
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int N=2005; int f[N][N]; int dist[N]; int n; bool vis[N]; void prim() { long long ans=0; for(int i=1;i< =n;i++)dist[i]=f[0][i];vis[0]=1; for(int i=1;i<=n;i++)//n-1个缝隙 n个数字 { int mn=0x3f3f3f3f,p=0; for(int i=0;i<=n;i++) if(!vis[i]) { if(mn>dist[i]){mn=dist[i],p=i;} } ans+=dist[p];vis[p]=1; for(int i=0;i< =n;i++) if(!vis[i]) { dist[i]=min(dist[i],f[p][i]); } } cout<<ans<<endl; } int main() { scanf("%d",&n); for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) { int t=0;scanf("%d",&t); f[i][j]=f[j][i]=t; } prim(); return 0; }
CodeForces – 699D Fix a Tree
给一个n条边n个点的图，问最少需要改变多少次边才能把这张图变成一棵树，并输出一种方案。
第一反应是，拆环，把环上任意一点作为根。
但是有可能有好多环。倘若出现第二个环，只需要再把环拆开，把环上一点连到根上即可。
注意不连通的情况，若出现自环，就把他作为根（把自环做为根不算一次操作！），或者把这个存在自环的点练到根上。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int N=200005; int s[N],n,root; int fa[N]; int get(int x) { if(x==fa[x])return fa[x]; fa[x]=get(fa[x]); return fa[x]; } int main() { scanf("%d",&n); int ans=0; for(int i=1;i< =n;i++) { scanf("%d",&s[i]); if(s[i]==i)root=i; } for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=n;i++) if(i!=root) { int u=get(s[i]),v=get(i); if(u==v) { ans++; if(root==0)root=i; s[i]=root; } else fa[v]=u; } printf("%d\n",ans); for(int i=1;i<=n;i++)printf("%d ",s[i]); return 0; }
poj1050 To the max
给出一个矩阵，要求选出一个子矩阵，使得子矩阵中的数的和最大。
最大子串和的推广！
我们知道，在最大子串和里有一个经典的O(N)dp，我们可以把它推广到二维。
对于一个矩阵，我们把他的每一列求前缀和，然后枚举i行和j行，对于i行与j行之间的列k，我们通过前缀和求出第k列中i行到j行的和。对于所有的k，我们做经典的最大子串和dp就行了！
具体一点说，就是把列拍扁了！
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=105; int s[N][N],sum[N][N],n; int main() { scanf("%d",&n); for(int i=1;i< =n;i++) for(int j=1;j<=n;j++)scanf("%d",&s[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)sum[i][j]=sum[i-1][j]+s[i][j]; int ans=-0x7fffffff; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { int mx=0; for(int k=1;k<=n;k++) { if(mx<0)mx=sum[j][k]-sum[i-1][k]; else mx+=sum[j][k]-sum[i-1][k]; ans=max(ans,mx); } } printf("%d\n",ans); return 0; }
第三类：较为复杂的题目
bzoj1196公路修建问题
在一个地方修建道路(图的生成树)，有一级公路和二级公路两种，要求：1.一级公路不能少于k条。2.最大边的边权最小。求最大边的边权。
看到最大边最小，想到二分，看到不能少于k条，想到贪心+最小生成树。
所以二分答案，kruscal最小生成树判定，贪心的先选一级公路，再选二级公路。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=10015,M=30005; struct edge { int u,v,x; }a[M],b[M]; bool cmp(edge a,edge b) {return a.x<b .x;} int fa[N],n,m,k; int get(int x) { if(fa[x]==x)return x; fa[x]=get(fa[x]); return fa[x]; } bool kru(int mx) { for(int i=1;i<=n;i++)fa[i]=i; int cnt=0; for(int i=1;i<=m;i++) { int u=a[i].u,v=a[i].v,x=a[i].x; if(get(u)==get(v)||a[i].x>mx)continue; int uu=get(u),vv=get(v); cnt++; fa[vv]=uu; } if(cnt<k )return 0; for(int i=1;i<=m;i++) { int u=b[i].u,v=b[i].v,x=b[i].x; if(get(u)==get(v)||b[i].x>mx)continue; int uu=get(u),vv=get(v); cnt++; fa[vv]=uu; } return cnt==n-1; } int main() { scanf("%d%d%d",&n,&k,&m); int l=0x3f3f3f3f,r=0; for(int i=1;i< =m-1;i++) { scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].x,&b[i].x); b[i].u=a[i].u,b[i].v=a[i].v; l=min(l,min(a[i].x,b[i].x)),r=max(r,max(a[i].x,b[i].x)); } sort(a+1,a+m,cmp); sort(b+1,b+m,cmp); int ans=0; while(l<=r) { int mid=(l+r)/2; if(kru(mid))ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0; }
codeforces 823DMisha, Grisha and Underground
在一棵树上，两个人分别从A,B两点出发，到C点集合。求两人路径中重合的点数。
第一反应，树剖或者动态树啊！每次操作就是A-C之间+1，B到C之间+1 ，统计哪些点等于2。
第二反应，LCA好像直接能做。。分类讨论三个点的关系。1.AB两点LCA是否为C 2.A与C的LCA是否为C,B与C的LCA是否为C 3.A与C，B与C的LCA是否相同 4.其它情况？
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=500005,M=N*2+100; int head[N],nxt[M],list[M],tot; void add(int a,int b) { tot++; list[tot]=b; nxt[tot]=head[a]; head[a]=tot; } int d[N],fa[N][22],n,m; bool vis[N]; void dfs(int a) { vis[a]=1; for(int i=head[a];i;i=nxt[i]) { int x=list[i]; if(!vis[x]) { d[x]=d[a]+1; fa[x][0]=a; dfs(x); } } } void zeng() { for(int j=1;j< =20;j++) for(int i=1;i<=n;i++) { fa[i][j]=fa[fa[i][j-1]][j-1]; } } int query(int a,int b) { if(d[a]>d[b])swap(a,b); if(d[a]<d [b]) { int del=d[b]-d[a]; for(int i=0;i<=20;i++)//binary split if(del&(1<<i))b=fa[b][i]; } if(a==b)return a; for(int i=20;i>=0;i--) { if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i]; } a=fa[a][0],b=fa[b][0]; return a; } int dist(int a,int b) { int lca=query(a,b); return d[a]+d[b]-2*d[lca]; } int work(int a,int b,int x) { int l1=query(a,b),l2=query(a,x),l3=query(b,x); if(l2==x&&l3==x)return d[l1]-d[x]+1; if((l2==x&&l3!=x)||(l2!=x&&l3==x))return 1; if(l2!=l3)return d[x]-max(d[l2],d[l3])+1; return dist(l1,x)+1; } int main() { scanf("%d%d",&n,&m); for(int i=2;i< =n;i++) { int q=0;scanf("%d",&q); add(i,q);add(q,i); } dfs(1); zeng(); while(m--) { int x,y,z;scanf("%d%d%d",&x,&y,&z); printf("%d\n",max(work(x,y,z),max(work(x,z,y),work(z,y,x)))); } return 0; }
代码高亮插件好像出了点问题。。。