Codeforces round 784 (Div. 4) (a - H)

A rare time Div4, From beginning to end

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

Find three identical numbers and output , No output -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

You can add... To all odd or even digits 1, If we can finally turn all numbers into odd or even numbers , It outputs YES

Judge whether the parity of all current odd digits is the same , Then judge all even bits

#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

You can dye two consecutive Stamps , Must be dyed in different colors , It can be dyed repeatedly , But you must have two at a time .

Scan from beginning to end , With w Division , If there is... In each substring R and B That's legal .

#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

The question ： to n A length of 2 character string , Find out how many pairs of characters in the same position are the same , Another string with different position characters .

Ideas ： Save it. The first place is x Of the characters in the y The number of , And then multiply by the corresponding , Add it up . Then the second character is the same .

#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

The question ： Two people eat candy from left to right , You can't jump to eat , Ask them if they want to eat the same weight , How many will they eat altogether .

Double pointer enumeration

#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

There are three things ,. It's air * It's stone ,o I don't know what it is , You can't fall down anyway , Stones can fall , Fall on a stone or o On .

Run layer by layer , If you don't change after running, you're finished , You can quit .

#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

That is, any binary bit of a number in the array can be changed into 1, Find the maximum sum of this pile of numbers . Can change k Time .

Save each bit of the binary bits of all numbers into an array , If that one in the array reaches n 了 , It shows that the final one is 1, then k Add greedily at once , If you add it all in, you can't get to n, Then change to a lower one .

#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();
    }
}