B. Game with string
题意：
给出一个字符串s只包括小写字母。当轮到一个玩家的时候，他可以选择两个连续且相等的字母并且删除它。当一个玩家没得删的时候他就输了。
题解：
乍一看有点懵，像dp，但是观察一下就发现输赢和顺序无关，只跟能组成相同的对数量有关，这个数量是一定的。那么我们用栈扫一遍就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack> using namespace std;
const int maxn=1e5+;
char s[maxn];
int n;
stack<char>S;
int ans;
int main(){
scanf("%s",s);
n=strlen(s);
for(int i=;i<n;i++){
if(!S.empty()&&S.top()==s[i]){
S.pop();
ans++;
}else{
S.push(s[i]);
}
}
if(ans%){
printf("Yes\n");
}else{
printf("No\n");
}
return ;
}
C. Grid game
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int maxn=+;
char s[maxn];
int n;
int main(){
scanf("%s",s);
n=strlen(s);
int a=,b=;
for(int i=;i<n;i++){
if(s[i]==''){
a=a%+;
printf("3 %d\n",a);
}else{
b=b%+;
printf("1 %d\n",b*-);
}
}
return ;
}
D. Game with modulo
题意：交互题。
V和P要玩一个游戏，P有一些正整数a，V要用下面的问题来猜这个数字a。他可以问(x,y)，P会回答他：
1.'x'，如果x mod a >= y mod a
2.'y',如果 x mod a < y mod a
V需要在60次问题内猜到数字a。保证a<=1e9.
题解：
首先询问0,1。如果返回x，那么a一定是1.如果返回y那么去询问1 2如果返回y再询问2 4然后4 8,8 16。直到返回x，则证明a一定在x和y之间。然后二分[x,y]这个区间。
这种办法我也没想到，看了答案后可以推一下发现可以很容易推出y=2*x.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int Max=1e9; string com; int main(){
while(cin>>com){
if(com=="end")break;
if(com=="mistake")break;
if(com=="start"){
char c;
printf("? 0 1\n");
fflush(stdout);
scanf(" %c",&c);
if(c=='x'){
printf("! 1\n");
fflush(stdout);
continue;
}else{
int x=,y=;
printf("? %d %d\n",x,y);
fflush(stdout);
while(scanf(" %c",&c)){
if(c=='x'){
break;
}
x=y,y=*y;
printf("? %d %d\n",x,y);
fflush(stdout);
}
int l=x,r=y;
int ans=;
for(int j=;j<=;j++){
int mid=l+(r-l)/;
printf("? %d %d\n",mid,r);
fflush(stdout);
scanf(" %c",&c);
if(c=='x'){
l=mid;
}else{
r=mid;
}
}
printf("! %d\n",max(l,r));
fflush(stdout);
}
}
}
// fflush(stdout);
return ;
}
E. Johnny Solving
题意：
给出一张连通图，不存在自环和重边，有n个结点和m条边，每个点的度数至少为3，给出一个参数k，若存在长度大于等于n/k的路径，则输出PATH并将路径输出，若存在k个满足周长不被3整除的环，且每一个环都存在一个只属于只属于这个环的点则输出CYCLES，并将k个环输出。
题解：下面是翻译自官方题解。。
从1结点开始建dfs树，然后确定这颗生成树的深度为depth。如果深度最少为n/k，那么我们就可以打印从根结点到最深结点的路径。否则的话，在dfs树中至少存在k+1个叶子结点。（想一想为什么，其实比较显然，也很好证明）。现在考虑dfs树中的一个叶子结点v，这个叶子结点至少有两条反向边，我们定义这两条反向边连向的祖先为x和y。显然我们有三个环，x到v，y到v，和x到y加上v。他们的长度分别是d(v,x)+1,d(v,y)+1,和d(x,y)+2.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector> using namespace std;
const int maxn=25e4+;
const int maxm=5e5+;
int head[maxn],Next[*maxm],to[*maxm];
int n,m,sz,k,goal,cir;
vector<int>path;
void init(){
sz=;
memset(head,-,sizeof(head));
}
void add_edge(int a,int b){
++sz;
to[sz]=b;Next[sz]=head[a];head[a]=sz;
}
int vis[maxn];
bool find_path(int u,int fa){
vis[u]=;
path.push_back(u);
if(path.size()>goal)
return true;
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(vis[v])continue;
if(find_path(v,u))
return true;
}
path.pop_back();
return false;
}
int depth[maxn];
void dfs(int u,int fa){
vis[u]=;
depth[u]=path.size();
path.push_back(u);
int flag=;
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(!vis[v]){flag=;break;}
}
if(flag){
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(!vis[v])
dfs(v,u);
}
}else{
if(cir){
cir--;
int fax=-,fay=-;
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(v==fa)continue;
if(fax==-)fax=v;
else if(fay==-){fay=v;break;}
}
if(depth[fax]<depth[fay])swap(fax,fay);
int ori=-;
if((depth[u]-depth[fax]+)%)ori=fax;
if((depth[u]-depth[fay]+)%)ori=fay;
if(ori==-){
printf("%d\n",depth[fax]-depth[fay]+);
printf("%d ",u);
for(int i=depth[fax];i>=depth[fay];i--){
printf("%d ",path[i]);
}
printf("\n");
}else{
printf("%d\n",depth[u]-depth[ori]+);
for(int i=depth[u];i>=depth[ori];i--){
printf("%d ",path[i]);
}
printf("\n");
}
}
}
path.pop_back();
} int main(){
scanf("%d%d%d",&n,&m,&k);
goal=n/k;
if(n%k)goal++;
init();
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
if(find_path(,)){
printf("PATH\n");
printf("%d\n",path.size());
for(int i=;i<path.size();i++){
printf("%d ",path[i]);
}
}else{
cir=k;
memset(vis,,sizeof(vis));
path.clear();
printf("CYCLES\n");
dfs(,);
}
return ;
}