AtCoder Beginner Contest 263（A~F）

• A Full House
• • 思路
  • 代码
• B Ancestor
• • 思路
  • 代码
• C Monotonically Increasing
• • 思路
  • 代码
• D Left Right Operation
• • 大意
  • 思路
  • 代码
• E Sugoroku 3
• • 大意
  • 思路
  • 代码
• F - Tournament
• • 大意
  • 思路
  • 代码

链接：ABC263

对五个数排序,判断 a [ 1 , 2 , 3 ] , a [ 4 , 5 ] a[1,2,3],a[4,5] a[1,2,3],a[4,5]相等且 a [ 3 ] ! = a [ 4 ] a[3]!=a[4] a[3]!=a[4]，或 a [ 1 , 2 ] , a [ 3 , 4 , 5 ] a[1,2],a[3,4,5] a[1,2],a[3,4,5]相等且 a [ 2 ] ! = a [ 3 ] a[2]!=a[3] a[2]!=a[3].

#include 
#include 
using namespace std;
#define ll long long
int a[100];
int main()
{
    int x;
    for(int i=1;i<=5;i++){
        cin >> a[i];
    }
    sort(a+1,a+1+5);
    if((a[1]==a[2] && a[3]==a[5] && a[2] != a[3]) || (a[1] == a[3] && a[4] == a[5] && a[3] != a[4]))puts("Yes");
    else puts("No");
    return 0;
}

dfs从根节点向下递归，设置 d e p [ 1 ] = 0 dep[1] = 0 dep[1]=0并记录深度最后输出 d e p [ n ] dep[n] dep[n]即可

#include 
#include 
#include 
using namespace std;
vectorg[100];
int dep[100];
void dfs(int u,int d)
{
    dep[u] = d;
    for(int v : g[u]){
        dfs(v,d+1);
    }
}
int main()
{
    int n;
    cin >> n ;
    for(int i=2;i<=n;i++)
    {
        int x;
        cin >> x;
        g[x].push_back(i);
    }
    dfs(1,0);
    cout << dep[n];
    return 0;
}

dfs递归时两个参数id,sum,分别代表当前可选的最小的值，和当前选定的值的位置，选定的数用数组记录 a [ s u m ] = i a[sum] = i a[sum]=i递归到最后输出数组即可

#include 
#include 
using namespace std;
int a[15];
int n,m;
void dfs(int id,int sum)
{
    if(sum == n + 1){
        for(int i=1;i<=n;i++)printf("%d ",a[i]);
        puts("");
        return ;
    }
    for(int i=id;i<=m;i++){
        a[sum] = i;
        dfs(i+1,sum+1);
    }
}
int main()
{
    cin >> n >> m;
    dfs(1,1);
    return 0;
}

给定长度为 n n n的数组 a a a，可以选定 L L L将 [ 1 , L ] [1,L] [1,L]区间的数置换为 X X X,选定 R R R将 [ R , n ] [R,n] [R,n]区间的数置换为 Y Y Y，对于两种操作可以任意选择操作与否。询问数组可能的最小的和是多少。

预处理好操作一的最优前缀,即 b [ i ] b[i] b[i]代表前i个数都置换为 X X X的相比原数组改变的价值，再对前缀求最优值 v a l 1 [ i ] = m a x ( v a l 1 [ i ] , b [ 1 ] , b [ 2 ] , . . . . , b [ i ] ) val1[i] = max(val1[i] , b[1],b[2],....,b[i]) val1[i]=max(val1[i],b[1],b[2],....,b[i])
此时再处理一遍最优后缀,设 s u m = ∑ a [ i ] sum = ∑a[i] sum=∑a[i] ， a n s = s u m − v a l 1 [ i − 1 ] + v a l 2 [ i ] ans = sum - val1[i-1] + val2[i] ans=sum−val1[i−1]+val2[i]取最优。

#include 
#include 
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int a[N];
ll val[N];
int main()
{
    int n;
    ll L,R;
    cin >> n >> L >> R;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        ans += a[i];
        val[i] = ans - (L * i);//置换为X的最优前缀
        val[i] = max(val[i],val[i-1]);
    }
    ll sum = 0,res = 0;//res即代表最优后缀，只用一遍就可以即用即算不用数组存储
    ll answer = min(ans , L * n);
    for(int i=n;i>=1;i--)
    {
        sum += a[i];
        res = max(res,sum - R * (n - i + 1));
        answer = min(answer , ans - res - val[i - 1]);
    }
    cout << answer;
    return 0;
}

在 n n n个方格上掷骰子，骰子的点数为 [ 0 , a [ i ] ] [0,a[i]] [0,a[i]] 掷的点数随机,初始在第 1 1 1个格子走到第 n n n个格子前重复进行掷骰子的动作。问掷骰子次数的期望,保证 1 ≤ a i ≤ n − i ( 1 ≤ i ≤ n − 1 ) 1≤ai≤n−i(1≤i≤n−1) 1≤ai≤n−i(1≤i≤n−1)。

对于每个格子，我们掷骰子的各点数的概率为 p i = 1 / ( a [ i ] + 1 ) pi = 1 / (a[i] + 1) pi=1/(a[i]+1)即掷一次骰子到 i i i~ a [ i ] + i a[i]+i a[i]+i的概率相同，设从当前格子出发到 n n n的掷骰子期望为 F [ i ] F[i] F[i]。则有公式: F [ i ] = p i ∗ ( ( F [ i ] + 1 ) + ( F [ i + 1 ] + 1 ) + . . . . + F [ i + 1 + a [ i ] ] + 1 ) F[i] = pi * ((F[i] + 1) + (F[i+1]+1)+....+F[i+1+a[i]]+1) F[i]=pi∗((F[i]+1)+(F[i+1]+1)+....+F[i+1+a[i]]+1)。
这里解释一下各项的含义：
设 i = 1 且 a [ i ] = 1 i = 1且a[i] = 1 i=1且a[i]=1 那么我们期望 F [ 1 ] = p i ∗ ( F [ 1 ] + 1 ) + p i ∗ ( F [ 2 ] + 1 ) F[1] = pi * (F[1] + 1) + pi * (F[2] + 1) F[1]=pi∗(F[1]+1)+pi∗(F[2]+1)。 第一项的含义:掷出 0 0 0留在原地不动的概率 * （从 1 1 1开始到 n n n的期望 + 本次掷的一次）。
同理第二项：掷出 1 1 1走到格子 2 2 2的概率 * （从 2 2 2开始到 n n n的期望 + 本次掷的一次）
我们可以从后往前求出各点的 F [ i ] F[i] F[i]，因为已知 F [ n ] = 0 F[n] = 0 F[n]=0。所以公式的未知项只有 F [ i ] F[i] F[i],式子中的各个 F i Fi Fi之和可以用后缀和记录,化简一下公式求解即可。

#include 
#include 
using namespace std;
#define ll long long
const int N = 2e5 + 10,MOD = 998244353;
ll ksm(ll a,ll b)//求逆元
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = (a % MOD) * (ans % MOD) % MOD;
        a = (a % MOD) * (a % MOD);
        b >>= 1;
    }
    return ans;
}
ll a[N],F[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i
        scanf("%lld",&a[i]);
    }
    F[n] = 0;
    for(int i=n-1;i>=1;i--){
        F[i] = (F[i + 1] + MOD - F[i + a[i] + 1] + a[i] + 1)%MOD * ksm(a[i],MOD - 2) % MOD;//公式
        if(i == 1){
            printf("%lld",F[1]);
        }
        F[i] = (F[i] + F[i + 1]) % MOD;//F[i]用作记录后缀和
    }
    return 0;
}

相邻两两决斗,输的被淘汰，直到决出最后的胜者。对于每个人胜利次数 k k k都会有 c [ i ] [ k ] c[i][k] c[i][k]的奖励，问任意决定决斗胜负情况得到的最大价值是多少。

可以将比赛过程看做是一棵n层的满二叉树,获胜者两两决斗直到最终获胜者出现 转化为树形DP
我们从第0层(比赛的最终胜者层) 开始向下一层递归 树形DP思想先处理好下一层的数据再向上转移。具体思路和代码实现都在代码注释中。

#include 
#include 
using namespace std;
#define ll long long
const int N = 1<<17;
int n,c[N][20];

ll f[20][N];//f[i][j]:第i层j是获胜者的最大价值
void dfs(int l,int r,int d)
{
    if(r - l == 1){//最底下一层就是相邻两两比赛,根据f定义,f[d][i]等于各自胜利一场的价值
        f[d][l] = c[l][1];
        f[d][r] = c[r][1];
        return ;
    }

    //先递归到下一层
    int mid = (l + r) >> 1;
    dfs(l,mid,d+1);
    dfs(mid+1,r,d+1);

    

    ll val1 = 0,val2 = 0;
    for(int i=l;i<=mid;i++) val1 = max(val1 , f[d+1][i]);
    for(int i=mid+1;i<=r;i++) val2 = max(val2 , f[d+1][i]);
    
    int k = n - (d + 1);
    //枚举胜者 + 另一区间败者的最大价值
    for(int i=l;i<=mid;i++){
        f[d][i] = f[d+1][i] - c[i][k] + c[i][k+1] + val2;
    }
    for(int i=mid+1;i<=r;i++){
        f[d][i] = f[d+1][i] - c[i][k] + c[i][k+1] + val1;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=1<
        ans = max(ans , f[0][i]);
    }
    printf("%lldn",ans);
    return 0;
}