20250719

发布于：2025-07-22 ⋅ 阅读:(19) ⋅ 点赞:(0)

https://codeforces.com/contest/2126/problem/E

根据前缀数组p[i], 后缀数组s[i], 可以知道的是对于某一个数组res[i]来说，第i个位置上的数一定是p[i]的倍数，也是s[i]的倍数，所以我们可以直接从p[i], s[i]得到一个lcm当作res[i]的值，最后通过res[i]计算一次gcd看是否能与前缀gcd,和后缀gcd匹配

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n;
int p[N], s[N];
int v1[N], v2[N];
int res[N];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i];
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= n; i++) res[i] = p[i] * s[i] / __gcd(p[i], s[i]);
    v1[1] = res[1];
    for (int i = 2; i <= n; i++)
        v1[i] = __gcd(res[i], v1[i - 1]);
    v2[n] = res[n];
    for(int i = n - 1; i >= 1; i--)
        v2[i] = __gcd(res[i], v2[i + 1]);
    for(int i = 1; i <= n; i++)
        if(v1[i] != p[i] || v2[i] != s[i])
        {
            cout << "NO" << '\n';
            return;
        }
    cout << "YES" << "\n";
    return;
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    return 0;
}

https://codeforces.com/contest/2126/problem/F

之前都是以边考虑，但是并没有利用上 树 的特点---一个节点只有一个父亲
那么我们在考虑贡献的时候，可以利用每一个节点连接他儿子的边来计算贡献信息，这样我们就做到了每一个只要有儿子的节点都能够包含上所有的边，做到不重不漏。在更新点的时候，我们可以直接用map记录这个节点的子节点的不同颜色对答案的贡献，然后在修改自己颜色之前先考虑对父节点的影响，因为父节点掌管的边里面包含这个节点，然后再用map做到O(1)的更改

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, q;
int a[N];
vector<PII> vec[N];
int fa[N];
int ans;
map<int, int> mp[N];
int valu[N];

void dfs(int u, int f)
{
    fa[u] = f;
    for(auto [it, val] : vec[u])
        if(it != f)
        {
            if(a[it] != a[u]) ans += val;
            mp[u][a[it]] += val;
            valu[it] = val;
            dfs(it, u);
        }
}

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        vec[i].clear();
    memset(fa, 0, sizeof fa);
    ans = 0;
    for(int i = 1; i <= n; i++)
        mp[i].clear();

    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < n; i++)
    {
        int u, v, val;
        cin >> u >> v >> val;
        vec[u].push_back({v, val});
        vec[v].push_back({u, val});
    }
    dfs(1, 0);

    while(q--)
    {
        int poi, x;
        cin >> poi >> x;
        if(fa[poi] != 0)
        {
            mp[fa[poi]][a[poi]] -= valu[poi];
            if(a[poi] == a[fa[poi]]) ans += valu[poi];
            if(a[fa[poi]] == x) ans -= valu[poi];
            mp[fa[poi]][x] += valu[poi];
        }
        ans += mp[poi][a[poi]];
        ans -= mp[poi][x];
        a[poi] = x;
        cout << ans << '\n';
    }
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    return 0;
}

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, q;
int a[N];
map<PII, int> mp;
int sum;
vector<int> vec[N];

void solve()
{
    memset(a, 0, sizeof a);
    sum = 0;
    cin >> n >> q;
    mp.clear();
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1;  i <= n; i++)
        vec[i].clear();
    for(int i = 0; i < n - 1; i++)
    {
        int aa, b, c;
        cin >> aa >> b >> c;
        mp[{min(aa, b), max(aa, b)}] = c;
        vec[aa].push_back(b);
        vec[b].push_back(aa);
        if(a[aa] != a[b])
            sum += c;
    }

    while (q--)
    {
        int poi, x;
        cin >> poi >> x;
        if(n == 1)
        {
            cout << 0 << '\n';
            continue;
        }
        for(auto it : vec[poi])
            if(a[it] == a[poi])
                sum += mp[{min(poi, it), max(poi, it)}];
            else if(a[it] == x)
                sum -= mp[{min(poi, it), max(poi, it)}];
        cout << sum << '\n';
        a[poi] = x;
    }
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    return 0;
}
*/

https://codeforces.com/problemset/problem/2123/E

当我们想正着做发现难得时候可以正难则反
如果我们要让x作为我们的mex,那么是不是要保证值为x的个数要全部删除完，其次还要保证从0~(x-1)的数中，每个数的个数至少需要有一个，那么其他剩余的数不会影响我们的结果就能全部删除了
所以我们用逆向思维来看的话，其实就是我们枚举每一个可能成为mex的数，然后得到删除这个数的操作数的左右区间，最后做一次前缀和就能得到删除几个数能得到几种不同的答案了

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n;
int a[N], b[N];
int ans[N];


void solve()
{
    memset(ans, 0, sizeof ans);
    memset(b, 0, sizeof b);
    int ed = -1;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        ed = max(ed, a[i]);
        b[a[i]]++;
    }

    for(int i = 0; i <= ed + 1; i++)
    {
        int l = b[i];
        int r = n - i;
        ans[l]++, ans[r + 1]--;
        if(b[i] == 0)
            break;
    }

    for(int i = 1; i <= n; i++)
        ans[i] += ans[i - 1];
    for(int i = 0; i <= n; i++)
        cout << ans[i] << ' ';
    cout << '\n';
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    return 0;
}

https://codeforces.com/problemset/problem/2120/C 

 

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define pb push_back

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;

void solve()
{
    cin >> n >> m;
    if (m < n || m > n * (n + 1) / 2)
    {
        cout << -1 << '\n';
        return;
    }
    if (m == n)
    {
        cout << 1 << '\n';
        for (int i = 1; i < n; i++)
            cout << i << ' ' << i + 1 << '\n';
        return;
    }
    if (m == n * (n + 1) / 2)
    {
        cout << n << '\n';
        for (int i = 1; i < n; i++)
            cout << i << ' ' << n << '\n';
        return;
    }
    
    int top = 1;
    int sum = n;
    while (sum < m)
    {
        sum += (n - top);
        top++;
    }
    cout << top << '\n';
    int tp = top;
    for (int i = 1; i <= top - 1; i++)
        cout << i << ' ' << top << '\n';
    sum = m - top * (top + 1) / 2;

    int tt = n * tp - tp * tp - sum;

    for (int i = 1; i <= tt; i++)
        cout << ++top << ' ' << tp - 1 << '\n';
    for(int i = top + 1; i <= n; i++)
        cout << i << " " << tp << '\n';
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

Contest Login

逆向思维

题目是让求出每一段区间的中位数且限制了数组的长度只能为奇数，如果暴力枚举区间然后再求中位数的话时间复杂度会到n*n*logn，那么我们可以反向思考，我们直接枚举一个数，他在哪些区间内可以成为中位数，这个样子我们的时间复杂度就降低为了n*n。

当我们枚举一个数x时，我们新维护一个差分数组，将小于x的数置为-1，大于x的数置为1，然后求一个前缀和，显而易见的是如果x是[l, r]这个区间的中位数，那么[l, r]这一段区间内的-1 1的个数应该是相等的，由于我们维护的前缀数组，即b[r] = b[l-1]

整体思路有了就是细节问题了，如果我们求出来了这个前缀数组但是每次比较的时候都暴力求相等的区间的话，时间复杂度还是不够，对于如果i1和i2位置上的数都可以和j匹配的话，那么我们可以用乘法结合律变成(i1 + i2) * j * x，那么我们可以先求出x左边的前缀num出现在哪些坐标上，然后用一个桶累加即可，但是如果我们枚举到了一个最大的数，那么会导致前面的数全为负数，我们访问桶的时候就会越界，因为我们的数组大小为2000，那么就可以设置一个偏移量变为b[i] + P这样就有效防止了数组越界的情况。还有一定要记得把x位置上的b[]置为0，因为我们求的是b[r] = b[l - 1]那么我们在统计i1 i2的时候，其实他们的下表要比其真实的下标小1才对

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define pb push_back

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e4 + 10, INF = 0x3f3f3f3f;
int n;
int a[N];
int b[N];
int sum[N];
int P = 2010;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        memset(b, 0, sizeof b);
        memset(sum, 0, sizeof sum);
        for(int j = 1; j <= n; j++)
            b[j] = a[j] > a[i] ? 1 : -1;
        b[i] = 0;
        for(int j = 1; j <= n; j++)
            b[j] += b[j - 1];
        for(int j = 0; j < i; j++)
            sum[b[j] + P] += j + 1;
        for(int j = i; j <= n; j++)
            ans += j * sum[b[j] + P] * a[i];
        
    }
    cout << ans << '\n';
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

Contest Login

根据贪心的原则，我们两边的数越大，包含的端点数才可能越多，但是也存在其他情况，但是数据范围数2e6，所以只能想O(n)的做法。

如果我们最开始就以最大的数和最小的数为两个端点，然后依次向较小的数的位置扩展，这样我们能做到O(n)的时间

如果我们扩展到了第i大的数，如果第i大的数在[l, r]之间，那么其对结果没有影响。

如果i在l左边，那么应当把区间左端点扩展到i的位置上去，但是中间可能存在比i大数怎么办呢？根据我们的扩展方法可以知道，此时我们的i是第i大的数，那么比i大的数个数有(n - i - 1) 个。因为我们只有在区间边界扩展时才更新ans的值，那么其实比i大的数一定都包含在[i, r]的区间内，所以直接减去这些数即可。

反证：如果比i大的数不在[i, r]内，那么这个数的坐标一定在i左边，那么我们在更新这个数的时候就会移动边界而不是等到更新到i的时候才移动边界，得证。

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define pb push_back

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 4e6 + 10, INF = 0x3f3f3f3f;
int n, a[N];
int poi[N];

void solve()
{
    cin >> n;
    memset(poi, 0, sizeof poi);
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        poi[a[i]] = i;
    }

    int l = min(poi[n], poi[n - 1]), r = max(poi[n], poi[n - 1]);
    int ans = r - l + 1;
    if(n == 1)
    {
        cout << 1 << '\n';
        return;
    }

    for(int i = n - 2; i >= 1; i--)
    {
        int p = poi[i];
        if(p < l)
        {
            l = p;
            ans = max(ans, (r - l + 1) - (n - i - 1));
        }
        else if(p > r)
        {
            r = p;
            ans = max(ans, (r - l + 1) - (n - i - 1));
        }
    }
    cout << ans << '\n';
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    return 0;
}

 https://codeforces.com/contest/2122/problem/A

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define pb push_back

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;

void solve()
{
    cin >> n >> m;
    if(n == 1 || m == 1)
    {
        cout << "NO" << '\n';
        return;
    }
    if(n == 2 && m == 2)
    {
        cout << "NO" << '\n';
        return;
    }
    cout << "YES" << '\n';
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    return 0;
}

 https://codeforces.com/contest/2122/problem/B

思维题，要么只考虑送出去的情况，要么只考虑拿进来的情况，就能做到不重不漏

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define pb push_back

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n;
int a[N], b[N], c[N], d[N];

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (b[i] > d[i])
            ans += a[i] + b[i] - d[i];
        else if (a[i] > c[i])
            ans += a[i] - c[i];

    cout << ans << '\n';
}

signed main()
{
    IOS;
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布