0%

cf1481

cf1481

A:Space Navigation

足够即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
per(){
int x,y;cin>>x>>y;
int r=0,u=0,d=0,l=0;
cin>>in;
for(auto i:in){
if(i=='R')r++;
else if(i=='L')l++;
else if(i=='D')d++;
else u++;
}
int tag=1;
if(x>0&&r<x) tag=0;
else if(x<0&&l<-x) tag=0;
else if(y>0&&u<y)tag=0;
else if(y<0&&d<-y)tag=0;
if(tag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}

B: New Colony

暴力模拟即可,注意实现。

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
per(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>in[i];
}
int i=1;
int tot=0;
map<int ,int> ma;
while(1){
if(i==n)break;
if(in[i]<in[i+1]){
in[i]+=1;
ma[++tot]=i;
for(int j=max(i-1,1);j>=1;--j){
if(in[j]<in[i]){
ma[++tot]=j;
in[j]++;
}else break;
}
continue;
}else{
i++;
}
}
if(k<=tot){
cout<<ma[k]<<endl;
}else{
cout<<-1<<endl;
}
}

C:Fence Painting

贪心倒序处理即可,
对c,倒序处理,如果这个颜色有需要改的就放对应位置
如果不要改就:
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const int maxn=1e5+10;
int a[maxn];
int b[maxn];
int c[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
//freopen("d:\\desk\\in.txt","r",stdin);
//freopen("d:\\desk\\out.txt","w",stdout);
per(){
int n,m;
cin>>n>>m;
map<int, vector<int> >ma;
map<int,int> mb;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
cin>>b[i];
mb[b[i]]=i;
if(b[i]!=a[i]){
ma[b[i]].push_back(i);
}
}
for(int i=1;i<=m;++i){
cin>>c[i];
}
int tag=1;
int pos=-1;
int f=0;
for(int i=m;i>=1;--i){
if(f==0&&ma[c[i]].size()==0){
if(mb[c[i]]!=0){
int tmp=mb[c[i]];
c[i]=tmp;
f=1;
pos=tmp;
}else {tag=0;break;}
}else if(f==1){
if(ma[c[i]].size()==0){
c[i]=pos;
}else{
int tmp=c[i];
c[i]=ma[tmp][ma[tmp].size()-1];
ma[tmp].pop_back();
}
}else{
int tmp=c[i];
c[i]=ma[tmp][ma[tmp].size()-1];
ma[tmp].pop_back();
pos=c[i];
f=1;
}
}
for(auto i:ma){
if(i.second.size()!=0){
tag=0;break;
}
}
if(tag){
cout<<"YES"<<endl;
for(int i=1;i<=m;++i){
cout<<c[i]<<' ';
}cout<<endl;
}else cout<<"NO"<<endl;
}
}

D:AB Graph

赛后1h才ac。。。一开始脑子很乱。
在草稿纸上模拟得出,只用前3个点即可以。
其中偶数的反复横跳即可。
奇数的注意找来去一样的特殊情况

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
const int maxn=1005;
int woe[maxn][maxn];
char in[maxn];

int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
//freopen("d:\\desk\\in.txt","r",stdin);
//freopen("d:\\desk\\out.txt","w",stdout);
per(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>in+1;
for(int j=1;j<=n;++j){
if(j!=i){
if(in[j]=='a')woe[i][j]=1;
else woe[i][j]=2;
}else woe[i][j]=0;
}
}
if(m%2==1){
cout<<"YES"<<endl;
for(int i=1;i<=m+1;++i){
cout<<(i%2==1? 1:2)<<' ';
}cout<<endl;
}else{
int n1=-1;
int n2=-1;
int tag=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(i!=j&&woe[i][j]==woe[j][i]){
tag=1;
n1=i;n2=j;
}
}
if(tag==1){
cout<<"YES"<<endl;
for(int j=1;j<=m+1;++j){
if(j%2==1)cout<<n1<<' ';
else cout<<n2<<' ';
}cout<<endl;
}else{
if(woe[1][2]==woe[2][3]&&woe[2][3]==woe[3][1]){
cout<<"YES"<<endl;
for(int j=1;j<=m+1;++j){
if(j%3==0)cout<<1<<' ';
else if(j%3==1)cout<<2<<' ';
else cout<<3<<' ';
}cout<<endl;
}else{
if(n<3){
cout<<"NO"<<endl;
continue;
}
int n1,n2,n3;
if(woe[1][2]==woe[2][3]){
n1=1;n2=2;n3=3;
}else if(woe[2][3]==woe[3][1]){
n1=2;n2=3;n3=1;
}else {
n1=3;n2=1;n3=2;
}cout<<"YES"<<endl;
if(m%4==2){
int tmp=m/2;
for(int i=1;i<=tmp+1;++i){
if(i%2==1)cout<<n1<<' ';
else cout<<n2<<' ';
}
for(int i=1;i<=tmp;++i){
if(i%2==1)cout<<n3<<' ';
else cout<<n2<<' ';
}cout<<endl;
}else{
int tmp=m/2;
for(int i=1;i<=tmp+1;++i){
if(i%2==1)cout<<n2<<' ';
else cout<<n3<<' ';
}
for(int i=1;i<=tmp;++i){
if(i%2==1)cout<<n1<<' ';
else cout<<n2<<' ';
}
}
}
}
}
}
}