首页 > 其他分享 >cf2009 Codeforces Round 971 (Div. 4)

cf2009 Codeforces Round 971 (Div. 4)

时间：2024-10-09 22:49:19浏览次数：9  
标签：oo last int ll Codeforces seg mp cf2009 Div

A. Minimize!

签到题。计算\((c-a)+(b-c)\)的最小值，其实值固定的，等于\(b-a\)。

int a, b;

void solve()
{
    cin >> a >> b;
    cout << b - a << endl;
}

B. Osu!mania

签到题。给定一个4k下落式的网格，求#下落顺序。直接数组记录就好了。

int n;
const int N = 500;
char s[N][4];
int v[N];

void solve(void)
{
    cin >> n;
    int vlen = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            cin >> s[i][j];
            if (s[i][j] == '#')
            {
                v[vlen++] = j + 1;
            }
        }
    }

    for (int i = vlen - 1; i >= 0; --i)
    {
        cout << v[i] << " \n"[i == 0];
    }
}

C. The Legend of Freya the Frog

签到题。一个人从\((0,0)\)出发跳跃到\((x,y)\)。每步只能跳\(d\)格，\(0\leq d \leq k\)。并且，当朝着\(x/y\)方向跳了一次后，下次就会朝着\(y/x\)方向。这个人初始朝向\(x\)方向。给定\((x,y),k\)求跳的最小次数。

小学数学算一下是x->y->x->y->x还是x->y->x->y就行了。

ll x, y, k;

void solve()
{
    cin >> x >> y >> k;
    ll dx = (x + k - 1) / k, dy = (y + k - 1) / k;
    ll res = -1;
    if (dx > dy)
    {
        res = (dx << 1) - 1;
    }
    else
    {
        res = dy << 1;
    }
    cout << res << endl;
}

D. Satyam and Counting

水题。现在有一个1xn的网格，给出\(n\)个这个网格上已有的格点坐标。求这些格点能组成多少个直角三角形。分情况讨论再加起来就行。

  1. 两个点能组成一条竖边，则剩下的\(n-2\)个点都可以和它们组成三角形。遍历所有点，记录竖边数量\(c_1\)，则这种三角形就有\(c_1\times (n-2)\)个。

    image-20240924222508380

  2. 两个点能组成一条斜边。然后它们中间也有一个点。不要忘记(1,1)(2,0)(3,1)这样颠倒过来也能组成三角形就行了。遍历的时候记录一下即可。

image-20240924222710646 
int n;
const int N = 2e5 + 5;
int a[N][2];

void solve()
{
    scanf("%d", &n);
    for (int i = 0; i <= n + 1; ++i)
    {
        a[i][0] = a[i][1] = 0;
    }
    int p, q;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d", &p, &q);
        a[p][q] = 1;
    }
    ll one = 0, two = 0, three = 0;
    for (int i = 0; i <= n; ++i)
    {
        if (a[i][0] && a[i][1])
        {
            one = one + n - 2;
        }
        if (i + 2 <= n && a[i][0] && a[i + 1][1] && a[i + 2][0])
        {
            two++;
        }
        if (i + 2 <= n && a[i][1] && a[i + 1][0] && a[i + 2][1])
        {
            three++;
        }
    }
    printf("%lld\n", one + two + three);
}

E. Klee's SUPER DUPER LARGE Array!!!

Klee有一个长度为n的序列[k,k+1,...,k+n-1]，他想选定一个下标\(i\)，使得\(x=|a_1+a_2+..+a_i-a_{i+1}-...-a_n|\)最小。\(2\leq n,k\leq 10^9\)。

水题，这个\(x\)随着\(i\)变大，必是单调增加的，所以二分即可。（狼狈回忆二分）

ll n, k;

ll check(ll x)
{
    ll right = (n + k - 1) * (n + k) / 2LL - (x + 1) * x / 2LL;
    ll left = (x + 1) * x / 2LL - (k - 1) * k / 2LL;
    return right - left;
}

void solve()
{
    cin >> n >> k;
    ll res = 1e18;
    ll l = 1, r = n + k - 1;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        ll cur = check(mid);
        res = min(res, abs(cur));
        if (cur <= 0)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << res << endl;
}

F. Firefly's Queries

小水题。有一个长度为\(n\)的数组\(a[n]\)。然后定义了一个cyclic shift的操作。（The x-th\((1\leq x\leq n)\) cyclic shift of the array a is \(a_x,a_{x+1},...,a_n,a_1,a_2,...,a_{x-1}\)）。\(c_i\)就代表了\(a\)的第\(i\)个cyclic shift数组。然后又创建数组\(b\)等于\(c_1,c_2,...,c_n\)（所有的\(c_i\) concatenation到一起）。现有\(q\)次查询，每次查询输出\(b[l:r]\)的元素和。

包含整个\(c_i\)的部分就是\(a[1:n]\)，然后再加上一个小尾巴就行了。

int n, q;
const int N = 2e5 + 5;
int a[N];
ll pre[N];

ll cal(ll x)
{
    if (x < 0LL)
        return 0LL;
    ll p = x / n, q = x % n;
    if (p == 0)
    {
        return pre[x];
    }
    ll left = pre[n - 1] * p;
    ll pos = (p + q) % n;
    ll right = 0;
    if (pos >= p)
    {
        right = pre[pos] - pre[p - 1];
    }
    else
    {
        right = pre[n - 1] - pre[p - 1] + pre[pos];
    }
    return left + right;
}

void solve()
{
    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        pre[i] = (i == 0) ? (a[i]) : (pre[i - 1] + a[i]);
    }
    ll l, r;
    while (q--)
    {
        cin >> l >> r;
        ll lres = cal(l - 2), rres = cal(r - 1);
        cout << rres - lres << endl;
    }
}

G1. Yunli's Subarray Queries (easy version)

有点思维的水题。题面：

对于任意数组\(b\)（下标从1开始），Yunli可以执行以下操作任意次：

  • 选择下标\(i\)，令\(b[i]=x\)，\(x\)可以是任意整数。

设\(f(b)\)为她把\(b\)变成一个满足以下条件的数组的最小操作次数：存在长度\(\geq k\)的子序列\(b_{sub}\)（下标从1开始），\(\forall j>1, b_{sub}[j]=b_{sub}[j-1]+1\)。（consecutive subarray）

现给定数组\(a[n]\)以及\(q\)次查询，在每次查询时，输出\(\sum\limits^r_{j=l+k-1}f([a_l,a_{l+1},..,a_j])\)。在easy version中，\(r\equiv l+k-1\)。也就是说，输出的是\(f([a_l,a_{l+1},..,a_j])\)。

数据范围：\(n\leq 2\times 10^5, q\leq 2\times 10^5, 1\leq a[i]\leq n\)。

思路：

首先，我们要知道这样一件事：怎么找一个consecutive subarray？

(1)(2)(3)(4)(5)(6) k=3
 2  3  4  9  6  11

对于这个\(a[n]\)，我们知道可以把2，3，4，x，6中的x改为5，也可以将9，x，11中的x改为10。或者我们可以换一种角度看问题：2，3，4，(x)，6是属于一组的，9，(x)，11是属于另一组的。想要判断数与数之间有没有属于同一组的机会，我们只要对数组\(a\)做一个简单的操作。

令\(a'[i]=a[i]-i\)，此时

(1)(2)(3)(4)(5)(6) k=3
 1  1  1  5  1  5

能看出这件事，这道题就结束了。做一个长度为\(k\)的滑动窗口，记录目前的窗口中数量最多的元素即可。

int n, k, q;
const int N = 2e5 + 5;
int a[N], res[N];

void solve()
{
    cin >> n >> k >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    int last = a[0];
    map<int, int> mp;
    set<pii, greater<pii>> s;

    for (int i = 0; i < n; ++i)
    {
        if (i >= k)
        {
            res[i - k] = k - s.begin()->first;
        }
        // add nxt
        if (mp.count(a[i] - i))
        {
            pii cur = pii(mp[a[i] - i], a[i] - i);
            if (s.count(cur))
                s.erase(cur);
        }
        mp[a[i] - i]++;
        s.insert(pii(mp[a[i] - i], a[i] - i));
        // erase last
        if (i >= k)
        {
            s.erase(pii(mp[last - i + k], last - i + k));
            if (mp[last - i + k] == 1)
            {
                mp.erase(last - i + k);
            }
            else
            {
                mp[last - i + k]--;
                s.insert(pii(mp[last - i + k], last - i + k));
            }
            last = a[i - k + 1];
        }
    }
    res[n - k] = k - s.begin()->first;

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << res[l - 1] << endl;
    }
}

G2. Yunli's Subarray Queries (hard version)

这题是上题的困难版本，其中\(r\)的条件改变为\(r\geq l+k-1\)，求\(\sum\limits^r_{j=l+k-1}f([a_l,a_{l+1},..,a_j])\)。

这题需要用到上一题的结论，令\(p_i\)为滑动窗口的起始位置为\(i\)时，记录的\(a'[i:i+k-1]\)重复数量最多的元素数。\(c_i=k-p_i\)，也就是\(c_i=f([a_l,a_{l+1},..,a_{l+k-1}])\)。则\(f([a_l,a_{l+1},..,a_j])=\min(c_l, c_{l+1},..,c_{j-k+1})\)。

区间求最值可以用线段树or树状数组来做，但是还要解决另一个事情，我们要求的是\(\sum\limits^r_{j=l+k-1}\min\{c[l:j-k+1]\}\)，还有个区间求和。再进一步观察，可以看到另一条性质。假设数组\(c\)如下：

(1)(2)(3)(4)(5)(6)(7)
 1  3  7  4  5  3  6

现在我们算\(c[4]\sim c[7]\)这段的值

(1)(2)(3)(4)(5)(6)(7)
          4  4  3  3

可以看到，值是单调非增的。也就是说，当\(l=4\)时，\(c[4]=4\)，这个值会一直覆盖后面的值，直到发现了\(c[6]<4\)，则再往后更新就用\(c[6]\)的值更新后面的。那我们就可以想到用一个单调栈来解决这件事。从后往前遍历，当遍历到\(c[cur]\)时，弹出栈顶元素\(c[top]\)，直到\(c[top]<c[cur]\)。然后将\(c[cur]\sim c[top-1]\)的值都更新为\(c[cur]\)。然后再通过区间求和算出此时的\(\sum\limits _{i=cur} ^{r}c_i\)即可，时间复杂度\(O(n\log n)\)。

int n, k, q;
const int N = 2e5 + 5;
ll a[N], c[N];
ll res[N];

struct node{
    int l, r;
    ll v, lz;
};
node seg[N<<2];

void pushup(int oo){
    seg[oo].v = seg[ls].v + seg[rs].v;
}

void pushdown(int oo){
    int mid = seg[oo].l + seg[oo].r >> 1;
    seg[ls].v = seg[oo].lz * (mid - seg[oo].l + 1LL);
    seg[rs].v = seg[oo].lz * (seg[oo].r - mid);
    seg[ls].lz = seg[rs].lz = seg[oo].lz;
    seg[oo].lz = 0;
}

void build(int oo, int l, int r){
    seg[oo] = node{l, r, 0LL, 0LL};
    if (l >= r) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid+1, r);
    pushup(oo);
}

void update(int oo, int x, int y, ll val){
    int l = seg[oo].l, r = seg[oo].r;
    if (x <= l && y >= r){
        seg[oo].v = val * (r - l + 1);
        seg[oo].lz = val;
        return;
    }
    int mid = l + r >> 1;
    if (seg[oo].lz) pushdown(oo);
    if (mid >= x) update(ls, x, y, val);
    if (y > mid) update(rs, x, y, val);
    pushup(oo);
}

ll query(int oo, int x, int y){
    int l = seg[oo].l, r = seg[oo].r;
    if (x <= l && y >= r){
        return seg[oo].v;
    }
    ll ans = 0;
    int mid = l + r >> 1;
    if (seg[oo].lz) pushdown(oo);
    if (x <= mid) ans += query(ls, x, y);
    if (y > mid) ans += query(rs, x, y);
    return ans;
}

void calc(){
    map<int, int> mp;
    set<pii, greater<pii> > st;
    for (int i = 1; i <= n; ++i){
        // pop last
        if (i > k){
            int last = a[i - k] - i + k;
            st.erase(pii(mp[last], last));
            mp[last]--;
            if (mp[last] == 0) mp.erase(last);
            else st.insert(pii(mp[last], last));
        }
        // push cur
        st.erase(pii(mp[a[i] - i], a[i] - i));
        mp[a[i] - i]++;
        st.insert(pii(mp[a[i] - i], a[i] - i));
        // calculate c value
        if (i >= k){
            pii x = *st.begin();
            c[i - k + 1] = - x.first;
        }
    }
}

void solve(){
    cin >> n >> k >> q;
    vector<vector<pii> > vec(n - k + 2);
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    int l, r;
    for (int i = 1; i <= q; ++i){
        cin >> l >> r;
        vec[l].push_back(pii(r - k + 1, i));
    }
    calc();
    build(1, 1, n - k + 1);
    stack<int> stk;
    for (int i = n - k + 1; i >= 1; --i){
        while (!stk.empty() && c[i] <= c[stk.top()]){
            stk.pop();
        }
        int ed = stk.empty() ? (n - k + 1) : (stk.top() - 1);
        stk.push(i);
        update(1, i, ed, c[i]);
        for (auto p: vec[i]){
            res[p.second] = 1LL * (p.first - i + 1) * k + query(1, i, p.first);
        }
    }
    for (int i = 1; i <= q; ++i){
        cout << res[i] << endl;
    }
}

标签：oo,last,int,ll,Codeforces,seg,mp,cf2009,Div
From： https://www.cnblogs.com/vivaldi370/p/18455355

相关文章

  • codeforces round 974(div.3)E(优先队列实现dijstra算法，devc++的优先队列用greater报
    解题历程：看到两边同时移动，计算最终的相遇时间，我就想到两边同时计算各点到起点的最短距离，就是使用dijstra算法，最后所有节点取两次计算的最大值，再对所有节点取最小值，就是最终答案了，可是这个思路没有考虑有马的情况，思考一番后发现可以多列一个数组记录有马的情况下的行走最短路，然后......
  • Codeforces Round 804 (Div. 2)(C - D)
    CC观察题意,模拟样例,首先\(0\)不能动,因为相邻的\(mex\)会改变,然后\(1\)也是如此,所以我们固定了\(0\)和\(1\),设两个指针\(l\)和\(r\)表示固定的位置,那么此时在他们两个中间的数可以随便移动,假设有\(x\)个空位,那么如果\(2\)在里面,\(2\)的选......
  • [AGC064C] Erase and Divide Game 题解
    DescriptionTakahashi和Aoki玩游戏。先在黑板上写若干个数，由\(N\)个互不相交的区间\([l_i,r_i]\)组成。两人轮流操作，每次操作先删去所有的奇数/偶数，再把剩下的数除以\(2\)（向下取整），无法操作的人输。Takahashi先手，假设两人都采用最优策略，问谁能获胜。\(1\leqN\leq10^......
  • Codeforces Round 970 (Div. 3) D. Sakurako‘s Hobby
     链接cf_Sakurako‘sHobby大意：给一堆点和边，并给出点的颜色，输出每个点能遍历到几个黑点思路：1、这些点边里面有拓扑结构，也有环2、先处理拓扑排序的一些点，依次遍历无父节点的即可，之后就会剩下环3、有环的说明每个点都能去到环内任意一点，那么直接就记录一个sum，然后递归......
  • Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)
    目录写在前面A签到B贪心，枚举C1贪心C2贪心，枚举DDPE1/E2Kruscal重构树，树上背包写在最后写在前面补题地址：https://codeforces.com/contest/2021。上大分失败呃呃呃呃我不要上班呜呜A签到考虑仅有三个数\(a,b,c(a<b<c)\)时最优操作，手玩下发现最优操作顺序一定是......
  • divide by zero encountered in log10 my_vmin=np.log10(data['PValue'].min())
     sm=plt.cm.ScalarMappable(cmap='viridis',norm=plt.Normalize(vmin=np.log10(data['PValue'].min()),vmax=np.log10(data['PValue'].max()))) C:\Python310\lib\site-packages\pandas\core\arraylike.py:397:RuntimeWarning:d......
  • Codeforces Round 316 (Div. 2) D题 Tree Requests（二分，dfs，在线，前缀异或）
    题目链接CodeforcesRound316(Div.2)D题TreeRequests思路将262626个字母全部当作一个二进制数。将每个深度的结点按照dfs序放到一个vector里，同时记录每个vector......
  • 【前缀和+开区间二分】codeforces 1187 B. Letters Shop
    题意第一行，输入一个正整数\(n(1\leqn\leq2*10^5)\)，代表字符串\(s\)的长度。第二行，输入一个字符串\(s\)。第三行，输入一个正整数\(m(1\leqm\leq5*10^4)\)，代表接下来要输入的询问次数，对于每次询问：输入一个字符串\(t(1\leq|t|\leq2*10^5)\)，并保证\(\sum_{i=1}^m......
  • Codeforces Round 969 (Div. 2)
    一万五参赛，赛时（VP）排名80A.Dora'sSet比较新的结论题。显然，一个合法三元组最多只能有一个偶数。每个偶数都可以跟相邻两个奇数组成合法三元组。因此，答案为奇数个数的二分之一（下取整）。#include<bits/stdc++.h>usingnamespacestd;intT,l,r;intmain(){ scanf("%d",......
  • Codeforces Round 977 (Div. 2)
    手速局，因为水平不够三题遗憾离场。A.MeaningMean题意你一个序列，你每次可以选择两个数删掉，并把他们的平均数加入到序列的末尾。当序列长度为\(1\)的时候，剩下的数最大值是多少。思路当时比赛的时候唐了，耽误了好几分钟。想的是先奇数和奇数相加，偶数和偶数相加，这样能避免下取......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99