0%

Dirt030的Codeforces码题记录No.1

发表于 更新于

太长了比较难找，所以每十个放一起吧。

而且这次尝试修改了一些格式，让它看起来舒服一点。但是hexo的markdown解析器对Tab的谜之处理还没能搞定。

Codeforces Round #619 (Div. 2)

A. Three Strings

传送门

题解

因为一定要交换，所以ci必须和ai或者bi相同，这样才能用ci去交换掉不同的那个。

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>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int T;
	cin>>T;
	while(T--){
		string a,b,c;
		cin>>a>>b>>c;
		int len=a.size();
		int flg=1;
		for(int i=0;i<len;i++){
			if(c[i]==a[i]||c[i]==b[i]) continue;
			flg=0;
			break;
		}
		if(flg) cout<<"YES\n"; else cout<<"NO\n";
	}

	//fclose(stdin);
	//fclose(stdout);
}

B. Motarack’s Birthday

传送门

题解

当时读错题了，以为求的是Sigma，然而题目是Max。所以对于Miss的部分，只要取其相邻的数中最大最小的两个的平均就行了，因为其他的Miss部分不影响答案。其次原始数列的m可能比最小化Miss部分的还大，要比较一下。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int a[100005],minn=1000000009,maxx=-2,m=-1;
		cin>>a[0];
		for(int i=1;i<n;i++){
			cin>>a[i];
			if(a[i-1]==-1&&a[i]!=-1){
				minn=min(minn,a[i]);
				maxx=max(maxx,a[i]);
			}
			else if(a[i-1]!=-1&&a[i]==-1){
				minn=min(minn,a[i-1]);
				maxx=max(maxx,a[i-1]);
			}
			else if(a[i-1]!=-1&&a[i]!=-1){
				m=max(m,abs(a[i]-a[i-1]));
			}
		}
		//cout<<minn<<' '<<maxx<<endl;
		if(maxx==-2){
			cout<<"0 0\n";
			continue;
		}
		m=max(m,(maxx-minn)/2+(maxx-minn)%2);
		cout<<m<<' '<<(maxx-minn)/2+(maxx-minn)%2+minn<<'\n';
	} 

	//fclose(stdin);
	//fclose(stdout);
}

C. Ayoub’s function

传送门

题解

先考虑长度为n的串，一共有(n+1)*n/2个子串。其中每有一段长度为x的‘0’串，就会使答案减少(x+1)*x/2。因此，在‘0’的总数不变的情况下，显然每个‘0’串的长度越短越好。所以把‘0’平均分给m+1个空位就行。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int t;
	cin>>t;
	while(t--){
		ll n,m;
		cin>>n>>m;
		ll n0=n-m,n1=m;
		ll ans=n*(n+1)/2;
        //写的时候搞错了n和m的定义，因为懒得改了
        //就干脆将错就错加了两行改了n和m而不是计算部分的代码。
		n=n1;m=n0;
		ll md=m/(n+1),mm=m%(n+1);
		ans-=((md+1)*(md+1+1)/2)*mm;
		if(md!=0) ans-=(md*(md+1)/2)*(n+1-mm);
		cout<<ans<<endl;
	}

	//fclose(stdin);
	//fclose(stdout);
}

D. Time to Run

传送门

题解

显然这个图是符合欧拉回路的，考虑到操作数量要少于3000，所以要构造一个重复操作程度高的操作序列。

我的构造方式是——

  1. 除第n行外，对于奇数行，除第m列外，走“下上右”，第m列走“下”；对于偶数行，除第1列外，走“下上左”，第1列走“下”；

  2. 第n行，如果是奇数行就一直走“右”，偶数行就一直走“左”；

  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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct ansdata{
	string s;
	int f;
}ans[3003];//记录答案
int main() {
	int n,m,k;
	cin>>n>>m>>k;
	int maxk=4*n*m-2*n-2*m;
	if(k>maxk){
		cout<<"NO\n";
		return 0;	
	}
	string m1="DUR",m2="DUL";
	int z=0;
    //除最后一行
	for(int i=1;i<n;i++){
		if(k>=m*3-2){
			if(i%2==1) ans[z].s=m1; else ans[z].s=m2;
			ans[z].f=m-1;
			if(m!=1) z++;//在m==1的情况下，是没有左右的操作的，以下同理
			ans[z].s="D";
			ans[z].f=1;
			z++;
			k-=m*3-2;
		}
		else{
			if(k>=3){
				if(i%2==1) ans[z].s=m1; else ans[z].s=m2;
				ans[z].f=k/3;
				z++;
				k%=3;
			}
			if(k==1){
				ans[z].s="D";
				ans[z].f=1;
				z++;
				k-=1;
			}
			else if(k==2){
				ans[z].s="DU";
				ans[z].f=1;
				z++;
				k-=2;
			}
		}
		if(k==0) break;
	}
	//最后一行
	int tag=n%2;//用来标记奇偶数行
	if(k!=0){
		if(tag==1) ans[z].s="R"; else ans[z].s="L";
		ans[z].f=min(m-1,k);
		if(m!=1) z++;
		k-=min(m-1,k);
		tag=(tag+1)%2;
	}
    //原路返回
    //因为之前判断过k的大小了，所以k最后一定能走完
	while(k!=0){
		if(k>=m){
			if(tag==1) ans[z].s="R"; else ans[z].s="L";
			ans[z].f=m-1;
			if(m!=1) z++;
			ans[z].s="U";
			ans[z].f=1;
			z++;
			k-=m;
		}
		else{
			if(tag==1) ans[z].s="R"; else ans[z].s="L";
			ans[z].f=k;
			z++;
			k=0;
		}
		tag=(tag+1)%2;
	}
	cout<<"YES\n";
	cout<<z<<'\n';
	for(int i=0;i<z;i++){
		cout<<ans[i].f<<' '<<ans[i].s<<"\n";
	}
}