首页 > 其他分享 >AtCoder Beginner Contest 356

AtCoder Beginner Contest 356

时间:2024-06-01 23:11:40浏览次数:30  
标签:lfloor AtCoder frac Beginner int sum cin rfloor 356

A - Subsegment Reverse (abc356 A)

题目大意

给定一个 \(1,2,3,...,n\)的排列\(a\),给定两个数 \(l,r\),左右颠倒\(a[l..r]\)。输出。

解题思路

按照题意模拟即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    --a;
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 1);
    reverse(ans.begin() + a, ans.begin() + b);
    for (auto x : ans)
        cout << x << ' ';
    cout << '\n';

    return 0;
}



B - Nutrients (abc356 B)

题目大意

给定一天\(n\)种营养的摄入目标量。

给定\(m\)种食物的\(n\)种营养的含量。

问是否所有营养都达到目标摄入了。

解题思路

按照题意,对每种营养的摄入总量求和,与目标比较即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (auto& x : a)
        cin >> x;
    while (n--) {
        for (auto& x : a) {
            int s;
            cin >> s;
            x -= s;
        }
    }
    bool ok = true;
    for (auto x : a) {
        ok &= x <= 0;
    }
    if (ok) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }

    return 0;
}



C - Keys (abc356 C)

题目大意

\(n\)把钥匙,有些真的,有些假的。一个门,可以拿一些钥匙打开它,若其中有 \(k\)个真的钥匙,则门打开。

给定了 \(m\)条记录,表示用了哪些钥匙,门是否打开。

对于这\(n\)把钥匙的真假,共 \(2^n\)种情况,问有多少种情况,不违反上述的记录。

解题思路

\(n\)只有 \(15\),直接 \(O(2^n)\)枚举所有情况,然后枚举每个记录,检测其钥匙能否打开门,与结果是否相符。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<vector<int>, int>> a(m);
    for (auto& [v, c] : a) {
        int x;
        cin >> x;
        v.resize(x);
        for (auto& x : v) {
            cin >> x;
            --x;
        }
        string s;
        cin >> s;
        c = s[0] == 'o';
    }
    int ans = 0;
    int up = (1 << n);
    for (int i = 0; i < up; ++i) {
        bool ok = true;
        for (auto& [v, c] : a) {
            int cnt = 0;
            for (auto x : v) {
                if (i & (1 << x)) {
                    ++cnt;
                }
            }
            if ((cnt >= k) ^ c) {
                ok = false;
                break;
            }
        }
        ans += ok;
    }
    cout << ans << '\n';

    return 0;
}



D - Masked Popcount (abc356 D)

题目大意

给定\(n,m\),求 \(\sum_{k=0}^{n}popcount(k\&m)\)

\(popcount(x)\)表示 \(x\)二进制下 \(1\)的个数。

解题思路

\(n\)高达 \(10^{18}\),直接枚举会超时。

考虑贡献转换。

考虑到答案来自于二进制下\(1\)的个数。 由于\(\&\)运算的特性,这些实际都是来自于\(m\)的每一个\(1\)。 我们需要考虑\(m\)二进制下每一个 \(1\)对答案的贡献,即有多少个 \(k\),使得 \(k\&m\)后该位是 \(1\)。

假设\(m\)的二进制表示为 \(1...10...0\),考虑第 \(i\)位上的\(1\),思考有多少个 \(k\),使得 \(k\&m\)的第\(i\)位是 \(1\)。

考虑如何计算 \(k\)的数量,首先, \(k\)的第 \(i\)位一定是 \(1\),然后就剩下低位高位的情况数。低位就是低于\(i\)位的那些位数的取值,高于 \(i\)位的就是高于 \(i\)位的位数取值。这个计数问题其实和数位\(dp\)差不多。

由于\(k\)有最大值 \(n\)的限制,低位的情况数会依赖于高位 ,为方便表述,设高位是\(up\),当前位是 \(middle\),低位是 \(down\),比如 \(n=110101\),当前第 \(i=2\)位(从 \(0\)开始),则 \(up=110, middle=1, down=01\)。然后情况数其实就分两种:

  • 如果高位取值和\(n\)的高位不一致,则低位取值没有限制,因此低位的情况数是\(2^i\) ,而高位的情况数是\(up\),若此时 \(m\)的第 \(i\)位是 \(1\),则其贡献(出现的次数)为 \(2^i \times up\)。
  • 如果高位取值和\(n\)的高位一致,则当前位低位的都会收到\(n\)的限制。如果此时 \(middle=0\),则说明该位不能取 \(1\),则 \(m\)的第 \(i\)位没有贡献。否则 \(middle=1\),低位的情况数就有 \(down+1\)种情况,而高位的 情况数只有\(1\)种,若此时 \(m\)的第 \(i\)位是 \(1\),则其贡献(出现的次数)为 \(down + 1\)。

综上,考虑第\(i\)位,其中 \(n\)的高位是 \(up\),当前位是 \(middle\),低位是 \(down\),若 \(m\)的第 \(i\)位是 \(1\),则其对答案的贡献(满足 \(k\&m\)的第 \(i\)位是 \(1\)的 \(k\)的个数)为 \(2^i \times up + middle \times (down + 1)\)。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL n, m;
    cin >> n >> m;
    LL ans = 0;
    LL up = n >> 1, middle = n & 1, down = 0, cnt = 1;
    for (int i = 0; i < 60; ++i) {
        if ((m >> i) & 1) {
            ans += 1ll * up * cnt % mo + middle * (down + 1);
            ans %= mo;
        }
        down = down | (middle << i);
        middle = up & 1;
        up >>= 1;
        cnt <<= 1;
    }
    cout << ans << '\n';

    return 0;
}



E - Max/Min (abc356 E)

题目大意

给定一个数组\(a\),求 \(\sum_{i=1}^{n}\sum_{j=i+1}^{n} \lfloor \frac{\max(a_i, a_j)}{\min(a_i, a_j)} \rfloor\)。

解题思路

作除法始终是最大值除以最小值,因此可以先对\(a\)进行排序再计算,这不会影响答案。

对 \(a\)从小到大排序后,考虑枚举 \(j\),然后计算 \(i < j\)情况对答案的贡献,即枚举最大值。

一个比较明显的观察是,可能会有若干个 \(a_i\),使得 \(\lfloor \frac{a_j}{a_i} \rfloor\)是同样的值。那我们可以把这些值合并地来算,即\(\times\)个数

事实上可以通过数论分块来求解,\(\lfloor \frac{a_j}{a_i} \rfloor\)的值的可能数量和因子个数同一个数量级,即\(O(\sqrt{a_i})\)个,而造成该取整结果的\(a_i\)的取值就是数论分块里的两个边界 \(l,r\),可以在 \(a\)中二分得到对应位置,因而得到个数。而这复杂度是\(O(n\log n\sqrt{a_i})\),会超时。

数论分块复杂度是根号级别,在这里用不了,只能另寻它路。

这次考虑枚举 \(i\),然后计算 \(i < j\)情况对答案的贡献,即枚举最小值。

同样考虑贡献转换,原本的想法是求\(\lfloor \frac{a_j}{a_i} \rfloor = val\)的\(a_j\)数量\(cnt\),然后累计\(val \times cnt\)。

我们将其\(val\)看成\(1+1+1...\),然后重组一下,变成求 \(\lfloor \frac{a_j}{a_i} \rfloor \geq val\)的\(a_j\)数量\(cnt\)。

即原本是求\(\lfloor \frac{a_j}{a_i} \rfloor = 1,2,3\)的\(a_j\)数量,现在求\(\lfloor \frac{a_j}{a_i} \rfloor \geq 1,2,3\)的\(a_j\)数量。

这里的贡献转换就是将\(\lfloor \frac{a_j}{a_i} \rfloor = 3\)对答案有\(3\)的贡献,拆成了 \(1+1+1\),即\(\lfloor \frac{a_j}{a_i} \rfloor \geq 1 + \lfloor \frac{a_j}{a_i} \rfloor \geq 2 + \lfloor \frac{a_j}{a_i} \rfloor \geq 3\),然后合并所有的\(\lfloor \frac{a_j}{a_i} \rfloor \geq 1\)(或\(2,3\)),求其个数。

现在我们的视角转换成求 \(\lfloor \frac{a_j}{a_i} \rfloor \geq v\)的\(a_j\)数量,即枚举\(v\),求\(a_j \geq va_i\)的\(j\)的数量。很明显通过在\(a\)数组二分\(va_i\),就能求得\(j\)的数量了。

由于\(max_a = 10^6\),那么这里枚举的\(v\)的数量就是\(O(\sum_{i=1}^{n} \frac{max_a}{a_i})\)。每次枚举都有一个二分的\(O(\log n)\),因此总的时间复杂度是\(O(\sum_{i=1}^{n} \frac{max_a}{a_i} \log n)\)。

如果所有的\(a_i\)都很小,比如都是 \(a_i=1\),那时间复杂度就是 \(O(nmax_a \log n)\),又炸了!

但看这个式子,非常像对数求和,如果\(a_i\)唯一,那复杂度就是\(O(\sum_{i=1}^{max_a} \frac{max_a}{i} \log n) = O(max_a \log max_a \log n)\),是可过的。

因此,如果\(a_i\)有重复的,那么我们就合并重复的数,并记录\(cnt_k\)表示 \(a_i=k\)的数量,然后考虑怎么修正一下答案的计算。

合并相同的数,并从小到大排序,然后枚举当前的 \(a_i\),再枚举 \(v\),求得第一个\(a_j > va_i\)的 \(a_j\),那么此时\(\lfloor \frac{a_j}{a_i} \rfloor \geq v\)的数量就是\(cnt_{a_i} \times \sum_{k \geq j} cnt_{a_k}\)。而后者\(\sum_{k=j}^{n} cnt_{a_j}\)就是一个关于\(cnt\)数组的后缀和,预处理一下就能\(O(1)\)得到。

然后对于相同数之间的贡献,则是\(\sum_{i} \frac{cnt_{a_i} \times (cnt_{a_i} - 1)}{2}\)。

最终的答案就是两者的和。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> r(n);
    for (auto& x : r)
        cin >> x;
    map<int, int> s;
    for (auto& i : r)
        s[i]++;
    vector<int> a;
    vector<int> sum;
    for (auto& [x, y] : s) {
        a.push_back(x);
        sum.push_back(y);
    }
    vector<int> suf(sum.size());
    partial_sum(sum.rbegin(), sum.rend(), suf.rbegin(), plus<int>());
    LL ans = 0;
    n = a.size();
    for (int i = 0; i < n; ++i) {
        int x = a[i];
        int pos = i + 1;
        ans += 1ll * sum[i] * (sum[i] - 1) / 2;
        while (pos < n) {
            pos = lower_bound(a.begin() + pos, a.end(), x) - a.begin();
            if (pos < n)
                ans += 1ll * sum[i] * suf[pos];
            x += a[i];
        }
    }
    cout << ans << '\n';

    return 0;
}



F - Distance Component Size Query (abc356 F)

题目大意

<++>

解题思路

<++>

神奇的代码



G - Freestyle (abc356 G)

题目大意

<++>

解题思路

<++>

神奇的代码



标签:lfloor,AtCoder,frac,Beginner,int,sum,cin,rfloor,356
From: https://www.cnblogs.com/Lanly/p/18226539

相关文章

  • atcoder350,351,352,353,354,355期部分题解
    声明:有些题感觉已经说到很明白了,就先不写代码了,有空会补上目录350D: newfriend350E:toward0351D:GridandMagnet352D:permutation subsequence353C:sigmaproblem353D:anothersigmaproblem354C:atcodermagics355C:bingo2355D:intersectingintervals......
  • AtCoder Beginner Contest 355 (E,F)
    总结:这把B都错题了一直Wa,然后队友告诉我说F貌似可做,写了半个小时F发现题目读假了,于是四题下班。E-GuesstheSum题目大意:给定一个隐藏的、长度为N的数组,下标从0开始,题目给定L,R,要你用最少的询问次数求出\(\sum_{i=L}^{R}a_{i}\)。对于每次询问,可以选择一个i和j,然......
  • Atcoder ABC355 C~F
    C出题人太善良了,加强到\(10^5\)都没问题。考虑维护每条横线竖线两条对角线上被标记的点的个数,每次标记点后,判断是否有线上点全被标记。再考虑如何将点编号转为坐标,记编号为\(t\),推柿子:\[(x-1)\timesn+y=t\]\[nx+y=t+n\]\[x=\frac{t+n-y}{n}\]等同于找到\(y\)使得:\[n......
  • 迅为RK3562开发板安卓人工智能主板性能之选
      迅为RK3562开发板在CPU性能上表现卓越。这款开发板采用了先进的处理器和丰富的接口设计,为用户提供了无与伦比的使用体验。   在CPU性能方面,迅为RK3562开发板搭载了高性能的四核A53处理器,主频高达2.0GHz,确保了强大的运算能力和高效的处理速度。无论是复杂的图像处理、......
  • AtCoder Beginner Contest 328
    A-NotTooHard#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<int>;i32main(){ ios::sync_with_stdio(false),cin.tie(nullptr); intn,x; cin>>n&g......
  • 全国产RK3568J + FPGA的PCIe、FSPI通信实测数据分享!
    测试数据汇总案例时钟频率理论速率测试结果FSPI通信案例150MHz71.53MB/s读速率:67.452MB/s写速率:52.638MB/sPCIe通信案例100MHz803.09MB/s读速率:595.24MB/s写速率:791.14MB/s备注:(1)当TLPheadersize=16Byte时,PCIe理论传输速率为:7......
  • 含税168元起!四核A53+NPU+PCIe+USB3.0,瑞芯微RK3562性价比真高!
     ......
  • 【日记】终于鼓起勇气买了吹风机!(356 字)
    正文好忙。今天比昨天还要忙,水都没喝几口。嗯,好像只喝了两口。今天补了一份印鉴卡,销了一个户,变了一个户,弄了一大堆资料找人签字,还顺带要解决一个押品的历史遗留问题。中午睡得好香,都不想起床。终于鼓起勇气,买下了米家的吹风机!降了整整8块钱。69块钱拿下。......
  • AtCoder Beginner Contest 124
    A-Buttons#include<bits/stdc++.h>usingnamespacestd;intmain(){ inta,b; cin>>a>>b; intres=0; if(a>b)res+=a,a--; elseres+=b,b--; if(a>b)res+=a,a--; elseres+=b,b--; cout<<res......
  • AtCoder abc325D
    原题链接ProblemStatementThereare\(N\)productslabeled\(1\)to\(N\)flowingonaconveyorbelt.AKeyenceprinterisattachedtotheconveyorbelt,andproduct\(i\)enterstherangeoftheprinter\(T_i\)microsecondsfromnowandleavesit......