牛客多校1
D. Chocolate
题意：
A、B轮流吃巧克力，当一个人选择一个点吃的时候，会把这个点及其左下的所有全部吃完，谁先吃完谁就输了，给出巧克力的大小，问谁会赢。
思路：
考虑当一个人吃完只剩一行或一列时，那么下一个吃的人就可以控制把最后一块留给这个人，因此当一个人吃完剩一行和一列的时候，就可以控制剩下一行或者剩下一列给谁，因此除非初始巧克力大小只有1*1，否则先手必胜
#include<bits/stdc++.h>
using namespace std;
int main(){
int x, y;
cin>>x>>y;
if(x == 1 && y == 1){
cout<<"Walk Alone\n";
}
else{
cout<<"Kelin\n";
}
return 0;
}
L.Three Permutations
题意：
初始点(1, ,1 , 1)，给出三个排列a, b, c，每次x->a[y], y->b[z], z->c[x]，给出q组询问，每次询问给出x'、y'、z'，问最少经过多少秒到达(x',y',z')，若无法到达，输出-1
思路：
显然每三秒x->abc[x], y->bca[y], z->cab[z]，此时这个置换只和我当前对应的x，y，z有关，因此可以通过这个置换得到循环节大小、在一个循环里到达某一个位置的时间。然后对于每一个询问，枚举从第0秒、第1秒、第2秒开始所能到达的时间，用扩展中国剩余定理即可求得答案。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 10;
int n, q;
ll a[maxn], b[maxn], c[maxn];
ll ia[maxn], ib[maxn], ic[maxn];
ll abc[maxn], bca[maxn], cab[maxn];
ll dista[maxn], distb[maxn], distc[maxn];
ll mi[5], ai[5];
ll exgcd(ll a, ll b, ll &x, ll &y){
if(b == 0){
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a/b * x;
return d;
}
ll excrt(){
ll x, y;
ll a1 = ai[1], m1 = mi[1];
ll ans = 0;
for(int i = 2; i <= 3; i++){
ll a2 = ai[i], m2 = mi[i];
ll a = m1, b = m2, c = (a2 - a1 % m2 + m2) % m2;
ll d = exgcd(a, b, x, y);
if( c % d != 0) return -1;
x = x * (c / d) % (b / d);
ans = a1 + x * m1;
m1 = m2 / d * m1;
ans = (ans % m1 + m1) % m1;
a1 = ans;
}
return ans;
}
void query(){
cin>>q;
while(q--){
int x, y, z;
cin>>x>>y>>z;
ll t1, t2, t3;
ai[1] = dista[x];
ai[2] = distb[y];
ai[3] = distc[z];
if(ai[1] == -1 || ai[2] == -1 || ai[3] == -1) t1 = -1;
else t1 = excrt();
ai[1] = dista[ic[z]];
ai[2] = distb[ia[x]];
ai[3] = distc[ib[y]];
if(ai[1] == -1 || ai[2] == -1 || ai[3] == -1) t2 = -1;
else t2 = excrt();;
ai[1] = dista[ic[ib[y]]];
ai[2] = distb[ia[ic[z]]];
ai[3] = distc[ib[ia[x]]];
if(ai[1] == -1 || ai[2] == -1 || ai[3] == -1) t3 = -1;
else t3 = excrt();
ll ans = 1e18;
if(t1 != -1) ans = min(ans, 3 * t1);
if(t2 != -1) ans = min(ans, 3 * t2 + 1);
if(t3 != -1) ans = min(ans, 3 * t3 + 2);
if(ans == 1e18) cout<<"-1\n";
else cout<<ans<<"\n";
}
}
void solve(){
memset(dista, -1, sizeof(dista));
memset(distb, -1, sizeof(distb));
memset(distc, -1, sizeof(distc));
cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i], ia[a[i]] = i;
for(int i = 1; i <= n; i++) cin>>b[i], ib[b[i]] = i;
for(int i = 1; i <= n; i++) cin>>c[i], ic[c[i]] = i;
for(int i = 1; i <= n; i++) abc[i] = a[b[c[i]]];
for(int i = 1; i <= n; i++) bca[i] = b[c[a[i]]];
for(int i = 1; i <= n; i++) cab[i] = c[a[b[i]]];
ll ta = 0, tb = 0, tc = 0;
for(ll i = 1; dista[i] == -1; i = abc[i], ++ta) dista[i] = ta;
for(ll i = 1; distb[i] == -1; i = bca[i], ++tb) distb[i] = tb;
for(ll i = 1; distc[i] == -1; i = cab[i], ++tc) distc[i] = tc;
mi[1] = ta, mi[2] = tb, mi[3] = tc;
query();
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
M.Water
题意：
初始有两个空水杯，容量为a, b,然后要通过倒水、转移的操作喝到d容量的水，并且喝也算一次操作，问最少操作几次能喝到d的水。
思路：
显然若ax+by=d无解时输出-1。那么当有解时怎样得到操作最少呢。
当x>=0, y>=0时，ans = 2 * (x + y)；
否则，ans = 2 *abs(x - y) - 1
通过观察一次函数可以发现再原点附近的(x + y)最小。
因此，通过扩展欧几里得求得x, y后先得到原点附近的x, y,再枚举其左右两个点对答案取小。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 10;
ll n, m, k;
ll a ,b , c;
ll ans = 1e18;
ll exgcd(ll a, ll b, ll &x, ll &y){
if(b == 0){
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void calc(ll t, ll x, ll y){
ll s = x + t * b, r = y - t * a;
if(s >= 0 && r >= 0){
ans = min(ans, 2*(s + r));
}
else{
ans = min(ans, 2*(abs(s) + abs(r)) - 1);
}
}
void solve(){
cin>>n;
for(int i = 1; i <= n; i++){
ans = 1e18;
cin>>a>>b>>c;
if(a > b) swap(a, b);
ll x ,y;
ll d = exgcd(a, b ,x , y);
if(c % d != 0){
cout<<"-1\n";
continue;
}
a /= d, b /= d, c /= d, x *= c, y *= c;
ll t0 = -x / b;
for(int t = t0 - 1; t <= t0 + 1; t++){
calc(t, x, y);
}
t0 = y / a;
for(int t = t0 - 1; t <= t0 + 1; t++){
calc(t, x, y);
}
cout<<ans<<"\n";
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
//cin>>T;
while(T--){
solve();
}
return 0;
}