526互联

Codeforces Round 888 (Div. 3)

发布时间 2023-07-26 19:58:43作者: PHarr

A. Escalator Conversations

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int n , m , k ,H;
    cin >> n >> m >> k >> H;
    vector<int> h(n);
    int res = 0;
    for( int h , i = 1 ; i <= n ; i ++ ){
        cin >> h;
        h = abs( h - H );
        if( h % k != 0 || h == 0 )continue;
        if( (h / k) < m ) res ++ ;
    }
    cout << res << "\n";
    return ;

}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while( t -- )
        solve();

    return 0;

}

B. Parity Sort

把奇偶分别排序在重新放回去

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b, c;
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        a[i] = x & 1;
        if (a[i]) b.push_back(x);
        else c.push_back(x);
    }
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    for( int i = 0 , j = 0 , k = 0 ; i < n ; i ++ ){
        if( a[i] ) a[i] = b[j] , j ++;
        else a[i] = c[k] , k ++;
    }
    for( int i = 1 ; i < n ; i ++ ){
        if( a[i] < a[i-1] ) {
            cout << "NO\n";
            return ;
        }
    }
    cout << "YES\n";
    return ;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

另一种更简洁的思路就是排序后，判断排序前后数组每一位的奇偶性是否相同

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    auto b = a;
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++)
        if ((a[i] - b[i]) & 1) {
            cout << "NO\n";
            return;
        }


    cout << "YES\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Tiles Comeback

贪心的选择前缀和c[1]相同的、后缀和c[n]相同的。

特判一下c[1]==c[n]的情况

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];
    int l = -1, r = -1;
    for (int i = 1, cnt = 0; l == -1 && i <= n; i++) {
        if (c[i] == c[1]) cnt++;
        if (cnt == k) l = i;
    }
    for (int i = n, cnt = 0; r == -1 && i >= 1; i--) {
        if (c[i] == c[n]) cnt++;
        if (cnt == k) r = i;
    }

    if (l == -1 || r == -1)
        cout << "NO\n";
    else if (c[1] == c[n])
        cout << "YES\n";
    else if (l < r)
        cout << "YES\n";
    else
        cout << "NO\n";

    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. Prefix Permutation Sums

先差分回去，统计缺少的数字数量。

  1. 缺大于 2 个 ，无解
  2. 缺2个，检查缺的数字之和和多的数字之和是否相同
  3. 缺 1 个，此时多的数字应该是0
  4. 不缺，不存在
#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), vis(n + 1);
    int x = 0, y = n * (n + 1) / 2, z = n;
    for (int i = 1; i < n; i++) cin >> a[i];
    for (int i = n - 1; i > 1; i--) a[i] = a[i] - a[i - 1];
    for (int i = 1; i < n; i++) {
        if (a[i] > n) x += a[i];
        else if (vis[a[i]] == 0) vis[a[i]] = 1, y -= a[i], z--;
        else x += a[i];
    }
    if (z > 2) cout << "NO\n";
    else if (x == y) cout << "YES\n";
    else if (z == 1 && x == 0) cout << "YES\n";
    else cout << "NO\n";

    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. Nastya and Potions

把无限供应的药品的cost修改为 0，合成药品的关心其实可以看做有向图，建反向图，在反向图上跑拓扑序，根据拓扑序去计算每种药品获得的最小代价。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> cost(n + 1), v(n + 1, -1);
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    for (int i = 1, x; i <= k; i++)
        cin >> x, cost[x] = 0;
    vector<vector<int>> e(n + 1), g(n + 1);
    vector<int> inner(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> inner[i];
        for (int j = 0, x; j < inner[i]; j++)
            cin >> x, e[i].push_back(x), g[x].push_back(i);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (inner[i] == 0) q.push(i);

    while (!q.empty()) {
        int i = q.front();
        q.pop();
        if (!e[i].empty()) {
            int sum = 0;
            for (auto j: e[i])
                sum += cost[j];
            cost[i] = min(cost[i], sum);
        }

        for (auto j: g[i]) {
            inner[j]--;
            if (inner[j] == 0) q.push(j);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << cost[i] << " ";
    cout << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

F. Lisa and the Martians

首先\((a_i\oplus x)\&(a_j\oplus x )= a_i\odot a_j =\overline{(a_i\oplus a_j)}= y\)，所以\(y\)实际上就是同或最大值或者异或的最小值。

同时可以知道\(x=(a_i \oplus y ) | (a_j \oplus y)\)

数组中任意两数异或的最小值一定是排序后的相邻数的异或

根据这个性质就很好求了。

求异或最小值

#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef bitset<30> Num;
vector<int> Temp(31);

void solve() {
    int n, k;
    cin >> n >> k;
    int T = (1ll << k) - 1;
    vector<pair<int,int>> a;
    for( int i = 1 , x ; i <= n ; i ++ )
        cin >> x , a.emplace_back( x , i );
    sort( a.begin(), a.end() );
    int l , r , res = INT_MAX , val;
    for( int i = 1 ; i < n ; i ++ ){
        if( res > (a[i].first^a[i-1].first)){
            res = a[i].first ^ a[i-1].first;
            l = a[i].second , r = a[i-1].second;
            val = T ^ ( a[i].first | a[i-1].first );
        }
    }
    cout << l << " " << r << " " << val << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

求同或最大值

#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef bitset<30> Num;
vector<int> Temp(31);

void solve() {
    int n, k;
    cin >> n >> k;
    int T = (1ll << k) - 1;
    vector<pair<int, int>> a;
    for (int i = 1, x; i <= n; i++)
        cin >> x, a.emplace_back(x, i);
    sort(a.begin(), a.end());
    int l, r, res = INT_MIN, val;
    for (int i = 1, t; i < n; i++) {
        t = (~(a[i].first ^ a[i - 1].first)) & T;
        if (t > res) {
            res = t;
            l = a[i].second, r = a[i - 1].second;
            val = (a[i].first ^ t) | (a[i - 1].first ^ t);
        }
    }
    cout << l << " " << r << " " << val << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G. Vlad and the Mountains

首先可以知道的是，从\(a\)出发可能到达的点\(i\)一定满足\(h[i]\le h[a] + e\)

对于每条边\(i\)，记\(w_i=\max( h[u_i],h[v_i])\)，这样的话从\(a\)出发可以走的边一定满足\(w_i\le h[a]+e\)

取所用复合条件的边，用并查集维护，最后检查 \(a,b\)是否联通即可。

为了优化，可以离线询问，按照\(h[a]+e\)从小到大的顺序回答即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

class dsu {
private:
    vector<int> fa;
public:
    dsu(int n = 1) {
        fa = vector<int>(n + 1, -1), fa[0] = 0;
    }

    int getfa(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = getfa(fa[x]);
    }

    void merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        if (x == y) return;
        if (fa[x] > fa[y]) swap(x, y);
        fa[x] += fa[y], fa[y] = x;
    }

    bool same(int x, int y) {
        x = getfa(x), y = getfa(y);
        return (x == y);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    vector<array<int, 3>> edge(m);
    for (auto &[w, x, y]: edge)
        cin >> x >> y, w = max(h[x], h[y]);
    sort(edge.begin(), edge.end());

    int q;
    cin >> q;
    vector<array<int, 4>> Q(q);
    for (int i = 0, a, b, e; i < q; i++)
        cin >> a >> b >> e, e += h[a], Q[i] = {e, a, b, i};
    sort( Q.begin(), Q.end() );

    dsu d(n);
    vector<bool> res(q);
    int t = 0;
    for( const auto & [ e , a , b , id ] : Q ){
        for ( ; t < edge.size() && edge[t][0] <= e ; t  ++ )
            d.merge( edge[t][1] , edge[t][2] );
        if( d.same( a , b ) ) res[id] = true;
    }

    for (auto i: res)
        if (i) cout << "YES\n";
        else cout << "NO\n";
    cout << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}