题解：CF1312F Attack on Red Kingdom

Le probleme est simple a comprendre, mais difficile a programmer.

Chaque chateau est independant. On doit utiliser les fonctions SG pour calculer le resultat final.

Mais attention : Le nombre de troupes par chateau est tres grand. Mais la fonction SG se repete (cycle), Donc on trouve ce cycle pour calculer rapidement.

Solution :

Essayer tous les premiers coups possibles.

Verifier si le coup est legal avec la fonction SG.

Mais Comprendre $≠$ Savoir programmer !
J’ai donc ajoute beaucoup de commentaires dans le code.

Je ne suis pas tres bon en francais, mais mon editorial en anglais a ete rejete sans explication - juste des insulte. Donc, je pense que peut-etre je devrais l’ecrire en francais ?

Voici le code.

Desole mais les commentaires sont encore en anglais parce’que je ne suis pas assez bon en francais

/*
the essential constraint that allows us to
quickly find the loop knot is the fact
that x, y, z <= 5 so we will only
use the last 5 rows
*/
#include<bits/stdc++.h>
#define INF 1000000000000005
#define int long long
using namespace std;
int t;
int n, X, Y, Z, a[300005], cnt, sz, ans;
typedef vector<vector<int> > sta;
//this is a state of the sg function
//sg[i][j] meaning a castle with i
//troops remaining and the last attack
//being type j
sta looplog;
//keeping track of the values of
//all sg function <= the loop knot
int mex(vector<int> x){
	//umm do i need to explain how to find the mex
	//of a vector???
	for(int i = 0; i <= x.size(); i++){
		int check = 0;
		for(auto j: x)if(j == i)check = 1;
		if(check)continue;
		return i;
	}
	return 0;//yeah umm
}
void loop_knot(){
	//gotta find the loop knot first
	map<sta, int> d;
	d.clear();
	//wheter this combination of the
	//5 rows of vectors existed before
	//specifically each d keep track of
	//5 rows in the sg table each with
	//3 columes the 5 rows represent
	//the number of troops left from
	//i to i - 5 and columes are for the
	//type of the last move made
	sta cur(3, vector<int>(5, 0));
	//meaning cur is 3 vectors each with
	//5 0s in it
	//this is the initial vector just
	//like i said, cur[0, 1, 2] each
	//represent a colume with 5 elements in each
	//of them meaning the value of the sg
	//function for i, i - 1, i - 2 ... i - 5 troops
	//in a castle
	cnt = 0;
	//if there are cnt troops in a castle
	looplog.clear();
	while(!d.count(cur)){
		//while cur haven't existed
		//yet we continue computing later
		//curs, but if it has, we know
		//it MUST go into a cycle because
		//we ONLY use the last 5 rows
		//when transfering the sg function
		d[cur] = cnt;
		//cur first existed for the sg 
		//function of a castle with cnt troops
		looplog.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
		//the bottom of each of the columes aka the
		//last row, is the value of the sg function if
		//u launch an attack of type 0 1 or 2 on a castle
		//with cnt troops remaining
		
		
		//compute the new cur value
		sta nw = cur;
		nw[0].push_back(mex({cur[0][5 - X], cur[1][5 - Y], cur[2][5 - Z]}));
		nw[1].push_back(mex({cur[0][5 - X], cur[2][5 - Z]}));
		nw[2].push_back(mex({cur[0][5 - X], cur[1][5 - Y]}));
		//for each colume, we add another number to it meaning
		//if we had 1 more soldier in the castle and we
		//last did move 0/1/2 on it
		//5 - X/Y/Z is because we're currently at colume
		//5 which means the sg function for cnt troops being in
		//the castle, so the sg function of cnt + 1 troops
		//is just cnt + 1 - X/Y/Z(depending on which move)
		//which is just 5 - X/Y/Z(depending on which move)
		//for cur, and taking mex is just cuz that's
		//the def of sg function
		
		nw[0].erase(nw[0].begin());
		nw[1].erase(nw[1].begin());
		nw[2].erase(nw[2].begin());
		//we only need to keep 5 rows because the 
		//earlier rows won't ever be used for transfering
		//so we erase the first row after each time we
		//increase a soldier
		
		cur = nw; 
		
		cnt++;
		//now we consider the case where there is 1 more
		//soldier in the castle
	}
	sz = cnt - d[cur];
	//sz = the size of each loop, because
	//we know we ended after cnt troops but
	//that's not the size of the loop knot
	//unless cur is also the first state to appear
	//but if it isn't the size of the loop knot is
	//just the second time cur appeared(which is cnt) - first
	//time which is just d[cur]
}
//alright good job u just walked through the most
//difficult part of this problem with me, now that
//we found the loop knots' size and kept track of all
//values <= loop knot in looplog we can O(1) caluclate
//the sg function value for any sg[x][y] meaning 
//a castle with x troops left and last attack being type y,
//by just doing the following = 
int sg_function(int x, int y){
//	cout<<x<<" "<<y<<endl;
	if(x < cnt){
		//from 0 to cnt is before
		//any value appeared more than once
		//they're also the spots that are recorded
		//DIRECTLY in log
		return looplog[x][y];
	}
	x -= (cnt - sz);
	//cnt - sz is the number of elements
	//that are not in the loop, the elements that
	//appeared before the first loop element appeared
	int tmp = (cnt - sz) + (x % sz);
	//x % sz = to which element in the loop have we
	//reached, + (cnt - sz) because we need to add
	//back the first unlooped elements
	return looplog[tmp][y];
	
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>X>>Y>>Z;
		//x = mixed
		for(int i = 1; i <= n; i++){
			cin>>a[i];
		}
		loop_knot();
		//first we find the loop knot
		int orig = 0;
		for(int i = 1; i <= n; i++){
			orig ^= sg_function(a[i], 0);
			//if we don't do any attack
			//on any castle the value
			//is obviously sg[a[i]][0] bc
			//0 doesn't bring any restrictions
			//on the next attack and a[i]
			//means it's not yet attacked
		}
		ans = 0;
		for(int i = 1; i <= n; i++){
			orig ^= sg_function(a[i], 0);
			//if we don't not do an attack on
			//castle i instead what if 
			//we do a type 0/1/2 attack?
			ans += (orig == sg_function(max(0LL, a[i] - X), 0));
			ans += (orig == sg_function(max(0LL, a[i] - Y), 1));
			ans += (orig == sg_function(max(0LL, a[i] - Z), 2));
			//only when they're equal would they xor to 0
			//which is a must lose condition for the black
			//king who is about to make move next
			orig ^= sg_function(a[i], 0);
			//add it back
		}
		cout<<ans<<endl;
	}
	return 0;
}

S’il vous plait, si vous est le meme administrateur auparavant, n’insultez pas mon editorial, dites-moi simplement ce que je dois faire pour l’ameliorer s’il vous plait.