Atcoder-Green

这篇博客记录下atcoder上的绿色难度的刷题记录；

ABC194 E

题解

定义\(\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)\)为不出现在\(x_1, x_2, x_3, \dots, x_k\)中的最小非负整数；

给定长度为\(n\)的序列\(A\)，求出最小的\(\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})\)；

这类不出现在指定区间的最大值、最小值，貌似一般都需要记录每个数字出现的位置；

首先记录下每个数字的位置\(t[A[i]]\)，每次让\(t[A[i]]++,t[A[i-m]]--\)；并且用\(ans\)记录当前的\(mex\)，如果\(t[A[i-m]]=0\)，那么\(A[i-m]\)不出现在当前\(\text{mex}\)序列中，并且如果\(A[i]\le ans\)，那么它比ans更优；

code

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int N = 2e6 + 5;
typedef pair < int , int > pe;
typedef long long ll;

ll a[N] , dp[N], num[N];
void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n ; ++ i){
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 0; i < m; ++ i){
        dp[a[i]] ++ ;
        if(a[i] == ans){
            ans ++;
            while(dp[ans]) ans ++;
        }
    }
    for(int i = m; i < n; ++ i){
        dp[a[i - m]] -- ;
        dp[a[i]] ++;
        if(dp[a[i - m]] == 0 && ans > a[i - m]){
            ans = a[i - m];
        }
    }
    cout << ans << endl;
}


int main(){
    solve();
    return 0;
}

ABC188 D

题解

code

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main(){
    ll N, C;
    cin >> N >> C;
    vector<pair<ll, ll>> event;
    for(ll i = 0; i < N; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        event.emplace_back(a - 1, c);
        event.emplace_back(b, -c);
    }
    sort(event.begin(), event.end());
    ll ans = 0, fee = 0, t = 0;
    for(auto [x, y] : event){
        if(x != t){
            ans += min(C, fee) * (x - t);
            t = x;
        }
        fee += y;
    }
    cout << ans << endl;
}

ABC188 E

题解

给了一个\(n\)个点的有向图，以及每个点的权值\(A[i]\)，一开始可以在任意一个点花费\(A[i]\)买黄金，之后通过有向图到达其他点，再在某个点\(j\)卖出黄金获得\(A[j]\)的金钱；问这个过程最多可以获利多少钱；

整张图可能是由若干个连通量构成；因为一开始可以在任意一点，那么最好的情况就是肯定一开始在买入的地方，那么贪心的想，它肯定权值\(A\)尽可能小，之后从最小点开始枚举（需要一个\(vis\)来剪枝），进行\(bfs\)，每次记录遍历到当前点之前的最小的\(A\)作为买入的值\(buy\)，然后每到一个点\(v\)，用\(A[v]-buy\)来更新\(answer\)；

用\(bfs\)也可以，从具有最小的\(A[i]\)的点\(i\)出发，遍历从\(i\)出发能到达的所有点\(j\)，更新\(ans=A[j] - A[i]\)；然后第二次从具有第二小\(A\)的点出发，并且这一次，不用访问那些从\(i\)出发能到达的点（因为上次一从最小权值开始出发）；

另外一种做法就是，由于题目告诉我们\(x_i \lt y_i\)，那么我们可以从\(1\)到\(n\)遍历点，同时遍历点\(i\)所出去的边，对于点\(u\)，求出在访问\(u\)之前的点中，买入所需的最小价格\(buy\)（不包括\(u\)），之后拿\(A[u]-buy\)更新\(ans\)；

code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m, A[200005], vis[200005];
int ans = -0x3f3f3f3f;
vector<int> vec[200005];

void dfs(int x, int buy) {
    vis[x] = 1;
    for (int i = 0; i < vec[x].size(); i++) {
        int v = vec[x][i];
        if (!vis[v]) {
            ans = max(ans, A[v] - buy);
            dfs(v, min(buy, A[v]));
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    vector<int> vex;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        vec[x].push_back(y);
        vex.push_back(x);
    }
    sort(vex.begin(), vex.end(), [](int a, int b) {
        return A[a] < A[b];
    });
    for (auto &u: vex) {
        if (!vis[u]) {
            dfs(u, A[u]);
        }
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <cstdint>
#include <iomanip>
#include <sstream>
#include <string>
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using P = pair<int, int>;
const int INF = 1001001001;
const int mod = 1e9 + 7;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    rep(i, n) { cin >> a[i]; }
    vector<vector<int>> G(n);
    rep(i, m) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        G[x].push_back(y);
    }
    vector<ll> buy(n, 1e18);
    ll ans = -1e18;
    rep(i, n) {
        chmax(ans, a[i] - buy[i]);
        for (int u : G[i]) {
            chmin(buy[u], min(buy[i], a[i]));
        }
    }
    cout << ans << endl;
    return 0;
}

ABC185 F

题解

方法很多，线段树、树状数组（才知道树状数组还叫作\(Fenwick tree\)）；异或的性质应用到区间之上；定义\(f(i) = A_1 \oplus A_2 \oplus A_3 \oplus \dots \oplus A_i\)，那么\([x_i,y_i]\)之间的答案就是\(f(Y_i) \oplus f(X_i - 1)\);

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 300005;
int n, q, A[MAX];
void update(int pos, int val) {
    for (int  x = pos; x <= n; x += x & -x) {
        A[x] ^= val;
    }
}
int sum(int pos) {
    int ans = 0;
    for (int x = pos; x; x -= x & -x)
        ans ^= A[x];
    return ans;
}
int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        update(i, x);
    }
    for (int i = 1; i <= q; i++) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1)
            update(x, y);
        else {
            cout << (sum(y) ^ sum(x - 1)) << endl;
        } 
    }        
}

ABC193 D

题解

暴力即可，枚举\(s\)与\(t\)的可能情况；

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 100005;

int k, cnt[11][2], ans[11][2];

int main() {
    freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    cin >> k;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < 4; i++) {
        cnt[s[i] - '0'][0]++;
        cnt[t[i] - '0'][1]++;
    }
    int anst = 0, anss = 0;
    int cnttemp[11] = {0};
    for (int i = 1; i <= 9; i++) {
        ans[i][0] = i * pow(10, cnt[i][0]);
        ans[i][1] = i * pow(10, cnt[i][1]);
        anss += ans[i][0];
        anst += ans[i][1];
        cnttemp[i] = k - cnt[i][0] - cnt[i][1];
    }
    int ltc = 9 * k - 8;
    ll all_cnt = 1ll * ltc * (ltc - 1);
    ll x = 0;
    for (int i = 1; i <= 9; i++) {
        if (cnttemp[i]) {
            for (int j = 1; j <= 9; j++) {
                if (anss + 9 * ans[i][0] > anst + 9 * ans[j][1]) {
                    if (i == j and cnttemp[j] >= 2) {
                        x += 1ll * cnttemp[i] * (cnttemp[i] - 1);
                    } else if (i != j and cnttemp[j]) {
                        x += 1ll * cnttemp[i] * cnttemp[j];
                    }
                }
            }
        }
    }
    cout << 1.0 * x / all_cnt << endl;
}

官方代码。。。。

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
using ll = int64_t;

ll score(string S){
    vector<ll> cnt(10);
    iota(cnt.begin(), cnt.end(), 0);
    for(char c : S) cnt[c - '0'] *= 10;
    return accumulate(cnt.begin(), cnt.end(), 0);
}
int main(){
    ll K;
    string S, T;
    cin >> K >> S >> T;
    vector<ll> cnt(10, K);
    for(char c : S + T) cnt[c - '0']--;
    ll win = 0;
    for(ll x = 1; x <= 9; x++) for(ll y = 1; y <= 9; y++){
        S.back() = '0' + x;
        T.back() = '0' + y;
        if(score(S) <= score(T)) continue;
        win += cnt[x] * (cnt[y] - (x == y));
    }
    const ll rem = 9 * K - 8;
    cout << double(win) / rem / (rem - 1) << endl;
}

K = int(input())
S = input()[:4]
T = input()[:4]
cnt = [K] * 10
for c in S:
    cnt[int(c)] -= 1
for c in T:
    cnt[int(c)] -= 1

def score(S):
    cnt = [0] * 10
    for c in S:
        cnt[int(c)] += 1
    ans = 0
    for i in range(1, 10):
        ans += i * 10 ** cnt[i]
    return ans

ans = 0

for i in range(1, 10):
    if cnt[i] == 0:
        continue
    for j in range(1, 10):
        if i == j or cnt[j] == 0:
            continue
        if score(S + str(i)) > score(T + str(j)):
            ans += cnt[i] * cnt[j]

for i in range(1, 10):
    if cnt[i] < 2:
        continue
    if score(S + str(i)) > score(T + str(i)):
        ans += cnt[i] * (cnt[i] - 1)

N = 9 * K - 8
print(ans / N / (N - 1))

ABC182 E

题解

code

#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

int H,W,N,M;
int ver[1500][1500];
int sid[1500][1500];
int des[1500][1500];

void vertical(int x,int y){
    if(x<0 || H<=x || des[x][y] || ver[x][y])return;
    ver[x][y]=1;
    vertical(x+1,y);
    vertical(x-1,y);
}

void side(int x,int y){
    if(y<0 || W<=y || des[x][y] || sid[x][y])return;
    sid[x][y]=1;
    side(x,y+1);
    side(x,y-1);
}

int main(){
    cin>>H>>W>>N>>M;
    vector<P>L;
    rep(i,N){
        int a,b;
        cin>>a>>b;a--;b--;
        L.push_back({a,b});
    }
    rep(i,M){
        int c,d;
        cin>>c>>d;c--;d--;
        des[c][d]=1;
    }

    rep(i,N){
        vertical(L[i].first,L[i].second);
        side(L[i].first,L[i].second);
    }

    int ans=0;
    rep(i,H){
        rep(j,W){
            ans+=(ver[i][j]||sid[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

ABC181 E

题解

一种自然的想法就是，将\(n\)个人的身高\(h\)排序，然后枚举\(w_i\)，插入\(h\)中，求出所有情况下的最小值；

但是其实可以不用每次都求一边答案；其实只需要考虑插入位置；比如对于a b c x d e和a b x c d e；只需要预处理\(|H_{2i-1}-H_{2i}|\)和\(|H_{2i}-H_{2i+1}|\)，这种题第一次见；这题标答还给了滑动窗口的解法；

code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
void chmin(int& a, int b){ if(a > b){ a = b; } }

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    for(auto& h : H) cin >> h;
    vector<int> W(M);
    for(auto& w : W) cin >> w;
    sort(H.begin(), H.end());
    vector<int> sum1((N + 1) / 2), sum2((N + 1) / 2);
    for(int i = 0; i + 1 < N; i += 2) sum1[i / 2 + 1] = sum1[i / 2] + H[i + 1] - H[i];
    for(int i = N - 2; i > 0; i -= 2) sum2[i / 2] = sum2[i / 2 + 1] + H[i + 1] - H[i];
    int ans = INF;
    for(int w : W){
        int x = lower_bound(H.begin(), H.end(), w) - H.begin();
        if(x & 1) x ^= 1;
        chmin(ans, sum1[x / 2] + sum2[x / 2] + abs(H[x] - w));
    }
    cout << ans << endl;
}

ABC178 E

题解

求曼哈顿距离，比较经典； https://www.cnblogs.com/tanhehe/archive/2013/05/25/3099400.html

code

n = int(input())

t1 = []
t2 = []
for i in range(n):
    x, y = map(int, input().split())
    t1.append(x - y)
    t2.append(x + y)
t1.sort()
t2.sort()

print(max(t1[-1] - t1[0], t2[-1] - t2[0]))