Recently, I can't balance the grade point scientific research competition

It's coming back this week Increase of efficiency Good balance

B - Reverse Game（ Game theory ）

The key to this problem is to transform 1 Put it all on the right and the game is over

So each operation can make 1 Left 1 A or 2 individual

Then it can be transformed into a stone taking model ,n A stone , Every time 1 Or 2 individual

Judgment is not 3 Just a multiple of

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

int main()
{
    string s;
    cin >> s;
    int len = s.size();

    long long sum = 0, cnt = 0;
    rep(i, 0, len)
        if(s[i] == '1')
        {
            sum += len - i - 1;
            cnt++;
        }
    sum -= cnt * (cnt - 1) / 2;

    if((sum % 3) == 0) puts("Bob");
    else puts("Alice");

    return 0;
}

M - Mistake（ greedy ）

Is a very clever greed

Assign each number to the smallest number currently available

The answer constructed in this way is the most perfect , And it's guaranteed to be solved

So the input figure is given

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 5e5 + 10;
int a[N], n, m, k;

int main()
{
    scanf("%d%d%d", &n, &k, &m);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
	}
	_for(i, 1, n * k)
	{
		int x; scanf("%d", &x);
		printf("%d ", ++a[x]);
	}

    return 0;
}

Shuffle Cards（stl rope）

This problem is done with a balanced tree

But there is one way , use stl Containers rope

Its interior is realized by balanced tree

This container is used to process strings , Can be in logn Realize interval insertion in , Interval delete , Interval substitution

Array query O（1） Delete O（n）

Linked list query O（n） Delete O（1）

And this container , That's the balance tree , It's a query O（logn） Delete O（logn）

First, add the header file Note that the universal head does not include , And one more using namespace

#include <ext/rope>
using namespace __gnu_cxx;

The operation is as follows

Reference resources [rope Dafa is good ] STL Inside the persistent balance tree --rope - viv - Blog Garden

rope<int> r, x;
r.push_back(x)     //  Add... At the end x
r.insert(pos,x)    //  stay pos Insert x  Interval insertion 
r.erase(pos,x)     //  from pos To delete x individual   Interval delete 
r.replace(pos,x)   //  from pos Start changing to x  Interval substitution 
r.substr(pos,x)    //  extract pos Start x individual 

This question AC Code , Just extract the interval and add it directly

#include <bits/stdc++.h>
#include <ext/rope>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
using namespace __gnu_cxx;

int main()
{
	rope<int> r;
	int n, m;

	scanf("%d%d", &n, &m);
	_for(i, 1, n) r.push_back(i);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		r = r.substr(a - 1, b) + r.substr(0, a - 1) + r.substr(a + b - 1, n - a - b + 1);
	}
	rep(i, 0, n) printf("%d ", r[i]); puts("");

    return 0;
}

E  Sort String( Hash + Output optimization )

In fact, it is to quickly process whether this string has appeared before

The routine is hash cooperation unordered_map

I handed in a hair T 了

This output is huge , So I added an output optimization

Output optimization is actually very simple , Just use putchar

Break down the numbers one by one and use putchar Output

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef unsigned long long ull;
const int N = 2e6 + 10;
const int base = 131;
unordered_map<ull, int> mp;
vector<int> ans[N];
ull Hash[N], p[N];
char s[N];
int n;

ull get_hash(int l, int r)
{
	return Hash[r] - Hash[l - 1] * p[r - l + 1]; 
}

int w[60];
void write(int x)
{
	int t = 0;
	while(x)
	{
		w[++t] = x % 10;
		x /= 10;
	}
	if(!t) putchar('0');
	for(int i = t; i >= 1; i--) putchar(w[i] + '0');

}

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	_for(i, 1, n) s[n + i] = s[i];

	p[0] = 1;     // Don't miss this sentence 
	_for(i, 1, 2 * n) 
	{
		p[i] = p[i - 1] * base;
		Hash[i] = Hash[i - 1] * base + s[i];
	}

	int cnt = 0;
	_for(i, 1, n)
	{
		ull cur = get_hash(i, i + n - 1);
		if(!mp[cur]) mp[cur] = ++cnt;
		ans[mp[cur]].push_back(i - 1);
	}

	write(cnt); puts("");
	_for(i, 1, cnt)
	{
		write(ans[i].size()); putchar(' ');
		for(auto x: ans[i]) write(x), putchar(' ');
		puts("");
	}

	return 0;
}

E  Sort String(KMP Cycle section )

There is another way to solve this problem

If equal , There must be a circular section

Prove to be more emotional Draw with a pen and paper

So use kmp Just judge the circular section

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int Next[N], n, num, cnt;
char s[N];

void get_next()
{
	Next[0] = -1;
	int i = 0, j = -1;
	while(i < n)
	{
		if(j == -1 || s[i] == s[j])
		{
			i++; j++;
			Next[i] = j;
		}
		else j = Next[j];
	}
}

int main()
{
	scanf("%s", s);
	n = strlen(s);

	get_next();
	if(n % (n - Next[n])) num = 1;
	else num = n / (n - Next[n]);
	cnt = n / num;
	
	printf("%d\n", cnt);
	_for(i, 1, cnt)
	{
		printf("%d ", num);
		_for(j, 0, num - 1) printf("%d ", i - 1 + cnt * j);
		puts("");
	}

	return 0;
}

J.farm( Hash + randomization )

I see a coquettish approach to this problem

If it doesn't wither , Then add up the types of fertilizer and the types of mold flowers, which is equal to 0

But not when the number is very small such as 1 + 2 = 3 and 3

Then we can use hash , Map to a large value , It's hard to happen

For big and random , We can use randomization , That is, multiply by one rand

There was a construction problem in the previous competition , The data range is very small , It can be verified in a very short time , Therefore, the answer can be randomly constructed

Randomization is a method

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
vector<ll> a[N], b[N];
int n, m, t;
ll Hash[N];

int main()
{
	srand(time(0));
	_for(i, 0, 1e6) Hash[i] = i * i + i * rand();
	scanf("%d%d%d", &n, &m, &t);
	_for(i, 0, n + 10) a[i].resize(m + 10), b[i].resize(m + 10);
	_for(i, 1, n)
		_for(j, 1, m)
		{
			int x; scanf("%d", &x);
			b[i][j] = Hash[x];
		}

	while(t--)
	{
		int x1, y1, x2, y2, k;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
		a[x1][y1] += Hash[k];
		a[x2 + 1][y1] -= Hash[k];
		a[x1][y2 + 1] -= Hash[k];
		a[x2 + 1][y2 + 1] += Hash[k];
	}

	int ans = 0;
	_for(i, 1, n)
		_for(j, 1, m)
		{
			a[i][j] += -a[i - 1][j - 1] + a[i - 1][j] + a[i][j - 1];
			if(a[i][j] % b[i][j]) ans++;
		}
	printf("%d\n", ans);

	return 0;
}