Revizia anterioară Revizia următoare
Cal
Se verifică pentru fiecare punct dacă distanta manhattan fata de (sx,sy) e egală cu S si se creşte un contor.
Distanţa manhattan pentru 2 puncte A(a,b) B(x,y) se calculează cu formula: |a-x|+|b-y|
ScaleCrop
Pentru ca poza se scaleaza, avem ca wpn=f*wp si hpn=f*hp. Ramane doar sa gasim cel mai mic factor f cu care trebuie sa inmultim dimensiunile pozei, pentru a obtine wpn >= wf si hpn >= hf. Acest factor il putem gasi in timp logaritmic folosind cautarea binara sau in timp constant, alegand f dintre wf/wp si hf/hp in asa fel incat sa nu ramana nicio bucata din flyer neacoperita de poza.
ProDiv
Solutie O(sqrtN)
Se decompune N în factori primi. Fiecare factor il "distribuim" între cele 2 numere egal. De exemplu pentru 24 il inmultim pe a si pe b cu 22.
Notăm nrm = numărul de factori primi care au exponentul impar. Solutia este 2nrm
Arbore5
Solutie O(N)
Pentru fiecare nod reţinem nr[nod]=câte query-uri au unul din capete in nod sau în subarborele lui nod. Solutia este numărul de noduri diferite de rădăcină(nu are o muchie care să-l lege de un tată) care au nr[nod] par.
Observam ca un query (nod1, nod2) este echivalent cu query-urile (1, nod1) (2, nod2).
Tinem un vector state[nod], initial pe zero si de fiecare data cand intalnim querry(1, nod) facem state[nod] ^=1.
Observam ca pentru fiecare x cu state[x] = 1 daca putem afla culoarea muchiei de la x la father de x, este echivalent cu a adauga sau nu 1 la solutie si a face state[father[x]] ^= 1
Asadar vom face o parcurgere dfs incepand cu nodul 1 astfel:
void dfs(int x){
vis[x] = 1;
stack.push_back(x);
for(int i = 0; i < graph[x].size(); ++i)
if(!vis[graph[x][i]])
dfs(graph[x][i]);
stack.pop_back();
if(!stack.empty())
if(state[x] == 1){
++sol;
state[stack.back()] ^= 1;
}
}
