得分：100+40+30=170，还是可以的。

1. 水灾（sliker.cpp/c/pas） 1000MS  64MB

大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。

CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。

CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。

求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。

输入文件 sliker.in

输出文件 sliker.out

Input

3 3

D.*

…

.S.

 

Output

3

 

Input

3 3

D.*

…

..S

Output

ORZ hzwer!!!

 

Input

3 6

D…*.

.X.X..

….S.

Output

6

思路：

　　广搜。和其他题不同的是可以扩展的点不只有起点，还有洪水所在的点。处理好每个点的扩展状态就和一般广搜一样了。

代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4  5 int n,m,Sx,Sy,Ex,Ey,cnt,To[5]={
    1,0,-1,0,1}; 6 struct State 7 { 8     int x,y,step; 9 }cur,nxt,F,Fnxt;10 bool vis[66][66],Map[66][66];11 queue
        
         q;12 queue
         
          Flow;13 14 void bfs()15 {16     cur.x=Sx;cur.y=Sy;cur.step=0;17     q.push(cur);18     while(!q.empty())19     {20         int now=q.size();21         while(now--)22         {23             cur=q.front();24             q.pop();25             int x=cur.x,y=cur.y;26             if(!Map[x][y])continue;27             Map[x][y]=0;28             for(int i=0;i<4;i++)29             {30                 int xx=x+To[i],yy=y+To[i+1];31                 if(xx==Ex && yy==Ey)32                 {33                     printf("%d",cur.step+1);34                     return;35                 }36                 if(xx>n||xx<1||yy>m||yy<1||!Map[xx][yy])continue;37                 nxt.x=xx;nxt.y=yy;nxt.step=cur.step+1;38                 q.push(nxt);39             }40         }41         int tmp=Flow.size();42         while(tmp--)43         {44             F=Flow.front();45             Flow.pop();46             for(int i=0;i<4;i++)47             {48                 int xx=F.x+To[i],yy=F.y+To[i+1];49                 if(xx>n||xx<1||yy>m||yy<1||!Map[xx][yy])continue;50                 Map[xx][yy]=0;51                 Fnxt.x=xx;Fnxt.y=yy;52                 Flow.push(Fnxt);53             }54         }55     }56     printf("ORZ hzwer!!!");57     return;58 }59 60 int main()61 {62     freopen("sliker.in","r",stdin);63     freopen("sliker.out","w",stdout);64     scanf("%d%d",&n,&m);65     for(int i=1;i<=n;i++)66     {67         char s[66];68         scanf("%s",s+1);69         for(int j=1;j<=m;j++)70           if(s[j]=='.')71             Map[i][j]=1;72           else if(s[j]=='X')73             Map[i][j]=0;74           else if(s[j]=='*')75           {76                 F.x=i;F.y=j;77                 Flow.push(F);78                 Map[i][j]=0;79           }80           else if(s[j]=='D')81             Ex=i,Ey=j;82           else83             Sx=i,Sy=j,Map[i][j]=1;84     }85     /*for(int i=1;i<=n;i++,printf("\n"))86       for(int j=1;j<=m;j++)87         if(Map[i][j])88           printf("1 ");89         else90           printf("0 ");*/91     bfs();92     return 0;93 }
         
        
       
      

2.某种数列问题  (jx.cpp/c/pas) 1000MS 256MB

 

众所周知，chenzeyu97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，chenzeyu97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一个妹子不能被编入多个队伍而且一定要拿出三队，不然czy会闲着没事做~。

简单滴说就是：

给定一个数列，从中找到3个无交集的连续子数列使其和最大。

【输入文件】

第一行一个数n，表示数列长度。

接下来有n行，每行一个数，第i行为第i个数。

【输出文件】

仅有一个数，表示最大和。

【样例输入】 jx.in

10

-1

2

3

-4

0

1

-6

-1

1

-2

【样例输出】 jx.out

7

【样例说明】

第一队妹子取2，3。

第二队妹子取0，1。

第三队妹子取1。

【数据范围】

请大家放心，虽然chenzeyu97妹子无数，但是这次他叫来的个数n是有限的。=v=

对于30%的数据，妹子数不大于200。

对于60%的数据，妹子数不大于2000。

对于100%的数据，妹子数1000000。

而且，由于chenzeyu97没有CCR那样的影响力，所以他的妹子选完的最大美丽度和不超过maxlongint。(注:CCR随便选就爆long long，因为他是把妹狂魔=V=)。

思路：

 　　做的时候想的是三段最大子段和，正好是老师讲过的，然而实际并不对。

　　正解是DP加贪心。

代码：

正解（我的没存下来就用同学的了，思路是一样的）：

1 #include
      
        2 #include
       
         3 using namespace std; 4  5 int note[1000001]; 6 int dp[4][1000001][2]; 7  8 int read() 9 {10        int f=1;11        int num=0;12        char c=getchar();13        while(c<'0'||c>'9')14        {15               if(c=='-')f=-1;16               c=getchar();17        }18        while(c>='0'&&c<='9')19        {20               num*=10;21               num+=c-'0';22               c=getchar();23        }24        return f*num;25 }26 int main()27 {28        freopen("jx.in","r",stdin);29        freopen("jx.out","w",stdout);30        int n=read();31        for(int i=1;i<=n;i++)32        {33               note[i]=read();34        }35        for(int i=1;i<=n;i++)36        {37               for(int j=1;j<=3;j++)38              {      39                      dp[j][i][0]=max(dp[j][i-1][0],dp[j][i-1][1]);40                      /*既然当前的的不拿，最大值就和当前无关，只需要判断前一步的最大值*/41                      dp[j][i][1]=max(dp[j][i-1][1]+note[i],max(dp[j][i][1],dp[j-1][i-1][0]+note[i]));42                      /*当前的若要拿的话   分两种情况*/43                      /*与上一个连着  单成一个*/44                      /*但是如果这两种情况都小于0时还不如不选*/45               }46        }47        printf("%d",max(dp[3][n][1],dp[3][n][0]));48        return 0;49 }
       
      

错误的40分最大子段和

1 #include
      
        2 using namespace std; 3  4 int n,Num[1000005]; 5 long long Ans; 6  7 int main() 8 { 9     freopen("jx.in","r",stdin);10     freopen("jx.out","w",stdout);11     scanf("%d",&n);12     for(int i=1;i<=n;i++)13       scanf("%d",&Num[i]);14     15     int Max=1<<31,Temp1,Temp2,Mark1=0,Mark2=0;16     int Sum=0;bool flag=0;17     for(int i=1;i<=n;i++)18     {19         Sum+=Num[i];20         if(Sum>Max)21         {22             Max=Sum;23             if(flag)24               continue;25             Mark1=i;26             flag=1;27         }28         if(Sum<0)29           Sum=0,flag=0;//断开 30     }31     32     Ans+=Max;//printf("1:%d Mark:%d\n",Max,Mark1);33     Temp1=Max;34     Max=1<<31;35     Sum=0;flag=0;36     37     for(int i=1;i<=n;i++)38     {39         if(i==Mark1)40         {41             int tmp=0;42             while(tmp
       
        Max)48         {49             Max=Sum;50             if(flag)51               continue;52             Mark2=i;53             flag=1;54         }55         if(Sum<0)56           Sum=0,flag=0;57     }58     59     Ans+=Max;//printf("2:%d   Mark:%d\n",Max,Mark2);60     Temp2=Max;61     Max=1<<31;62     Sum=0;flag=0;63     64     for(int i=1;i<=n;i++)65     {66         if(i==Mark1)67         {68             int tmp=0;69             while(tmp
       
      

 

 

3.密码锁 1000MS 512MB

Input: password.in

Output: password.out

【题目描述】

hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。

他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）

本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有的钱他哪里能逃过被chenzeyu97 NTR的命运？>_<  于是，他为了虐爆czy，也为了去泡更多的妹子，决定打开这把锁。但是他那么神的人根本不屑这种”水题”。于是，他找到了你。

你的任务很简单，求出最少需要多少步才能打开密码锁，或者如果无解的话，请输出-1。

【输入格式】

第1行，三个正整数N，K，M，如题目所述。

第2行，K个正整数，表示开关x1,x2,x3..xk必须为开，保证x两两不同。

第三行，M个正整数，表示size[i]，size[]可能有重复元素。

【输出格式】

输出答案，无解输出-1。

【样例输入1】

10 8 2

1 2 3 5 6 7 8 9

3 5

【样例输出1】

2

【样例输入2】

3 2 1

1 2

3

【样例输出2】

-1

【数据规模】

对于50%的数据，1≤N≤20，1≤k≤5，1≤m≤3;

对于另外20%的数据，1≤N≤10000，1≤k≤5,1≤m≤30;

对于100%的数据，1≤N≤10000，1≤k≤10，1≤m≤100。

思路：

　　考试时的想法是：一半数据都很小，像A-B数对那题那样强行判断m<=3时的可行状况，实际还是有很大问题，只得了30（不过也不低了）。

　　正解：状态压缩+差分序列+bfs+完全图最小权最大匹配(?)

　　完全不会。

代码：

引用学长的（）：

1 /*  2     对于区间取反 复杂度是O(n)  3     但是因为这题序列只有01  4     如果操作查分序列的话就快多了  5     先搞出查分序列 然后bfs求出每两个点的1相互抵消最少操作次数  6     因为最后的序列最多20个1 所以状丫dp搞一搞求出min操作次数  7       8       9     注意到题目中的是区间修改，把沿途的位置取反， 10     这个可以看做是在模2意义下，给区间的加一操作。在我们通常的思路中，对于区间的操作，原本是要修改区间长度个的位置的情况，我们都可以通过考虑它的差分序列，使得要修改的位置个数变成2个，我们要求最少的修改，使得原序列变成全0。 11  12     所以对原序列进行差分，那么每次修改就是要你对i号位置和i+size[]模2意义下的加1。 13  14     差分后的序列中，数值为1的个数是不会超过2k个，即不会超过20个。 15  16     考虑每次对i和i+x改动的过程，如果原序列中， 17     i号位置和i+x号位置都是0的话，我们这么改，没有任何必要。 18     所以任意时刻，数值为1的位置个数是不会增加的，那么我们可以把每一个的1看成一个的石子， 19     那么每次我们可以把石子往某个方向移动size[]步，如果移动之后的位置存在石子的话，就对对碰，消掉了。 20  21     因为是对对碰，石子之间的关系肯定是一个匹配的关系，我们不妨求出Dist[i][j]表示， 22     石子i要走到石子j的位置，至少需要移动多少步，那么我们可以枚举每一个石子， 23     然后进行一遍的bfs即可，这一部分的复杂度是O(2kmn)。 24     现在问题转化为有一个大小不超过20的完全图，我们想要求它的最小权最大匹配。 25 */ 26 #include
      
        27 #include
       
         28 #include
        
          29 #include
         
           30 #define maxn 10010 31 using namespace std; 32 int n,m,k,size[110],a[maxn],c[maxn],s[maxn],cnt,step[110][110]; 33 int f[maxn],dis[maxn],dp[1<<22],inf; 34 struct node 35 { 36     int x,t; 37 }; 38 queue
          
           q; 39 void Bfs(int S,int o) 40 { 41     while(!q.empty())q.pop(); 42     memset(f,0,sizeof(f)); 43     memset(dis,127/3,sizeof(dis)); 44     inf=dis[0]; 45     q.push((node) 46     { 47         S,0 48     }); 49     f[S]=1; 50     dis[S]=0; 51     while(!q.empty()) 52     { 53         node p=q.front(); 54         q.pop(); 55         for(int i=1; i<=k; i++) 56         { 57             int y=p.x+size[i]; 58             if(y<=n&&f[y]==0) 59             { 60                 f[y]=1; 61                 dis[y]=p.t+1; 62                 q.push((node) 63                 { 64                     y,dis[y] 65                 }); 66             } 67             y=p.x-size[i]; 68             if(y>=1&&f[y]==0) 69             { 70                 f[y]=1; 71                 dis[y]=p.t+1; 72                 q.push((node) 73                 { 74                     y,dis[y] 75                 }); 76             } 77         } 78     } 79     for(int i=1; i<=cnt; i++) 80         if(dis[c[i]]
          
         
        
       
      

 30分代码

1 #include
      
        2 #include
       
         3 using namespace std; 4  5 int n,k,m,cnt,Ans,Last,size[110],Num[110]; 6 bool opt[50010]; 7 struct Interval 8 { 9     int fr,to;10 }Inv[10010];11 12 /*void Init()13 {14     for(int i=1;i<=n;i++)15       now[i]=0;16 }*/17 18 /*bool Check(bool a[])19 {20     for(int i=1;i<=n;i++)21       if(a[i]!=Ans[i])22         return 0;23     return 1;24 }*/25 26 int main()27 {28     freopen("password.in","r",stdin);29     freopen("password.out","w",stdout);30     scanf("%d%d%d",&n,&k,&m);31     //printf("%d %d %d\n",n,k,m);32     //Init();33     Inv[0].fr=Inv[0].to=-12345;34     for(int i=1;i<=k;++i)35     {36         scanf("%d",&Num[i]);37         if(Num[i]-1!=Inv[cnt].to)38           Inv[++cnt].fr=Num[i],Inv[cnt].to=Num[i];39         else40           Inv[cnt].to=Num[i];41     }42     //for(int i=1;i<=cnt;++i)43       //printf("i:%d From:%d  To:%d\n",i,Inv[i].fr,Inv[i].to);44     for(int i=1;i<=m;++i)45     {46         scanf("%d",&size[i]);47         opt[size[i]]=1;48     }49     sort(size+1,size+1+m);50     //for(int i=1;i<=m;i++)51       //printf("i:%d  size:%d\n",i,size[i]);52     for(int i=1;i<=cnt;++i)53     {54         int tmp=Inv[i].to-Inv[i].fr+1;55         bool GoOn=1;56         if(opt[tmp])57         {58             ++Ans;continue;59         }60         if(m>=2)61         {62             for(int i=1;i<=m && GoOn;++i)63               for(int j=i;j<=m;++j)64                 if(size[i]+size[j]==tmp||size[j]-size[i]==tmp)65                 {66                     Ans+=2;67                     GoOn=0;68                     break;69                 }70         }71         if(GoOn && m>=3)72         {73             for(int i=1;i<=m && GoOn;++i)74               for(int j=i;j<=m && GoOn;++j)75                 for(int k=j;k<=m && GoOn;++k)76                   if(size[i]+size[j]+size[k]==tmp||size[i]+size[j]+tmp==size[k])77                   {78                         Ans+=3;//printf("%d + %d + %d=%d !\n",size[i],size[j],tmp,size[k]);79                         GoOn=0;80                         break;81                   }82         }83         if(Last==Ans)84         {85             printf("-1");86             return 0;87         }88         Last=Ans;89     }90     printf("%d",Ans);91     return 0;92 }/*93 15 8 394 1  2 3 9 10 11 12 1395 12 3 496 Out: 497 */