ZOJ比赛——2010.4.17

本次比赛由我和CZM一起参加。
先贴提交记录：
Run ID Submit Time Judge Status Problem ID Language Run Time(ms) Run Memory(KB) User Name 3470 2010-04-17 16:19:45 Accepted K C++ 130 220 CWJ&&CZM 2991 2010-04-17 15:35:34 Accepted J C++ 890 13752 CWJ&&CZM 1496 2010-04-17 13:46:15 Accepted E FPC 20 28 CWJ&&CZM 1188 2010-04-17 13:28:52 Wrong Answer E FPC 20 28 CWJ&&CZM 1085 2010-04-17 13:20:44 Accepted G C++ 0 176 CWJ&&CZM 596 2010-04-17 12:50:55 Accepted B C++ 0 176 CWJ&&CZM 463 2010-04-17 12:45:57 Accepted L C++ 0 176 CWJ&&CZM 311 2010-04-17 12:41:33 Accepted A C++ 0 176 CWJ&&CZM
首先一开场，CZM没在，于是我AC3道水题：A、B、L。
然后CZM上了，然后兵分两路，他做E，我做K。
然后他说E题十分水。
然后我看了一下K以后，发现和SGU122很像，但是又略有不同，然后想留着后面做算了。
于是我看到G题，一大堆英文和五行的，什么都没看懂。
绝望之际，随便交了个n/2，居然AC了！
。。。十分无语
然后CZM的E题WA了一次，然后还是AC了。
于是我开始YY J题。
一看。。。恩，感觉应该是以i划分状态，然后f[i,j,k]表示第i个完成，A处理器末时间为j，B处理器末时间为k的时候能否做到。当我看到我的f是布尔型的时候，觉得有些搞笑。。。于是换成f[i,j]表示第i个任务完成，A处理器末时间为j，B处理器末时间最小能是多少。
然后将sum猥琐优化一下，1Y，不过这个时间确实挺难看。。。
然后我们两个最后再来搞K题，讨论了半天，CZM觉得他的构造法是对的，我表示没听懂~
我想的是费用流，写了没几行，突然想起费用流不能有环。。。
于是我想用度数预处理一下暴力，CZM继续做他的构造法。
然后我的AC，他用小号交WA了。。。
我的做法是：选取出度最大的一个点做起点，然后DFS即可。
因为图是接近完全图，所以搜出来也很正常。。。
然后，我想暴力C题，最后没时间，比赛结束。
最后我们过了7题。
rank：22
排名围观地址：http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=308

现在说说AC的两道不算太弱智的题目，现在贴贴简单的解题报告和程序：
J：F[i,j]表示完成第i个任务，A处理器末时间为j时，B处理器末时间最小为多少。然后转移即可。
K：由于每个点的出度+入度=n-1，于是把出度最大的那个当起点，暴力DFS即可。当然也可以DLX。
【CODE For J】
#include using namespace std;
const int N=105;
const int INF=100000000;
int Tc,n;
int a[N],b[N],tail[N];
int F[N][N*N];
int list[N][N*N*2];

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
}

int solve(){
int i,j,k,sum=0,*f;
a[n+1]=0;
for (i=1;i<=n+1;i++){
sum+=a[i];
for (j=0;j<=sum;j++)
F[i][j]=INF;
}
F[1][0]=0;
sum=0;
for (i=1;i<=n;i++){
f=F[i+1];
for (j=0;j<=sum;j++)
if (F[i][j]!=INF){
f[j+a[i]]=min(f[j+a[i]],max(F[i][j],j));
f[max(j,F[i][j])]=min(f[max(j,F[i][j])],F[i][j]+b[i]);
}
sum+=a[i];
}
int ans=INF;
for (j=0;j<=sum;j++)
ans=min(ans,max(j,F[n+1][j]));
return ans;
}

int main(){
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
init();
cout << solve() << endl;
}
}

【CODE For K】
#include #include #include const int N=105;
int n,S,step;
int din[N],dout[N],a[N][N],v[N],list[N];
bool flag;

void init(){
scanf("%d",&n);
memset(din,0,sizeof(din));
memset(dout,0,sizeof(dout));
memset(a,0,sizeof(a));
int i,j,x,y;
for (i=1;i<=n*(n-1)/2;i++){
scanf("%d%d",&x,&y);
a[x][y]=1;
din[y]++;
dout[x]++;
}
}

void dfs(int i){
v[i]=1;
step++;
list[step]=i;
if (step==n){
flag=true;
return;
}
for (int j=1;j<=n;j++)
if (a[i][j] && !v[j]){
dfs(j);
if (flag) return;
}
step–;
v[i]=0;
}

void work(){
if (n==1){
printf("1n");
return;
}
S=1;
for (int i=1;i<=n;i++)
if (dout[i]>dout[S]) S=i;
memset(v,0,sizeof(v));
flag=false;
step=0;
dfs(S);
if (!flag) printf("Impossiblen");
else
for (int i=1;i<=n;i++){
printf("%d",list[i]);
if (i!=n) printf(" ");
else printf("n");
}
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
init();
work();
}
}