题目列表：
| ID | Origin | Title | ||
|---|---|---|---|---|
| 10 / 15 | Problem A | FZU 2152 | 文件系统 | |
| 0 / 16 | Problem B | FZU 2153 | A simple geometric problems | |
| 9 / 17 | Problem C | FZU 2154 | YesOrNo | |
| 4 / 18 | Problem D | FZU 2155 | 盟国 | |
| 10 / 20 | Problem E | FZU 2156 | Climb Stairs | |
| 5 / 11 | Problem F | FZU 2157 | ProgramCaicai's Trees | |
| 1 / 7 | Problem G | FZU 2158 | 数字密码 | |
| 6 / 34 | Problem H | FZU 2159 | WuYou |
A - 文件系统
比较复杂的模拟，用bool in[i][j]记录i号人是否在j组里，注意细节就能撸出来，我交了好多次，简直逗
#include<iostream>
#include <cstdio>
#include <cstring>
//#include <cstdlib>
#define RE freopen("in.txt","r",stdin); using namespace std;
int farm(); int main()
{
int t,T;
//RE
cin>>T;
for(t=;t<T;t++)
{
farm();
}
return ;
} int farm()
{
int n,i,j,m,x;
bool in[][];
string username[];
string groupname[];
int quanxian[];
string ftouser[];
int ftogroup[];
int groupn=;
string s;
memset(in,,sizeof(in));
cin>>n;
for(i=;i<n;i++)
{
cin>>username[i];
cin>>x;
for(j=;j<x;j++)
{
cin>>s;
bool ok=false;
for(int k=;k<groupn;k++)
if(groupname[k]==s)
{
ok=true;
in[i][k]=true;
break;
}
if (!ok)
{
groupname[groupn]=s;
in[i][groupn]=true;
groupn++;
} }
}
cin>>m;
for(i=;i<m;i++)
{
cin>>s;
cin>>quanxian[i];
cin>>ftouser[i];
cin>>s;
ftogroup[i]=;
for(int k=;k<groupn;k++)
if(groupname[k]==s)
{
ftogroup[i]=k;
break;
}
//cout<<i<<'.'<<ftogroup[i]<<endl;
}/*
for(i=0;i<n;i++)
{
for(j=0;j<groupn;j++)
cout<<in[i][j]<<',';
cout<<endl;
}*/
for(i=;i<n;i++)
{
j=;
if (ftouser[j]==username[i]) cout<<(int)(quanxian[j]/);
else {if(in[i][ftogroup[j]]) cout<<((int)(quanxian[j]/))%;
else cout<<(quanxian[j]%);}
for(j=;j<m;j++)
{
cout<<' ';
if (ftouser[j]==username[i]) cout<<(int)(quanxian[j]/);
else {if(in[i][ftogroup[j]]) cout<<((int)(quanxian[j]/))%;
else cout<<(quanxian[j]%);}
}
cout<<endl;
} return ;
}
B - A simple geometric problems
不会，好像不仅要凸包，虽然凸包我也不会。不过也没人做出来我就不管了……
C - YesOrNo
试一下发现不管换多少次，都可以换一次达到。就二重循环，if(s1[j]!=s2[(i+j)%length])break;直接对比就行。我还怕它出奇怪的数据，例如所有字符都一样，只有一个字符不一样，这样要对比好久……可是好像没有这样的数据耶，不管了。
#include<iostream>
#include <cstdio>
#include <cstring>
//#include <cstdlib>
#define MAXN 500
#define RE freopen("inC.txt","r",stdin); using namespace std; char s1[];
char s2[];
char a1[];
char a2[]; int farm();
void init(); int main()
{
//RE
while(scanf("%s",s1)!=EOF)
{
farm();
}
return ;
} int farm()
{
int i,j,st;
init();
scanf("%s",s2);
if(strlen(s1)!=strlen(s2)){cout<<"No"<<endl;return ;}
int length=strlen(s1);
for(i=;i<length;i++)
{ }
st=;j=;
for(i=;i<length;i++)
{
for(j=;j<length;j++)
{ if(s1[j]!=s2[(i+j)%length])break;
}
if(j==length){cout<<"Yes"<<endl;return ;}
}
cout<<"No"<<endl;
return ;
} void init()
{
memset(a1,,sizeof(a1));
memset(a2,,sizeof(a2));
}
D - 盟国
竟然是要带删除操作的并查集，当时没做出来。并查集用两个数组来，a[i]存一般的并查集的东西，b[i]表示国家i用的并查集物体存在a[b[i]]，这样的话，删除就是把b[i]指向一个新的a[j]，新创建一个a[j]来存b[i]的并查集物体，而以前用的那个就不管了，继续留在并查集里……这样就相当于删掉啦！最后统计一下同盟数就好。
#include<iostream>
#include <cstdio>
#include <cstring>
//#include <cstdlib>
#define RE freopen("inD.txt","r",stdin); using namespace std; struct biu{
int n;
int father;
}; int N,M;
biu a[];
int b[];
bool g[];
int w;
int ans;
int t; int farm();
void init(); int getfather(int x)
{
int y;
if(a[x].father!=x) y=getfather(a[x].father);
else return x;
a[x].father=y;
return y;
} int meng(int x,int y)
{
int fx=getfather(b[x]);
int fy=getfather(b[y]);
if(fx==fy) return ;
if(a[fx].n>a[fy].n)
{
a[fy].father=fx;
a[fy].n+=a[fx].n;
}
else
{
a[fx].father=fy;
a[fx].n+=a[fy].n;
}
//ans--;
return ;
} int out(int x)
{
b[x]=w;
a[w].n=;
a[w].father=w;
w++;
//ans++;
return ;
} int main()
{
t=;
//RE
while(true)
{
scanf("%d%d",&N,&M);
if(N==) return ;
farm();
}
return ;
} int farm()
{
int i,j,x,y;
char c;
init();
for(i=;i<M;i++)
{
do{scanf("%c",&c);}while(c!='M' && c!='S');
if(c=='M')
{
scanf("%d%d",&x,&y);
//cout<<x<<','<<y<<endl;
meng(x,y);
}
else
{
scanf("%d",&x);
//cout<<x<<endl;
out(x);
}
}
for(i=;i<N;i++)
{
g[getfather(b[i])]=true;
}
ans=;
for(i=;i<w;i++)
if(g[i]) ans++;
cout<<"Case #"<<++t<<": "<<ans<<endl;
return ;
} void init()
{
int i;
for(i=;i<N;i++)
{
b[i]=i;
a[i].father=i;
a[i].n=;
}
w=N;
//ans=N;
memset(g,,sizeof(g));
}
E - Climb Stairs
意思是这个人一次能走X级或Y级台阶，要统计经过A台阶和B台阶到达N台阶的方法数。简单动规，我是先统计到A、B中较低的那个的方法数，然后把之前的方法数全清零！然后再统计到A、B中较高的那个方法数，再把之前的清零，这样就只剩经过A和B的方法了，然后再撸到N级就行了。
#include<iostream>
#include <cstdio>
//#include <cstring>
//#include <cstdlib>
#define MAXN 500
#define RE freopen("inE.txt","r",stdin); using namespace std; int N, X, Y, A, B; int farm(); int main()
{
//RE
while(cin>>N>>X>>Y>>A>>B)
{
farm();
}
return ;
} int farm()
{
int i,j,k;
int dp[]={};
dp[]=;
for(i=;i<=A && i<=B;i++)
{
if (i>=X) dp[i]=(dp[i]+dp[i-X])%;
if (i>=Y) dp[i]=(dp[i]+dp[i-Y])%;
}
j=i;
for(i=;i<j-;i++)
dp[i]=;
for(i=j-;i<=A || i<=B;i++)
{
if (i>=X) dp[i]=(dp[i]+dp[i-X])%;
if (i>=Y) dp[i]=(dp[i]+dp[i-Y])%;
}
k=i;
for(i=j-;i<k-;i++)
dp[i]=;
for(i=k-;i<=N;i++)
{
if (i>=X) dp[i]=(dp[i]+dp[i-X])%;
if (i>=Y) dp[i]=(dp[i]+dp[i-Y])%;
}
cout<<dp[N]<<endl;
return ;
}
F - ProgramCaicai's Trees
意思是有一棵树，要你选择每个节点是0还是1，每个节点是0或者是1各自有不同的分数，还有各个边的两边是00、01、10、11各有不同的分数。树形DP！其实我以前从来没做过树形DP，当时编了好久还没撸出来。原来是要dfs回溯时DP。好像可以先多叉转二叉再做，不过我是直接像图一样做了…具体看代码。
#include<iostream>
#include <cstdio>
#include <cstring>
//#include <cstdlib>
//#include<queue>
#define RE freopen("inF.txt","r",stdin); using namespace std; struct bian
{
int fr,to;
int b[][];
int next;
}; int a[][];
int firstbian[];
bian b[];
int next[];
int bn;
bool walked[];
int dp[][];
int N;
int farm();
void init(); int dfs(int now)
{
int nb=firstbian[now];
walked[now]=true;
//cout<<'('<<now<<','<<choose<<')';
while(nb!=-)
{
if(!walked[b[nb].to])
{
//cout<<"to "<<b[nb].to<<' ';
dfs(b[nb].to);
dp[][now]+=min(dp[][b[nb].to]+b[nb].b[][] , dp[][b[nb].to]+b[nb].b[][]);
dp[][now]+=min(dp[][b[nb].to]+b[nb].b[][] , dp[][b[nb].to]+b[nb].b[][]);
}
nb=next[nb];
}
dp[][now]+=a[][now];
dp[][now]+=a[][now];
//cout<<now<<','<<choose<<' '<<sum<<'+'<<a[choose][now]<<endl;
return ;
} int main()
{
int t,T;
//RE
scanf("%d",&T);
for(t=;t<T;t++)
{
farm();
}
return ;
} int farm()
{
int i,j,P,Q,A,B,C,D;
scanf("%d",&N);
init();
for(i=;i<N;i++)
{
scanf("%d",&a[][i]);
}
for(i=;i<N;i++)
{
scanf("%d",&a[][i]);
}
bn=;
for(i=;i<N-;i++)
{
scanf("%d%d%d%d%d%d",&P,&Q,&A,&B,&C,&D);
P--;Q--;
b[bn].fr=P;
b[bn].to=Q;
b[bn].b[][]=A;
b[bn].b[][]=B;
b[bn].b[][]=C;
b[bn].b[][]=D;
next[bn]=firstbian[b[bn].fr];
firstbian[b[bn].fr]=bn;
bn++; b[bn].fr=Q;
b[bn].to=P;
b[bn].b[][]=A;
b[bn].b[][]=C;
b[bn].b[][]=B;
b[bn].b[][]=D;
next[bn]=firstbian[b[bn].fr];
firstbian[b[bn].fr]=bn;
bn++;
}
//walked[0]=true;
dfs();
printf("%d\n",min(dp[][],dp[][]));
return ;
} void init()
{
memset(walked,,sizeof(walked));
memset(firstbian,-,sizeof(firstbian));
memset(dp,,sizeof(dp));
}
G - 数字密码
完全不会！看了woshilalala神犇的代码才会的，超碉。
动规，dp[T]，T是八进制数t6t5t4t3t2t1t0，dp[T]代表当第0个人的字符串有t0位在密码里，第1个人的有t1位在密码里……第i个人有ti位在密码里时，密码的最小位数。
dp[0]=0，从dp[0]推到dp[end]，end为(T|ti=第i个人字符串长度)，dp[end]就是答案。
dp[0]=0，其他是INF，i从0循环到end-1，d[k]=min(d[k],d[i]+1)，k是从i的状态增加一个数字能达到的状态，0~9每个数字都要试一遍。
关键部分：
inline int gank(int x,int y)
{
int next=,i,t;
for(i=;i<N;i++)
{
t=x%;
x=x>>;
if(t<len[i] && s[i][t]==y) t++;
next+=t<<q[i];
}
return next;
}
//x是当前状态，y是试的数字(0~9之一)，q[i]是3*i。返回的next就是能达到的下一个状态。
举例说明容易理解，例如样例：
3个人，字符串分别是：
123 14 21
dp[0]=0，从0状态开始，试0，发现“0”字符串完全不得力，得到的next还是0，d[0]=min(d[0],d[0]+1)，故不做改变。
试1，发现“1”字符串让第一第二个人的字符串得力了，于是得到的next为011（八进制，下同），dp[011]=min(d[011],d[0]+1)，由于d[011]初始值为INF，所以dp[011]变为d[0]+1=1。意思是：在011状态（第三个人的字符串还没有一个字符在密码里，第二个人和第一个人的字符都有1个在密码里）下，密码的长度为1。
后面循环到dp[011]的时候，试2的时候，将2加到各字符串中已经确认在密码里的位数之后的那一位，看看是否相同，例如第一个人的字符串，已经确认了一位，将2与第二位对比，发现相同，这个字符串的已经确认的位数就加1。然后看第二个人的字符串，已经确认了一位，将2与第二位对比，发现不同，则已经确认的位数不变，第三个人的字符串同理。因为第一个人的字符串第二个数是2，其他的都没有2，所以得到的next是012，dp[012]=dp[011]+1=2。 这样一直撸下去就能得到答案啦，太碉啦！
#include<iostream>
#include <cstdio>
#include <cstring>
#include<cmath>
//#include <cstdlib>
#define RE freopen("inG.txt","r",stdin); using namespace std; string s[];
int q[];
int d[];//8^7
int len[];
int N; int farm();
void init(); int main()
{
int t,T;
//RE
q[]=;
for(t=;t<;t++)
q[t]=q[t-]+;
cin>>T;
for(t=;t<T;t++)
{
farm();
}
return ;
} inline int gank(int x,int y)
{
int next=,i,t;
for(i=;i<N;i++)
{
t=x%;
x=x>>;
if(t<len[i] && s[i][t]==y) t++;
next+=t<<q[i];
}
return next;
} int farm()
{
int i,j,k;
int tot=;
cin>>N;
init();
for(i=;i<N;i++)
{
cin>>s[i];
len[i]=s[i].length();
tot+=(len[i]<<q[i]);
}
d[]=;
for(i=;i<tot;i++)
{
if(d[i]<0x7f)
{
for(j='';j<='';j++)
{
k=gank(i,j);
d[k]=min(d[k],d[i]+);
}
}
}
cout<<d[tot]<<endl;
return ;
} void init()
{
memset(d,0x7f,sizeof(d));
}
H - WuYou
从左到右一位一位看，记住看过的数是等于还是小于，大于就直接-1，小于了一下的话就一直小于了，这样遇见？就能填9。如果是左边都等于的时候遇到问号，有时需要填与B相等的，有时需要填比B小1的，我是深搜的，先搜相等的，后面的位都弄好了成功了就找到了最大的A，不行再搜减一的。
#include<iostream>
#include <cstdio>
#include <cstring>
//#include <cstdlib>
#define RE freopen("inH.txt","r",stdin);
#define EQUAL 1
#define LITTLE 2
using namespace std;
char A[],B[];
int length;
int farm(); int main()
{
int t,T;
//RE
cin>>T;
for(t=;t<T;t++)
{
farm();
}
return ;
} int dfs(int now,int EQ)
{
int x=;
if(now>=length)
{
if (EQ==LITTLE)return ;
else return ;
}
if(A[now]=='?')
{
if(EQ==LITTLE)
{
A[now]='';
x=dfs(now+,EQ);
if (x==) return ;
A[now]='?';
}
else
{
A[now]=B[now];
if(!(now== && A[now]=='')) x=dfs(now+,EQ);
if(x==) return ;
if(B[now]!='')
{
A[now]=B[now]-;
if(!(now== && A[now]=='')) x=dfs(now+,LITTLE);
if(x==) return ;
}
A[now]='?';
} }
else
{
if(EQ==EQUAL && A[now]>B[now]) return ;
if(EQ==EQUAL && A[now]<B[now]) x=dfs(now+,LITTLE);
else x=dfs(now+,EQ);
}
return x;
} int farm()
{
int N,i,j;
scanf("%s",A);
scanf("%s",B);
bool ok=false;
length=strlen(A);
j=dfs(,EQUAL);
if(j==) printf("%s",A);
else printf("-1");
printf("\n");
return ;
}