0%

Dirt030的Codeforces码题记录No.0

发表于 更新于

为了监督自己补题，顺便存代码，把码的题扔在Blog上吧。

Educational Codeforces Round 82 (Rated for Div. 2)

A Erasing Zeroes

传送门

题解

把夹在中间的都删了就行。

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>
#define ll long long
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--){
		string st;
		cin>>st;
		int len=st.size();
		int left=-1,right;
		int ans=0;
		for(int i=0;i<len;i++){
			if(st[i]=='1'){
				left=i;
				break;
			}
		}
		if(left==-1) cout<<0<<endl;
		else{
			for(int i=len-1;i>=0;i--){
				if(st[i]=='1'){
					right=i;
					break;
				}
			}
			for(int i=left;i<=right;i++){
				if(st[i]=='0') ans++;
			}
			cout<<ans<<'\n';
		}
		
	}
}

B National Project

传送门

题解

如果g≥b，显然前n天一定满足条件。

否则，每需要g天，就需要一段整个(g+b)天来提供。这里特判一下，如果所需要的好天数是g的倍数，那么不用再等最后的b天了。这里有个问题是，这样算的总天数可能比n小，可以特判，也可以直接和n取max。

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,g,b;
		cin>>n>>g>>b;
		if(g>=b) cout<<n<<endl;
		else{
			long long half=(n+1)/2;
			long long t=half/g;
			t*=g+b;
			if(half<=g) cout<<n<<endl;
			else if(half%g==0) cout<<max(n,t-b)<<endl;
			else cout<<max(n,t+half%g)<<endl;
		}
	}

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

C Perfect Keyboard

传送门

题解

按照相邻关系建图，只要图只包含孤立节点和链就可以成立。之所以只能是链，因为移动方法使得每个字母至多和两个其他字母相邻，而作为一个串不能首尾相连，所以环也不可以。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mmp[30][5];
bool vis[30];
string ans;
//连接节点，以及判断是否有非法情况（连接超过两个点）
bool connect(int x,int y){
	if(mmp[x][0]==2){
		if(y!=mmp[x][1]&&y!=mmp[x][2]) return 0;
	}
	else if(mmp[x][0]==1){
		if(y!=mmp[x][1]){
			mmp[x][0]=2;
			mmp[x][2]=y;
		}
	}
	else{
		mmp[x][0]=1;
		mmp[x][1]=y;
	}
	return 1;
}
//把整条链记录下来
void dfs(int x){
	vis[x]=1;
	ans+='a'+x;
	if(!vis[mmp[x][1]]) dfs(mmp[x][1]);
	else if(mmp[x][0]==2&&!vis[mmp[x][2]]) dfs(mmp[x][2]);
}
int main(){
	int T;
	cin>>T;
	while(T--){
		memset(mmp,0,sizeof(mmp));
		string pd;
		cin>>pd;
		int len=pd.size();
		bool flg=0;
		for(int i=1;i<len;i++){
			if(!connect(pd[i-1]-'a',pd[i]-'a')||!connect(pd[i]-'a',pd[i-1]-'a')){
				cout<<"NO\n";
				flg=1;
				break;
			}
		}
		if(flg) continue;
		memset(vis,0,sizeof(vis));
		ans="";
		for(int i=0;i<26;i++){
			if(!vis[i]){
                //孤立节点
				if(mmp[i][0]==0){
					ans+='a'+i;
					vis[i]=1;
				}
                //链的端点显然度数为1
				else if(mmp[i][0]==1){
					dfs(i);
				}
			}
		}
        //如果ans不为26，则说明图中存在环
		if(ans.size()==26) cout<<"YES\n"<<ans<<'\n'; else cout<<"NO\n";
	}
}

D Fill The Bag

传送门

题解

在记录二进制下每一位有几个数，然后从低位到高位减一遍，答案是类似“往上借一位”这个操作的次数。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int bits[100];
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int t;
	cin>>t;
	while(t--){
		ll n;
		int m;
		cin>>n>>m;
		memset(bits,0,sizeof(bits));
		int a;
		ll tota=0;
		for(int i=0;i<m;i++){
			cin>>a;
			tota+=a;
			bits[int(log2(a))]++;
		}
		if(tota<n){
			cout<<"-1\n";
			continue;
		}
		int pos=0;
		int op=0;
		while(n!=0){
			if(n%2){
                //借一位下来以后，中间所有位都+1了，可以联想一下竖式计算减法
				if(!bits[pos]){
					int tpos=pos;
					while(!bits[tpos]){
						bits[tpos]=1;
						tpos++;
					}
					bits[tpos]--;
                    //每一位都需要division才能借下来，所以op的增量为中间位数
					op+=tpos-pos;
				}
				bits[pos]--;
			}
			n>>=1; 
            //没用完的要进位，因为只有division操作有代价，有限用进位上来的答案更优
			bits[pos+1]+=bits[pos]/2;
			pos++;
		}
		cout<<op<<'\n';
	}

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

Codeforces Round #617 (Div. 3)

A Array with Odd Sum

传送门

题解

偶数是没有用的，所以只要看奇数能不能有奇数个就行。

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
#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_odd=0,a_even=0;
		for(int i=0;i<n;i++){
			int tmp;
			cin>>tmp;
			if(tmp%2) a_odd++; else a_even++;
		}
		if(a_odd==0){
			cout<<"NO\n";
		}
		else if(a_even==0){
			if(a_odd%2){
				 cout<<"YES\n";
			}
			else{
				cout<<"NO\n";
			}
		}
		else cout<<"YES\n";
	} 

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

B Food Buying

传送门

题解

十个十个买就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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 s;
		cin>>s;
		int ans=0;
		while(s>=10){
			ans+=s-s%10;
			s=s/10+s%10;
		}
		cout<<ans+s<<'\n';
	}

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

C Yet Another Walking Robot

传送门

题解

用map记录上一次某位置出现的时间，因为要求最小的一段，所以只需要保存上一次的时间而非所有历史时间，然后每次有重复就更新时间和答案就行。

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
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mmp;
map<pair<int,int>,int>::iterator iter;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		string op;
		cin>>op;
        
		//初始位置（0，0）也是合法答案，要加入。
		mmp.clear();
		mmp.insert(map<pair<int,int>,int>::value_type(make_pair(0,0),0));
		int x=0,y=0;
		int ll=0,rr=n*2;//记录最短的区间位置，初始化成差值一个远比n大的就行。
		
		for(int i=1;i<=n;i++){
			char ch=op[i-1];
			if(ch=='L'){
				x--;
			}
			else if(ch=='R'){
				x++;
			}
			else if(ch=='U'){
				y++;
			}
			else{
				y--;
			}
			
			iter=mmp.find(make_pair(x,y));
            //如果没出现过当前位置就直接加入，否则更新答案并更改当前位置最后出现的时间。
			if(iter!=mmp.end()){
				if(i-iter->second<=rr-ll+1){
					ll=iter->second+1;
					rr=i;
				}
				iter->second=i;
			}else{
				mmp.insert(map<pair<int,int>,int>::value_type(make_pair(x,y),i));
			}
		}
		if(ll) cout<<ll<<' '<<rr<<'\n'; else cout<<"-1\n";
	}

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

D Fight with Monsters

传送门

题解

预处理出每个怪物需要用几次黑科技才能让我得分，然后从小到大贪心取就行。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int n,a,b,k;
	cin>>n>>a>>b>>k;
	int h[200005];
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		tmp%=a+b;
        //注意余数为0的话要补一个a+b回去。
		if(!tmp) tmp=a+b;
		h[i]=(tmp+(a-1))/a-1;
	}
	sort(h,h+n);
	//for(int i=0;i<n;i++) cout<<h[i]<<' ';cout<<endl;
	int ans=0,i=0;
	while(i<n&&k>=0){
		k-=h[i];
		if(k>=0) ans++;
		i++;
	}
	cout<<ans<<endl;

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

E1 String Coloring (easy version)

传送门

题解

从左到右处理，保证每一位及其之前全部有序再进行下一位的交换处理，那么每个数字只需要和它前面比它大的交换（因为小于等于它的已经到了它该到的位置了）。问题就变成了求解单调不下降子序列数量，如果序列小于等于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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int n;
	cin>>n;
	string st;
	cin>>st;
	int s0=0,s1=0;
	int c[233];
	bool flg=1;
	for(int i=0;i<n;i++){
		if(st[i]-'a'+1>=s0){
			c[i]=0;
			s0=st[i]-'a'+1;
		}
		else if(st[i]-'a'+1>=s1){
			c[i]=1;
			s1=st[i]-'a'+1;
		}
		else{
			flg=0;
			cout<<"NO\n";
			break;
		}
	}
	if(flg){
		cout<<"YES\n";
		for(int i=0;i<n;i++) cout<<c[i];
	}

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

E2 String Coloring (hard version)

传送门

题解

和前面一样，不过这次改成多个序列了。其实可以加优化，但是数据范围小,至多就26个序列，所以用穷举检测就过得去了。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int n;
	cin>>n;
	string st;
	cin>>st;
	int c[200005];
	int seq[30];
	memset(seq,0,sizeof(seq));
	for(int i=0;i<n;i++){
		for(int j=1;j<30;j++){
			if(seq[j]<=st[i]-'a'+1){
				c[i]=j;
				seq[j]=st[i]-'a'+1;
				break;
			}
		}
	}
	int res=1;
	while(seq[res]!=0){
		res++;
	}
	cout<<res-1<<'\n';
	for(int i=0;i<n;i++){
		cout<<c[i]<<' ';
	}

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

Codeforces Round #616 (Div. 2)

A Even But Not Even

传送门

题解

根据奇偶性，显然当且仅当存在至少两个奇数位的时候有解。

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>
#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 len;
		cin>>len;
		string st;
		cin>>st;
		char ch=' ';
		bool flg=1;
		for(int i=0;i<len;i++){
			if((st[i]-'0')%2){
				if(ch!=' '){
					cout<<ch<<st[i]<<'\n';
					flg=0;
					break;
				}
				else{
					ch=st[i];
				}
			}
		}
		if(flg) cout<<"-1\n";
	}

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

B Array Sharpening

传送门

题解

因为可以无限次使用-1-1-1-1-1（太暴力了），所以可以直接减到最小，即第零位减到0，第一位减到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
27
28
29
30
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[300005];
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		int linc=0;
		bool flg=1;
		for(int i=0;i<n;i++){
			cin>>a[i];
			if(flg&&a[i]>=i) linc++; else flg=0;
		}
		int ldec=0;
		flg=1;
		for(int i=n-1;i>=0;i--){
			if(flg&&a[i]>=n-1-i) ldec++; else flg=0;
		}
		if(linc+ldec>n) cout<<"Yes\n"; else cout<<"No\n";
	}

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

C Mind Control

传送门

题解

首先如果可控制的人数k超过m-1，那肯定后面的是没意义的。其次先手控制和后手控制造成的局面是一样的，所以不妨就控制前k个人。那么对应的，有m-1-k个人无法控制。以及在最后的时候，我自己可以选择两端中较大的，这个也可以控制。

所以，我们枚举可控制的人在前端和后端分布的情况，再枚举不可控制的人的分布，取最劣解，最后取其中的最优解就可以了。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[5003];
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	 
	int t;
	cin>>t;
	while(t--){
		int n,m,k;
		cin>>n>>m>>k;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		k=min(m-1,k);
		int ans=-1;
		for(int i=0;i<=k;i++){
			int tmp=1e9+9;
			for(int j=0;j<=m-1-k;j++){
				tmp=min(tmp,max(a[i+j],a[n-(m-i-j)]));
			}
			ans=max(ans,tmp);
		}
		cout<<ans<<'\n';
	}

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

D Irreducible Anagrams

传送门

题解

对于字串来说，其存在符合题意的对应串的情况为——

  1. 只存在一个字母且长度为1；
  2. 只存在两个字母且首尾字母不同；
  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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string st;
vector<vector<int> > sig;//前缀和
bool check(int l,int r){
	int diff=0;
	for(int i=0;i<26;i++){
		diff+=sig[l-1][i]!=sig[r][i];//统计不同的字母数量
	}
	if(diff==1) return l==r;
	else if(diff==2) return st[l-1]!=st[r-1];
	else return 1;
}
int main(){	
	sig.clear();
	vector<int> sig0(26,0);
	sig.push_back(sig0);
	
	cin>>st;
	int len=st.size();		
	for(int i=0;i<len;i++){
		sig.push_back(sig[i]);
		sig[i+1][st[i]-'a']++;
	}
	
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		if(check(l,r)) cout<<"YES\n"; else cout<<"NO\n";
	}
}

Educational Codeforces Round 81 (Rated for Div. 2)

A Display The Number

传送门

题解

一个整数显然位数越多，本身就越大，换言之，要优先拼出来“1”来获得位数。如果线段是奇数的话，我们把第一位变成“7”就行了。

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>
#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;
		if(n%2){
			cout<<7;
			n-=3;
		}
		n/=2;
		for(int i=0;i<n;i++) cout<<1;
		cout<<'\n';
	}

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

B Infinite Prefixes

传送门

题解

对于每一位来说，要么单调增长或下降，要么保持不变，其取决于整个循环节的blance。因此统计一下循环节的blance然后简单if判断就行。

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<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,x;
		cin>>n>>x;
		string s;
		cin>>s;
		int len=s.size();
		int tot_cnt=0;
		for(int i=0;i<len;i++){
			if(s[i]=='0') tot_cnt++; else tot_cnt--;
		}
		int now_cnt=0;
		int ans=0;
		if(x==0) ans++;
		for(int i=0;i<len;i++){
			if(s[i]=='0') now_cnt++; else now_cnt--;
			if(now_cnt==x&&tot_cnt==0){
				ans=-1;
				break;
			}
			if(now_cnt==x) ans++;
			if(now_cnt<x&&tot_cnt>0&&(x-now_cnt)%tot_cnt==0) ans++;
			if(now_cnt>x&&tot_cnt<0&&(now_cnt-x)%(0-tot_cnt)==0) ans++;
		}
		cout<<ans<<'\n';
	}

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

C Obtain The String

传送门

题解

记录下来每一位后面第一次出现的各个字母的位置，然后照着t跑一边就行。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int sloc[100005][30];
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int T;
	cin>>T;
	while(T--){
		string s,t;
		cin>>s>>t;
		int ls=s.size(),lt=t.size();
		for(int i=0;i<ls;i++){
			for(int j=0;j<26;j++){
				sloc[i][j]=-1;
			}
		}
		for(int i=ls-2;i>=0;i--){
			for(int j=0;j<26;j++){
                //如果后一位是第j个字母那么就更新
                //不然当前位后面第一次出现第j个字母和它后面一位一样
				if(s[i+1]-'a'==j){
					sloc[i][j]=i+1;
				}
				else{
					sloc[i][j]=sloc[i+1][j];
				}
			}
		}
        //这里由于状态设计的问题，在重新开始新的一轮s时，
        //要分别询问当前位是不是目标字母和当前位后面有没有目标字母
		int ans=1,p;
		if(s[0]==t[0]){
			p=0;
		}
		else if(sloc[0][t[0]-'a']!=-1){
			p=sloc[0][t[0]-'a'];
		}
		else{
			cout<<-1<<'\n';
			continue;
		}
		for(int i=1;i<lt;i++){
			p=sloc[p][t[i]-'a'];
			if(p==-1){
				if(s[0]==t[i]){
					p=0;
					ans++;
				}
				else if(sloc[0][t[i]-'a']!=-1){
					p=sloc[0][t[i]-'a'];
					ans++;
				}
				else{
					ans=-1;
					break;
				}
			}
		}
		cout<<ans<<'\n';
	}

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

D Same GCDs

传送门

题解

因为gcd(a, m) = gcd(a + x, m) = gcd((a+x) % m, m),

而(a+x) % m $\in$ [0, m - 1],

所以即求[0, m / gcd(a, m) )中有多少与m / gcd(a, m) 互质的数，即phi(m / gcd(a, m))

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
	if (!b) return a;
	gcd(b,a%b);
}
ll phi(ll n){
    ll m=(ll)sqrt(n+0.5);
    ll ans=n;
    for(ll i=2;i<=m;i++){
    	if(n%i==0){
    		ans=ans/i*(i-1);
    		while(n%i==0) n/=i;
    	}
    } 
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	
	int T;
	cin>>T;
	while(T--){
		ll a,m;
		cin>>a>>m;
		cout<<phi(m/gcd(a,m))<<'\n';
	}

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

Codeforces Round #615 (Div. 3)

A Collecting Coins

传送门

题解

加起来除以三比较一下。

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--){
		int a,b,c,n;
		cin>>a>>b>>c>>n;
		int m=(a+b+c+n)/3;
		//cout<<m;
		if(m*3!=n+a+b+c||m<a||m<b||m<c){
			cout<<"NO\n";
		}
		else{
			cout<<"YES\n";
		}
	}

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

B Collecting Packages

传送门

题解

优先向右，判一下能不能走就行。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct P{
	int x,y;
}p[1003];
bool cmp_p(P a,P b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>p[i].x>>p[i].y;
		}
		p[n].x=0;p[n].y=0;
		sort(p,p+n+1,cmp_p);
		bool flg=0;
		for(int i=0;i<n;i++){
			if(p[i].x>p[i+1].x){
				flg=1;
				break;
			}
		}
		if(flg) cout<<"NO\n";
		else{
			cout<<"YES\n";
			for(int i=0;i<n;i++){
				for(int j=p[i].x;j<p[i+1].x;j++){
					cout<<"R";
				}
				for(int j=p[i].y;j<p[i+1].y;j++){
					cout<<"U";
				}
			}
			cout<<"\n";
		}
	}

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

C Product of Three Numbers

传送门

题解

随便找个筛法暴力一遍。

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=100005;
int prime[MAXN],prime_tot=0;
bool check[MAXN];
void prime_get()
{
	memset(check,0,sizeof(check));
	check[0]=check[1]=1;
	int i,j;
	for(i=2;i<=MAXN;i++)
	{
		if (check[i]==0) prime[prime_tot++]=i;
		for(j=0;j<prime_tot&&i*prime[j]<=MAXN;j++)
		{
			check[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
}
int main()
{
	prime_get();
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		int a=0,b=0;
		for(int i=0;i<prime_tot;i++){
			if(n%prime[i]==0){
				a=prime[i];
				n/=a;
				break;
			}
		}
		if(a==0){
			cout<<"NO\n";
			continue;
		}
		for(int i=0;i<prime_tot;i++){
			if(n%prime[i]==0&&){
				b=prime[i];
				n/=b;
				break;
			}
		}
		if(b==0||n==1){
			cout<<"NO\n";
			continue;
		}
		cout<<a<<' '<<b<<' '<<n<<endl;
	}

    return 0;
}

D MEX maximizing

传送门

题解

因为可以任意 +x 或 -x ，因此有且只有在模 x 下同余的数字可以相互转化，问题就变成了以模 x 划分的集合的元素数量的维护。看一下最小值就行。这里有个注意点，最小值如果存在多个，只有第一个有用，因为在此之前的集合元素数量都至少比最小值大 1 才能保证能轮到它。

然后全部读进来反过来处理可以保证最小值的单调性，每次是维护是O(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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define ll long long
#define MAXN 400005
using namespace std;
int mx[MAXN],y[MAXN],ans[MAXN];
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int q,x;
	cin>>q>>x;
	memset(mx,0,sizeof(mx));
	for(int i=0;i<q;i++){
		cin>>y[i];
		mx[y[i]%x]++;
	}
	int minn_num=MAXN;
	int minn_pos=MAXN;
	for(int i=0;i<x;i++){
		if(mx[i]<minn_num){
			minn_num=mx[i];
			minn_pos=i;
		}
	}
	/*for(int i=0;i<x;i++){
		cout<<mx[i]<<' ';
	}
	cout<<endl;
	cout<<minn_num<<' '<<minn_pos<<endl;*/
	for(int i=q-1;i>=0;i--){
		ans[i]=minn_num*x+minn_pos;
		mx[y[i]%x]--;
		if((mx[y[i]%x]<minn_num)||(mx[y[i]%x]==minn_num&&(y[i]%x)<minn_pos)){
			minn_num=mx[y[i]%x];
			minn_pos=y[i]%x;
		}
	}
	for(int i=0;i<q;i++) cout<<ans[i]<<endl;


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

E Obtain a Permutation

传送门

题解

每一列是独立的所以分开来处理，对于每一列，对每一行的元素判断是否可以移动到正确的位置，如果可以就记载需要移动几次，最后对所有不同的移动次数去一个min。

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
#include<bits/stdc++.h>
#define ll long long
#define MAXN 200005
using namespace std;
int move030[200005];
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int n,m;
	cin>>n>>m;
	vector<vector<int> > a(n+5,vector<int>(m+5));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	ll ans=0;
	for(int j=0;j<m;j++){
		for(int i=0;i<n;i++) move030[i]=0;//用memset在第五个点T了，，裂开来
		for(int i=0;i<n;i++){
            //据说在第85个点有超过n*m的数据，因此这里加了对值域的判断
			if(j+1<=a[i][j]&&a[i][j]<=n*m-m+j+1&&(a[i][j]-(j+1))%m==0){
				int tar=(a[i][j]-(j+1))/m,ori=i;
				if(tar<=ori) move030[ori-tar]++;
				else move030[n-(tar-ori)]++;
			}
		}
		/*cout<<j+1<<' ';
		for(int i=0;i<n;i++) cout<<move030[i]<<' ';
		cout<<endl;*/
		int min_move=MAXN;
		for(int i=0;i<n;i++){
			min_move=min(min_move,n-move030[i]+i);
		}
		ans=ans+(ll)min_move;
	}
	cout<<ans<<"\n";

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

F Three Paths on a Tree

传送门

题解

想了很久怎么写比较优美，最后还是觉得写三个dfs方便。

题目很简单，就是找一下最长链然后在上面找一个最长支链。然后为了写的好看，再找出最长链的一端之后，在找另外一个端点的同时记录下来各点到此端点的距离。接着从另外一个端点反向搜索的时候，只要拿每个点到两端的距离和减去最长链的长度再除以二就是这个点到达最长链的支链长度了。

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
#include<bits/stdc++.h>
#define ll long long
#define MAXN 200005
using namespace std;
int head[MAXN];
vector<pair<int,int> > edge;
bool vis[MAXN];
int maxv,maxd;
int a,b,ld;//ld是最长链长度
int d2a[MAXN];//每个点到最长链端点a的距离
void dfs(int x,int d){
    //找最长链的一个端点
	vis[x]=1;
	if(d>maxd){
		maxd=d;
		maxv=x;
	}
	for(int i=head[x];i<head[x+1];i++){
		if(!vis[edge[i].second]){
			dfs(edge[i].second,d+1);
		}
	}
	return;
}
void dfs2(int x,int d){
    //找另外一个端点顺便记录各点距离
	vis[x]=1;
	d2a[x]=d;
	if(d>maxd){
		maxd=d;
		maxv=x;
	}
	for(int i=head[x];i<head[x+1];i++){
		if(!vis[edge[i].second]){
			dfs2(edge[i].second,d+1);
		}
	}
	return;
}
void dfs3(int x,int d){
    //计算支链长
	vis[x]=1;
	if(x!=a&&x!=b&&(d2a[x]+d-ld)/2>maxd){
		maxd=(d2a[x]+d-ld)/2;
		maxv=x;
	}
	for(int i=head[x];i<head[x+1];i++){
		if(!vis[edge[i].second]){
			dfs3(edge[i].second,d+1);
		}
	}
	return;
}
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int ta,tb;
		cin>>ta>>tb;
		edge.push_back(make_pair(ta,tb));
		edge.push_back(make_pair(tb,ta));
	}
	sort(edge.begin(),edge.end());
	head[edge[0].first]=0;
	for(int i=1;i<edge.size();i++){
		if(edge[i].first!=edge[i-1].first){
			head[edge[i].first]=i;
		}
	}
	head[n+1]=edge.size();

	memset(vis,0,sizeof(vis));
	maxd=-1;
	dfs(1,0);
	a=maxv;

	memset(vis,0,sizeof(vis));
	memset(d2a,0,sizeof(d2a));
	maxd=-1;
	dfs2(a,0);
	b=maxv;
	ld=maxd;

    //在这一个dfs中，maxd表示最长支链长，maxv表示对应的点
	memset(vis,0,sizeof(vis));
	maxd=-1;
	dfs3(b,0);

	cout<<maxd+ld<<'\n'<<a<<' '<<b<<' '<<maxv<<'\n';

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

Codeforces Round #614 (Div. 2)

A ConneR and the A.R.C. Markland-N

传送门

题解

读进来sort一下，然后lower_bound找到s层，贪心向两个方向找最近的可访问楼层。

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>
#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,s,k;
		cin>>n>>s>>k;
		int a[2333];
		for(int i=0;i<k;i++){
			cin>>a[i];
		}
		sort(a,a+k);
		//for(int i=0;i<k;i++)cout<<a[i]<<' ';cout<<endl;
		int ix=lower_bound(a,a+k,s)-a;
		//cout<<ix<<endl;
		//cout<<a[ix]<<' '<<s<<endl;
        //这里的边界条件一开始没加 ix==x 导致后面的p总是访问越界，WA得🐎都不认识。
		if(ix==k||a[ix]!=s) cout<<0<<endl;
		else{
			int ans=1000000009;
			int p=ix;
			while(p!=k-1&&a[p+1]==a[p]+1){
				p++;
			}
			//cout<<a[p-1]<<endl;
			if(p!=k-1&&a[p+1]!=a[p]+1) ans=min(ans,a[p]+1-s);
			else if(p==k-1&&a[p]!=n) ans=min(ans,a[p]+1-s);
			//cout<<ans<<endl;
			p=ix;
			while(p!=0&&a[p-1]==a[p]-1){
				p--;
			}
			if(p!=0&&a[p-1]!=a[p]-1) ans=min(ans,s-a[p]+1);
			else if(p==0&&a[p]!=1) ans=min(ans,s-a[p]+1);
			cout<<ans<<endl;
		}
	}

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

B JOE is on TV!

传送门

题解

大胆猜想每次去掉一个，应该可以把一部分加起来证明单步是最优的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	double n;
	cin>>n;
	double ans=0;
	while(n!=0){
		ans+=1/(n--);
	}
	cout<<ans<<endl;

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

C NEKO’s Maze Game

传送门

题解

阻塞的方式只有岩浆块的正上（下）方、左斜上（下）方、右斜上（下）方也存在岩浆块。因此通过对可构成阻塞的岩浆块对数进行计数来判断全局是否被阻塞。

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<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int n,q;
	cin>>n>>q;
	int mp[2][100005];
    //0为可通行块，1为岩浆块
	memset(mp,0,sizeof(mp));
	int b=0;
	while(q--){
		int r,c;
		cin>>r>>c;
        //这里忘了我地图不是从0开始WA得🐎都不认识
		r--;
		c--;
		int flg;//用来压代码，控制到底是增加还是减少已有得阻塞块对数
		if(mp[r][c]){
			flg=-1;
			mp[r][c]=0;
		}else
		{
			flg=1;
			mp[r][c]=1;
		}
        //压了一些代码，但因为心态快崩了所以不太好看
		if(c!=0) b+=mp[(r+1)%2][c-1]*flg;
		b+=mp[(r+1)%2][c]*flg;
		if(c!=n-1) b+=mp[(r+1)%2][c+1]*flg;
		if(b==0) cout<<"YES\n"; else cout<<"NO\n";
	}

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

传送门

题解

由于保证了ax和ay是大于或等于2的，因此实际上可能会访问到的node只有log2(1016)个，数量并不多，因此可以随便暴力枚举，本来还打算尺取法的。当然显而易见取的node是连续的。这道题最坑的实际上是数据范围，中间有个地方会爆掉long long，导致我被第126个点卡了好几次。

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
#include<bits/stdc++.h>
//嫌麻烦直接全部换成ull了，代价是abs函数里面要强转型一下，我用的编译器abs没有对ull的重载
#define ll unsigned long long
#define MAXN 2e17
using namespace std;
ll c_dis(ll a,ll b,ll c,ll d){
	return abs((long long)a-(long long)c)+abs((long long)b-(long long)d);
}
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	ll a[3][233];
	ll x0,y0,ax,ay,bx,by;
	cin>>a[0][0]>>a[1][0]>>ax>>ay>>bx>>by;
	a[2][0]=0;
	ll xs,ys,t;
	cin>>xs>>ys>>t;
	int p=0;
	while(a[0][p]*ax+bx<MAXN&&a[1][p]*ay+by<MAXN){
		a[0][p+1]=a[0][p]*ax+bx;
		a[1][p+1]=a[1][p]*ay+by;
        //前缀和优化一下，没试过连前缀和都没有的暴力时间上够不够
		a[2][p+1]=c_dis(a[0][p],a[1][p],a[0][p+1],a[1][p+1])+a[2][p];
		p++;
	}
	int ans=0;
    //枚举两端
	for(int i=0;i<=p;i++){
		for(int j=0;j<=p;j++){
			unsigned long long tmp=c_dis(xs,ys,a[0][i],a[1][i])+a[2][j]-a[2][i];
			if(tmp<=t) ans=max(ans,j-i+1);
			tmp=c_dis(xs,ys,a[0][j],a[1][j])+a[2][j]-a[2][i];
			if(tmp<=t) ans=max(ans,j-i+1);
		}
	}
	cout<<ans<<endl;

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

Educational Codeforces Round 80 (Rated for Div. 2)

A Deadline

传送门

题解

将总时间的函数对x求导，然后令其等于零，得到总时间最少是2$\sqrt{d} $-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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int T;
	cin>>T;
	while(T--){
		double n,d;
		cin>>n>>d;
		//cout<<2*sqrt(d)-1<<endl;
		if(2*sqrt(d)-1<=n)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

B Yet Another Meme Problem

传送门

题解

可以解出来b的取值只能是9、99、999…而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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int T;
	cin>>T;
	while(T--){
		ll A,B;
		cin>>A>>B;
		ll numb=0;
		ll tmpb=9;
		while(tmpb<=B){
			numb++;
			tmpb=tmpb*10+9;
		}
		cout<<numb*A<<endl;
	}

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

C Two Arrays

传送门

题解

用C[i][j]表示共i位，使用了1~j个数的方案数，使用记忆化搜索减少时间复杂度。显然这两个数列的整体大小关系与最后一位数字的大小关系是相同的，因此只需要枚举最后一位就可以了。

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
#include<bits/stdc++.h>
#define ll long long
#define MAXN 1000000007
using namespace std;
ll C[23][2333];
ll calc(int m,int n){
	if(C[m][n]!=0) return C[m][n];
	if(m==1) return C[m][n]=n;
	if(n==1) return C[m][n]=1;
	ll tmp=0;
	for(int i=1;i<=n;i++){
		tmp=(tmp+calc(m-1,i))%MAXN;
	}
	//cout<<m<<' '<<n<<' '<<tmp<<endl;
	return C[m][n]=tmp;
}
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int n,m;
	cin>>n>>m;
	memset(C,0,sizeof(C));
	ll ans=0;
	for(int i=1;i<=n;i++){
        //这里没有用容斥，而是直接用减法的形式来强制a数列最后一位选取i
		ans=(ans+(calc(m,i)-calc(m,i-1))*calc(m,n-i+1)%MAXN+MAXN)%MAXN;
	}
	cout<<ans<<endl;

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

D Minimax Problem

传送门

题解

看似二分的check需要进行n2m次比对，但是实际上，数列每一位只有大于或等于和小于mid两种状态，因此合计只有2m-1个数列的状态。换言之，将原数列处理之后，check实际上只有（2m-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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int a[300005][10];
int g[555];
int ans1,ans2;
bool check(int x){
	//cout<<"---->"<<x<<endl;
	memset(g,0,sizeof(g));
	for(int i=1;i<=n;i++){
		int tmp=0;
		for(int j=0;j<m;j++){
			//cout<<a[i][j]<<' '<<x<<endl;
			if(a[i][j]>=x) tmp|=(1<<j);
		}
		//cout<<tmp<<endl;
		if(!g[tmp]) g[tmp]=i;
	}
	//cout<<(1<<m)-1<<endl;
	for(int i=0;i<(1<<m);i++){
		for(int j=0;j<(1<<m);j++){
			if(g[i]&&g[j]&&((i|j)==((1<<m)-1))){
				//cout<<g[i]<<' '<<g[j]<<' '<<((i|j)==((1<<m)-1))<<endl;
                //在这个地方WA得🐎都不认识，本来从0开始存数列的，但是忘了答案加一
				ans1=g[i];
				ans2=g[j];
				//cout<<"----"<<x<<endl;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	int l=0,r=1e9+9;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
		//if(check(l)&&!check(l+1)) break;
	}
    //答案在check的时候就存下来了
	cout<<ans1<<' '<<ans2<<endl;

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

Codeforces Round #601 (Div. 2)

A Changing Volume

传送门

题解

首先大于等于五格音量的肯定优先按+/-5

然后人工处理一下，四格音量要两次+/-2；三格音量一次+/-1，一次+/-2；两格和一格都是一次

因为忘了case的语法，所以使用了嵌套if

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int T;
	cin>>T;
	while(T--){
		int a,b;
		cin>>a>>b;
		int ans=0;
		int d=abs(a-b)/5,m=abs(a-b)%5;
		if(m==0) ans=d;
		else if(m==1) ans=d+1;
		else if(m==2) ans=d+1;
		else if(m==3) ans=d+2;
		else if(m==4) ans=d+2;
		cout<<ans<<endl;
	}

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

B Fridge Lockers

传送门

题解

这道题当时好像出锅了，赛后开VP里面多了m≤n的限制。显然一个冰箱至少要和两个其他冰箱相连才能保证不会被别人打开，结合m≤n的限制，冰箱只能成环。特判一下n==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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		int ans=0,tmp;
		for(int i=0;i<n;i++){
			cin>>tmp;
			ans+=tmp;
		}
		ans*=2;
		if(n==2||m<n) cout<<-1<<endl;
		else
		{
			cout<<ans<<endl;
			for(int i=1;i<n;i++)
				cout<<i<<' '<<i+1<<endl;
			cout<<n<<' '<<1<<endl;
		}
	}

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

C League of Leesins

传送门

题解

纯模拟，因为开头只出现过一次，所以找出来然后一个一个推过去就行。

懒得想变量名所以代码写的很丑陋。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
//tga记录每个三元组的三个数字，agt记录每个数字被包含于哪几个三元组
struct tgadata{
	int num,q[3];
}tga[100005],agt[100005];
//枚举寻找同时包含b和c的三元组，然后如果其不含有a，那它就是下一个三元组
int findnxt(int a,int b, int c){
	for(int i=0;i<agt[b].num;i++){
		for(int j=0;j<agt[c].num;j++){
			if(agt[b].q[i]==agt[c].q[j]){
				for(int k=0;k<3;k++){
					if(tga[agt[b].q[i]].q[k]!=b&&tga[agt[b].q[i]].q[k]!=c){
						if(tga[agt[b].q[i]].q[k]!=a) return tga[agt[b].q[i]].q[k];
						break;
					}
				}
			}
		}
	}
	return 0;
}
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int n;
	cin>>n;
	for(int i=0;i<n-2;i++){
		for(int j=0;j<3;j++){
			cin>>tga[i].q[j];
			agt[tga[i].q[j]].q[agt[tga[i].q[j]].num++]=i;
		}
		tga[i].num=i;
	}
    //这里因为懒得压代码所以直接分开来写的，实际上如果考虑到n>=5的限制，第二和第三个数有更简单的办法找出来
    //我这里针对了不存在的n==3和n==4进行了处理
	int p1;
	for(int i=0;i<n-2;i++){
		if(agt[i].num==1){
			p1=i;
			break;
		}
	}
	int p2;
	for(int i=0;i<3;i++)
	{
		if(tga[agt[p1].q[0]].q[i]!=p1&&agt[tga[agt[p1].q[0]].q[i]].num<=2){
			p2=tga[agt[p1].q[0]].q[i];
			break;
		}
	}
	int p3;
	for(int i=0;i<3;i++)
	{
		if(tga[agt[p1].q[0]].q[i]!=p1&&tga[agt[p1].q[0]].q[i]!=p2){
			p3=tga[agt[p1].q[0]].q[i];
			break;
		}
	}
	cout<<p1;
	for(int i=0;i<n-3;i++){
		int tmp=findnxt(p1,p2,p3);
		p1=p2;
		p2=p3;
		p3=tmp;
		cout<<' '<<p1;
	}
	cout<<' '<<p2<<' '<<p3<<endl;

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

Hello 2020

A New Year and Naming

传送门

题解

类似中国的天干地支纪年法，将y分别对n和m取模然后对应到名字即可。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int n,m;
	cin>>n>>m;
	string a[23],b[23];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<m;i++){
		cin>>b[i];
	}
	int q;
	cin>>q;
	int y;
	while(q--){
		cin>>y;
		string ans=a[(y-1)%n]+b[(y-1)%m]+"\n";
		cout<<ans;
	}

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

B New Year and Ascent Sequence

传送门

题解

将序列分为两类，一种是本身存在上升数对的，记有a个；一种是本身不存在上升数对的，记有b个。

对于前一种和前一种排列，任意排列均可，因此有a*a个可行解；对于前一种和后一种排列，任意排列均可，因此有a*b个可行解；对于后一种和后一种排列，需要满足前一个序列的最小值小于或等于后一个的最大值，这个需要枚举计算。

对于计算第三类排列，考虑到我们并不关心到底是谁和谁排列，只关心能排列出多少种，因此可以只保留每个序列的最大和最小值这一信息。接下来，先将最大和最小值数列分别升序排列，注意到可以利用数列的单调性降低枚举复杂度（暴力为O(n^2^)）。对于某个特定的最小值，我们找到了一个刚好大于它的最大值，那么比这个值更大的均可以成为可行解；而比当前选取的最小值更大的最小值，能与其形成可行解的最大值必然在之前选取的最大值之后。通过单调性，我们只需要将序列枚举一遍，复杂度降为O(n)。

比赛时由于没考虑到第一类可行解，导致在debug的时候缝缝补补，代码很丑陋，变量名也在乱来。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int smin[100005],smax[100005];
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	ll n;
	cin>>n;
    //nn为第一种序列，nnn为第二种序列
	ll nn=0,nnn=0;
	for(int j=0;j<n;j++){
		int l;
		cin>>l;
		bool flg=1;
		int minn=1000006,maxx=-1;
		for(int i=0;i<l;i++){
			int tmp;
			cin>>tmp;
            //判断是否自身存在上升数对
			if(flg&&tmp>minn){
				nnn++;
				flg=0;
			}
			minn=min(tmp,minn);
			maxx=max(tmp,maxx);
		}
		if(flg){
			smin[nn]=minn;
			smax[nn]=maxx;
			nn++;
		}
	};
	//cout<<nn<<' '<<nnn<<endl;
	sort(smin,smin+nn);
	sort(smax,smax+nn);
	//for(int i=0;i<nn;i++) cout<<smax[i]<<' ';cout<<endl;
	//for(int i=0;i<nn;i++) cout<<smin[i]<<' ';cout<<endl;

	ll ans=0;
    //计算第三类排列
	ll p1=0,p2=0;
	while(p1!=nn){
		while(p1!=nn&&p2!=nn&&smin[p1]>=smax[p2]){
			p2++;
		}
		ans+=nn-p2;
		p1++;
	}
    //计算前两类排列
	ans+=nnn*nn*2+nnn*nnn;

	cout<<ans<<"\n";

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

C New Year and Permutation

传送门

题解

首先不能把思路放在对于特定的数列怎么求其满足题意的子序列数量，而是直接思考如何构造满足题意的子序列。

因为r-l正好是max-min，而每个数又是不一样的，所以显然l到r这个区间里的数也必须正好是连续的。

我们考虑这段连续的数字的个数是i，那么这段数字有n-i+1种取法，其排列方式有 i! 种，而对于剩下的n-i个数字，其排列在选出的这段数字区间两端，首先，其排列有 (n-i)! 种，然后用插板法将其分为两份放在选定数字区间的两侧，因此还要再乘以（n-i+1）。

因此最终答案为 Σni=1( i! * (n-i+1) * (n-i+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
27
28
29
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll jc[250004];
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	ll n,m;
	cin>>n>>m;
    //预处理阶乘的值
	jc[0]=1;
	for(ll i=1;i<=n;i++){
		jc[i]=jc[i-1]*i%m;
	}
    //计算公式
	ll ans=0;
	for(ll i=1;i<=n;i++){
		//ans=(ans+(((jc[i]*jc[n-i])%m)*(((n-i+1)*(n-i+1)))%m)%m)%m;
		ans=(ans+(jc[i]*jc[n-i+1]%m)*(n-i+1)%m)%m;
	}
	cout<<ans<<endl;


	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

D New Year and Conference

传送门

题解

一共有两种NO的情况，分别是两个演讲在A场地冲突，在B场地不冲突；在B场地冲突，在A场地不冲突。所以需要判断两次，但其实判断流程是一样的。

那前一种NO的情况做例子，我们先将每场演讲在A场地的开始和结束的时间节点按照时间顺序排列，同时将演讲的序号也记录进去。有点像括号匹配，我们顺序枚举每个时间节点，用一个Set记录当前有哪些演讲在讲，然后每当碰到一个时间节点具有未出现的演讲序号，就加进去，碰到已出现的就删除Set里的对应的演讲。这就意味着，同时出现在Set中的演讲序号其对应的演讲在A场地是冲突的。

那么如何处理这些演讲是否在B场地也冲突呢，我们用一个线段树维护每个时间节点有多少演讲，即每当Set中加入一场演讲，我们就把其在B场地演讲的时间段包含的时间节点全部加一，每当删除就全部减一。因为演讲只要在一个节点全部冲突，那么就是全部冲突，所以我们只要询问当前线段树所有节点的最大值，如果最大值等于Set中的演讲数量，那么他们必然在B中至少有一个时间节点全部冲突，否则不存在一个全部冲突的时间节点。这样就可以解决Set中演讲是不是同时在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
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
#include<bits/stdc++.h>
using namespace std;
//每场演讲的属性
struct cfdata{
	int sa,ea,sb,eb;
}cf[100005];
//演讲的开始和结束的时间节点和对应的演讲序号
pair<int,int> cfina[200005],cfinb[200005];
//按照时间顺序排序
bool cmp(pair<int,int> a,pair<int,int> b){
	return a.second<b.second;
}
//离散化
vector<int> trans;
int gettrans(int x){
	return lower_bound(trans.begin(),trans.end(),x)-trans.begin()+1;
}
//线段树，因为询问全局最大值就是询问f[1]，所以没有query()
//而初始就是空树，所以也没有build()
int f[2001005],tag[2001005];
void downtag(int x){
    if(tag[x]==0) return;
    tag[x*2]+=tag[x];
    f[x*2]+=tag[x];
    tag[x*2+1]+=tag[x];
    f[x*2+1]+=tag[x];
    tag[x]=0;
}
void modify(int x,int l,int r,int ll,int rr,int d){
    if(ll<=l&&r<=rr){
        f[x]+=d;
        tag[x]+=d;
    }
    else{
        downtag(x);
        int mid=(l+r)/2;
        if(ll<=mid) modify(x*2,l,mid,ll,rr,d);
        if(rr>=mid+1) modify(x*2+1,mid+1,r,ll,rr,d);
        f[x]=max(f[x*2],f[x*2+1]);
    }
}
int main(){
 	/*freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);*/

	int n;
	cin>>n;
    //输入数据并复制到对应的记录表中
	for(int i=0;i<n;i++){
		cin>>cf[i].sa>>cf[i].ea>>cf[i].sb>>cf[i].eb;
		trans.push_back(cf[i].sa);
		trans.push_back(cf[i].ea);
		trans.push_back(cf[i].sb);
		trans.push_back(cf[i].eb);
		cfina[i]=make_pair(i,cf[i].sa);
		cfina[n+i]=make_pair(i,cf[i].ea);
		cfinb[i]=make_pair(i,cf[i].sb);
		cfinb[n+i]=make_pair(i,cf[i].eb);
	}
    //离散化
	sort(trans.begin(),trans.end());
	trans.erase(unique(trans.begin(),trans.end()),trans.end());
    //按时间顺序排列
	sort(cfina,cfina+n*2,cmp);
	sort(cfinb,cfinb+n*2,cmp);
	//for(int i=0;i<n*2;i++) cout<<cfina[i].first<<' ';cout<<endl;
    //记录当前时间节点有哪些演讲
	set<int> cfinnow;
    //build()
	memset(f,0,sizeof(f));
	memset(tag,0,sizeof(tag));
	for(int i=0;i<n*2;i++){
        //判断当前时间节点是演讲的开始节点还是结束节点
        //如果是结束节点，那么对应的演讲序号应该已在Set中存在，反之亦然
		if(cfinnow.find(cfina[i].first)!=cfinnow.end()){
            //在A场地和B场地都删除当前演讲
			cfinnow.erase(cfina[i].first);
			modify(1,1,trans.size(),gettrans(cf[cfina[i].first].sb),gettrans(cf[cfina[i].first].eb),-1);
		}else
		{
            //在A场地和B场地均加入当前演讲
			cfinnow.insert(cfina[i].first);
			modify(1,1,trans.size(),gettrans(cf[cfina[i].first].sb),gettrans(cf[cfina[i].first].eb),1);
            //判断当前所有演讲是否在两个场地均冲突
			if(f[1]!=cfinnow.size()){
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}
    //再做一次B场地冲突是不是A场地也冲突
	cfinnow.clear();
	memset(f,0,sizeof(f));
	memset(tag,0,sizeof(tag));
	for(int i=0;i<n*2;i++){
		if(cfinnow.find(cfinb[i].first)!=cfinnow.end()){
			cfinnow.erase(cfinb[i].first);
			modify(1,1,trans.size(),gettrans(cf[cfinb[i].first].sa),gettrans(cf[cfinb[i].first].ea),-1);
		}else
		{
			cfinnow.insert(cfinb[i].first);
			modify(1,1,trans.size(),gettrans(cf[cfinb[i].first].sa),gettrans(cf[cfinb[i].first].ea),1);
			if(f[1]!=cfinnow.size()){
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}
	cout<<"YES"<<endl;

	/*fclose(stdin);
    fclose(stdout);*/

    return 0;
}

Codeforces Round #590 (Div. 3)

D Distinct Characters Queries

传送门

题解

用26个BIT维护一下。

然而比赛的时候给B题整自闭了（循环写成i–，结果一直找不到哪儿错了），最后被忽悠说一定要用线段树就没做。

补题的时候还把memset()的参数顺序搞错了，又查了半天（VSCode把我养成five了，参数次次记不得）。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[100005][30];
int lowbit(int x){
	return x&(-x);
}
void modify(int x,int c,int d,int len){
	while(x<=len){
		f[x][c]+=d;
		x+=lowbit(x);
	}
	return;
}
void query(int x,int *tf){
	while(x!=0){

		for(int i=0;i<26;i++){
			tf[i]+=f[x][i];
		}
		x-=lowbit(x);
	}
	return;
}
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	char s[100005];
	cin>>s;
	int len=strlen(s);
	memset(f,0,sizeof(f));
	for(int i=0;i<len;i++){
		modify(i+1,s[i]-'a',1,len);
	}
	int n;
	cin>>n;
	int t,p,l,r;
	char ch;
	int tfl[30],tfr[30];
	int ans;
	for(int i=0;i<n;i++){
		/*cout<<s<<endl;
		for(int k=1;k<=len;k++){
			cout<<k<<' '<<lowbit(k)<<endl;
			for(int j=0;j<26;j++){
				cout<<f[k][j]<<" ";
			}
			cout<<endl;
		}*/
		cin>>t;
		if(t==1){
			cin>>p>>ch;
			modify(p,s[p-1]-'a',-1,len);
			s[p-1]=ch;
			modify(p,s[p-1]-'a',1,len);
		}
		else{
			cin>>l>>r;
			memset(tfl,0,sizeof(tfl));
			query(l-1,tfl);
			memset(tfr,0,sizeof(tfr));
			query(r,tfr);
			ans=0;
			/*for(int j=0;j<26;j++){
				cout<<tfl[j]<<' ';
			}
			cout<<endl;
			for(int j=0;j<26;j++){
				cout<<tfr[j]<<' ';
			}
			cout<<endl;*/
			for(int j=0;j<26;j++){
				if(tfl[j]!=tfr[j]){
					ans++;
				}
			}
			cout<<ans<<endl;
		}
	}

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