转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
偶尔找场CF做做。
http://codeforces.com/contest/208
A. Dubstep
单词之间用若干个”WUB“隔开了,现在恢复原来的句子,字符串基本处理。
每次判断3位是否是指定字符串,注意转移时候指针的变化。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define N 1000000
using namespace std;
char str[205];
bool check(int i){
if(str[i]=='W'&&str[i+1]=='U'&&str[i+2]=='B')
return true;
return false;
}
int main(){
while(scanf("%s",str)!=EOF){
bool word=false;
for(int i=0;i<strlen(str);i++){
//如果不是“WUB”,说明接下来是单词
if(!check(i)){
if(word)
printf(" ");
for(;i<strlen(str);i++)
//直到出现“WUB”单词结束
if(check(i))
break;
else
printf("%c",str[i]);
i+=2;
word=true;
}
else
i+=2;
}
puts("");
}
return 0;
}
B. Solitaire
有N堆牌,每次可以把最右边的往倒数第二堆上放,或者放到倒数第四堆,其中要求是最上面一张的花色或者面值一样。
直接记忆化搜索,map保存已搜到的状态。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#define LL long long
#define N 1000000
using namespace std;
map<vector<string>,bool>m;
int n;
bool check(string s1,string s2){
if(s1[0]==s2[0])
return true;
if(s1[1]==s2[1])
return true;
return false;
}
bool dfs(vector<string>s){
if(s.size()<=1)
return true;
if(m.count(s))
return m[s];
m[s]=false;
if(s.size()>=4&&check(s[s.size()-1],s[s.size()-1-3])){
vector<string>ts=s;
ts[s.size()-1-3]=s[s.size()-1];
ts.pop_back();
if(dfs(ts))
m[s]=true;
}
if(s.size()>=2&&check(s[s.size()-1],s[s.size()-1-1])){
vector<string>ts=s;
ts[s.size()-1-1]=s[s.size()-1];
ts.pop_back();
if(dfs(ts))
m[s]=true;
}
return m[s];
}
vector<string>s;
int main(){
while(scanf("%d",&n)!=EOF){
s.clear();
m.clear();
for(int i=0;i<n;i++){
string str;
cin>>str;
s.push_back(str);
}
cout<<(dfs(s)?"YES":"NO")<<endl;
}
return 0;
}
C. Police Station
图论,软肋啊。
从1-N的最短路,求出某个点,在所有最短路径的最大点覆盖???解释不清楚。。。
总之先用floyd求出最短路,然后通过 DP,求出从1到i最短路有多少条以及从j到n的最短路有多少条。
然后枚举每一条边,从1到i+从j到n+1是从1到n的最短路,以及i到j为1,说明从i到j是最短路的路径。然后把i,j权值计算。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#define LL long long
#define N 1000000
#define inf 1<<20
using namespace std;
int n,m,dist[205][205];
double cnt1[205],cnt2[205];
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=i==j?0:inf;
while(m--){
int u,v;
scanf("%d%d",&u,&v);
dist[u][v]=1;
dist[v][u]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
cnt1[1]=1;
cnt2[n]=1;
for(int d=1;d<=n;d++){
for(int i=1;i<=n;i++)
if(dist[1][i]==d)
for(int j=1;j<=n;j++)
if(dist[1][j]==d-1&&dist[j][i]==1)
cnt1[i]+=cnt1[j];
for(int i=1;i<=n;i++)
if(dist[n][i]==d)
for(int j=1;j<=n;j++)
if(dist[n][j]==d-1&&dist[j][i]==1)
cnt2[i]+=cnt2[j];
}
double num[205];
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dist[1][i]+dist[j][n]+1==dist[1][n]&&dist[i][j]==1){
num[i]+=cnt1[i]*cnt2[j];
num[j]+=cnt2[j]*cnt1[i];
}
double mmax=0.0;
for(int i=1;i<=n;i++)
mmax=max(mmax,num[i]);
printf("%.10f\n",mmax/cnt1[n]);
}
return 0;
}
D. Prizes, Prizes, more Prizes
直接模拟,每次吃一块,然后从代价最高的物品开始取,取的时候不能模拟,直接计算就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define N 1000000
using namespace std;
struct Node{
int cost,idx;
}a[5];
int n;
LL p[50];
bool cmp(Node n1,Node n2){
return n1.cost>n2.cost;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%I64d",&p[i]);
LL sum=0;
for(int i=0;i<5;i++){
scanf("%d",&a[i].cost);
a[i].idx=i;
}
sort(a,a+5,cmp);
LL cnt[5];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++){
sum+=p[i];
for(int j=0;j<5;j++){
cnt[a[j].idx]+=sum/a[j].cost;
sum%=a[j].cost;
}
}
printf("%I64d %I64d %I64d %I64d %I64d\n%I64d\n",cnt[0],cnt[1],cnt[2],cnt[3],cnt[4],sum);
}
return 0;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<...const int M = 2e5+