UESTC 2017 Summer Training #19 Div.2 (1)
普通的ｄｆｓ题。。 https://vjudge.net/contest/176860#problem/L 按照了昨天的那个五子棋的方式来判断符不符合，， 然后打算直接暴力，可是错了。。。 另外，这个地方的输入输出还是很坑的。。 自己试了下用两种别人的那个输入输出，，为什么我的还是错了。。只能用ｃｉｎ
rep(i,1,3){ rep(j,1,3){ char c; sf("%c",&c); while(c!='.'&&c!='x'&&c!='o')sf("%c",&c); mp[i][j]=c; } } rep(i,1,3)rep(j,1,3)sf(" %c",&mp[i][j]);居然都不可以。。 ａｃ代码：
char mp[5][5]; char b[3]; bool jian(){ rep(i,1,3){ rep(j,1,3){ if(mp[i][j]!='.'&&mp[i][j]==mp[i][j+1]&&mp[i][j+1]==mp[i][j+2])return 1; if(mp[i][j]!='.'&&mp[i][j]==mp[i+1][j]&&mp[i+1][j]==mp[i+2][j])return 1; if(mp[i][j]!='.'&&mp[i][j]==mp[i+1][j+1]&&mp[i+1][j+1]==mp[i+2][j+2])return 1; if(mp[i][j]!='.'&&i-2>=1&&mp[i][j]==mp[i-1][j+1]&&mp[i-1][j+1]==mp[i-2][j+2])return 1; } } return 0; } bool dfs(int x){ if(jian())return 0; if(x==3)return 1; for(int i=1;i<=3;++i){ for(int j=1;j<=3;++j){ if(mp[i][j]!='.')continue; mp[i][j]=b[x%2]; if(!dfs(x+1)){ mp[i][j]='.'; return 1; } mp[i][j]='.'; } } return 0; } int main(){ int T;sf("%d",&T); while(T--){ rep(i,1,3)rep(j,1,3)cin>>mp[i][j]; cin>>b[0]; if(b[0]=='x')b[1]='o'; else b[1]='x'; if(dfs(0))puts("Kim win!"); else puts("Cannot win!"); } }(2) 常见的期望题。。https://vjudge.net/contest/175294#problem/G 这个想法好，，和这题一样。。 http://blog.csdn.net/qq_34374664/article/details/63260392 **我们假设已经有了a张卡片的话，如果我们想要得到第a+1张，我们抽中他的概率显然就是(n-a)/n，只要我们得到除了这a张卡片的任意一张即可。那么从a张卡片变成a+1张卡片的期望抽奖次数是多少呢？
我们考虑这样一个问题，假设我们抽奖中奖的概率为1/4，那么期望中奖的抽奖次数是多少呢？显然是1/（1/4）=4.
那么回归到当前问题，如果我们已经有了a张卡片，想要得到第a+1张，我们抽中一张新的卡片概率很显然是（n-a）/n，那么期望进行的次数就是n/（n-a）；** （３） https://vjudge.net/contest/175294#problem/K 这题题用的是 组合数＋错排＋费马小定理。。。 参考http://blog.csdn.net/mr_treeeee/article/details/76272785
（４）https://vjudge.net/contest/175294#problem/D 就是ｋｍｐ。。结果我还往别的地方想了。。。
（５）
https://vjudge.net/contest/175294#problem/I ｈａｓｈ＋暴力，可是还不太会ｈａｓｈ。。。。 直接贴代码。。 自己敲得又不知道为什么错了，直接交别人的吧。。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int x = 131; const int mx = 1005; typedef unsigned long long ul; ul h[mx][mx]; ul xp[mx]; int len[mx]; char s[mx][mx]; int a[mx]; int n,q; void geth(){ xp[0] = 1; for(int i = 1; i <= 1000; i++) xp[i] = xp[i-1]*x; for(int i = 1; i <= n; i++){ h[i][len[i]] = 0; for(int j = len[i]-1; j >= 0; j--) h[i][j] = h[i][j+1]*x + (s[i][j]-'a'); } } ul HASH(int i,int j,int l){ return h[i][j]-h[i][j+l]*xp[l]; } int search(int x){ int ans = 0; for(int i = 1; i <= n; i++){ if(a[i]>a[x]) continue; if(len[x] == len[i]) ans += HASH(x,0,len[x])==HASH(i,0,len[x]); else if(len[x] < len[i]) ans += HASH(x,0,len[x])==HASH(i,len[i]-len[x],len[x]); } return ans; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%s%d",s[i],&a[i]); len[i] = strlen(s[i]); } geth(); scanf("%d",&q); while(q--){ int casei,x,y; scanf("%d",&casei); if(casei == 2){ scanf("%d",&x); printf("%d\n",search(x)); } else{ scanf("%d%d",&x,&y); a[x] = y; } } } return 0; }http://www.cnblogs.com/chendl111/p/7224864.html
（６） https://vjudge.net/contest/175294#problem/F ｄｆｓ＋树状数组
２０１７年０８月０６日 联合训练赛。。 （１）码力不够，只能学别人的。。。 用三种方式吧：
①字符串的ｈａｓｈ
//２０１７年０８月０６日２０：２５：２９ 给２０ｍｉｎ set<ULL>ma; char s[N][N]; int n,m; ULL gethash(int x,int y,int r,int c){ ULL tmp1=0,tmp2=0,tmp3=0,tmp4=0; for(int i=x;i<x+r;++i) for(int j=y;j<y+c;++j) tmp1=tmp1*37+(ULL)s[i][j]; for(int i=x+r-1;i>=x;i--) for(int j=y+c-1;j>=y;j--) tmp2=tmp2*37+(ULL)s[i][j]; for(int j=y+c-1;j>=y;j--) for(int i=x;i<x+r;i++) tmp3=tmp3*37+(ULL)s[i][j]; for(int j=y;j<y+c;++j) for(int i=x+r-1;i>=x;i--) tmp4=tmp4*37+(ULL)s[i][j]; return min(min(tmp1,tmp2),min(tmp3,tmp4)); } int main(){ sf("%d%d",&n,&m); rep(i,0,n-1)sf("%s",s[i]); int r,c; for(r=1;s[r+1][1]!='#';++r); for(c=1;s[1][c+1]!='#';++c); ma.clear(); for(int i=1;i<n;i+=r+1){ for(int j=1;j<m;j+=c+1){ ma.insert(gethash(i,j,r,c)); } } pf("%d\n",(int)ma.size()); }②直接暴力遍历
（２） https://vjudge.net/contest/174972#problem/F 并查集＋思维 参考，好简洁啊。。 http://blog.csdn.net/v5zsq/article/details/64126167
(3) 最大生成树+树上倍增的
别人的代码，https://vjudge.net/solution/10190750 还算好理解。。 （４） 这题的贪心还不太会证明。。 放个坑。。 https://vjudge.net/contest/174972#problem/K Ｆ题 看着看着看不出来了。放个坑 http://blog.csdn.net/ouqingliang/article/details/75002780 Ｆ题 看着看着看不出来了。放个坑 http://blog.csdn.net/ouqingliang/article/details/75002780
VK cup http://codeforces.com/contest/828/problem/C
这题比较坑，以为要用特殊方法做，，看了有人暴力过了。。。 他就只是对于每一个的终止位置有保留就过了。。如果没有就ＴＬＥ。可是那么多的点，为什么这样就能过。。。 然后也看了一个别人的，用并查集或者是线段树维护，这样非常好。。。 还是做题少。。。 参考http://blog.csdn.net/ouqingliang/article/details/75002780JJ
http://codeforces.com/contest/828/problem/D 贪心。参考了别人的。。。http://blog.csdn.net/mengxiang000000/article/details/75072865
Ｆ题 看着看着看不出来了。放个坑 http://blog.csdn.net/ouqingliang/article/details/75002780
