首页 > 其他分享 >Codeforces Round 969 Div.2+Div.1

Codeforces Round 969 Div.2+Div.1

时间：2024-09-02 10:26:03浏览次数：3  
标签：define int 969 long read while Div.2 Div.1 getchar

A. Dora's Set

注意到任意两个偶数的 \(\gcd\) 都大于 \(1\) ，因此选择的三个数中至多一个偶数，而注意到相邻的奇数一定互质，因此每次选两个奇数一个偶数，答案=奇数的个数÷2

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}



int main()  
{   
    int T = read();
    while(T--)
    {
        int l = read(), r = read();
        int cnt = 0;
        for(int i = l; i <= r; ++i)
            if(i & 1) ++cnt;
        printf("%d\n", cnt >> 1);
    }
    return 0;   
}

B. Index and Maximum Value

每次对某个值域中的数+1或-1，问最大值？

只记录最大值即可，每次操作判断是否会操作最大值

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}



int main()  
{   
    int T = read();
    while(T--)
    {
        int n = read(), m = read();
        int mx = 0;
        for(int i = 1; i <= n; ++i)
        {
            int a = read();
            mx = max(mx, a);
        }
        while(m--)
        {
            char c;
            scanf(" %c", &c);
            int l = read(), r = read();
            if(c == '+')
            {
                if(l <= mx && mx <= r) ++mx;
            }else
            {
                if(l <= mx && mx <= r) --mx;
            }
            printf("%d ", mx);
        }
        printf("\n");
    }
    return 0;   
}

C. Dora and C++

发现只需要关注相对大小，对 \(x, y\) 反复加 \(a, b\) 总可以使相对大小变化 \(d = \gcd(a, b)\)

使 \(x, y\) 更接近，都放到 \([0, d - 1]\) 中，即所有的数对 \(d\) 取模

发现可以把后缀的一些数放到 \([-d, -1]\)

枚举从哪个点开始断即可

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

int gcd(int x, int y)
{
    if(!y) return x;
    return gcd(y, x % y);
}

const int N = 1e5 + 5;
int A[N];

int main()  
{   
    int T = read();
    while(T--)
    {
        int n = read(), x = read(), y = read(), d = gcd(x, y);
        // printf("x = %d, y = %d, d = %d\n", x, y, d);
        for(int i = 1; i <= n; ++i) A[i] = read() % d;
        sort(A + 1, A + n + 1);
        // for(int i = 1; i <= n; ++i) printf("%d ", A[i]);
        // printf("\n");
        int ans = A[n] - A[1];
        for(int i = 1; i < n; ++i)
        {
            ans = min(ans, d - (A[i + 1] - A[i]));
        }
        printf("%d\n", ans);
    }
    return 0;   
}

D. Iris and Game on the Tree

发现如果某个叶子的值和根一样，那么这条路径没有贡献，只有当根和叶子值不同时会有贡献

根确定时两个人抢叶子，根不确定时发现第一个填根的人一定不优，此时路径上的其他 \(?\) 决定谁先手

贺的代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

ll read()
{
    ll x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 1e5 + 5;
int n;
vector<int> e[N];
int du[N];
char s[N];

int main()  
{   
    int T = read();
    while(T--)
    {
        n = read();
        for(int i = 1; i <= n; ++i) du[i] = 0;
        for(int i = 1; i < n; ++i)
        {
            int u = read(), v = read();
            ++du[u], ++du[v];
        }
        scanf("%s", s + 1);
        int X = 0, Y = 0, Z = 0, K = 0;
        for(int i = 2; i <= n; ++i)
        {
            if(du[i] == 1)
            {
                if(s[i] == '1') ++X;
                if(s[i] == '0') ++Y;
                if(s[i] == '?') ++Z;
            }else if(s[i] == '?') ++K;
        }
        int ans = 0;
        if(s[1] == '?')
        {
            ans = max(X, Y) + Z / 2;
            if(X == Y)
            {
                if(K % 2 == 1) ans = max(ans, X + (Z + 1) / 2);
                else ans = max(ans, X + Z / 2);
            }
        }else
        {
            if(s[1] == '1') ans = Y + (Z + 1) / 2;
            else ans = X + (Z + 1) / 2;
        }
        printf("%d\n", ans);
    }
    return 0;   
}

E. Iris and the Tree

记一个点对路径上已经确定的边的权值为 \(a\) ，所有已经确定的边的权值为 \(b\) ，如果这个点对路径上的边没有全部确定，那么最大值可以取到 \(w - b + a\)

同时注意到一条边只会被两个点对包含，记录每个路径上的边被覆盖的次数即可，同时维护 \(w - b\)

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

ll read()
{
    ll x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int n;
ll w;
vector<int> e[N];

int dep[N], f[N][20], dfn[N], low[N], rk[N], tot;

void dfs(int k, int fa)
{
    dep[k] = dep[fa] + 1, f[k][0] = fa;
    for(int i = 1; i <= 19; ++i)
    {
        f[k][i] = f[f[k][i - 1]][i - 1];
    }
    dfn[k] = low[k] = ++tot, rk[tot] = k;
    for(auto v : e[k])
    {
        dfs(v, k);
    }
    low[k] = tot;
}

int LCA(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 19; i >= 0; --i)
    {
        if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; --i)
    {
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

int cnt[N];

int main()  
{   
    int T = read();
    while(T--)
    {
        n = read(), w = read(), tot = 0;
        for(int i = 1; i <= n; ++i) e[i].clear();
        for(int i = 2; i <= n; ++i)
        {
            int fa = read();
            e[fa].emplace_back(i);
        }
        dfs(1, 0);
        for(int i = 1; i <= n; ++i)
        {
            int v = i % n + 1;
            int lca = LCA(i, v);
            cnt[i] = dep[i] - dep[lca] + dep[v] - dep[lca];
        }
        ll ans = 0, now = w, m = n;
        ll sum = 0;
        for(int i = 1; i < n; ++i)
        {
            int x = read();
            int u = (x == 1) ? (n) : (x - 1);
            ll y = read();
            sum += 2 * y, now -= y;
            --cnt[u];
            if(cnt[u] == 0) --m;
            int v = rk[low[x]];
            --cnt[v];
            if(cnt[v] == 0) --m;
            printf("%lld ", sum + m * now);
        }
        printf("\n");
    }
    return 0;   
}

F. Eri and Expanded Sets

一个数的序列一定是明智的，考虑两个数的序列

要求差为 \(2\) 的次幂

发现实际上是，差为偶数时，还可以再分，直到分成若干的奇数，最终的目的是所有的奇数都是 \(1\)

考虑三个数 \(x, y, z\) ，其中 \(x < y < z\) ，记 \(a = y - x, b = z - y\)

当 \(a, b\) 有一个是偶数时可以再分，当两个是奇数时 \(a + b = z - x\) 是偶数也可以再分，该分到什么时候？

记 \(d = \gcd(a, b)\) ,则 \(a = pd, b = qd\) 且 \(\gcd(p, q) = 1\) ，再分出的 \(\frac{a+b}{2^k}\) 一定小于 \(b\) ，且与 \(a\) 的最大公约数仍为 \(d\) ，此时再让它和 \(a\) 相加再分，这样每次取最小的两个数相加再分，一定可以分出 \(d\)

同理可知，一个序列是明智的当且仅当它的差分序列的全体 \(\gcd\) 是 \(2\) 的次幂（此时不必排序好）

区间 \(\gcd\) 是具有单调性的，双指针+st表统计答案

一个坑点是上面讨论的是所有的数都不相同，当相邻的数相同时差分为0，会出错，一个方法是相邻相同的点缩成一个点，统计答案时有点麻烦

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

ll gcd(ll x, ll y)
{
    if(!y) return x;
    return gcd(y, x % y);
}

const int N = 4e5 + 5;
int n, a[N], num[N], b[N], sum[N];
int st[N][20], lg[N];

int get(int l, int r)
{
    int d = lg[r - l + 1];
    return gcd(st[l][d], st[r - (1 << d) + 1][d]);
}

int cnt(int x)
{
    int s = 0;
    while(x) s += x & 1, x >>= 1;
    return s;
}

void solve()
{
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    ll ans = n;

    int nn = 1, now = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(a[i] == a[i - 1]) ++now;
        else num[nn] = now, ans += 1ll * now * (now - 1) / 2, now = 1, a[++nn] = a[i];
    }
    num[nn] = now, ans += 1ll * now * (now - 1) / 2;
    for(int i = 1; i <= nn; ++i) sum[i] = sum[i - 1] + num[i];

    for(int i = 2; i <= nn; ++i) b[i] = abs(a[i] - a[i - 1]);
    for(int i = 2; i <= nn; ++i) st[i][0] = b[i];
    for(int j = 1; j <= 19; ++j)
        for(int i = 2; i + (1 << j) - 1 <= nn; ++i)
            st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    
    int l = 2, r = 2;
    while(l <= nn && r <= nn)
    {
        r = max(l, r);
        while(r <= nn && cnt(get(l, r)) > 1) ++r;
        ans += 1ll * (n - sum[r - 1]) * num[l - 1], ++l;
    }
    printf("%lld\n", ans);
}

int main()
{
    int T = read();
    lg[0] = -1;
    for(int i = 1; i <= 4e5; ++i) lg[i] = lg[i >> 1] + 1;
    while(T--) solve();
    return 0;
}

Div.1 D. Iris and Adjacent Products

感觉比 \(C\) 还好想，直接贪心就完了

容易发现按照最大值，最小值，次大值，次小值依次放置最优，只需要保证相邻的数乘积不大于 \(K\) 即可，当不满足时将最大值换成 \(1\) ，然后重新排序，判断

记 \(cnt(l, r, i, j)\) 表示区间 \([l, r]\) 中值域在 \([i, j]\) 之间的数的个数，那么就需要时刻满足 \(cnt(l, r, 1, i) \ge cnt(l, r, \frac{n}{i}, n)\)

如果可以 \(O(1)\) 计算出 \(cnt(l, r, i, j)\) 就好了

欸，主席树！带个 \(log\) 被卡时间了

欸，可以预处理前缀和 \(cnt\) ，被卡空间了

题解变换了枚举顺序，先枚举 \(cnt(l, r, 1, i)\) 中的 \(i\) ，再枚举每个区间处理，这样空间就不会被卡了

还可以莫队！

发现这是一个 \(n\sqrt{n}\) 次的 \(O(1)\) 移动操作和一个 \(n\) 次的 \(O(\sqrt{n})\) 的统计答案操作

莫队代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 1e5 + 5, M = 1e6 + 5;
int n, Q, K;
int b[N];
int x[1005], be[N], cnt[2005];
int Size, belong[N], ans[N];

struct node
{
    int id, l, r;
    node(){ id = l = r = 0; }
    bool friend operator < (const node &a, const node &b)
    {
        if(belong[a.l ] == belong[b.l ]) return a.r < b.r ;
        else return a.l < b.l ;
    }
}q[N];

void solve()
{
    n = read(), Q = read(), K = read();
    for(int i = 1; i <= n; ++i) belong[i] = 0;
    for(int i = 1; i <= Q; ++i) ans[i] = 0;
    for(int i = 1; i <= n; ++i) b[i] = read();
    Size = sqrt(K);
    for(int i = Size << 1; i >= 1; --i) cnt[i] = 0;
    for(int i = 1; i <= Size; ++i) x[i] = max(K / (i + 1) + 1, Size + 1);
    x[0] = K;
    for(int i = 1; i <= n; ++i)
    {
        if(b[i] <= Size) be[i] = b[i];
        else
        {
            int l = 0, r = Size;
            while(l < r)
            {
                int mid = (l + r + 1) >> 1;
                if(x[mid] <= b[i]) r = mid - 1;
                else l = mid;
            }
            be[i] = l + 1 + Size;
        }
    }
    for(int i = 1; i <= n; i += Size) belong[i] = 1;
    for(int i = 1; i <= n; ++i) belong[i] += belong[i - 1];
    for(int i = 1; i <= Q; ++i) q[i].id = i, q[i].l = read(), q[i].r = read();
    sort(q + 1, q + Q + 1);
    int l = 1, r = 0;
    for(int i = 1; i <= Q; ++i)
    {
        while(l > q[i].l ) --l, ++cnt[be[l]];
        while(r < q[i].r ) ++r, ++cnt[be[r]];
        while(l < q[i].l ) --cnt[be[l]], ++l;
        while(r > q[i].r ) --cnt[be[r]], --r;
        int len = q[i].r - q[i].l + 1, X = 0, Y = 0;
        for(int j = 1; j <= Size; ++j)
        {   
            X += cnt[j], Y += cnt[j + Size];
            if(X + Y == len) ans[q[i].id ] = max(ans[q[i].id ], (Y - X) >> 1); // 后面没数了，最后一个位置可以放大数
            else ans[q[i].id ] = max(ans[q[i].id ], (Y - X + 1) >> 1); // 后面还有数，最后一个位置必须放小数
        }
    }
    for(int i = 1; i <= Q; ++i) printf("%d ", ans[i]);
    printf("\n");
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

Div.1E. Iris's Full Binary Tree

咕咕咕（大概率不会改了）

Div.1F. Dora's Paint

咕咕咕（大概率不会改了）

标签：define,int,969,long,read,while,Div.2,Div.1,getchar
From： https://www.cnblogs.com/wenqizhi/p/18392261

相关文章

  • Codeforces Round 969 (Div. 2)
    ab题没啥好说的，b题一开始看题错成线段树了，后面发现维护最大值就过了（我就说b怎么会有线段树）。。。C:DoraandC++卡的我死死的，好久没卡c了，数论果然是最短板。。。我有两个推论，但是一个都不会用：1.翡蜀定理。（但是这题只有正数）（处理两个数的情况）2.断环为链。（但是我只会n方，即以每个......
  • Codeforces Round 967(Div.2)之赛后总结
    CodeforcesRound967(Div.2)传送锚点A.MakeAllEqual1.题面分析废话这么多，说白了就是求总数减去最多出现数的个数的值。2.解法直接用桶装一下，然后扫一遍维护最大值。3.code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+520;......
  • CF 2001 E2 solution (967 Div.2)
    CF2001E2由于对称，所以设\(heap[u]\)为两次确定堆，且第一次弹出的是\(u\)，\(heap[u,v]\)是第一次\(u\)，第二次\(v\)则答案就是\(\sumheap[u]=2^{n-1}·heap[x]\)其中\(x\)任意。不妨我们考虑第一次都是从第一个叶子弹出，那么对于其他不同的第二个弹出的点，根据对称性......
  • panic: 8e85653db463fe36 state.commit 942043166 is out of range [939698375, 93970
    根据您提供的日志信息，看起来您的etcd服务遇到了一个panic错误，具体是因为state.commit的索引值942043166超出了预期的范围[939698375,939700076]。这种情况可能是由于etcd集群中的数据不一致导致的。首先，您可以尝试查看etcd集群的状态，确认所有成员是否都在正......
  • CF1969F-Card Pairing【dp】
    正题题目链接:https://www.luogu.com.cn/problem/CF1969F题目大意有一个长度为\(n\)的卡牌序列\(a\)，每张牌是\(1\simk\)中的一个类型，你先取出序列里的前\(k\)张牌，然后你每次可以选择两张牌打出然后再抽两张牌，如果类型一样就加一分。求打完所有牌你最多能加多少分。......
  • Codeforces Round 960(Div.2）
    CodeforcesRound960(Div.2)A从大到小去判断数字个数的奇偶性，只要出现过奇数，先手必赢，如果不出现奇数，后手必赢#include<iostream>#include<queue>#include<map>#include<set>usingnamespacestd;constintN=55;inta[N];voidsolve(){ intn; cin>>n; ma......
  • Codeforces Round 960 (Div.2) 补题
    A非常容易观察到性质，注意Alice为先手，发现当\(a_{\max}\)的个数为奇数时显然能win，但如果\(a_{\max}\)的个数为偶数且有一个数具有奇数个可以作为跳板，那么也能win，否则就lose。B结论：\(presum_x\geq2+presum_{y-1}\geq2+\min{presum_i}\geq1+\max{presum_i}......
  • SSM豫东乡村生产信息管理系统-计算机毕业设计源码02969
     ssm豫东乡村生产信息管理系统摘要 在当前信息技术快速发展和普及的背景下，乡村地区的公共管理和农村生产活动也面临着新的挑战和需求。为了提升公共管理的效率和服务质量，以及支持农村生产的规划和组织，需要引入信息化手段来改善管理和运营。同时，随着乡村经济的发展和现代......
  • 【TWVRP】蚁群算法求解带时间窗的车辆路径规划（目标函数：最短距离）【含Matlab源码 4969期
    ✅博主简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，Matlab项目合作可私信或扫描文章底部QQ二维码。......
  • Codeforces Round 953(Div.2) 题解(A-E)
    CodeforcesRound953(Div.2)题解(A-E)A题意Alice有n本书，第一本书有\(a_1\)页，序号为1，第二本书有\(a_2\)页,序号为2，……,第n本书有\(a_n\)页，序号为n。Alice将把所有书分成两堆，并阅读每一堆中序号最大的一本书。Alice喜欢读书，请你告诉她，她最多可以读多少页的书。Solution第......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99