这场极水,手速狗的战争…

A

读懂题就好了

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=110;
bool vis[maxn];
vector<int> ans;

int main()
{
//freopen("test.txt","r",stdin);
int n,x,cnt=0;
scanf("%d",&n);
for(int i=0;i<n;++i){
vis[i]=1;
for(int j=0;j<n;++j){
scanf("%d",&x);
if(x==1 || x==3) vis[i]=0;
}
if(vis[i]) ++cnt;
}
printf("%d\n",cnt);
for(int i=0;i<n;++i){
if(vis[i]){
printf("%d",i+1);
if(--cnt) printf(" ");
}
}
return 0;
}

B

定义两个字符串距离为两字符串对应位置不同字符的个数
给两个等长01串,找到一个相同长度的01串使得到两串长度一致。

贪心+构造: 首先保证两串距离为偶数,否则无法构造。
然后相同位置字符不变,不同位置各取一半,即为生成的串。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=100010;
char s[maxn],t[maxn];
bool vis[maxn];

int main()
{
memset(vis,0,sizeof vis);
scanf("%s %s",s,t);
int err,n=strlen(s);
for(int i=0;i<n;++i){
if(s[i]!=t[i]) ++err;
}
if(err&1){
puts("impossible");
return 0;
}
for(int i=0;i<n;++i){
if(s[i]!=t[i] && err--) vis[i]=(err&1)?(s[i]=='1'):(t[i]=='1');
else vis[i]=(s[i]=='1');
}
for(int i=0;i<n;++i){
putchar(vis[i]?'1':'0');
}
puts("");
return 0;
}

C

DP 但是这题贪心是正解。。。

d[i][0..2] 表示第i个树(0左倒,1不倒,2右倒)
状态转移比较复杂,直接参考程序。

需要注意的是只有一棵树的情况。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=100010;
int H[maxn],X[maxn];
int d[maxn][3];

int dp(int p,int k){
if(p==0) return 1;
int &ans=d[p][k];
if(ans!=-1) return ans;
ans=0;

if(k==0){
if(X[p]-H[p]>X[p-1]) ans=max(ans,max(dp(p-1,0),dp(p-1,1))+1);
if(X[p]-H[p]>X[p-1]+H[p-1]) ans=max(ans,dp(p-1,2)+1);
}

if(k==1){
ans=max(dp(p-1,2),max(dp(p-1,0),dp(p-1,1)));
}

if(k==2){
if(X[p]+H[p]<X[p+1]){
ans=max(dp(p-1,0),dp(p-1,1))+1;
if(X[p]>X[p-1]+H[p-1]) ans=max(ans,dp(p-1,2)+1);
}
}

return ans;
}

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d %d",X+i,H+i);
if(n==1){
puts("1");
return 0;
}
memset(d,-1,sizeof d);
printf("%d\n",dp(n-1,1)+1);
return 0;
}

这是贪心解法,只需用last记录上一棵树倒下的状态,优先向左,然后向右,最后是不倒。

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
#include<cstdio>
#include<iostream>
using namespace std;

const int maxn=100010;
const int INF=0x7fffffff;
int X[maxn],H[maxn];

int main()
{
// freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d %d",X+i,H+i);
int cnt=1,last=1;
X[n]=INF;H[n]=0;
for(int i=1;i<n;++i){
if(last<2){
if(X[i]-H[i]>X[i-1]){
last=0;
++cnt;
}else if(X[i]+H[i]<X[i+1]){
last=2;
++cnt;
}else last=1;
}else{
if(X[i]-H[i]>X[i-1]+H[i-1]){
last=0;
++cnt;
}else if(X[i]+H[i]<X[i+1]){
last=2;
++cnt;
}else last=1;
}
}
printf("%d\n",cnt);
return 0;
}

D

这题放这个位置完全是唬人…
贪心,直接排序后依次选取满足条件的顾客。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=100010;
int save[maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",save+i);
sort(save,save+n);
int cnt=1;
LL cur=save[0];
for(int i=1;i<n;++i){
if(save[i]>=cur){
++cnt;
cur+=save[i];
}
}
printf("%d\n",cnt);
return 0;
}