首页 > 代码库 > Codeforces Round #260 (Div. 1)
Codeforces Round #260 (Div. 1)
大三目标把codeforces打成黄色以上！
从div1下手，每次做前三道题。
A
一道简单的DP。
#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<string>#include<cmath>#include<vector>#define LL long long#define MAXN 100005using namespace std;LL vis[100005];LL dp[1000005];int main(){ int n; scanf("%d",&n); int maxi=0; for(int i=0; i<n; ++i) { int a; scanf("%d",&a); vis[a]+=a; maxi=max(maxi,a); } for(int i=1; i<=maxi; ++i) if(i-2>=0) dp[i]=max(dp[i-1],dp[i-2]+vis[i]); else dp[i]=vis[i]; printf("%I64d\n",dp[maxi]); return 0;}
B
Tire+dp+博弈
win[i]表示当前在i结点时先手是否有胜利可能，lost[i]表示当前在i结点时先手是否有失败可能。
如此可计算出先手是否有胜利和失败可能，然后再进行简单博弈即可。
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vector>using namespace std;int n,K;struct Tire{ int ch[100005][26]; bool win[100005],lost[100005]; int sz; int newnode() { memset(ch[sz],0,sizeof(ch[sz])); win[sz]=lost[sz]=0; return sz++; } void init() { sz=0; newnode(); } int getX(char c) { return c-‘a‘; } void insert(char *word) { int now=0; for(int i=0; word[i]; ++i) { int x=getX(word[i]); if(ch[now][x]==0) ch[now][x]=newnode(); now=ch[now][x]; } } bool getWin(int now) { win[now]=false; bool noChild=true; for(int i=0; i<26; ++i) { if(ch[now][i]) { noChild=false; win[now]|=(!getWin(ch[now][i])); } } if(noChild) return win[now]=false; return win[now]; } bool getLost(int now) { lost[now]=false; bool noChild=true; for(int i=0; i<26; ++i) { if(ch[now][i]) { noChild=false; lost[now]|=(!getLost(ch[now][i])); } } if(noChild) return lost[now]=true; return lost[now]; }};char word[100005];Tire tree;int main(){ scanf("%d%d",&n,&K); tree.init(); for(int i=1; i<=n; ++i) { scanf("%s",word); tree.insert(word); } bool firstWin=false,firstLost=false; firstWin=tree.getWin(0); firstLost=tree.getLost(0); if(!firstWin) puts("Second"); else { if(firstLost) puts("First"); else { if(K&1) puts("First"); else puts("Second"); } } return 0;}
Codeforces Round #260 (Div. 1)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。