首页 > 代码库 > 5.20 考试 20 未完

5.20 考试 20 未完

水灾(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

解题思路:对于每一秒,洪水东会移动,是较难处理的,可以用一个三维数组记录每一秒时洪水的状态f[s][i][j],第s秒时洪水的状态;然后就是bfs

由于当时先做的后两题,so此题时间不够,乱写一通:

当时代码,留个纪念

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 const int N=60;
 8 
 9 int a[N][N];
10 
11 inline void read(int &x)
12 {
13     char c=getchar();
14     x=0;
15     while(c<0||c>9)c=getchar();
16     while(c>=0&&c<=9)x=x*10+c-0,c=getchar();
17 }
18 
19 int sx,sy,dx,dy,xx,xy;
20 
21 int main()
22 {
23     freopen("sliker.in","r",stdin);
24     freopen("sliker.out","w",stdout);
25     int n,m;
26     read(n);
27     read(m);
28     char c;
29     for(int i=1;i<=n;i++)
30         for(int j=1;j<=m;j++)
31         {
32             scanf("%c",&c);
33             if(c==S)
34                 sx=i,sy=j;
35             if(c==*)
36                 xx=i,xy=j;
37             if(c==D)
38                 dx=i,dy=j;
39         }    
40     if(((dx<=xx&&dx<=sx)||(dx>=xx&&dx>=sx))&&((dy<=xy&&dy>=sy)||(dy>=xy&&dy<=sy)))
41     {
42         int xj=abs(xx-dx)-1+abs(xy-dy)+3;
43         int sj=abs(sx-dx)+abs(xy-dy);
44         if(sj<=xj) {printf("%d",sj); return 0;}
45         else {printf("ORZ hzwer!!!"); return 0;}
46     }
47     if(((dx<=xx&&dx<=sx)||(dx>=xx&&dx>=sx))&&((dy<=xy&&dy<=sy)||(dy>=xy&&dy>=sy)))
48     {
49         if(sy<=xy) {printf("%d",abs(sx-dx)+abs(sy-dy));return 0;}
50         else {printf("ORZ hzwer!!!");return 0;}
51     }
52     if(((dx<=xx&&dx>=sx)||(dx>=xx&&dx<=sx))&&((dy<=xy&&dy>=sy)||(dy>=xy&&dy<=sy)))
53     {
54         int xj=abs(xx-dx)+abs(xy-dy);
55         int sj=abs(sx-dx)+abs(xy-dy);
56         if(sj<=xj) {printf("%d",sj); return 0;}
57         else {printf("ORZ hzwer!!!");return 0;}
58     }
59     if(((dx<=xx&&dx>=sx)||(dx>=xx&&dx<=sx))&&((dy<=xy&&dy<=sy)||(dy>=xy&&dy>=sy)))
60     {
61         int xj=abs(xx-dx)+abs(xy-dy);
62         int sj=abs(sx-dx)+abs(sy-dy);
63         if(sj<=xj) {printf("%d",sj);return 0;}
64         else {printf("ORZ hzwer!!!");return 0;}
65     }
66     printf("ORZ hzwer!!!");
67     return 0;
68 }
View Code

正解(还未看):

技术分享
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 const int N=55;
 6 char a[N][N];
 7 bool vis[N][N];
 8 int n,m,ex,ey,d[N][N],dis[N][N];
 9 struct node{
10     int x,y;
11     node(int x=0,int y=0):x(x),y(y){}
12 };
13 const int dx[]={0,0,1,-1};
14 const int dy[]={1,-1,0,0};
15 inline bool inside(int &x,int &y){
16     return x>0&&x<=n&&y>0&&y<=m;
17 }
18 void bfs(int sx,int sy){
19     memset(vis,0,sizeof vis);
20     queue<node>q;
21     q.push(node(sx,sy));
22     vis[sx][sy]=1;
23     d[sx][sy]=0;
24     while(!q.empty()){
25         node h=q.front();q.pop();
26         int px=h.x,py=h.y;
27         vis[px][py]=0;
28         for(int i=0,nx,ny;i<4;i++){
29             nx=px+dx[i];
30             ny=py+dy[i];
31             if(inside(nx,ny)&&a[nx][ny]!=X&&a[nx][ny]!=D){
32                 if(d[nx][ny]>d[px][py]+1){
33                     d[nx][ny]=d[px][py]+1;
34                     if(!vis[nx][ny]){
35                         vis[nx][ny]=1;
36                         q.push(node(nx,ny));
37                     }
38                 }
39             }
40         }
41     }
42 }
43 void spfa(int sx,int sy){
44     memset(vis,0,sizeof vis);
45     queue<node>q;
46     q.push(node(sx,sy));
47     vis[sx][sy]=1;
48     dis[sx][sy]=0;
49     while(!q.empty()){
50         node h=q.front();q.pop();
51         int px=h.x,py=h.y;
52         vis[px][py]=0;
53         for(int i=0,nx,ny;i<4;i++){
54             nx=px+dx[i];
55             ny=py+dy[i];
56             if(inside(nx,ny)&&a[nx][ny]!=X){
57                 if(dis[px][py]+1>=d[nx][ny]) continue;
58                 if(dis[nx][ny]>dis[px][py]+1){
59                     dis[nx][ny]=dis[px][py]+1;
60                     if(!vis[nx][ny]){
61                         vis[nx][ny]=1;
62                         q.push(node(nx,ny));
63                     }
64                 }
65             }
66         }
67     }
68 }
69 int main(){
70     memset(dis,0x3f3f3f3f,sizeof dis);
71     memset(d,0x3f3f3f3f,sizeof d);
72     scanf("%d%d",&n,&m);
73     for(int i=1;i<=n;i++){
74         scanf("%s",a[i]+1);
75     }
76     for(int i=1;i<=n;i++){
77         for(int j=1;j<=m;j++){
78             if(a[i][j]==*){
79                 bfs(i,j);
80             }
81         }
82     }
83     for(int i=1;i<=n;i++){
84         for(int j=1;j<=m;j++){
85             if(a[i][j]==S){
86                 spfa(i,j);
87             }
88             if(a[i][j]==D){
89                 ex=i;ey=j;
90             }
91         }
92     }
93     if(dis[ex][ey]<0x3f3f3f3f) printf("%d\n",dis[ex][ey]);
94     else puts("ORZ hzwer!!!");
95     return 0;
96 }
View Code

 

 

 

某种数列问题  (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问题,对于每一个元素,都存在选与不选的问题,所以定义 f[i][j][0]表示前 i 个中取 j 段的最大值,
其中第 i 个被取到。f[i][j][1]表示前i个中取j段的最大值,
其中第 i 个没被取到。显然max(f[n][3][0],f[n][3][1])即是所求,不过当时写了个暴力,感觉不应该只得20分的,可能有错误吧

暴力20:

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 const int N=1000010;
 8 
 9 int a[N];
10 int b[N-30];
11 int js;
12 int n;
13 
14 inline void read(int &x)
15 {
16     char c=getchar();
17     x=0;
18     while(c<0||c>9)c=getchar();
19     while(c>=0&&c<=9)x=x*10+c-0,c=getchar();
20 }
21 
22 int main()
23 {
24     freopen("jx.in","r",stdin);
25     freopen("jx.out","w",stdout);
26     read(n);
27     for(int i=1;i<=n;i++)
28     {
29         scanf("%d",&a[i]);
30     }
31     int ans;
32     for(int i=1;i<=n;i++)
33     {
34         if(a[i]>=0)
35         {
36             ans=0;
37             int j=i;
38             while(a[j]>=0)
39             {
40                 ans+=a[j];
41                 j++;
42             }
43             b[++js]=ans;
44             i=j;
45         }
46     }
47     sort(b+1,b+js+1);
48     long long Answer=b[js]+b[js-1]+b[js-2];
49     
50     printf("%lld",Answer);
51     
52     return 0;
53 }
54 /*
55 10
56 -1
57 2
58 3
59 -4
60 0
61 1
62 -6
63 -1
64 1
65 -2
66 */
View Code

正解:

技术分享
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 
 5 #define maxn 1000001
 6 
 7 using namespace std;
 8 
 9 inline int read() 
10 {
11     int x=0,f=1;
12     char ch=getchar();
13     while(ch<0||ch>9) 
14     {
15         if(ch==-)f=-1;
16         ch=getchar();
17     }
18     while(ch>=0&&ch<=9) 
19     {
20         x*=10;
21         x+=ch-0;
22         ch=getchar();
23     }
24     return x*f;
25 }
26 
27 int n,cnt;
28 int a[maxn];
29 int s[maxn];
30 int f[maxn][4][2];
31 
32 /*
33 
34 dp  f[i][j][0]表示前i个中取j段的最大值,
35 其中第i个被取到。f[i][j][1]表示前i个中取j段的最大值,
36 其中第i个没被取到。显然max(f[n][3][0],f[n][3][1])即是所求
37 
38 */
39 
40 int main() 
41 {
42     //freopen("jx.in","r",stdin);
43     //freopen("jx.out","w",stdout);
44     n=read();
45     for (int i=1; i<=n; i++) a[i]=read();
46     for (int i=1; i<=n; i++)
47         for (int j=1; j<=3; j++) 
48         {
49             f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
50             f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+a[i]);
51             f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[i]);
52         }
53     printf("%d",max(f[n][3][1],f[n][3][0]));
54 }
View Code

 

 

密码锁 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

Size[1]  size[2]

【样例输出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。

解题思路:暴力感觉也能点分,不过0

当时:

思路:记录出所有段的长度,存到struct 之后枚举暴力,判断每一段是否都能找到其整数倍,若不能输出‘-1’,否则输出最少步数,然而输出-1,就得10分,可我却得0分:

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 const int M=101;
 8 const int N=10010;
 9 const int K=15;
10 
11 inline void read(int &x)
12 {
13     char c=getchar();
14     x=0;
15     while(c<0||c>9)c=getchar();
16     while(c>=0&&c<=9)x=x*10+c-0,c=getchar();
17 }
18 
19 struct node{
20     int js;
21     int start;
22 }E[M];
23 
24 int now;
25 int n,m,k;
26 int a[N];
27 int b[K];
28 bool vis[M];
29 
30 int main()
31 {
32     freopen("password.in","r",stdin);
33     freopen("password.out","w",stdout);
34     read(n);read(m);read(k);
35     read(a[1]);
36     E[1].js++;
37     E[1].start=a[1];
38     now=1;
39     for(int i=2;i<=m;i++)
40     {
41         read(a[i]);
42         if(a[i]!=a[i-1]+1)
43         {
44             now++;
45             E[now].js++;
46             E[now].start=a[i];
47         }
48         else E[now].js++;
49     }
50     for(int i=1;i<=k;i++)
51     {
52         read(b[i]);
53     }
54     for(int i=1;i<=now;i++)
55     {
56         if(!vis[E[i].js])
57         {
58             vis[E[i].js]=1;
59             bool flag=0;
60             for(int j=1;j<=k&&!flag;j++)
61             {
62                 if(b[j]==E[i].js)
63                 {
64                     flag=1;
65                 }
66             }
67             if(!flag) { printf("-1"); return 0;}
68         }
69     }
70     printf("%d",now);
71     return 0;
72 }
View Code

正解:

 

5.20 考试 20 未完