首页 > 其他分享 >The 2020 ICPC Asia Shenyang Regional Programming Contest

The 2020 ICPC Asia Shenyang Regional Programming Contest

时间：2024-09-11 22:25:21浏览次数：1  
标签：Shenyang frac Contest int Regional i64 HM using pi

D - Journey to Un'Goro

记\(p_i\)表示前缀\(i\)中\(\mathrm r\)的个数。则题目要求的是\(p_r - p_{l-1}\)为奇数最多有多少对。显然应该越平均越好。

\(p_i\)总共有\(n+1\)个，则奇偶数的数量均不超过\(m = \left\lceil \frac {n + 1}{2}\right\rceil\)，答案就是\((n + 1 - m )\times m\)。

因此我们可以按照字典序最小进行搜索，并根据\(m\)的值进行剪枝。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9, INF = 1e18;

void test() {
    for (int _ = 1; _ <= 10; _++) {
        int n = _;
        vector<vector<int>> ret;
        int mx = 0;
        for (int i = 0; i < (1 << n); i++) {
            vector<int> bit;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) bit.push_back(1);
                else
                    bit.push_back(0);
            }
            int ans = 0;
            for (int j = 0; j < n; j++) {
                int cnt = 0;
                for (int k = j; k < n; k++) {
                    cnt += bit[k];
                    if (cnt & 1) ans++;
                }
            }
            if (ans > mx) {
                mx = ans;
                ret.clear();
            }
            if (ans == mx) ret.push_back(bit);
        }
        cout << n << ' ';
        cout << mx << '\n';
        sort(ret.begin(), ret.end());
        for (int j = 0; j < ret.size() && j < 100; j++) {
            cout << j + 1 << " : ";
            for (int k = 0; k < n; k++) {
                if (ret[j][k] == 1) cout << 'r';
                else
                    cout << 'b';
            }
            cout << '\n';
        }
    }
}

int cnt = 0, n, m;
vector<char> s;

void dfs(int i, int x, int y, int t) { // x 为偶数的个数, y 为奇数的个数
    if (x > m or y > m) return;
    if (i == n) {
        if (x != m and y != m) return;
        for (auto c: s)
            cout << c;
        cout << "\n";
        if (++cnt == 100) exit(0);
        return;
    }
    s[i] = 'b';
    dfs(i + 1, x + (t == 0), y + (t == 1), t);
    s[i] = 'r';
    dfs(i + 1, x + (t == 1), y + (t == 0), t ^ 1);
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    m = (n + 2) / 2;
    cout << m * (n + 1 - m) << "\n";
    s.resize(n);
    dfs(0, 1, 0, 0);
    return 0;
}

F - Kobolds and Catacombs

我们把原序列称为\(a\)，排序后称为\(b\)。如果序列\(a,b\)在区间\([l,r]\)中所有数字出现次数相同，则\([l,r]\)可以被分为一段。

根据这个规则，直接贪心分割就好了。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9, INF = 1e18;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    vi b = a;
    ranges::sort(b);
    int res = 0;
    unordered_map<int, int> cnt;
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        cnt[a[i]]++;
        if (cnt[a[i]] == 0) y--;
        if (cnt[a[i]] == 1) x++;

        cnt[b[i]]--;
        if (cnt[b[i]] == 0) x--;
        if (cnt[b[i]] == -1) y++;

        if (x == 0 and y == 0) res++;
    }
    cout << res;
    return 0;
}

G - The Witchwood

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9, INF = 1e18;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (auto &i: a) cin >> i;
    ranges::sort(a, greater<>());
    a.resize(k);
    i64 sum = 0;
    for (auto i: a)
        sum += i;
    cout << sum;

    return 0;
}

H - The Boomsday Project

我们考虑记录\(\sum p_i \times q_i\)次骑车。

比如3条记录

1 2
2 3
3 2

我们就要记录为

1 1 2 2 2 3 3

这样的，假设总共骑车\(N\)次，其中第\(i\)次骑车的日期为\(date_i\)。

这样的话，我们记状态\(f[i]\)表示前\(i\)次骑车的最小花费。

我们的转移可以分为两类，第一类是直接购买，\(f[i] = f[i-1] +r\)。

还有一种情况是，我们枚举打折卡\((d,k,c)\)，我们找到最早的骑车\(j\)，满足\(date_j \ge date_i - d + 1 \and j \ge i + 1 - k\)，则有转移\(f[i] = f[j - 1] + c\)。

当然了这样转移复杂度是\(O(N^2 n)\)。

但是我们考虑对于\(i\)，\(j\)一定是单调的。这样的话，我们可以用\(n\)个双指针来维护。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9, INF = 1e18;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, r;
    cin >> n >> m >> r;
    vector<array<int, 3>> a(n); // d day, k free rents, c cost;
    for (auto &[d, k, c]: a) cin >> d >> k >> c;

    vi date(1);
    for (int i = 1, p, q; i <= m; i++) {// p date, q = times;
        cin >> p >> q;
        while (q--) date.push_back(p);
    }
    ranges::sort(date);
    int N = date.size() - 1;
    vi f(N + 1), lst(n, 1);
    for (int i = 1; i <= N; i++) {
        f[i] = f[i - 1] + r;
        for (int j = 0; j < n; j++) {
            const auto &[d, k, c] = a[j];
            while (date[lst[j]] < date[i] - d + 1 or lst[j] < i + 1 - k)
                lst[j]++;
            f[i] = min(f[i], f[lst[j] - 1] + c);
        }
    }
    cout << f[N] << "\n";
    return 0;
}

I - Rise of Shadows

首先分针的转速\(w_1 = \frac{2\pi}{M}\)，时针的转速\(w_2 = \frac{2\pi}{HM}\)，在经过\(T\)分钟后的角度差为

\[\Delta \theta = T (w_1 - w_2) \mod {2\pi} = T(\frac{2\pi}{M} - \frac{2\pi}{HM}) \mod {2\pi} = T\frac{2\pi}{HM}(H - 1)\mod{2\pi} \]

根据题目要求得到不等式

\[\Delta \theta \le \frac{2\pi A}{MH}\\ \Rightarrow T \frac{2\pi}{HM}(H - 1) \mod {2\pi} \le \frac{2\pi A}{HM}\\ \Rightarrow T (H - 1) \mod HM \le A \]

和不等式

\[2\pi - \Delta \theta \le \frac{2\pi A}{HM}\\ \Rightarrow \Delta \theta \ge 2\pi - \frac{2\pi A}{HM}\\ \Rightarrow T \frac{2\pi}{HM}(H - 1) \mod {2\pi} \ge 2\pi - \frac{2\pi A}{HM}\\ \Rightarrow T (H-1)\mod HM \ge HM - A \]

令\(d = \gcd(H-1,HM)\)，根据

\[AB \le C \Rightarrow A\le \left\lfloor \frac C B\right\rfloor\\ AB \ge C \Rightarrow A\ge \left\lceil \frac C B\right\rceil\\ \]

可以得到

\[T \frac{(H - 1)}{d} \mod \frac{HM}{d} \le \left\lfloor \frac{A}{d}\right\rfloor\\ T \frac{(H - 1)}{d} \mod \frac{HM}{d} \ge \left\lceil \frac{HM - A}{d}\right\rceil \]

对于左侧，因为\(\frac{H-1}{d},\frac{HM}{d}\)互质，因此左侧整个的取值为\([0,\frac{HM}{d})\)

对于右侧，根据题目已知条件\(A\le \frac{HM}{2}\)可以得到

\[\left\lfloor \frac{A}{d}\right\rfloor < \frac{HM}{d}\\ \left\lceil \frac{HM - A}{d}\right\rceil < \frac{HM}{d} \\ \]

因此对于第一个不等式左侧的合法取值范围是\([0,\left\lfloor \frac{A}{d}\right\rfloor]\)，第二个不等式合法取值范围是\([\left\lceil \frac{HM - A}{d}\right\rceil,\frac{HM}{d})\)。

所以解的个数就是

\[\left\lfloor \frac{A}{d}\right\rfloor + 1 + \frac{HM}{d} - \left\lceil \frac{HM - A}{d}\right\rceil \]

特别的当\(A == HM - A\)在等号处会计算重复，此时的解的个数为\(\frac{HM}{d}\)。

当然了以上的计算，可以认为是一轮。一共进行的\(d\)轮，所以最终的答案还要乘\(d\)

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;
const int inf = LLONG_MAX / 2;

i32 main() {
    int H, M, A;
    cin >> H >> M >> A;
    int HM = H * M;
    int d = gcd(H - 1, HM);
    if (HM == A * 2) {
        cout << HM;
    } else {
        cout << (A / d + 1 + HM / d - (HM - A + d - 1) / d) * d;
    }
    return 0;
}

K - Scholomance Academy

关于题目难点是理解题目。

记真的阳性数为\(Positive\)，阴性数为\(Negative\)，则有\(Positive=TP + FN,Negative = TN + FP\)。

这样的话\(TPR,FPR\)实际上都是只有一个变量。然后再看这个积分，实际上就是样例里面的图的面积。

这个图怎么来的？实际上就是根据坐标点\((TPR,FPR)\)连成一个折线图。

而积分的值就是\(\sum \frac{tp}{Positive} \times \frac{1}{Negative}\)。

然后我们考虑初始的\(\theta = 0\)，此时\(TPR = 1 , FPR = 0\)。然后把所有的\(instances\)按照\(score\)排序，然后初始的\(tp = Positive\)，然后如果这个\(type\)为阳性，这说明随着\(\theta\)增大这个阳性要被错误的估计，所以tp —。否则的话，说明\(FPR\)会发生改变，此时产生了新的值，因此我们要记录一下当前的答案\(\frac{tp}{Positive} \times \frac{1}{Negative}\)。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9, INF = 1e18;

struct instance {
    bool type;
    int score;

    bool operator<(instance &b) const {
        if (score != b.score) return score < b.score;
        return type > b.type;
    }
};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, positive = 0, negative = 0;
    cin >> n;
    vector<instance> a(n);
    for (char c; auto &it: a) {
        cin >> c >> it.score;
        it.type = (c == '+');
        if (it.type) positive++;
        else negative++;
    }
    sort(a.begin(), a.end());
    int tp = positive, res = 0;
    for (auto it: a) {
        if (it.type) tp--;
        else res += tp;
    }
    cout << fixed << setprecision(20) << (long double) res / (long double) (positive * negative);

    return 0;
}

标签：Shenyang,frac,Contest,int,Regional,i64,HM,using,pi
From： https://www.cnblogs.com/PHarr/p/18409123

相关文章

  • AtCoder Beginner Contest 370 补题记录
    A-RaiseBothHands题意：给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid思路：举左手：（l==1&&r==0)举右手：(l==1&&r==0)其他情况都是Invalidvoidsolve(){intl=read(),r=read();if(l==1&&r==0){......
  • 2016 ACM/ICPC Asia Regional Qingdao Online(SDKD 2024 Summer Training Contest H2)
    A-ICountTwoThree题意给定n，求第一个\(\ge\)n的数k，且k=\(2^a3^b5^c7^d\)。思路考虑到样例很多，直接打表存入set省去数组排序操作，由于n$\le$1e9，所以只需要打到1e9后二分即可。(记得加上快读快写，T得饱饱的......
  • Contest7685 - 综合训练-105
    题目按难度顺序排序。C合体原题：P3147[USACO16OPEN]262144P\(O(n\times(V+\logn))\)TODO:\(O(n\logn)\)TODO:\(O(n)\)TODO:A迷宫设计注意到题目是特殊性质的最小生成树问题。直接Kruskal能获得没有什么分数的好成绩。注意到，根据Kruskal算法的过程，每次选......
  • The 2024 CCPC Online Contest
    B-军训II题意n个人，第i个人身高为\(a_i\)，定义不整齐度为所有区间的身高极差之和。求不整齐度的最小值以及现在的排列方案数。不整齐度：\(\sum_{l=0}^n\sum_{r=l}^nmax(a_{pl}+a_{pl+1},···,+a_{pr})-min(a_{pl}+a_{pl+1},···,+a_{pr})\)思路按身高排......
  • The 2024 CCPC Online Contest
    目录写在前面LKBDEJIGC写在最后写在前面补题地址：https://codeforces.com/gym/105336以下按个人向难度排序。唉唉唐吧真是我去居然还能打出名额哈哈真牛逼L签到。K签到。dztlb大神直接秒了。显然奇数先手取1必胜，则偶数时为了让自己不输，先手和后手均会保证在取到2之......
  • AtCoder Beginner Contest 274 A~E 题解
    吐槽：这比赛名字为啥没有英文版。。。A-BattingAverage题目大意给定整数\(A,B\)，输出\(\fracBA\)，保留三位小数。\(1\leA\le10\)\(0\leB\leA\)分析签到题，使用printf或cout格式化输出即可。代码#include<cstdio>usingnamespacestd;intmain(){ inta,b; sc......
  • TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 29
    好久没写题解了，这就来水一篇。A-JobInterview题目大意给定一个长为\(N\)的字符串\(S\)，由o、-、x组成。判断\(S\)是否符合下列条件：\(S\)中至少有一个o。\(S\)中没有x。\(1\leN\le100\)分析签到题。直接按题意模拟即可。代码#include<cstdio>usingn......
  • AtCoder Beginner Contest 318 G - Typical Path Problem 题解
    G-TypicalPathProblem题目大意给定一张\(N\)个点、\(M\)条边的简单无向图\(G\)和三个整数\(A,B,C\)。是否存在一条从顶点\(A\)到\(C\)，且经过\(B\)的简单路径？数据范围：\(3\leN\le2\times10^5\)\(N-1\leM\le\min(\frac{N(N-1)}2,2\times10^5)\)\(1\leA......
  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)（\(1\leB,G\le1000\)且\(B\neG\)），判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\)，求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位，注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数，因此无需使用整数输入，直接将输入看成......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99