A

解题思路
首先考虑对于给定的两个串 $t$ 和 $s$ ，判断 $s$ 是否为 $t$ 的子串只需要从头到尾扫描一遍 $t$ ，每次碰到 $s$ 中的首字母则将 $s$ 首字母弹出，最终判断 $s$ 是否为空即可，复杂度为 $O(|t|)$ 。
观察到本题数据量较小，因此完全可以暴力。对于每一个 $T[i]$ ，判断每个 $S[j]$ 是否为其子串即可。复杂度为 $O(m\sum_{i=1}^{n}{|T[i]|})$ 。

代码

#include<bits/stdc++.h>
#define rep(i,b,e) for(register int i=(b);i<(e);++i)
#define dep(i,b,e) for(register int i=(b);i>=(e);--i)
#define ll long long
#define inf 0x7fffffff
#define il inline
using namespace std;
int n,m;
string T[1000],S[100];
int cute(const string &t,const string &s){
  int j=0;
  rep(i,0,t.size()){
      if(t[i]==s[j]){
          j++;if(j>=s.length()) return 1;
      }
  }
  return 0;
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  rep(i,0,n) cin>>T[i];
  rep(i,0,m) cin>>S[i];
  rep(i,0,n){
      int ans=0;
      rep(j,0,m) ans+=cute(T[i],S[j]);
      cout<<ans<<endl;
  }
  system("pause");
  return 0;
}

B

解题思路
本题中 $v$ 与 $k$ 均为偶数，因此省去了许多麻烦。显然 $n$ 的低 $v$ 位为回文串时最小，此时 $k-=2$ ，然后从回文串的中间开始，依次向两边各增加1直到 $k=0$ ，若低 $v$ 位全为1是 $k$ 仍然大于0，那么只需要在高位补1即可。

代码

#include<bits/stdc++.h>
#define rep(i,b,e) for(register int i=(b);i<(e);++i)
#define dep(i,b,e) for(register int i=(b);i>=(e);--i)
#define ll long long
#define inf 0x7fffffff
#define il inline
using namespace std;
int v,k,s[200001];
const ll p=1e9+7;
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>v>>k;
  memset(s,0,sizeof(s));
  s[0]=s[v-1]=1;k-=2;
  int l=v/2-1,r=l+1;
  while(k&&l){
      s[l--]=s[r++]=1;k-=2;
  }
  r=v-1;
  while(k--) s[++r]=1;
  ll ans=0,power=1;
  rep(i,0,r+1){
      ans=(ans+s[i]*power)%p;
      power=power*2%p;
  }
  cout<<ans<<endl;
  system("pause");
  return 0;
}

D

解题思路
先给出结论：当 $n=1$ 时先手败，其余情况下均先手必胜。 $n=1,2$ 时不必解释，考虑 $n\geq 3$ 时的情况，先手策略如下：
第一轮， $1-2-x-1$ ，即先手往2号点走，无论对手走到哪，都返回1号点，此时轮到对手先行；
之后每轮， $1-x-2-y-1$ ，即无论对手从1号点往哪走（不可能是2号点，因为1-2在第一轮已经被走过了），下一步都走回2号点，然后等对手再走一步之后返回1号点，此时仍然轮到对手先行。
不难发现，从第二轮开始每轮都是对手先行，并且每次都能被你拉回1号点，形成循环。并且每轮1号点和2号点的度数都减少2。现在分两种情况：
1、 $n$ 为奇数，则1号点和2号点度数均为偶数，则最后一轮回到1号点时恰好对手先行，此时1号点度数耗尽，无路可走。
2、 $n$ 为偶数，则1号点和2号点度数均为奇数，考虑最后一轮可以这么走： $1-x-2$ ，此时2号点度数也被耗尽，轮到对手，依然无路可走。
因此无论如何先手必能获胜。

代码

#include<bits/stdc++.h>
#define rep(i,b,e) for(register int i=(b);i<(e);++i)
#define dep(i,b,e) for(register int i=(b);i>=(e);--i)
#define ll long long
#define inf 0x7fffffff
#define il inline
using namespace std;
int T,n;
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>T;
  while(T--){
      cin>>n;
      if(n==1) cout<<"Kozilek, Butcher of Truth"<<endl;
      else cout<<"Ulamog, the Infinite Gyre"<<endl;
  }
  system("pause");
  return 0;
}

F

解题思路
本题中给的图是连通仙人掌，其构成必然是若干个圈之间通过链相连。
考虑对于一个单独的圈，若它是偶圈，则显然只要2种颜色交替即可。若是奇圈则需要3种颜色。
那么本题结论就呼之欲出了：判断仙人掌中是否包含奇圈，若有则需要3种颜色，否则需要2种。由于每个圈之间通过链相连，且对于仙人掌来说不可能构成大环（不符合仙人掌定义），则只要确定了第一个圈的颜色，第二个圈也随之确定（与链的交点处作为起点涂色），随之第三个、第四个...，相互之间是不会产生冲突的。

代码

#include<bits/stdc++.h>
#define rep(i,b,e) for(register int i=(b);i<(e);++i)
#define dep(i,b,e) for(register int i=(b);i>=(e);--i)
#define ll long long
#define inf 0x7fffffff
#define il inline
using namespace std;
int n,m,u,v,ans=2;
vector<int> g[100001];
int dfn[100001];
void dfs(int nd,int fa){
  for(auto &to:g[nd]){
      if(to!=fa){
          if(dfn[to] && (dfn[nd]-dfn[to]+1)%2) ans=3;
          else if(!dfn[to]){
              dfn[to]=dfn[nd]+1;dfs(to,nd);
          }
      }
  }
  dfn[nd]=0;
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  while(m--){
      cin>>u>>v;
      g[u].push_back(v);
      g[v].push_back(u);
  }
  memset(dfn,0,sizeof(dfn));
  dfn[1]=1;dfs(1,0);
  cout<<ans<<endl;
  system("pause");
  return 0;
}

ABDF题解

A

B

D

F