Codeforces Round ＃784 (Div. 4) (A - H)题解

难得的一次Div4，从头写到尾

A. Division?

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

void mian()
{
    
	int n;
	cin >> n;
	if (n <= 1399)
		cout << "Division 4" << endl;
	else if (n <= 1599)
		cout << "Division 3" << endl;
	else if (n <= 1899)
		cout << "Division 2" << endl;
	else
		cout << "Division 1" << endl;
}

int main()
{
    
	int T;
	cin >> T;
	while (T--)
	{
    
		mian();
	}
}

B. Triple

找三个相同的数然后输出，没有就输出-1

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <unordered_map>

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

unordered_map<int, int> t;

void mian()
{
    
	int n;
	cin >> n;
	t.clear();
	bool flag = true;
	for (int i = 1; i <= n; i++)
	{
    
		int a;
		cin >> a;
		t[a]++;
		if (flag && t[a] >= 3)
		{
    
			cout << a << endl;
			flag = false;
		}
	}
	if (flag)
		cout << -1 << endl;
}

int main()
{
    
	int T;
	cin >> T;
	while (T--)
	{
    
		mian();
	}
}

C. Odd/Even Increments

可以给所有奇数位或偶数位加1，如果能最终把所有数都变成奇数或者偶数，就输出YES

判断当前所有奇数位的数的奇偶性是不是一样，然后判断所有偶数位

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

void mian()
{
    
	int n;
	cin >> n;
	int a, b, c;
	cin >> a >> b;
	bool flag = true;
	for (int i = 3; i <= n; i++)
	{
    
		cin >> c;
		if (i & 1)
		{
    
			if (a % 2 != c % 2)
				flag = false;
		}
		else
		{
    
			if (b % 2 != c % 2)
				flag = false;
		}
	}
	if (flag)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

int main()
{
    
	int T;
	cin >> T;
	while (T--)
	{
    
		mian();
	}
}

D. Colorful Stamp

可以给连续两张邮票染色，必须染不同的色，可以重复染，但是一次必须连续两张。

从头到尾扫描一遍，以w分割，每个子串中如果有R和B那就是合法的。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

void mian()
{
    
	int n;
	string s;
	cin >> n >> s;
	int b = 0, r = 0;
	bool flag = true;
	for (int i = 0; i < n; i++)
	{
    
		if (s[i] == 'W')
		{
    
			if (b == 0 && r != 0 || b != 0 && r == 0)
				flag = false;
			b = 0, r = 0;
		}
		else if (s[i] == 'B')
		{
    
			b++;
		}
		else if (s[i] == 'R')
		{
    
			r++;
		}
	}
	if (b == 0 && r != 0 || b != 0 && r == 0)
		flag = false;
	if (flag)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

int main()
{
    
	int T;
	cin >> T;
	while (T--)
	{
    
		mian();
	}
}

E. 2-Letter Strings

题意：给n个长度为2字符串，找出多少对同一个位置字符相同，另一个位置字符不同的字符串。

思路：存一下第一个位置为x的字符中字符y的个数，然后对应相乘，再加到一起。然后第二个字符同理。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 30;

struct node
{
    
	vector<int> num;
	node()
	{
    
		num.resize(30, 0);
	}
};

void mian()
{
    
	node a[N], b[N];
	int n;
	cin >> n;
	string s;
	for (int i = 1; i <= n; i++)
	{
    
		cin >> s;
		a[s[0] - 'a'].num[s[1] - 'a']++;
		b[s[1] - 'a'].num[s[0] - 'a']++;
	}
	ll res = 0;
	for (int i = 0; i <= 'k' - 'a'; i++)
	{
    
		for (int j = 0; j <= 'k' - 'a'; j++)
		{
    
			for (int k = j + 1; k <= 'k' - 'a'; k++)
			{
    
				res += 1ll * a[i].num[j] * a[i].num[k];
			}
		}
	}
	for (int i = 0; i <= 'k' - 'a'; i++)
	{
    
		for (int j = 0; j <= 'k' - 'a'; j++)
		{
    
			for (int k = j + 1; k <= 'k' - 'a'; k++)
			{
    
				res += 1ll * b[i].num[j] * b[i].num[k];
			}
		}
	}
	cout << res << endl;
}

int main()
{
    
	int T;
	cin >> T;
	while (T--)
	{
    
		mian();
	}
}

F. Eating Candies

题意：两人分别从左边右边开始吃糖果，不能跳着吃，问他们想要吃的重量一样，他们一共要吃多少个。

双指针枚举即可

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

void mian()
{
    
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
    
        cin >> a[i];
    }
    int res = 0, cnt = 0;
    int l = 1, r = n;
    int alice = 0, bob = 0;
    while (l <= r)
    {
    
        if (alice == bob)
        {
    
            res = cnt;
            alice += a[l++];
            cnt++;
        }
        else if (alice > bob)
        {
    
            bob += a[r--];
            cnt++;
        }
        else
        {
    
            alice += a[l++];
            cnt++;
        }
    }
    if (alice == bob)
    {
    
        res = cnt;
    }
    cout << res << endl;
}

int main()
{
    
    int T;
    cin >> T;
    while (T--)
    {
    
        mian();
    }
}

G. Fall Down

有三种东西，.是空气*是石头，o不知道是啥，反正不能掉下来，石头能掉下来，掉到石头上或者o上。

一层一层跑，如果跑一遍没变化就是跑完了，可以退出了。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

const int N = 60;

void mian()
{
    
    int n, m;
    string a[N];
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
    
        cin >> a[i];
        a[i] = " " + a[i];
    }
    bool flag = true;
    while (flag)
    {
    
        flag = false;
        for (int i = n; i > 1; i--)
        {
    
            for (int j = 1; j <= m; j++)
            {
    
                if (a[i][j] == '.' && a[i - 1][j] == '*')
                {
    
                    a[i][j] = '*';
                    a[i - 1][j] = '.';
                    flag = true;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
    
        cout << a[i] << endl;
    }
    cout << endl;
}

int main()
{
    
    int T;
    cin >> T;
    while (T--)
    {
    
        mian();
    }
}

H. Maximal AND

就是可以给数组中一个数的二进制任意一位变成1，求这一堆数求与最大能变为多少。可以变k次。

存一下所有数的二进制位的每一位到一个数组，如果数组中的那一个达到n了，说明最终的这一位是1，然后k次就贪心的添加，如果全加进去不能到n，那就换低一位的。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

void mian()
{
    
    int a[40] = {
    0};
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
    
        int t;
        cin >> t;
        int idx = 0;
        while (t)
        {
    
            a[idx++] += (t & 1);
            t >>= 1;
        }
    }
    for (int i = 30; i >= 0; i--)
    {
    
        if (a[i] + k >= n)
        {
    
            k -= n - a[i];
            a[i] = n;
        }
        if (k <= 0)
            break;
    }
    int res = 0;
    int t = 1;
    for (int i = 0; i <= 30; i++)
    {
    
        if (a[i] == n)
            res += t;
        t <<= 1;
    }
    cout << res << endl;
}

int main()
{
    
    int T;
    cin >> T;
    while (T--)
    {
    
        mian();
    }
}