A题。算是个模拟。华丽丽的写了100行，代码能力还是不行。
B题。凸包加dp，不会。
C题。字符串，kmp。操作是能将字符串一分为二然后交换位置。操作的次数是无限的。
发现将这两个字符串分别首尾相接他两是一样的。。于是将b+=b;然后kmp跑a在b中的匹配。
D题。并查集。比赛的时候想到并查集了。但是退盟操作没有想到比较好的方法。
每次退盟的时候，可以给这个国家一个新的id，相当于新加了一个独立的点，可以默认为已经将这个点从原来的盟国中删除掉了。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<string>
#include<map>
using namespace std;
#define re freopen("in.txt","r",stdin)
#define we freopen("out.txt","w",stdout)
#define maxn 100100*10
#define maxm 200005
#define ll long long
#define ld long double
int fa[maxn];
int n;
int id[maxn];
void ini()
{
for(int i=0; i<maxn; i++)
fa[i]=i,id[i]=i;
}
int Fin(int a)
{
if(fa[a]==a)return fa[a];
fa[a]=Fin(fa[a]);
return fa[a];
}
void Uni(int a,int b)
{
a=Fin(a);
b=Fin(b);
if(a==b)return;
fa[a]=b;
}
bool vis[maxn];
int main()
{
int a,b;
// re;
int m;
int nc=1;
while(~scanf("%d%d",&n,&m)&&(n+m))
{
char s[11];
ini();
int tot=n;
while(m--)
{
scanf("%s",s);
if(s[0]=='M')
{
scanf("%d%d",&a,&b);
Uni(id[a],id[b]);
}
else if(s[0]=='S')
{
scanf("%d",&a);
id[a]=tot++;
}
}
int ans=0;
memset(vis,false,sizeof(vis));
for(int i=0; i<n; i++)
{
int t=Fin(id[i]);
if(!vis[t])vis[t]=true,ans++;
}
printf("Case #%d: %d\n",nc++,ans);
}
return 0;
}
E题。比较简单的DP。因为我会。。
有n个台阶，每一次可以跨x或者y个台阶。问必须经过a和b两个台阶的方案数有多少。
用dp[i]表示到第i个台阶的方案数。那么要求的答案就是dp[a]*dp[b-a]*dp[n-b];相当于分解为三段小去走。
WA一次因为没看题下面的mod10……07；
#include<cstring>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<string>
#include<map>
using namespace std;
#define re freopen("in.txt","r",stdin)
#define we freopen("out.txt","w",stdout)
#define maxn 10011
#define maxm maxn*maxn/2
#define ll long long
#define ld long double
#define mod 1000000007
ll dp[maxn];
int main()
{
int nc;
//re;
int n;
int x,y,a,b;
while(5==scanf("%d%d%d%d%d",&n,&x,&y,&a,&b)){
memset(dp,0,sizeof(dp));
dp[0]=1;
if(a>b)swap(a,b);
for(int j=1;j<=n;j++){
if(j-x>=0)
dp[j]=(dp[j]+dp[j-x])%mod;
if(j-y>=0&&x!=y)
dp[j]=(dp[j-y]+dp[j])%mod;
}
printf("%lld\n",(dp[a]%mod*dp[b-a]%mod)%mod*dp[n-b]%mod);
}
return 0;
}
F题。树dp。以前一个树dp的题也没做过。看到之后就傻了。于是瞎搞。。一直超时。。记忆化搜索也不错。于是改改改改。但是连样例都过不了。
要回寝室了。于是交一发，结果都没看，想着就是回了寝室接着搞。。但是回去打开一看居然过了。。尼玛。逗我呢。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<string>
#include<map>
using namespace std;
#define re freopen("in.txt","r",stdin)
#define we freopen("out.txt","w",stdout)
#define maxn 200005
#define maxm 200005
#define ll long long
#define ld long double
struct pp
{
int u,v;
int tt[6];
int next;
}edge[maxm];
int head[maxn];
int vis[maxn];
int cnt;
void add(int u,int v,int a,int b,int c,int d)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].next=head[u];
edge[cnt].tt[0]=a;
edge[cnt].tt[1]=b;
edge[cnt].tt[2]=c;
edge[cnt].tt[3]=d;
head[u]=cnt++;
}
int aa[maxn],bb[maxn];
int dp[maxn][2];
bool dvis[maxn][2];
int dfs(int n,int type)
{
int sum=0;
if(dvis[n][type])return dp[n][type];
for(int i=head[n];~i;i=edge[i].next){
int v=edge[i].v;
if(vis[v])continue;
if(type==0)
sum+=min(dfs(v,1)+edge[i].tt[1]+bb[v],aa[v]+dfs(v,0)+edge[i].tt[0]);
else
sum+=min(dfs(v,1)+edge[i].tt[3]+bb[v],aa[v]+dfs(v,0)+edge[i].tt[2]);
}
dp[n][type]=sum;
dvis[n][type]=1;
return sum;
}
int main()
{
// re;
int nc;
scanf("%d",&nc);
while(nc--){
int n;
scanf("%d",&n);
memset(head,-1,sizeof(head));
cnt=0;
memset(vis,false,sizeof(vis));
memset(dvis,false,sizeof(dvis));
for(int i=1;i<=n;i++)
scanf("%d",&aa[i]);
for(int i=1;i<=n;i++)
scanf("%d",&bb[i]);
int m=n-1;
int a,b,c,d,e,f;
while(m--){
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
add(a,b,c,d,e,f);
}
vis[1]=true;
int ans=min(dfs(1,0)+aa[1],dfs(1,1)+bb[1]);
printf("%d\n",ans);
}
return 0;
}
F、G不会。日后补充。