Codeforces Round 937 (Div. 4)

B题是输出规律图形题，对于这种题不能直接不思考就上去模拟，而应该思考一下数学规律，往往是模意义下的规律。

本题只需要模4以后的结果分为两类，分别讨论即可。对于模4可以利用位运算取出第二位的，这与模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
char s1='#';
char s2='.';
void solve(){
	cin>>n;
	vector<vector<char>>ans(2*n+1,vector<char>(2*n+1,'0'));
	//vector<vector<bool>>v(2*n+1,vector<bool>(2*n+1,0));
	for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++){
			int u=i%4;int v=j%4;
			if(u==1||u==2){
				if(v==1||v==2){
					ans[i][j]=s1;
				}
			}
			else if(u==3||u==0){
				if(v==3||v==0){
					ans[i][j]=s1;
				}
				
			}
			if(ans[i][j]=='0')ans[i][j]=s2;
		}
	}
	for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++){
			cout<<ans[i][j];
		}
		cout<<endl;
	}
}

C:增加常识：12小时制没有0，是从1-12开始的，这符合时钟表盘下的数字。24小时制是没有24.

D：要求快速判断一个数能不能由只含若干0和1的数字相乘得到。

Solution：对于多次询问，我们提前打表预处理，实现O(1)O(1)查询。首先根据范围利用状态压缩得到范围内的可能01串，然后只需要将他们随意相乘能得到哪些数。

  • 我只想到了dfs暴搜，到边界了就剪枝return

  • 正解是跑完全背包，可达性统计

    Code:

    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
    int a[N];
    map<int,int>mp;
    vector<int>v;
    void dfs(int u){
    	if(u>100000)return ;
    	//cerr<<u<<endl;
    	mp[u]=1;
    	for(int i=0;i<30;i++){
    		dfs(u*v[i]);
    	}
    }
    void init(){
    	mp[100000]=1;
    	
    	for(int i=1;i<32;i++){
    		int len=__lg(i);
    		string s;
    		for(int j=len;j>=0;j--){
    			if((i>>j)&1)s+="1";
    			else s+="0";
    		}
    		int num=stoi(s);
    		mp[num]=1;
    		//cerr<<num<<endl;
    		if(num!=1)v.push_back(num);
    		}
    		dfs(1);
    	//cerr<<v.size()<<endl;
    }
    void solve(){
    	cin>>n;
    	if(mp[n])cout<<"YES"<<endl;
    	else cout<<"NO"<<endl;
    }

jiangly的代码学习一下

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

using i64 = long long;

constexpr int N = 1E5;

int dp[N + 1];

void solve() {
    int n;
    std::cin >> n;
    
    std::cout << (dp[n] ? "YES" : "NO") << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::vector<int> bin;
    for (int s = 1; s < (1 << 5); s++) {
        int x = 0;
        for (int i = 4; i >= 0; i--) {
            x = x * 10 + (s >> i & 1);
        }
        bin.push_back(x);
    }
    bin.push_back(N);
    
    dp[1] = 1;
    for (auto x : bin) {
        for (int y = 1; y * x <= N; y++) {
            dp[y * x] |= dp[y];
        }
    }
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

E:按照题意暴力模拟即可，需要注意的是

  • 只有因子长度string才可能作为daan
  • 需要拿两个子串分别check一遍，答案一定才被覆盖
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
void solve(){
	cin>>n;
	string s;
	cin>>s;
	vector<int>v;
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			v.push_back(i);
			if(i*i!=n){
				v.push_back(n/i);
			}
		}
	}
	auto check=[&](string s1,int len){
		string tmp;
		for(int i=1;i<=n/len;i++)tmp+=s1;
		int cnt=0;
		for(int i=0;i<n;i++){
			if(tmp[i]!=s[i])cnt++;
		}
		
		//cerr<<len<<" "<<cnt<<endl;
		if(cnt<=1)return true;
		 return false;
	};
	sort(v.begin(),v.end());
	
	
	for(auto x:v){
		//cerr<<x<<" ";
		string s1=s.substr(0,x);
	if(x==n){
		cout<<x<<endl;
		return ;
	}
	string s2=s.substr(x,x);
		if(check(s1,x)||check(s2,x)){
			cout<<x<<endl;;
			return ;
		}
	}
}

F:给定出度为0，1，2的点的具体数量为c,b,ac,b,a.要求构造一棵树高最小的树

Solution:首先很容易想到贪心方案：先把所有的2用完，然后再用1，最后补0。

  • 对于无解情况的判断，利用出度和边的数量关系构造等式a+2b=a+b+c−1a+2b=a+b+c-1，不符合这个的直接无解

  • 对于贪心的代码实现，非常的trick,利用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
    //2a+b=a+b+c-1
    void solve(){
    	int a,b,c;cin>>a>>b>>c;
    	if(a+1!=c){
    		cout<<-1<<endl;
    		return ;
    	}
    	queue<int>q;
    	int x=0;int ans=0;
    	q.push(0);
    	while(q.size()){
    		auto u=q.front();
    		//cerr<<u<<endl;
    		q.pop();
    		ans=u;
    		if(a){
    			a--;
    			q.push(u+1);
    			q.push(u+1);
    		}
    		else if(b){
    			b--;
    			q.push(u+1);
    		}
    	}
    	cout<<ans<<endl;
    }

G题: n个点，每个点有两种性质，两个点之间有一个性质相同就连边，图提前给定，求图上一条最长简单路径

Solution：对于这种一般图求最长路，在n范围较小的情况下，应该快速意识到是状态压缩的TSP类似问题。对于所有可能作为终点的点，计算他的最好状态中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
44
45
46
47
48
49
50
void solve(){
	vector<string>v1;
	vector<string>v2;
		cin>>n;
	vector<vector<int>>w(n+1,vector<int>(n+1,0));
	
	for(int i=0;i<n;i++){
		string s1,s2;cin>>s1>>s2;
		v1.push_back(s1);
		v2.push_back(s2);
	}
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			//if(j==i)continue;
			if(v1[i]==v1[j]||v2[i]==v2[j]){
				w[i][j]=1;w[j][i]=1;
			}
		}
	}
	// for(int i=0;i<n;i++){
		// for(int j=0;j<n;j++){
			// cerr<<w[i][j];
		// }
		// cerr<<endl;
	// }
	//寻找答案状态：枚举最终的状态和终点，从而计算答案
	int ans=0;
	vector<vector<int>>dp((1<<n)+1,vector<int>(n+1,0));
	for(int i=0;i<n;i++)dp[1<<i][i]=1;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			int u=(i>>j)&1;
			if(u==0)continue;
			for(int k=0;k<n;k++){
				//为什么不能判断终点j和k转移重复
				int v=(i>>k)&1;
				if(v==0)continue;
				int last=i-(1<<j);
	dp[i][j]|=dp[last][k]&w[k][j];
//	cerr<<i<<" "<<j<<endl;
	if(dp[i][j]){
		ans=max(ans,__builtin_popcount(i));
	}
	
			}
		}
	}
	
	cout<<n-ans<<endl;
}