广东民航机场建设有限公司网站,电子商务网站建设视频,广西壮族自治区教育厅,广州互联网公司【208A Dubstep】 http://codeforces.ru/problemset/problem/208/A 题目大意#xff1a;一个句子被添加了若干“WUB”#xff0c;问原句。 将WUB去掉就行了#xff0c;在句首或句尾直接删除#xff0c;在句中替换成空格#xff0c;注意多个“WUB”相连时特判。 #include …【208A Dubstep】 http://codeforces.ru/problemset/problem/208/A 题目大意一个句子被添加了若干“WUB”问原句。 将WUB去掉就行了在句首或句尾直接删除在句中替换成空格注意多个“WUB”相连时特判。 #include iostream
#include cstdio
#include cstring
#include cstdlib
using namespace std;char s[3000];
int len;
bool exist;int main(){scanf(%s,s);lenstrlen(s);int i0;while(true){if(s[i]W s[i1]U s[i2]B) i3;else break;}while(true){if(s[len-1]B s[len-2]U s[len-3]W) len-3;else break;}while(ilen){if(s[i]W s[i1]U s[i2]B){i3;if(!exist) printf( );existtrue;}else{couts[i];i;existfalse;}}coutendl;return 0;
}【208B Solitaire】 http://codeforces.ru/problemset/problem/208/B 题目大意桌面上n堆牌牌有数值和花色两个属性。一堆可以放到另一堆上当且仅当两堆牌最上面一张的牌面或花色相同。每次可以将最后一堆第x堆放到第x-1堆或x-3堆如果存在问是否存在策略使得所有牌合成一堆。 由于n很小容易想到搜索。但是O(2^n)显然难以令人接受。所以考虑对搜索过程记忆化。f[i][a][b][c]表示当前处理第i堆最后一堆是第a堆倒数第二堆是第b堆倒数第三堆是第c堆时是否可以合成一堆每次搜索后记录结果避免重复搜索。 #include iostream
#include cstdio
#include cstdlib
#include cstring
using namespace std;char card[52][2];
int n,f[53][53][53][53];bool check(char a[2], char b[2]){return a[0]b[0] || a[1]b[1];
}bool dfs(int cur,int a,int b,int c){bool resfalse;if(cur1) return true;if(f[cur][a][b][c]) return false;if(check(card[a],card[b]))res|dfs(cur-1,a,c,cur-3);if(!res cur-3 check(card[a],card[cur-3]))res|dfs(cur-1,b,c,a);return !(f[cur][a][b][c]!res);
}int main(){scanf(%d,n);memset(f,false,sizeof(f));for(int i1;in;i)scanf(%s,card[i]);if(dfs(n,n,n-1,n-2))printf(YES\n);else printf(NO\n);return 0;
}【208C Police Station】 http://codeforces.ru/problemset/problem/208/c 题目大意给定N个节点M条边的无向图边权相同。在图中选一个点使得从1到N的最短路上含有被点覆盖的边的数量的平均值最大。很别扭还是看原题吧…… 当时这个题很少有做的可能是因为不好想。 首先他要求最短路其次还要求出最短路的数量然后还要知道每个点分别在多少条最短路径上。 最短路可以用Floyd来求记为sp数量可以用DPf[i][j]表示从1出发走j步到达i的方案数f[i][j]Σf[u][j-1],u→i最后求经过每个点有多少条最短路可能让人感觉比较麻烦其实也很简单的。用g[i][j]再统计一下从n出发的方案数方程跟f[i][j]的一样那么对于一点x经过他的最短路条数num就是f[i][j]*g[i][sp-dist[i][j]]。此外还有一个问题就是如果这个点选在2~N上每个点将覆盖最短路上的两条边而如果选在1或N上只能覆盖最短路上的一条边。 #include iostream
#include cstdio
#include cstring
#include cstdlib
#include queue
using namespace std;
templateclass Tinline void gmax(T a,T b){if(ab)ab;}int n,m,x,y,sp,dist[200],f[200][200],g[200][200],map[200][200],ans;
bool vis[200];
double res;struct EDGE{int pnt;EDGE *pre;EDGE(){}EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
}Edge[20000],*SPEdge,*edge[200];inline void addedge(int a,int b){edge[a]new(SP)EDGE(b,edge[a]);edge[b]new(SP)EDGE(a,edge[b]);
} int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,x,y);addedge(x,y);map[x][y]map[y][x]1;}for(int k1;kn;k)for(int i1;in;i)if(map[i][k])for(int j1;jn;j)if(map[k][j])if(!map[i][j] || map[i][j]map[i][k]map[k][j])map[i][j]map[i][k]map[k][j];spmap[1][n];f[1][0]1;for(int i0;isp;i)for(int j1;jn;j)for(EDGE *kedge[j];k;kk-pre)f[k-pnt][i1]f[j][i];g[n][0]1;for(int i0;isp;i)for(int j1;jn;j)for(EDGE *kedge[j];k;kk-pre)g[k-pnt][i1]g[j][i];for(int i2;in;i)if(map[1][i]map[i][n]sp) gmax(ans,f[i][map[1][i]]*g[i][map[i][n]]);ans1;gmax(ans,f[n][sp]);res(double)ans/(double)f[n][sp];printf(%.12lf\n,res);return 0;
} 【204D Prizes,Prizes,more Prizes】 http://codeforces.ru/problemset/problem/208/d 题目大意好像是吃什么东西每吃一个就会得到多少积分就像方便面里面兑换卡一样。有五种奖品需要积分abcde主人公一包一包吃攒到能兑换奖品就去兑换并且先兑换价值最大的问最后能兑到五种奖品各多少还能剩下多少积分。 这个题烂大街了rating和第一题已经差不多了。 就是把积分累加、累加、累加……低于最小奖品价值的时候就去兑奖从高往低兑能兑多少对多少。兑换的时候不能暴力模拟会TLE。 #include iostream
#include cstdio
#include cstring
#include cstdlib
using namespace std;long long n,a[100],b[100],s[100],cur;long long exchange(long long x){for(int i5;i0;i--)b[i]x/a[i],x-(x/a[i]*a[i]);return x;
}int main(){cinn;for(int i1;in;i)cins[i];cina[1]a[2]a[3]a[4]a[5];cur0;for(int i1;in;i){curs[i];if(cura[1]) curexchange(cur);}for(int i1;i5;i) coutb[i] ;coutb[5]endl;coutcurendl;return 0;
}【208E Blood Cousins】 http://codeforces.ru/problemset/problem/208/e 题目大意给你若干颗树若干个询问(x,y)回答在含有结点x的树中有多少结点z使得x和z关于他们LCA的深度为y。 。。。。。。srO kAc Orz。。。。。。 kAc教的什么树套树、函数式线段树都不会写……只会写一个二分。 首先用倍增法求LCA然后求LCA下面深度为y的结点个数。 对于统计这一步可以用dfs序来搞。把时间戳按结点深度压一个vector每次询问的时候在与x同深度的时间戳序列里面二分找到进入LCA子树与离开LCA子树的时间戳之间的节点个数再减去x自己就是答案。 #include iostream
#include cstdio
#include cstdlib
#include cstring
#include vector
#include algorithm
#define MN 100010
using namespace std;vectorint pos[MN],t;
int n,m,x,y,deep[MN],l[MN],r[MN],idx,fa[MN][20];struct EDGE{int pnt;EDGE *pre;EDGE(){}EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
}Edge[MN],*SPEdge,*edge[MN];inline void addedge(int a,int b){edge[a]new(SP)EDGE(b,edge[a]);
}void dfs(int x,int dep){deep[x]dep;pos[dep].push_back(idx);l[x]idx;for(EDGE *jedge[x];j;jj-pre)dfs(j-pnt,dep1);r[x]idx;
}int main(){scanf(%d,n);for(int i1;in;i){scanf(%d,fa[i][0]);addedge(fa[i][0],i);}dfs(0,0);for(int j1;j17;j)for(int i1;in;i)fa[i][j]fa[fa[i][j-1]][j-1];scanf(%d,m);while(m--){scanf(%d%d,x,y);tpos[deep[x]];for(int i0;i17;i)if(yi1) xfa[x][i];printf(%d ,x?lower_bound(t.begin(),t.end(),r[x])-lower_bound(t.begin(),t.end(),l[x])-1:0);}return 0;
}转载于:https://www.cnblogs.com/Delostik/archive/2012/07/24/2606914.html
