社区讨论

题解怎么了?

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 条回复,欢迎继续交流。

正在加载回复...