AtCoder Beginner Contest 240 解题报告

第一次参加，感觉atcoder的题还是有ACM那味

A - Edge Checker

知识点：模拟
效率：$O(1)$
题意是一个约瑟夫环，给你两个数看是否相邻。
直接判断是否为(a+1) % N == b or (b+1) % N == a

#include <iostream>
using namespace std;
int main() {
    int a,b;
    cin >> a >> b;
    a--,b--;
    bool flag = false;
    if(a==(b+1)%10||b==(a+1)%10) flag = true;
    cout << (flag?"Yes":"No");
    return 0;
}

B - Count Distinct Integers

知识点：Set
效率：$O(nlogn)$
给你一组数，让你判断不同的数有多少个。
使用set即可

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;
    int n;
    cin >> n;
    int tmp;
    while(n--) cin >> tmp,s.insert(tmp);
    cout << s.size();
    return 0;
}

C - Jumping Takahashi

知识点：动态规划
效率：$O(n^2)$，一次倒序遍历，一次正序遍历，一次交换
给你两组数a，b，共选i次，你只能且必须从a[i],b[i]中选择一个数加到总和中，问最后是否能达到n
背包问题裸模板，要么选a[i]，要么选b[i]，问最后能到达n

#include <iostream>
#include <vector>
using namespace std;
vector<int> a,b,dp;
int N,X;
bool flag = false;
int main() {
    cin >> N >> X;
    a =  vector<int>(N+1,0);
    b =  vector<int>(N+1,0);
    dp =  vector<int>(X+1,0);
    for(int i = 0;i < N;i++) {
        cin >> a[i] >> b[i];
    }
    dp[0] = 1;
    for(int i =0 ;i < N;i++) {
        for(int j = X; j >= 0;j--) {
            if(j-a[i] >= 0) dp[j]=max(dp[j],dp[j-a[i]]+1);
            if(j-b[i] >= 0) dp[j]=max(dp[j],dp[j-b[i]]+1);
        }
    }
    //for(int j = 0; j <= X;j++) {
     //   cout << dp[j] << " ";
    //}
    cout << (dp[X]>N?"Yes":"No");
    return 0;
}

D - Strange Balls

知识点：栈、模拟
效率：$O(n)$

是一个栈，当push进去一个数$$n$$的时候，假如有$$n$$个$$n$$，那么就把他们全弹出去，类似于消消乐。
直接根据题意模拟即可，然后最后输出每次处理完成后的位置。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> data(N,0);
    for(int i = 0;i < N;i++) cin >> data[i];
    int last = -1,repeat = -1;
    stack<pair<int,int>> s;
    s.push({-1,-1});
    int nowPos = 0;
    for(auto n:data) {
        auto x = s.top();
        last = x.first,repeat = x.second;
        nowPos++;
        if(n!=last) {
            repeat = 1;
            s.push({n,1});
        }
        else {
            s.pop();
            repeat++;
            s.push({n,repeat});
        }
        last = n;
        if(repeat == last) {
            s.pop();
            nowPos-=last;
            last = -1,repeat=-1;
        }
        cout << nowPos << "\n";
    }
    return 0;
}

E - Ranges on Tree

知识点：树、DFS
效率：$O(n)$

问题简化为所有叶子节点均为(i,i++)，然后具有叶子节点的节点取所有叶子节点的(最小值,最大值)。
直接DFS搜索即可

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
vector<pair<ll,ll>> ans;
vector<vector<ll>> mp;
int n = 1;
void dfs(ll lst,ll now) {
    //cout << lst << " " << now << "\n";
    int cnt = 0;
    for(auto i : mp[now]) {
        if(i==lst) continue;
        cnt++;
        //cout << now << "->" << i << "\n";
        dfs(now,i);
        ans[now].first = min(ans[now].first,ans[i].first);
        ans[now].second = max(ans[now].second,ans[i].second);
    }
    if(cnt == 0) {
        ans[now] = {n, n};
        n++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b;
    ll T;
    cin >> T;
    ll N = T;
    mp = vector<vector<ll>>(T+1,vector<ll>());
    ans = vector<pair<ll,ll>>(T+1,{INT64_MAX,INT16_MIN});
    N--;
    while(N--) {
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    dfs(0,1);
    for(int i = 1;i <= T;i++) cout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}

F - Sum Sum Max

知识点：数学、函数性质
效率：$O(n)$

假如暴力发现时间复杂度太高，因此进行归纳
数学归纳

已知:

$B_i = \sum_{k=1}^iC_k \\ A_i = \sum_{k=1}^iB_k \\$

可得:

$A_i = \sum_{k=1}^iB_k = B_1 + B_2 + ... + B_k = \sum_{j=1}^kC_1 + \sum_{j=1}^{k-1}C_2 + ... + \sum_{j=1}^1C_k \\$

可以发现B序列类似于A序列的导数(离散)，C序列类似于B序列的导数(A序列的二阶导数)。
该问题问A序列最大值，因此根据极值的规律，找到所有导数（即B序列）为0的端点，求A值，并比较哪个最大。
因为该序列是离散的，可能不会出现$B_i$恰好是0的情况，因此可以找0附近的每一个端点，再加之每一个给定区间里的第一个点和最末点，将这些点进行比较。

#include <iostream>
#include <vector>
#include <stack>
#define ll long long
#define P pair<ll,ll>
using namespace std;
void solve() {
    ll sm[2] = {0};
    ll M,N;
    cin >> N >> M;
    ll s = 0;
    ll sa = 0;
    ll a,b;
    ll ans = INT64_MIN;
    for(int i = 0; i < N;i++){
        cin >> a >> b;
        if (a < 0 && sa >= 0) {
            ll t = max(min(sa/(-a),b),1ll);
            ans=max(ans,s + sa * t + a * t * (t + 1ll) / 2ll);
        }
        ll t = (((b+1ll)*b)/2ll);
        s += b * sa + a * t;
       // cout << s << " ";
        ans = max(ans,s);
        sa += a*b;
    }
    cout << ans << "\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}