codeforces#764补题

codeforces#764补题

codeforces#764补题

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

---

A. Plus One on the Subset

题意：给出 n n n个数，每次可以任选若干个数使其加一，问至少经过多少次 *** 作后各个数相等

找到最大值和最小值相减就可以

#include
#include
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t -- ){
        int maxx = -1;
        int minn = 1e9;
        int n;
        cin>>n;
        while(n -- ){
            int x;
            cin>>x;
            maxx = max(maxx,x);
            minn = min(minn,x);
        }
        cout< 
B.Make AP 
 题意：给一个三元组，问是否能找到一个正整数乘以其中的某个数令得到的三元组变为等差数列
 
枚举三种情况即可
 
#include
#include
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t -- ){
        int a,b,c;
        cin>>a>>b>>c;
        if(b - a == c - b) cout<<"YESn";
        else if((a + c) % 2 == 0 && (a + c) / 2 % b == 0 && (a + c) / 2 / b > 0) cout<<"YESn";
        else if(((b - a) + b) % c == 0 && ((b - a) + b) / c > 0) cout<<"YESn";
        else if((b - (c - b)) % a == 0 && (b - (c - b)) / a > 0) cout<<"YESn";
        else cout<<"NOn";
    }
}
 
C. Division by Two and Permutation 
题意：给出
     
      
       
        
         n
        
       
       
        n
       
      
     n个数，每次可以将其中某个数
     
      
       
        
         x
        
       
       
        x
       
      
     x变为
     
      
       
        
         ⌊
        
        
         x
        
        
         /
        
        
         2
        
        
         ⌋
        
       
       
        lfloor x /2rfloor
       
      
     ⌊x/2⌋，问是否能够组成一个
     
      
       
        
         n
        
       
       
        n
       
      
     n的全排列
 
 贪心，先将每个数变为
     
      
       
        
         n
        
       
       
        n
       
      
     n以内的数后，由高到低将某个数（出现次数大于1）变为其他没有出现过的数
 
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N = 55;
int a[N];
vector v;
int cnt[N];
bool cmp(int x,int y){
    return x > y;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t -- ){
        v.clear();
        for(int i = 0;i < 55;i ++ ){
            a[i] = 0;
            cnt[i] = 0;
        }
        int n;
        cin>>n;
        for(int i = 1;i <= n;i ++ ){
            cin>>a[i];
            while(a[i] > n){
                a[i] /= 2;
            }
            cnt[a[i]] ++;
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end(),cmp);
        for(int i = 0;i < v.size();i ++ ){
            if(cnt[v[i]] > 1){
                int t = v[i];
                while(v[i] && cnt[v[i]]){
                    v[i] /= 2;
                }
                if(v[i]){
                    cnt[t] --;
                    cnt[v[i]] ++;
                }
            }
        }
        bool flag = false;
        for(int i = 1;i <= n && !flag;i ++ ){
            if(!cnt[i]){
                flag = true;
                //cout< 
D. Palindromes Coloring 
题意：给出一个字符串和颜色数
     
      
       
        
         k
        
       
       
        k
       
      
     k，每种颜色必须至少给一个字符染色，且被染色的字符串是回文串，使最短的回文串的长度尽可能长
 
统计一下各个字符出现的
     
      
       
        
         对
        
        
         数
        
       
       
        对数
       
      
     对数，每对字符都可以拿出来作为回文串
 然后统计一下单个出现的字符数是否大于
     
      
       
        
         k
        
       
       
        k
       
      
     k,如果不大于的话，将这些字符插入到剩余的字符即可，否则，最短的字符串的长度就要加1，(中心位置插入了单个字符)
 
#include
using namespace std;
const int  N = 30;
int cnt[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		memset(cnt, 0, sizeof cnt);
		int ans = 0;
		string str;
		int n, k;
		cin >> n >> k >> str;
		int te = str.size();
		for (int i = 0;i < te;i++) {
			cnt[str[i] - 'a'] ++;
		}
		for (int i = 0;i < 26;i++) {
			ans += cnt[i] / 2;
		}
		ans /= k;
		ans *= 2;
		if (n - k * ans >= k) ans++;
		cout << ans << "n";
	}
}
 
E. Masha-forgetful 
题意没看懂（挠头.jpg）
 
F. Interacdive Problem 
题意：让你猜一个数
     
      
       
        
         x
        
        
         (
        
        
         1
        
        
         ≤
        
        
         x
        
        
         <
        
        
         n
        
        
         )
        
       
       
        x(1 leq x  
二分
 
#include
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    //getchar();
    bool flag = false;
    int i = 0;
    //int tt = n;
    int l = 1;
    int r = n - 1;
    int mid;
    int t = 0;
    while(l < r){
        mid = (l + r + 1) / 2;
        
        int ans = (n - mid + n - t % n) % n;
        cout<<"+ "<>x;
        //getchar();
        if(x == i){
            r= mid - 1;
            //++ i;
        }
        else{
            l = mid;
        }
        i = x;
    }
    cout<<"! "< 
G. MinOr Tree 
题意：给你一个带权无向图，询问这个图的生成树边权按位或后的最小值
 从高位向低位考虑，先是否能生成子树，如果不可以的话，说明需要考虑该位为1的边权，最终答案也要或上该位
 
#include
using namespace std;
void solve() {
	int n, m;
	cin >> n >> m;
	vector u(m + 1), v(m + 1), w(m + 1);
	for (int i = 0;i < m;i++) {
		cin >> u[i] >> v[i] >> w[i];
	}
	long long ans = 0;
	for (int i = 29;i >= 0;i--) {
		vector> ve(n + 1);
		for (int j = 0;j < m;j ++) {
			if (w[j] < (1 << i)) {
				ve[v[j]].push_back(u[j]);
				ve[u[j]].push_back(v[j]);
			}
		}
		vector vis(n + 1);
		vis[1] = 1;
		queue < int> q;
		q.push(1);
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (auto tt : ve[x]) {
				if (!vis[tt]) {
					q.push(tt);
					vis[tt] = true;
				}
			}
		}
		vector flag(n + 1, 1);
		flag[0] = 0;
		if (flag != vis) {
			ans |= 1 << i;
			for (int j = 0;j < m;j++) {
				if ((w[j] >> i) & 1) {
					w[j] ^= 1 << i;
				}
			}
		}
	}
	cout << ans << "n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5702653.html