Codeforces-Round-483-Div-1-A-B-C

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;
}