社区讨论
题解怎么了?
P1335[NOI2013] 小 Q 的修炼参与者 8已保存回复 20
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @lzkspdx3
- 此快照首次捕获于
- 2024/08/08 12:46 2 年前
- 此快照最后确认于
- 2024/08/08 13:50 2 年前
这篇题解(是最后一篇)
CPP#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include "Windows.h"
#define N 35005
#define M 1005
#define x first
#define y second
#define mk make_pair
using namespace std;
typedef pair<bool,int> Pair;
int ret[205][21],best[205],S[1005];
int P[N],Q[N],index[N],pos[N],sign[N],ch[21],now[66];
Pair A[N],B[N];char str[N][3];
int F[N][M],prei[N][M],prek[N][M],walk[N][M],extra[N][M];
int n,m,ans,st,i,k,newk,newi,tmpi,tmpk,tot,j;
Pair read(){
char tmp[10];int d;
scanf("%s%d",tmp,&d);
if (tmp[0]=='c') return mk(0,d);
return mk(1,d);
}
int Read(){
char tmp[10];scanf("%s",tmp);
return tmp[0]=='+'?1:-1;
}
int bug=0;
void DFS(int x){
if (x>10){
if (bug)
assert(str[st+12*10][0]=='i'&&A[st+12*10].y==3);
int get=0,b=st+12*10;
for (int i=b;i<st+174;i++){
//fprintf(stderr,"%d\n",i);
if (str[i][0]=='i'){
int t1=A[i].x?now[A[i].y]:A[i].y;
int t2=B[i].x?now[B[i].y]:B[i].y;
if (t1<t2) i=P[i]-1;else i=Q[i]-1;
}else if (A[i].y==1)
get+=sign[i]*(B[i].x?now[B[i].y]:B[i].y);
}//if (bug) fprintf(stderr,"%d\n",get);
if (get>best[tot])
best[tot]=get,memcpy(ret[tot],ch,sizeof(ch));
return;
}
ch[x]=2;DFS(x+1);
int b=st+(x-1)*12;
for (int i=1;i<=10;i++)
now[i+2]+=B[b+i].y;
ch[x]=1;DFS(x+1);
for (int i=1;i<=10;i++)
now[i+2]-=B[b+i].y;
}
void BACK(int i,int k){
if (i<=1) return;
//fprintf(stderr,"%d %d %d %d %d\n",i,k,F[i][k],walk[i][k],extra[i][k]);
BACK(prei[i][k],prek[i][k]);
//fprintf(stderr,"%d\n",i);
if (walk[i][k]!=-1)
printf("%d ",walk[i][k]),assert(walk[i][k]>0);
if (extra[i][k])
for (int c=1;c<=10;c++)
printf("%d ",ret[extra[i][k]][c]);
}
int calc(int x){
for (int i=1;i<=*S;i++)
if (S[i]==x){
int j=i;
for (;j<*S&&S[j+1]==S[j]+1;++j);
x=S[j]+1;break;
}
x-=lower_bound(S+1,S+*S+1,x)-(S+1);
return x;
}
int main(){
freopen("train10.in","r",stdin);
scanf("%d%d",&n,&m);n-=8;int last=0;
for (i=1,j=1;i<=n;i++,j++){
scanf("%s",str[i]);int t;index[i]=j;
if (str[i][0]=='v') scanf("%d",&t),A[i]=mk(1,t),sign[i]=Read(),B[i]=read();
if (str[i][0]=='i') A[i]=read(),B[i]=read(),scanf("%d%d",&P[i],&Q[i]);
if (str[i][0]=='s') scanf("%d%d",&P[i],&Q[i]);
if (i%174==2&&i>10)
if (!A[i].x)
assert(str[i][0]!='s'),i--,n--,S[++*S]=j;
}printf("%d ",n);
for (i=1;i<=n;i++)
P[i]=calc(P[i]),Q[i]=calc(Q[i]);
for (st=6;st<=n;st+=174){
best[++tot]=-1e9;
assert(str[st][0]=='s');
for (i=3;i<=12;i++) now[i]=0;
DFS(1);
//fprintf(stderr,"%d %d\n",st,best[tot]);
for (k=1;k<=10;k++)
assert(ret[tot][k]>0);//fprintf(stderr,"%d ",ret[tot][k]);
}assert(tot==200);
bug=0;tot=0;
for (st=2;st<=n;st+=174) pos[st]=++tot;
for (i=0;i<=tot+1;i++)
for (k=0;k<M;k++) F[i][k]=-1e9;
F[1][1000]=0;
for (i=1;i<=tot;i++)
for (k=0;k<M;k++)
if (F[i][k]>-1e9){
//fprintf(stderr,"%d %d %d\n",i,k,F[i][k]);
st=1+(i-1)*174+1;
assert(str[st][0]=='i'&&A[st].y==2);
if (k<B[st].y){
if (P[st+1]>=1&&P[st+1]<=n){
//printf("%d %d %d\n",st+1,index[P[st+1]],index[Q[st+1]]);
newi=pos[P[st+1]];assert(newi);
if (F[i][k]>F[newi][k])
F[newi][k]=F[i][k],prei[newi][k]=i,prek[newi][k]=k,
walk[newi][k]=-1,extra[newi][k]=0;
}else
if (F[i][k]>F[tot+1][k])
F[tot+1][k]=F[i][k],prei[tot+1][k]=i,prek[tot+1][k]=k,
walk[tot+1][k]=-1,extra[tot+1][k]=0;
continue;
}st+=2;assert(str[st][0]=='s');
if (Q[st]<1||Q[st]>n){
if (F[i][k]>F[tot+1][k])
F[tot+1][k]=F[i][k],prei[tot+1][k]=i,prek[tot+1][k]=k,
walk[tot+1][k]=2,extra[tot+1][k]=0;
}else{
assert(pos[Q[st]]);
newi=pos[Q[st]];
if (F[i][k]>F[newi][k])
F[newi][k]=F[i][k],prei[newi][k]=i,prek[newi][k]=k,
walk[newi][k]=2,extra[newi][k]=0;
}
++st;assert(A[st].y==2&&B[st].x==0);
//fprintf(stderr,"%d %d\n",sign[st],B[st].y);
newk=k+sign[st]*B[st].y;
assert(newk<=k);
//fprintf(stderr,"%d\n",F[i][k]+best[i]);
if (F[i][k]+best[i]>F[i+1][newk])
F[i+1][newk]=F[i][k]+best[i],prei[i+1][newk]=i,prek[i+1][newk]=k,
walk[i+1][newk]=1,extra[i+1][newk]=i;
}
//fprintf(stderr,"%d %d\n",F[tot][500],F[tot+1][500]);
for (k=0;k<M;k++)
if (F[tot+1][k]>ans)
ans=F[tot+1][k],tmpi=tot+1,tmpk=k;
fprintf(stderr,"%d\n",ans);
freopen("train10.out","w",stdout);
BACK(tmpi,tmpk);
return 0;
你们看!!!编译错误了!!!肯定是这篇题解错了!
回复
共 20 条回复,欢迎继续交流。
正在加载回复...