A

模拟,只要找出1和夹在两个1中间的0的个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 110;
int a[maxn];


int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
int ans = 0,rem = -1;
memset(a,0,sizeof a);
for(int i=0;i<n;++i) scanf("%d",a+i);
for(int i=0;i<n;++i)
{
if(a[i] == 1) ++ans;
if(a[i] == 0 && i && a[i-1] == 1 && a[i+1] == 1) ++ans;
}
printf("%d\n",ans);
return 0;
}

B

枚举每一条路径,找到最短和次短的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 110;
const int INF = 0x3f3f3f3f;

int a[maxn],b[maxn],c[maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
a[0] = b[0] = 0;
for(int i=1;i<n;++i) scanf("%d",a+i),a[i] += a[i-1];
for(int i=1;i<n;++i) scanf("%d",b+i),b[i] += b[i-1];
for(int i=0;i<n;++i) scanf("%d",c+i);
int mn1,mn2;
mn1 = mn2 = INF;
for(int i=0;i<n;++i)
{
int cur = b[n-1] - b[i] + c[i] + a[i] - a[0];
//printf("%d\n",cur);
if(mn1 >= cur)
{
mn2 = mn1;
mn1 = cur;
}
else if(mn2 > cur) mn2 = cur;
}
printf("%d\n",mn1+mn2);
return 0;
}

C

模拟,注意p一旦为负立即离队,还要注意会爆long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 4010;

int v[maxn],d[maxn],n;
LL p[maxn];
bool inque[maxn];


int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d %d %d",v+i,d+i,p+i);
inque[i] = 1;
}
int cur = 0,cnt = 0;
while(cur<n)
{
while(cur < n && !inque[cur]) ++cur;
if(cur < n) ++cnt;
else break;
LL dec = v[cur];
for(int i=cur+1;i<n;++i)
{
if(dec <= 0) break;
if(!inque[i]) continue;
p[i] -= dec;
--dec;
}
dec = 0;
for(int i=cur+1;i<n;++i)
{
if(!inque[i]) continue;
p[i] -= dec;
if(p[i] < 0)
{
inque[i] = 0;
dec += d[i];
}
}
++cur;
}
//for(int i=0;i<n;++i) printf("%d\n",p[i]);
printf("%d\n",cnt);
for(int i=0;i<n;++i) if(inque[i]) printf("%d%c",i+1,--cnt == 0?'\n':' ');
return 0;
}

D

bfs 注意读题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 110;
int n,m;
int p[maxn],line[maxn],len[maxn];
bool vis[3][maxn];

struct P
{
int t,r;
P() {}
P(int t,int r):t(t),r(r) {}
};

bool bfs(int po)
{
queue<P> Q;

Q.push(P(0,po));
memset(vis,0,sizeof vis);
vis[po][0] = 1;

while(!Q.empty())
{
P u = Q.front(); Q.pop();

int t = u.t,r = u.r;

// printf("%d %d\n",t,r);

if(t == n-1) return true;

int flag = 1;

for(int i=0;i<m;++i)
{
if(line[i] != r) continue;

if(t+1 == p[i] - t*2)
{
flag = -1;
break;
}

if((t+1 >= p[i]-t*2 && t+1 <= p[i]-t*2+len[i]-1) || (t+1 >= p[i]-(t+1)*2 && t+1 <= p[i]-(t+1)*2+len[i]-1))
{
flag = 0;
break;
}
}

if(flag == -1) continue;

if(flag && !vis[r][t+1])
{
vis[r][t+1] = 1;
Q.push(P(t+1,r));
}

if(r >= 1)
{
flag = 1;
for(int i=0;i<m;++i)
{
if(line[i] != r-1) continue;

if((t+1 >= p[i]-t*2 && t+1 <= p[i]-t*2+len[i]-1) || (t+1 >= p[i]-(t+1)*2 && t+1 <= p[i]-(t+1)*2+len[i]-1))
{
flag = 0;
break;
}
}
if(flag && !vis[r-1][t+1])
{
vis[r-1][t+1] = 1;
Q.push(P(t+1,r-1));
}
}

if(r <= 1)
{
flag = 1;
for(int i=0;i<m;++i)
{
if(line[i] != r+1) continue;

if((t+1 >= p[i]-t*2 && t+1 <= p[i]-t*2+len[i]-1) || (t+1 >= p[i]-(t+1)*2 && t+1 <= p[i]-(t+1)*2+len[i]-1))
{
flag = 0;
break;
}
}

if(flag && !vis[r+1][t+1])
{
vis[r+1][t+1] = 1;
Q.push(P(t+1,r+1));
}
}
}
return false;
}


int main()
{
//freopen("test.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
int cnt = 0,po = 0;
memset(len,0,sizeof len);
for(int i=0;i<3;++i)
{
char s[maxn];
scanf("%s",s);
if(s[0] == 's') po = i;
int j = 1;
while(j<n)
{
if(s[j] != '.')
{
line[cnt] = i;
p[cnt] = j;
char ch = s[j];
while(j<n && ch == s[j]) ++len[cnt],++j;
++cnt;
}
else ++j;
}
}
m = cnt;
//for(int i=0;i<m;++i) printf("%d %d %d\n",line[i],p[i],len[i]);
puts(bfs(po)?"YES":"NO");
}
return 0;
}