题解：CF1312F Attack on Red Kingdom
Le problème est simple à comprendre, mais difficile à programmer.
Chaque château est indépendant. On doit utiliser les fonctions SG pour calculer le résultat final.
Mais attention : Le nombre de troupes par château est très grand. La fonction SG se répète (cycle), donc on trouve ce cycle pour calculer rapidement.
Solution :
- Essayer tous les premiers coups possibles.
- Vérifier si le coup est légal avec la fonction SG.
Mais comprendre
Je ne suis pas très bon en français, mais mon éditorial en anglais a été rejeté sans explication - juste des insultes. Donc, je pense que peut-être je devrais l'écrire en français ?
Voici le code.
Désolé, mais les commentaires sont encore en anglais parce que je ne suis pas assez bon en français.
/*
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 plaît, si vous êtes le même administrateur qu'auparavant, n'insultez pas mon éditorial. Dites-moi simplement ce que je dois faire pour l'améliorer, s'il vous plaît.