AtCoder Beginner Contest 369 补题记录

标签：AtCoder Beginner int 等差数列偶数 read 补题序列 dp

A - 369

题意：

给定A和B,求有多少个x可以和A,B构成等差数列

思路：

分三种情况讨论

A == B
则x不得不与A和B想等
x位于A和B中间
只有B - A 为偶数才有这种情况存在
x位于A和B两边
可以在左边也可以在右边，只要A!=B这种情况总会存在

void solve()
{
    int a = read(), b = read();

    if(a == b){
        cout<<1<<endl;
    }else {
        if((b-a)&1){
            cout<<2<<endl;
        }else {
            cout<<3<<endl;
        }
    }
}

B - Piano 3

题意：

高桥有一架钢琴，上面有 \(100\) 个排成一行的琴键。从左边开始的 \(i\) 个键叫做 \(i\) 个键。
他会逐个按下 \(N\) 个键来弹奏音乐。在按下 \(i\) /th键时，如果 \(S_i=\) L，他会用左手按下 \(A_i\) 键，如果 \(S_i=\) R，则用右手按下 \(A_i\) 键。
开始演奏前，他可以将双手放在任何他喜欢的键上，此时他的疲劳度为 0。在演奏过程中，如果他将一只手从键 \(x\) 移到键 \(y\) 上，疲劳度会增加 \(|y-x|\) （反之，除了移动手以外，疲劳度不会增加）。用手按下某个键时，该手必须放在该键上。
找出表演结束时可能的最低疲劳度。

思路：

考虑到

\(1 \leq N \leq 100\)
\(1 \leq A_i \leq 100\)

直接暴力枚举每个按键为初始按键,左右手各枚举100个键，再遍历n遍，最高1e6

代码：

void solve()
{
    int n = read();
    vector<pair<int,char> > v;
    for(int i=0;i<n;i++){
        int a = read();
        char c; cin>>c;
        v.push_back({a,c});
    }

    int ans = INF;
    for(int i=1;i<=100;i++) for(int j=1;j<=100;j++){
        int ret = 0, l = i, r = j;
        for(auto it:v){
            if(it.se == 'L'){
                ret += abs(l - it.fi);
                l = it.fi;
            }else {
                ret += abs(r - it.fi);
                r = it.fi;
            }
        }
        ans = min(ret,ans);
    }

    cout<<ans<<endl;

}

C - Count Arithmetic Subarrays

题意：

给一个长度为n的序列，求能构成等差数列的子序列的个数

思路：

显然每个长度为1和长度为2的子序列都能构成等差数列，所以答案至少是 \(n+(n-1)\)
再去找每个长度大于等于3并且能构成等差数列的子序列，长度为n的等差数列子序列能拆分成 \(1+2+3+...+n\) 个等差子序列，去除已经计算的长度为1和2的子序列，能拆分成 \(1+2+3+...+(n-2)\)个
找等差子序列的过程类似于滑动窗口，维护 \(l\) 和 \(r\) 两个指针即可

代码：

void solve()
{
    int n = read();
    vector<int> v;
    for(int i=0;i<n;++i) v.emplace_back(read());
    
    int ans = n + n - 1;
    if(n <= 2){
        cout<<ans<<endl;
        return;
    }
    int l = 0 , r = 1 , d = v[r] - v[l];
    bool flag = 0;
    while(r < n && l < n){
        int dt = v[r] - v[r-1];
        if(dt == d){
            flag = 1;
        }else {
            flag = 0;
            if(r - l > 2){
                int t = r - l - 2;
                ans += (t+1)*t/2;
            }
            l = r - 1;
            d = v[r] - v[l];
        }
        r++;
    }
    if(r - l > 2 && flag){
        int t = r - l - 2;
        ans += (t+1)*t/2;
    }
    cout<<ans<<endl;
}

D - Bonus EXP

题意：

给一个长度为n的序列，在序列中从前往后取数。对于序列中的每个数，可以取也可以不取。对于所有取了的数，将所有第偶数次取的数乘2，再将所有取了的数求和，求该如何取数使这个和最大

思路：

线性dp

对于序列中每个数和上一个数之间的关系，只有取的次序是奇数还是偶数对该数有影响
所以只需要维护取到每个数的两种状态值，即到奇数次还是偶数次
- 奇数次：
  1. 上一个数是偶数次，本次取这个数
  2. 上一个数是奇数次，本次不取
- 偶数次：
  1. 上一个数是奇数次，本次取这个数
  2. 上一个数是偶数次，本次不取
状态转移方程：
dp[i][0] = max(dp[i-1][1] + 2*v[i], dp[i-1][0]); //偶数次
dp[i][1] = max(dp[i-1][0] + v[i], dp[i-1][1]); //奇数次

代码：

void solve()
{
    int n = read();
    vector<int> v;
    for(int i=0;i<n;++i) v.emplace_back(read());
    
    vector<vector<int> > dp(n,vector<int>(2));
    dp[0][1] = v[0];
    dp[0][0] = 0;
    for(int i=1;i<n;i++){
        dp[i][0] = max(dp[i-1][1] + 2*v[i], dp[i-1][0]);
        dp[i][1] = max(dp[i-1][0] + v[i], dp[i-1][1]);
    }

    int ans = max(dp[n-1][1],dp[n-1][0]);

    cout<<ans<<endl;
}

E - Sightseeing Tour

思路：

全排列+floyd

F - Gather Coins

思路：

第一维排序，第二维度LIS
用二分或树状数组优化LIS，达到 \(O(nlogn)\) 复杂度

G - As far as possible

思路：

行走的长度为 \(根到顶点的每个路径的集合的总权值*2\)
树剖-长链剖分，每个顶点指向最深的叶子顶点

标签：AtCoder,Beginner,int,等差数列,偶数,read,补题,序列,dp
From： https://www.cnblogs.com/klri/p/18391496