A - Finite or not?
在除完$gcd$之后，只需要看 $q$ 的质因子是不是全部都被 $b$ 包含就行，但是注意每次要把 $b=gcd$ ，不然TLE
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long ULL;LL Gcd(LL a,LL b){if (b == 0) return a; return Gcd(b , a%b);}LL Lcm(LL a, LL b){ return a/Gcd(a,b)*b;}inline long long read(){ long long f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f;}const int maxn = 1e6 + 10;int main(){ int T = read(); while(T--){ LL p = read(),q = read(),b = read(); if (p == 0 || p % q == 0){ cout << "Finite" << endl; continue; } LL g = Gcd(p,q),tag = 0; q /= g; while(b % q != 0){ g = Gcd(b,q); if (q != 1 && g == 1){ cout << "Infinite" << endl; tag = 1; break; } b = g; q /= g; } if (!tag) puts("Finite"); } return 0;}B - XOR-pyramid
考虑$dp$处理问题，我们设 $dp[i][j]$ 是数组中以$i$ 为开头长度
为 $j+1$ 的代价，那么根据题意就有如下转移方程
$$dp[i][j] = dp[i][j-1] \bigoplus dp[i+1][j-1]$$
状态转移后重新定义$dp[i][j]$ 是数组中以$i$ 为开头，长度至少为 $j+1$ 的代价，那么就有
$$dp[i][j] = min(dp[i][j],min(dp[i][j-1],dp[i+1][j-1]))$$
最后的答案就$dp[l][r-l]$
C - Elevator
首先先考虑状态，定义状态$dp[i][j][ta][tb][tc]$ 表示当前被送走的人数加上在电梯上的人数为 $i$ ，电梯停在第 $j$ 层，里面三个人的去向分别为$ta,tb,tc$。
后面不记录4个人去向的原因是空间开不下，所以在一个人上电梯之后，必定不可能有人上电梯，这个时候枚举一个人下去，这样就可以用10x10x10的状态表示电梯上的人数状态。
考虑转移
- 如果已经送走了 $n$ 个人，那么电梯上的人不断下电梯就行
$dp(i,j,ta,tb,tc) = min(dp(i,j,ta,tb,tc),dp(i,ta,0,tb,tc) + abs(j - ta) + 1)$
$dp(i,j,ta,tb,tc) = min(dp(i,j,ta,tb,tc),dp(i,tb,ta,0,tc) + abs(j - tb) + 1)$
$dp(i,j,ta,tb,tc) = min(dp(i,j,ta,tb,tc),dp(i,tc,ta,tb,0) + abs(j - tc) + 1)$
- 如果还没有送走 $n$ 个人，那么首先枚举所有人下电梯状态如上转移方程，然后再枚举谁下电梯让新来的人上电梯,这里用$ans$指代$dp(i,j,ta,tb,tc)$
$ ans = min(ans,dp(i+1,ta,b[i+1],tb,tc) + abs(j - a[i+1]) + abs(a[i+1] - ta) + 2);$
$ ans = min(ans,dp(i+1,a[i+1],b[i+1],tb,tc) + abs(j - ta) + abs(a[i+1] - ta) + 2); $
$ ans = min(ans,dp(i+1,tb,ta,b[i+1],tc) + abs(j - a[i+1]) + abs(a[i+1] - tb) + 2);$
$ ans = min(ans,dp(i+1,a[i+1],ta,b[i+1],tc) + abs(j - tb) + abs(a[i+1] - tb) + 2) $
$ ans = min(ans,dp(i+1,tc,ta,tb,b[i+1]) + abs(j - a[i+1]) + abs(a[i+1] - tc) + 2); $
$ ans = min(ans,dp(i+1,a[i+1],ta,tb,b[i+1]) + abs(j - tc) + abs(a[i+1] - tc) + 2);$
$ ans = min(ans,dp(i+1,b[i+1],ta,tb,tc) + abs(j - a[i+1]) + abs(a[i+1] - b[i+1]) + 2);$
暴力转移即可
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long ULL;int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);}int Lcm(int a, int b){ return a/Gcd(a,b)*b;}inline long long read(){ long long f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f;}const int maxn = 2000 + 10;const int inf = 0x3f3f3f3f;int dp[maxn][10][10][10][10],a[maxn],b[maxn],n;int dfs(int i,int j,int ta,int tb,int tc){ if (dp[i][j][ta][tb][tc] != -1){ return dp[i][j][ta][tb][tc]; }else{ int ans = inf; if (i == n){ if (ta == 0 && tb == 0 && tc == 0){ return dp[i][j][ta][tb][tc] = 0; }else{ if (ta) ans = min(ans, dfs(i,ta,0,tb,tc) + abs(j - ta) + 1); if (tb) ans = min(ans, dfs(i,tb,ta,0,tc) + abs(j - tb) + 1); if (tc) ans = min(ans, dfs(i,tc,ta,tb,0) + abs(j - tc) + 1); return dp[i][j][ta][tb][tc] = ans; } }else{ if (ta) ans = min(ans, dfs(i,ta,0,tb,tc) + abs(j - ta) + 1); if (tb) ans = min(ans, dfs(i,tb,ta,0,tc) + abs(j - tb) + 1); if (tc) ans = min(ans, dfs(i,tc,ta,tb,0) + abs(j - tc) + 1); if (ta == 0){ ans = min(ans,dfs(i+1,a[i+1],b[i+1],tb,tc) + abs(j - a[i+1]) + 1); }else if (tb == 0){ ans = min(ans,dfs(i+1,a[i+1],ta,b[i+1],tc) + abs(j - a[i+1]) + 1); }else if (tc == 0){ ans = min(ans,dfs(i+1,a[i+1],ta,tb,b[i+1]) + abs(j - a[i+1]) + 1); }else{ ans = min(ans,dfs(i+1,ta,b[i+1],tb,tc) + abs(j - a[i+1]) + abs(a[i+1] - ta) + 2); ans = min(ans,dfs(i+1,a[i+1],b[i+1],tb,tc) + abs(j - ta) + abs(a[i+1] - ta) + 2); ans = min(ans,dfs(i+1,tb,ta,b[i+1],tc) + abs(j - a[i+1]) + abs(a[i+1] - tb) + 2); ans = min(ans,dfs(i+1,a[i+1],ta,b[i+1],tc) + abs(j - tb) + abs(a[i+1] - tb) + 2); ans = min(ans,dfs(i+1,tc,ta,tb,b[i+1]) + abs(j - a[i+1]) + abs(a[i+1] - tc) + 2); ans = min(ans,dfs(i+1,a[i+1],ta,tb,b[i+1]) + abs(j - tc) + abs(a[i+1] - tc) + 2); ans = min(ans,dfs(i+1,b[i+1],ta,tb,tc) + abs(j - a[i+1]) + abs(a[i+1] - b[i+1]) + 2); } return dp[i][j][ta][tb][tc] = ans; } }}int main(){ memset(dp,-1,sizeof(dp)); n = read(); for(int i=1; i<=n; i++){ a[i] = read(); b[i] = read(); } cout << dfs(0,1,0,0,0) << endl; return 0;}