noip模拟测试18

T1：引子

　　呃呃呃……

　　大（？）模拟，好像也不难写？

　　模拟灌水过程就完了？？？

  1 #include<cstring>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<queue>
  6 #include<vector>
  7 #include<cstdlib>
  8 using namespace std;
  9 const int MAXN=2500;
 10 int n,m,idmx,id[MAXN][MAXN],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
 11 char s[MAXN][MAXN];
 12 vector<int> ver[MAXN];
 13 bool vis[MAXN][MAXN];
 14 struct node {
 15     int u,d,l,r;
 16 }blk[MAXN];
 17 struct sta {
 18     int x,y;
 19     sta(int _x,int _y) {
 20         x=_x;y=_y;
 21     }
 22 };
 23 void bfs1(int x,int y) {
 24     int c=0;
 25     for(int i=y;i<=m;i++)
 26         if(s[x][i]>='0'&&s[x][i]<='9') c=c*10+s[x][i]-'0';
 27         else break;
 28     blk[c].l=blk[c].r=y;
 29     blk[c].u=blk[c].d=x;
 30     queue<sta> q;
 31     for(int i=y;i<=m;i++)
 32         if(s[x][i]>='0'&&s[x][i]<='9') {
 33             id[x][i]=c,blk[c].r=i;
 34             q.push(sta(x,i));
 35         } else break;
 36     idmx=max(idmx,c);
 37     while(!q.empty()) {
 38         sta u=q.front(); q.pop();
 39         for(int i=0;i<4;i++) {
 40             int nx=u.x+dx[i],ny=u.y+dy[i];
 41             if(nx<1||ny<1||nx>n||ny>m) continue;
 42             if(s[nx][ny]!='.') continue;
 43             if(id[nx][ny]) continue;
 44             id[nx][ny]=c;
 45             blk[c].u=max(blk[c].u,nx),blk[c].d=min(blk[c].d,nx);
 46             blk[c].r=max(blk[c].r,ny),blk[c].l=min(blk[c].l,ny);
 47             q.push(sta(nx,ny));
 48         }
 49     }
 50     ++blk[c].u;--blk[c].d;++blk[c].r;--blk[c].l;
 51     for(int i=blk[c].l;i<=blk[c].r;i++)
 52         id[blk[c].u][i]=id[blk[c].d][i]=c;
 53     for(int i=blk[c].d;i<=blk[c].u;i++)
 54         id[i][blk[c].l]=id[i][blk[c].r]=c;
 55 }
 56 void bfs2(int x,int y,int c) {
 57     queue<sta> q;q.push(sta(x,y));
 58     while(!q.empty()) {
 59         sta u=q.front(); q.pop();
 60         for(int i=0;i<3;i++) {
 61             int nx=u.x+dx[i],ny=u.y+dy[i];
 62             if(nx<1||ny<1||nx>n||ny>m) continue;
 63             if(vis[nx][ny]) continue;
 64             if(id[nx][ny]==c) continue;
 65             if((s[u.x][u.y]=='|'||s[u.x][u.y]=='+')&&i==2) {
 66                 if(s[u.x][u.y]=='|'&&id[nx][ny]) {
 67                     ver[c].push_back(id[nx][ny]);
 68                     return;
 69                 }
 70                 if(s[nx][ny]=='|'||s[nx][ny]=='+')
 71                     vis[nx][ny]=1,q.push(sta(nx,ny));
 72             } else if((s[u.x][u.y]=='-'||s[u.x][u.y]=='+')&&i<=1) {
 73                 if(s[nx][ny]=='-'||s[nx][ny]=='+')
 74                     vis[nx][ny]=1,q.push(sta(nx,ny));
 75             }
 76         }
 77     }
 78 }
 79 void print(int u) {
 80     for(int i=0;i<ver[u].size();i++) print(ver[u][i]);
 81     printf("%d
",u);
 82 }
 83 int main() {
 84     scanf("%d%d",&n,&m);
 85     for(int i=1;i<=n;i++)
 86         scanf("%s",s[i]+1);
 87     for(int i=1;i<=n;i++)
 88         for(int j=1;j<=m;j++)
 89             if(!id[i][j]&&s[i][j]>='0'&&s[i][j]<='9')
 90                 bfs1(i,j);
 91     for(int i=1;i<=idmx;i++) {
 92         for(int j=blk[i].u;j>=blk[i].d;j--) {
 93             if(blk[i].l-1&&s[j][blk[i].l-1]=='-')
 94                 bfs2(j,blk[i].l-1,i);
 95             if(blk[i].r+1<=m&&s[j][blk[i].r+1]=='-')
 96                 bfs2(j,blk[i].r+1,i);
 97         }
 98     }
 99     print(1);
100     return 0;
101 }

t1 Code

T2：可爱精灵宝贝

　　发现捉的精灵一定是跨越点$k$的一段连续区间

　　设计状态$f[t][l][r][0/1]$表示$t$时刻捉完了$l$到$r$这一段的精灵现在站在左边（0）或右边（1）的最大得分

　　简单的转移就完了

 1 #include<cstring>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<queue>
 6 #include<vector>
 7 #include<cstdlib>
 8 using namespace std;
 9 const int MAXN=2100,MAXT=2100,T=2000;
10 int n,k,m,ans,tot,val[MAXN][MAXT],f[MAXT][150][150][2];
11 int pos[MAXN],id[MAXN];
12 inline int R() {
13     int a=0;char c=getchar();
14     while(a>'9'||c<'0')c=getchar();
15     while(c>='0'&&c<='9')a=a*10+c-'0',c=getchar();
16     return a;
17 }
18 void gmax(int &x,int y) {
19     x=max(x,y);
20 }
21 int main() {
22     n=R();k=R();m=R();
23     for(int i=1,aa,bb,cc;i<=m;i++) {
24         aa=R();bb=R();cc=R();
25         val[aa][cc]+=bb;
26     }
27     for(int i=1;i<=n;i++)
28         for(int j=T;j>=1;j--)
29             val[i][j]+=val[i][j+1];
30     for(int i=1;i<=n;i++)
31         if(val[i][1]||i==k) id[i]=++tot,pos[tot]=i;
32     memset(f,-1,sizeof(f));
33     f[1][id[k]][id[k]][0]=f[1][id[k]][id[k]][1]=val[k][1];
34     for(int t=1;t<=T;t++) {
35         for(int l=1;l<=id[k];l++) {
36             for(int r=id[k];r<=tot;r++) {
37                 if(~f[t][l][r][0]) {
38                     gmax(f[t+1][l][r][0],f[t][l][r][0]);
39                     if(t+pos[l]-pos[l-1]<=T&&l>1)
40                         gmax(f[t+pos[l]-pos[l-1]][l-1][r][0],f[t][l][r][0]+val[pos[l-1]][t+pos[l]-pos[l-1]]);
41                     if(t+pos[r+1]-pos[l]<=T&&r<tot)
42                         gmax(f[t+pos[r+1]-pos[l]][l][r+1][1],f[t][l][r][0]+val[pos[r+1]][t+pos[r+1]-pos[l]]);
43                 }
44                 if(~f[t][l][r][1]) {
45                     gmax(f[t+1][l][r][1],f[t][l][r][1]);
46                     if(t+pos[r+1]-pos[r]<=T&&r<tot)
47                         gmax(f[t+pos[r+1]-pos[r]][l][r+1][1],f[t][l][r][1]+val[pos[r+1]][t+pos[r+1]-pos[r]]);
48                     if(t+pos[r]-pos[l-1]<=T&&l>1)
49                         gmax(f[t+pos[r]-pos[l-1]][l-1][r][0],f[t][l][r][1]+val[pos[l-1]][t+pos[r]-pos[l-1]]);
50                 }
51                 ans=max(ans,max(f[t][l][r][0],f[t][l][r][1]));
52             }
53         }
54     }    
55     printf("%d
",ans);
56     return 0;
57 }

t2 Code

ps：一道相似的题——关路灯

T3：相互再归的鹅妈妈

　　听说是斯特林反演……

　　不会，咕咕咕