首页 > 其他分享 >【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2

【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2

时间：2023-08-05 19:23:16浏览次数：42  
标签：150 qr 洛谷 int sum cin long MAXN Div.2

比赛实况

赛前看了眼难度分布，红橙黄绿，感觉随便杀（爆我）

顺序开题，先看 A 题，没仔细读，一眼以为单次操作只能翻转一位，写了个十进制转二进制找不同，结果 WA 了。
再看了一眼题，发现题干定义的操作可以一次操作很多位，然后一个操作是把 0 变 1，另一个是把 1 变 0。
所以只需要看两个数二进制对应位置上的数分别是 0,1 还是 1,0，每种需要一步操作，至多两步，A 题 AC。

然后看 B，一眼瞪出了个二分做法，每次操作时枚举每一列，在每一列上做二分。
反正代码很简单，都没算复杂度直接开打，一交，50pts。
回来看了眼数据范围，发现这么做铁定 tle，然后想了想决定离线做，把时间复杂度搞到 \(O(n^2)\)。
然后就写炸了……，看了两眼 C 题，看到树就有点不太想开，回来再调了会儿，依然是全 WA。
不过好歹没 tle，就先抛下来去看 C 题，准备之后再调一调。

C 题看了一会儿，发现跟树没什么关系，做一遍 dfs 把深度处理出来，然后就跟树没关系了。
首先想到的判断无解的方法是对深度求和，看奇偶性，如果和是奇数直接判无解。
然后凑数字的部分也还挺好做的，跟用二进制表示一个数，以及求 lca 的时候倍增上跳很像，从大到小拿深度往上加就行了。
很快写好代码，一交，85pts。
看到两个点 WA，第一反应没开 long long，改完再一交，95pts，有点难受。
这个时候心态还算稳定，开始静态查错，发现深度居然没排序，这能干到 95pts 也真是神奇，补上排序一交，AC。

然后看 D，一眼感觉是个贪心，第二眼把自己否定了。
因为模模糊糊感觉单次操作不仅仅和 i 与 i+1 有关，如果 i 不够还可以从前面转换补一点过来。
然后马上决定看数据范围，先打部分分，看到 \(x_i=10^9\)，第一眼不明所以，稍微想了想，这不是根本不用操作？！
然后就炸了。
心态大崩，回去调 B，各种调调不出来，决定重写，然后写到一半突然发现我的 sort 写错了……
应该是 sort(qr+1, qr+q+1, cmp)，我写成了 sort(qr+1, qr+n+1, cmp)。
样例里面 \(n=q\)，怎么测都测不出来。警钟敲烂：两个大小不一样的数组分别做排序，要分清大小，不要顺手都写 \(n\)。

然后改完一交 B，发现最后一个 subtask 里面有两个点 tle 了，而且只超了一秒以内，马上把 cin/cout 换成 scanf/printf，AC。
然后突然想到，不会二分的做法也是因为这个挂了吧。
赶紧回头一测，还好改完还是挂成 50pts，不然心态真的要崩了。

300pts，本来以为稳得不得了，一看榜，好家伙 rk300+。
到这里这场比赛已经变成 ABC 手速场，以及 D 部分分大赛了，当下决定去 D 搞点分先。

再读了一遍题，看到了题干里的【非负数】，心里一惊，好家伙数据范围看错了，没看到 \(c=0\) 和 \(v=0\) 是可以的……
然后改了改代码，反正如果这个位置 \(v=0\)，那就操作一次丢到后面去，一交，依然 WA。
心态雪崩，回来看了眼数据范围，嗷又没开 long long ……
成功搞到 5pts，排名直接变成 200+，不愧是部分分大赛……

然后看 subtask2，\(x=1\)，一眼贪心，全部转到往后 \(v\) 最大的地方就行了。
本来以为很好写，没想到又是各种 WA。
再看了一眼数据范围，感觉如果全部操作完最后再算，能把 long long 撑爆开。
于是换写法，直接计算 c[i] 对答案的贡献，反正操作完再算和这个一样，结果又 WA。
想着反正就靠这题部分分了，心态稳定了不少，结果发现是写 for 循环的时候 <= 写成了 <，5pts->20pts。

特殊性质 3 不明所以，直接想 \(n\leq300\) 的暴力。
各种想怎么立方枚举，好久没想出来，决定先按照之前的 hack 思路先搓几个数据出来。
解法嗑了好久，先是想什么从 \(i\) 到 \(j\) 的最小 \(v\) 值，再是想转换过去的收益，然后往枚举上面靠，最后靠写注释理清了思路。

枚举 i、j，每次看看从 i 转换到 j 可不可行，赚不赚钱
如果可行又赚钱，那么必须转

是否可行，以及具体操作，都可以用模拟解决，反正复杂度能到立方。
结果写完一交发现是自己自信了，subtask3 全 T 了。
（这里加了 \(sid\) 的特判，丝毫没有意识到自己应该写的是 subtask4……）

然后一想，如果枚举 \(i\rightarrow j\)，结果中间有一步 \(i\rightarrow k\) 已经转换不了了，那么就没有继续枚举下去的必要了，直接跳出。
成功地再搞到了 15pts，rk 涨到了 100+。
然后终于发现了，应该写的是 subtask4，怎么 subtask3 莫名其妙过了，心里一喜，这不是 subtask3 随便过？！
然后就 WA 了…………………………………………………………
一直哇到比赛结束，各种调，怎么都写不出来……
比赛结束，rk129，跑完反作弊可能会再涨一点。
最后几分钟刷了几下榜，发现竟然有人 ak 了，%%%

为什么 2D 是一道黑题啊？？？
蚌埠住了，红—橙—黄—黑，这恒河里。

赛时代码

A (100pts)

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+5;
int t;

/*
*/

int main()
{
    cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen("A_00.in", "r", stdin);

    // I.N.
    cin >> t;
    while (t--) {
        long long a, b, s1=0, s2=0;
        cin >> a >> b;
        while (a || b) {
            if (a%2 != b%2) {
                s1 |= a%2;
                s2 |= b%2;
            }
            a/=2; b/=2;
        }
        cout << s1+s2 << endl;
    }

    // E.D.
    return 0;
}

B (50pts)

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e3+5;
int n, q, a[MAXN][MAXN];

/*
*/

int main()
{
    // cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen("B_00.in", "r", stdin);

    // I.N.
    // cin >> n >> q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // cin >> a[i][j];
            scanf("%d", &a[i][j]);
        }
        sort(a[i]+1, a[i]+n+1);
    }

    // Q.E.
    while (q--) {
        int v, sum=0;
        // cin >> v;
        scanf("%d", &v);
        for (int i = 1; i <= n; ++i) {
            int idx = lower_bound(a[i]+1, a[i]+n+1, v)-(a[i]+1);
            sum += n-idx;
            if (sum >= n) { break; }
        }
        // cout << min(sum, n) << endl;
        printf("%d\n", min(sum, n));
    }

    // E.D.
    return 0;
}

B (100pts)

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e3+5, MAXQ=5e5+5;
int n, q, a[MAXN][MAXN], ans[MAXQ];

/*
*/

struct query {
    int idx, v;
} qr[MAXQ];

bool cmp_v(query a, query b)
{
    return a.v < b.v;
} 

int main()
{
    // cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen("B_00.in", "r", stdin);

    // I.N.
    // cin >> n >> q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        a[i][0] = 0;
        for (int j = 1; j <= n; ++j) {
            // cin >> a[i][j];
            scanf("%d", &a[i][j]);
        }
        sort(a[i]+1, a[i]+n+1);
    }
    for (int i = 1; i <= q; ++i) {
        qr[i].idx=i;
        // cin >> qr[i].v;
        scanf("%d", &qr[i].v);
    }
    sort(qr+1, qr+q+1, cmp_v);

    // 离线
    int cnt_to_limit = 0;
    for (int i = 1; i <= q; ++i) {
        int sum = 0;
        if (cnt_to_limit < n) {
            for (int j = 1; j <= n; ++j) {
                if (a[j][0] > n) { continue; }
                while ( (a[j][0] <= n) && (a[j][ a[j][0] ] < qr[i].v) ) { ++a[j][0]; }
                cnt_to_limit += (a[j][0]>n);
                sum += n-a[j][0]+1;
            }
        }
        ans[qr[i].idx] = min(sum, n);
    }

    // E.D.
    for (int i = 1; i <= q; ++i) {
        // cout << ans[i] << "\n";
        printf("%d\n", ans[i]);
    }
    return 0;
}

C (100pts)

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e6+5;
int n, cnt=1, head[MAXN], c[MAXN];

struct edge {
    int v, nxt;
} e[MAXN<<1];

struct node {
    int idx, depth;
} nd[MAXN];

bool cmp_d(node a, node b)
{
    return a.depth < b.depth;
}

void add_edge(int u, int v)
{
    e[++cnt] = {v, head[u]};
    head[u] = cnt;
}

void dfs(int u, int fa, int d)
{
    nd[u] = {u, d};
    for (int i = head[u]; i; i=e[i].nxt) {
        int v = e[i].v;
        if (v != fa) { dfs(v, u, d+1); }
    }
}

int main()
{
    cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen("C_01.in", "r", stdin);

    // I.N.
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    // dfs 求深度
    dfs(1, 0, 1);
    sort(nd+1, nd+n+1, cmp_d);

    // 对深度求和
    long long sum = 0;
    for (int i = 1; i <= n; ++i) { sum += nd[i].depth; }
    
    // 如果和是奇数，那么不行，否则可行
    if (sum & 1) { cout << -1 << endl; return 0; }

    // 从大到小考虑染色
    long long sum_w = 0;
    for (int i = n; i; --i) {
        if (sum_w + nd[i].depth <= sum/2) {
            sum_w += nd[i].depth;
            c[nd[i].idx] = 1;
        }
    }

    // 输出
    if (sum_w != sum-sum_w) { cout << -1 << endl; return 0; }
    for (int i = 1; i <= n; ++i) { cout << c[i] << " "; }

    // E.D.
    return 0;
}

D (35pts)

#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e5+5, MOD=998244353;
int sid, t, n;
long long v[MAXN], c[MAXN], x[MAXN];

/*
*/

void in()
{
    // I.N.
    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> v[i]; }
    for (int i = 1; i <= n; ++i) { cin >> c[i]; }
    for (int i = 1; i < n; ++i) { cin >> x[i]; }
}

long long calc_sum()
{
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum = (sum + 1LL*v[i]*c[i]) % MOD;
    }
    return sum;
}

namespace case1
{
    void solve()
    {
        while (t--) {
            in();

            // 操作
            for (int i = 1; i < n; ++i) {
                if ( (c[i] >= x[i]) && (v[i] == 0) ) {
                    c[i] -= x[i];
                    ++c[i+1];
                }
            }

            // E.D.
            cout << calc_sum() << endl;
        }
    }
}

namespace case2
{
    long long gt[MAXN];
    long long maxv=0;

    void solve()
    {
        while (t--) {
            in();

            // 判断后方钱币中 v 的最大值
            // 如果 gt[i]>=v[i]，表示后方有 v 更大的钱币，在 x=1 的情况下需要往后转移，答案加上 gt[i]*c[i]
            // 否则答案加上 v[i]*c[i]
            maxv = gt[n] = v[n];
            for (int i = n-1; i; --i) {
                gt[i] = maxv;
                maxv = max(maxv, v[i]);
            }

            // 按照 gt[]操作
            long long sum = 0;
            for (int i = 1; i <= n; ++i) {
                sum = (sum + max(gt[i], v[i])*c[i]) % MOD;
            }

            // E.D.
            cout << sum << endl;
        }
    }
}

namespace case3
{
    /*
    枚举 i、j，每次看看从 i 转换到 j 可不可行，赚不赚钱
    如果可行又赚钱，那么必须转
    */

    bool f;

    long long profit(int s, int t)
    {
        long long p=0, curc=c[s];
        for (int i = s+1; i <= t; ++i) {
            p -= (curc-curc%x[i-1]) * v[i-1];
            p += (curc/x[i-1]) * v[i];
            if (curc / x[i-1] == 0) { f=false; return 0; }
            curc = c[i] + curc / x[i-1];
        }
        return p;
    }

    void operate(int s, int t)
    {
        for (int i = s+1; i <= t; ++i) {
            c[i] += c[i-1] / x[i-1];
            c[i-1] = c[i-1] % x[i-1];
        }
    }
   
    void solve()
    {
        while (t--) {
            in();

            // 枚举，把 i 转移到 j
            for (int i = 1; i <= n; ++i) {
                f = true;
                for (int j = i+1; j <= n; ++j) {
                    long long p = profit(i,j);
                    if (!f) { break; }
                    if (p > 0) { operate(i,j); }
                }
            }

            // E.D.
            cout << calc_sum() << endl;
        }
    }
}

namespace case4
{
    bool f;

    long long profit(int s, int t)
    {
        long long p=0, curc=c[s];
        for (int i = s+1; i <= t; ++i) {
            p -= (curc-curc%x[i-1]) * v[i-1];
            p += (curc/x[i-1]) * v[i];
            if (curc / x[i-1] == 0) { f=false; return 0; }
            curc = c[i] + curc / x[i-1];
        }
        return p;
    }

    void operate(int s, int t)
    {
        for (int i = s+1; i <= t; ++i) {
            c[i] += c[i-1] / x[i-1];
            c[i-1] = c[i-1] % x[i-1];
        }
    }
   
    void solve()
    {
        while (t--) {
            in();

            // 计算初始的和
            long long sum = calc_sum();

            // 枚举，把 i 转移到 j
            for (int j = 1; j <= n; ++j) {
                for (int i = 1; i < j; ++i) {
                    long long p = profit(i,j);
                    if (p > 0) { operate(i,j); sum = (sum+p)%MOD; }
                }
            }

            // E.D.
            cout << sum%MOD << endl;
        }
    }
}

int main()
{
    cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen("D_03.in", "r", stdin);

    // I.N.
    cin >> sid >> t;
    switch (sid) {
        case 1: case1::solve(); break;
        case 2: case2::solve(); break;
        case 3: case3::solve(); break;
        default: case4::solve();
    }
    
    // E.D.
    return 0;
}

标签：150,qr,洛谷,int,sum,cin,long,MAXN,Div.2
From： https://www.cnblogs.com/LittleDrinks/p/17608454.html

相关文章

  • 【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2
    T1一直没有详细看过位运算的我瑟瑟发抖。出题人给了帮助（有用但是不多）。直接讲考试想法：首先，手玩样例后，果断猜测：将两个数转化为二进制之后，把头对齐，然后找出不同位，再加上二者位数之差。结果：\(0Pts\)之后，又想了很久，发现了按位与等价于将原来二进制数中的1变为0，按位或等价于将原来......
  • LGR-147-Div.3】洛谷网校 7 月普及组月赛 & yLOI2022 总结
    Upd：2023/8/5补T1普及组的题，而且T1，而且叫签到题。所以非常简单，入门难度。没什么好说的。就是统计大写，小写和字母个数。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=100+5;strings;intmain(){ cin>>s; intx=0,y=0,z=0; for(inti=......
  • 洛谷 P1553 数字反转（升级版）
    题目描述给定一个数，请将该数各个位上数字反转得到一个新数。整数反转是将所有数位对调。小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分。分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母。百分数的分子一定是整数，百分数只改变数字......
  • 洛谷 P7911 [CSP-J 2021] 网络连接 题解
    写在前面一道普及级别的题目。CSP-J全国统一命题2021年第三题。本题解来自于一位真正的大佬。传送门https://www.luogu.com.cn/blog/xyf007/solution-p7911。题面信息来源于洛谷。请访问https://www.luogu.com.cn/problem/P7911。声明：本题解非商业用途，一切侵权行为请联系作......
  • nfls15095 Atcoder-abc123_d 蛋糕
    Atcoder-abc123_dAT小卖部从下学期开始售卖带有数字形状的蛋糕，\(X\)，\(Y\)和\(Z\)种蛋糕分别带有\(1\)形，\(2\)形和\(3\)形蜡烛，而且每个蛋糕都有美味值，如下所示：带有\(1\)形蜡烛的美味值有：\(A_1,A_2,\cdots,A_X\)带有\(2\)形蜡烛的美味值有：\(B_1,B_2,\cdots,B_Y\)......
  • 洛谷 U321190 麻将 加强加强版 题解
    Description给定一副\(k\)张牌的麻将牌，求能「听」哪些牌。对于所有数据，\(1\leqk\leq2\times10^5\)。link：https://www.luogu.com.cn/problem/U321190Solution算法零枚举「听」的牌，用状压DP或者贪心判断。时间复杂度\(\mathcal{O}(2^n\text{poly}(n))\)或\(\mathca......
  • 洛谷-P9485 题解
    写在前面：这是蒟蒻交的第一篇绿题题解（大祭），因为线性做法比较难想，本篇会着重讲述用RMQ问题求解，并尽可能用清晰明了的图片和简易的文字讲明白。正文最坏时间复杂度：\(\mathcal{O}(\sumn+\log\sumn)\)在求解之前，先让我们想个问题，如何求解积水格数？再简单点，对于每个\(i\)，其积水......
  • 洛谷 P9489 ZHY 的表示法 题解
    Description给定\(\{x_n\}\)，\(y\)为任意实数，求出在\([l,r]\)内\(\displaystyle\sum_{i=1}^{n}\lfloor\dfrac{y}{x_i}\rfloor\)有多少种取值。link：https://www.luogu.com.cn/problem/P9489Solution可以表示出的取值一定能被为某个\(x_i\)的倍数的\(y\)表示出。根据......
  • Round 889 Div.2 意识流简记。
    太丢人了！D2D狂吃6发罚时，D2C都不会！不过无所谓，反正老年选手就是打着玩。D2A.答案为\(\lceil\frac{\sum_{i=1}^n[a_i=i]}{2}\rceil\)。D2B.我不会啊，猜了一下只需要枚举\(\le2000\)的，莫名其妙过了。D2C1/C2.不会。D2D.考虑动态维护前\(i\)个能凑出的数的集合，适时......
  • 洛谷 P3243 [HNOI2015] 菜肴制作 - toposort 需自己理解翻译题面
    P3243[HNOI2015]菜肴制作题目描述知名美食家小A被邀请至ATM大酒店，为其品评菜肴。ATM酒店为小A准备了\(n\)道菜肴，酒店按照为菜肴预估的质量从高到低给予\(1\)到\(n\)的顺序编号，预估质量最高的菜肴编号为\(1\)。由于菜肴之间口味搭配的问题，某些菜肴必须在另一些......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99