The 2019 ICPC Asia Shanghai Regional Contest 签到题
B：https://ac.nowcoder.com/acm/contest/4370/B
题意：t次查询，每次给你n个字符串，问你有没有某个串是其他更长（或者长度相等）的串的前缀。没有的话就输出Yes,若有，No。
思路：查找大量字符串的前缀，很容易想到trie。唯一需要做的就是给这些字符串按照长度排个序。不过我为了处理同一个串出现多次，用了个map来维护（大可不必，只是比赛的时候慌了而已）。至此代码也就出来了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=5e5+7;
const ll mod=1e9+7;
struct node
{
int son[10];//纯数字串
int f;//我一开始以为问题在这里，就把这里改成int了
}trie[maxn];
int num=1;
void insert(string s)
{
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].son[s[i]-'0'] )
{
now=trie[now].son[s[i]-'0'];
}
else
{
trie[now].son[s[i]-'0']=num++;
now=trie[now].son[s[i]-'0'];
}
}
trie[now].f++;
}
bool find(string s)
{
int len=s.length();
int now=0;
for(int i=0;i<len;i++)
{
if(trie[now].f)
{
return 0;
}
if(trie[now].son[s[i]-'0'] )
{
now=trie[now].son[s[i]-'0'];
}
else
{
return 1;
}
}
if(trie[now].f)
{
return 0;
}
return 1 ;
}
map<string , int > MP;//有没有都一样
ll n,m,t;
string s[10005];
vector<string > vec;
bool cmp(string a,string b)
{
return a.length()<b.length();
}
int main()
{
MP.clear();
vec.clear();
cin>>t;
bool ans=1;
for(int qwer=1;qwer<=t;qwer++)
{
ans=1;
cin>>n;
MP.clear();
for(int i=0;i<n;i++)
{
cin>>s[i];
MP[s[i]]++;
if(MP[s[i]]>=2)
{
ans=0;
}
}
sort(s,s+n,cmp);
if(ans)
{
for(int i=0;i<n;i++)
{
if(ans)
{
ans=find(s[i]);
}
else
{
ans=0;
break;
}
insert(s[i]);
}
}
cout<<"Case #"<<qwer;
if(ans)
{
cout<<": Yes"<<endl;
}
else{
cout<<": No"<<endl;
}
num=1;
memset(trie,0,sizeof(trie));
}
return 0;
}
K：https://ac.nowcoder.com/acm/contest/4370/K
题意：就是给你n个点和m条边，要你对边染色，如果唯一的要求是你染色后的边如果会成环(这个环是完全由染色后的边组成的)，这个环的边数不能是奇数。问你最多能涂几条边。
思路：你把这n个点分成两组，一组在左侧，另一组右侧，如果他们彼此之间会成环，如果是奇数环，那么必然某一侧存在两个点之间有一条边。那么对于这种边，不进行涂色就好。
上面两幅图帮助你来理解（语文好像不是一般的菜）。
再结合节点数来看一下，也就是枚举完所有情况至多 种情况。每次就来看我们需要删除多少同处于一侧的点之间的边。至此也就可以把代码写出来了。
//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int t,n,m;
vector<int > zuo,you;
ll mi=mod;
bool edge[20][20];
void check()//这个是用来计算本次需要删除多少条同侧点之间的边的。
{
ll res=0;
//值得注意的是，两侧都要删除，可千万别只删除一侧。
for(int i=0;i<zuo.size();i++)
{
for(int j=i+1;j<zuo.size();j++)
{
if(edge[zuo[i]][zuo[j]])
{
//cout<<"删除了"<<zuo[i]<<"\t"<<zuo[j]<<endl;
res++;
}
}
}
for(int i=0;i<you.size();i++)
{
for(int j=i+1;j<you.size();j++)
{
if(edge[you[i]][you[j]])
{
//cout<<"删除了"<<zuo[i]<<"\t"<<zuo[j]<<endl;
res++;
}
}
}
mi=min(mi,res);//取最小值，删的越少，涂的越多！
}
void dfs(int o)//大爆搜来枚举每条边在左侧还是右侧。
{
if(o==n+1)
{
check();
return ;
}
zuo.push_back(o);
dfs(o+1);
zuo.erase(zuo.end()-1);
you.push_back(o);
dfs(o+1);
you.erase(you.end()-1);
}
ll u,v;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
cin>>t;
for(int qwe=1;qwe<=t;qwe++)
{
memset(edge,0,sizeof(edge));
mi=mod;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>u>>v;
edge[u][v]=1;
edge[v][u]=1;
}
dfs(1);
cout<<"Case #"<<qwe;
cout<<": "<<m-mi<<endl;
}
return 0;
}
写在最后：因为队里的哥哥都去CSP了，我们就得到今年上海站的机会。三个人组队写了去年的这场比赛，队友超C，强行carry坑到爆炸的我（我trie树不排序，硬生生WA了5发）。
我必须考虑这会不会是我此生仅有的机会。
还有一个题我们队也过了（但我没参与讨论，没错我在WA），我第二天想到了假思路，WA了。就先咕一下。
CN.TTDragon加油！
