补题报告：Codeforces Round #764 Div.3

补题报告：Codeforces Round #764 Div.3

A. Plus One on the SubsetB. Squares and CubesC. Division by Two and PermutationD. Palindromes ColoringE. Masha-forgetfulF. Interacdive ProblemG. MinOr Tree

A. Plus One on the Subset

https://codeforces.com/contest/1624/problem/A

Problem

给你一个整数序列，然后每次操作可以使任意个元素加一，问你最少需要多少次操作可以使所有元素相等。

Solution

很显然序列中的最小值和最大值决定了操作的次数，直接用最大值减最小值即可。

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
const int inf = 0x3f3f3f3f;

const int N = 60;
int a[N];

void sol() {
	long long ans = 0;
	int n;
	cin >> n;
	for (int i=1; i<=n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	cout << a[n] - a[1] << 'n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

B. Squares and Cubes

https://codeforces.com/contest/1624/problem/B

Problem

给你 3 3 3 个正整数 a , b , c a,b,c a,b,c，问是否能使其中任意一个数乘正整数 m m m ，使得 a , b , c a,b,c a,b,c 成为等差数列。

Solution

分类讨论：

a m + c = 2 b = > m = 2 b − c a am+c=2b => m=frac{2b-c} a am+c=2b=>m=a2b−c​ a + c m = 2 b = > m = 2 b − a c a+cm=2b => m=frac{2b-a} c a+cm=2b=>m=c2b−a​ a + c = 2 m b = > m = a + c 2 m a+c=2mb => m=frac{a+c} {2m} a+c=2mb=>m=2ma+c​

因为要求 m m m为正整数，所以其中一个情况要满足整除且分子为正数。否则不存在这样的 m m m

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
const int inf = 0x3f3f3f3f;

const int N = 60;

void sol() {
	int a, b ,c;
	cin >> a >> b >> c;
	if(((2*b-a)%c==0&&2*b>a) || ((2*b-c)%a==0&&2*b>c) || (a+c)%(2*b)==0){
		puts("YES");
	}
	else puts("NO");
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

C. Division by Two and Permutation

https://codeforces.com/contest/1624/problem/C

Problem

给你一个整数序列 ( n < = 50 , a i < = 1 e 9 ) (n<=50, a_i<=1e9) (n<=50,ai​<=1e9) ，问你能否通过任意次操作使序列成为 1 ∼ n 1 sim n 1∼n的一种全排列，每一次操作可以将任意元素 a i a_i ai​ 变为 ⌊ a i 2 ⌋ lfloor frac{a_i}{2} rfloor ⌊2ai​​⌋

Solution

贪心。不知道为什么这么贪就一定对的，反正就A了，坐等官方题解~

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
const int inf = 0x3f3f3f3f;

const int N = 60;
int a[N];
int n;
bool vis[N];

void sol() {
	memset(vis, false, sizeof vis);
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		while (a[i] > n) a[i] >>= 1;
	}
	sort(a+1, a+n+1);
	for (int i=n; i>=1; i--){
		while(vis[a[i]]){
			a[i]>>=1;
		}
		vis[a[i]] = true;
		if(a[i]==0) {
			puts("NO");
			return ;
		}
	}
	puts("YES");
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

D. Palindromes Coloring

https://codeforces.com/contest/1624/problem/D

Problem

给你一个字符串 s s s，在字符串上染色编号为 1 ∼ k 1 sim k 1∼k 的颜色，要求每一种颜色都被使用过但不要求每一个字符都被染过色。
你可以将串 s s s 的字符顺序任意调换。你的任务是为字符串的字符染色，以便生成的所有颜色串都是回文串，并且这些回文串中最短的长度尽可能大。
例：

蓝色子串：xyyx
红色子串：aba
（黑色为未染色）

Solution

考虑回文串的特性，从串中心分别向两端看，两端都一样（也就是每一个字符都是在两端成对出现）
比如 s = “ a b b a ” “ a b c b a ” s=“abba” “abcba” s=“abba”“abcba” 第一个串中心在两个 ′ b ′ 'b' ′b′ 之间，第二个串中心是 ′ c ′ 'c' ′c′
所以从每一个字母的出现对数入手，平均分配到 k k k 个子串里，剩下的字符用于插入到串中间。
比如 s = “ b f v f b v ” s=“bfvfbv” s=“bfvfbv”， k = 2 k=2 k=2 。一共有三对，平均分配到两个子串中，一个子串一对 ( ⌊ 3 2 ⌋ = 1 lfloor frac{3}{2} rfloor=1 ⌊23​⌋=1) ，还剩下两个字符，分别插入到两个子串中心，则两个子串各有 3 3 3个字符。

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
const int inf = 0x3f3f3f3f;

#define int long long

const int N = 60;
int cnt[N];
int n, k;

void sol() {
	memset(cnt, 0, sizeof cnt);
	cin >> n >> k;
	string s;
	cin >> s;
	for (int i=0; i= k) cout << sum/k*2 + 1 << 'n'; //sum/k为一个子串中分配到的对数个数，
	    												//sum/k*2*k为所有子串中分配到的成对字母的个数
	    												//n-sum/k*2*k为除去成对分配的字母还剩下的字母的个数
	    												//如果剩下的字母个数大于等于k，说明所有子串中间都可以插入一个字母
	    else cout << sum/k*2 << 'n';
	}
}

signed main(){
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

E. Masha-forgetful

https://codeforces.com/contest/1624/problem/E

Problem

给你一个模式串 s s s 和 n n n 个匹配串，是否能将串 s s s 分成任意段，使得每一段都在 n n n 个匹配串中出现过（任意一个匹配串的子串），并且要求每一段长度都大于等于 2 2 2.

Solution

将所有匹配串的子串用 m a p map map 存下来，由于题目只要求子串长度不小于 2 2 2，那么我们只需要存下来长度为 2 2 2 和 3 3 3 的子串，因为任意长度的串一定可以由长度为 2 2 2 和 3 3 3 的串拼起来。
然后dp存一下哪些位置可以作为起点（当前位置向后的两个字符形成的子串或三个字符形成的子串在匹配串中出现过），然后再从后往前存一下答案就可以了。

说一下找答案的过程：假设当前到第i个字符，如果i-2能够作为起点，则 s [ i − 2 ] , s [ i − 1 ] s[i-2],s[i-1] s[i−2],s[i−1]形成子串，否则 s [ i − 3 ] , s [ i − 2 ] , s [ i − 1 ] s[i-3],s[i-2],s[i-1] s[i−3],s[i−2],s[i−1]形成子串。

（代码学习的何逊佬）

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
const int inf = 0x3f3f3f3f;

#define int long long

const int N = 1010;
int n, m;

void sol() {
	cin >> n >> m;
	map> mp;
	for (int i=0; i> s;
		for (int j=0; j> s;
	vector dp(m+1, 0);
	dp[0] = 1;
	for (int i=0; i> ans;
		int p = m;
		while (p){
		    if(dp[p-2]){
		        ans.push_back(mp[s.substr(p-2, 2)]);
		        p-=2;
		    }else{
		        ans.push_back(mp[s.substr(p-3, 3)]);
		        p-=3;
		    }
		}
		reverse(ans.begin(), ans.end());
		cout << ans.size() << 'n';
		for(auto [u,v,w] : ans){
		    cout << u << ' '  << v << ' ' << w << 'n';
		}
	}
}

signed main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}

F. Interacdive Problem

https://codeforces.com/contest/1624/problem/F

Problem

交互题不想补了。

Solution

Code

G. MinOr Tree

https://codeforces.com/contest/1624/problem/G

Problem

在一个有权无向联通图上，找出一颗生成子树，使得生成子树所有边的或最小。

Solution

贪心。按位考虑（宁愿要第 20 20 20位，也不要第 21 21 21位），边权从高位向低位遍历，假设当前遍历到第 i i i 位，如果边权第 i i i 位为 1 1 1的边都不要，看下是否能形成子树，如果可以，则将边权第 i i i 位为 1 1 1 的边都删掉，如果不要第 i i i 位就无法形成生成子树，说明这一位非要不可。

Code

#include
using namespace std;

#define PII pair
#define x first
#define y second
const int inf = 0x3f3f3f3f;

const int N = 200010;
int n, m;

struct DSU {
    std::vector f, siz;
    DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    bool same(int x, int y) { return leader(x) == leader(y); }
    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) { return siz[leader(x)]; }
};

void sol() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	vector> edges(m);
	for (int i=1; i<=m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		edges.push_back({u,v,w});
	}
	for (int t=29; t>=0; t--){
		DSU g(n);
		int s = n;
		for (auto [u,v,w] : edges){
			if(~w >> t & 1){
				s -= g.merge(u, v);
			}
		}
		if(s==1){
		    edges.erase(remove_if(edges.begin(), edges.end(), [&](auto e){
		        return get<2>(e) >> t & 1;
		    }), edges.end());
		}else{
			ans |= 1 << t;
		}
	}
	cout << ans << 'n';
}

int main(){
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);

	int T_T=1;
	cin >> T_T;
	while (T_T--) sol();

	return 0;
}