首页 > 其他分享 >The 2022 ICPC Asia Hangzhou Regional Contest

The 2022 ICPC Asia Hangzhou Regional Contest

时间:2023-12-06 15:11:53浏览次数:34  
标签:Contest int vi sum Regional cin Asia long using

A. Modulo Ruins the Legend

首先题目要求的是$(\sum (a_i + s + i \times d))% m $的最小值

等价于求\((\sum a_i + n\times s + \frac{n(n+1)}{2} \times d) \%m\)的最小值

令\(sum =(\sum a_i) \% m , a=n\%m,b=(\frac{n(n+1)}{2})%m\)

即求\((sum + as + bd)\%m\)的最小值

其中根据贝祖定理可得\(as+bd=k_1g_1\),其中\(g_1=\gcd(a,b)\)

所以可转化为求\((sum+k_1g_1)\%m\)的最小值

因为\(k_1g_1\equiv k_1g_1+tm(\mod m)\)

所以可转化为求\((sum+k_1g_1+tm)%m\)的最小值

其中根据贝祖定理可得\(k_1g_1+tm=k_2g_2\),其中\(g_2=\gcd(g1,m)\)

所以可以转化为求\((sum+k_2g_2)\%m\)的最小值

其中\(sum\)可以表示为\(sum = k g_2+x\)的形式

所以可以转化为求\((kg_2+x+k_2g_2)\%m=((k+k_2)g_2+x)\%m\)的最小值

因为\(g_2\)是\(m\)的因子,这一定存在\(k_2\)使得\((k+k_2)g_2\equiv 0(\mod m)\)

所以最小值就是\(res=x=sum\%g_2\),同时可以解出\(k_2=\frac{res+m-sum}{g_2}\)

所以构造一组可行的解的方法是:

先解出\(as+bd=g_1\),再解出\(k_1g_1+tm=g_2\),根据\(g_2,sum\)解出\(res,k_2\)

最小值就是\(res\),等差数列是\(s=k_1k_2s,d=k_1k_2d\),解出的\(s,d\)可能为负数,要取模为正数

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
#define int long long

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int sum = 0;
    for (int i = 1, x; i <= n; i++)
        cin >> x, sum = (sum + x) % m;
    int a = n % m, b = (n * (n + 1) / 2) % m;
    int s, d;
    int g1 = exgcd(a, b, s, d);
    int k1, t;
    int g2 = exgcd(g1, m, k1, t);
    int res = sum % g2, k2 = (res + m - sum) / g2;
    s = (s * k1 % m * k2 % m + m) % m;
    d = (d * k1 % m * k2 % m + m) % m;
    cout << res << "\n" << s << " " << d << "\n";
    return 0;
}

C. No Bug No Game

本题中相当于最多只有一种装备不全部取走,所以设状态为\(f[i][j][0/1]\)表示前\(i\)种物品,拿了\(j\)件,是否有一件没有全部取走的最大收益。转移时就类似于 01 背包,但注意如果前一种状态是不合法的则无法进行转移。因为本题的要求是除非全部都取走的情况,否则必须严格的取\(k\)件。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, sum = 0;
    cin >> n >> m;
    vector f(m + 1, vi(2, -inf));
    f[0][0] = 0;
    for (int i = 1, p; i <= n; i++) {
        cin >> p, sum = min(sum + p, m);
        vi w(p + 1);
        for (int j = 1; j <= p; j++) cin >> w[j];
        for (int j = m; j >= 0; j--) {
            if (j - p >= 0) {
                if (f[j - p][0] > -inf) f[j][0] = max(f[j][0], f[j - p][0] + w[p]);
                if (f[j - p][1] > -inf) f[j][1] = max(f[j][1], f[j - p][1] + w[p]);
            }
            for (int k = 1; k < p; k++)
                if (j - k >= 0 and f[j - k][0] > -inf) f[j][1] = max(f[j][1], f[j - k][0] + w[k]);
        }
    }
    cout << max( f[sum][0] , f[sum][1] );
    return 0;
}

D. Money Game

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define double long double
const int N = 5e7 + 5;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<double> ve(n);
    for (int i = 0; i < n; ++i)cin >> ve[i];
    double all = accumulate(ve.begin(), ve.end(), 0.0);
    all /= (n + 1) * 1.0;
    cout << fixed << setprecision(7) << all * 2.0 << ' ';
    for (int i = 1; i < n; ++i) {
        cout << fixed << setprecision(7) << all << ' ';
    }
    return 0;
}

F. Da Mi Lao Shi Ai Kan De

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;

set<string> vis;

void solve() {
    int n, f = 1;
    cin >> n;
    for (string s; n; n--) {
        cin >> s;
        if (vis.insert(s).second == false) continue;

        if (s.find("bie") < s.size()) f = 0, cout << s << "\n";
    }
    if (f) cout << "Time to play Genshin Impact, Teacher Rice!\n";
}

i32 main() {
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

K. Master of Both

我的处理方法是首先处理任意影响两个串字典序的大小的对,然后统计所有对出现的次数,在每次询问时,我们只需枚举所有逆序对,然后查看逆序对出现的次数就好了。

统计影响字典序大小对的方式就是按照顺序把串插入到字段树上,在插入过程中每个分叉口统计。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
#define int long long
using vi = vector<int>;
const int inf = 1e18;

int n;
int cnt[27][27];

struct Tire {
    struct node {
        vi nxt;
        int val;

        node() {
            nxt = vi(27, -1);
            val = 0;
        }
    };

    vector<node> t;

    Tire() : t(1, node()) {};

    void insert(vi s) {
        int pos = 0;
        for (auto i: s) {
            t[pos].val++;

            for (int j = 0, v; j <= 26; j++) {
                if (i == j) continue;
                v = t[pos].nxt[j];
                if (v == -1) continue;
                cnt[j][i] += t[v].val;
            }

            if (t[pos].nxt[i] == -1)
                t[pos].nxt[i] = t.size(), t.push_back(node());
            pos = t[pos].nxt[i];
        }
    }
};


void solve() {
    string s;
    cin >> s;
    vi vis(27);
    int res = 0;
    vis[0] = 1;
    for (int i; auto c: s) {
        i = c - 'a' + 1;
        for (int j = 0; j <= 26; j++) {
            if (vis[j] == 0) continue;
            res += cnt[i][j];
        }
        vis[i] = 1;
    }
    cout << res << "\n";


}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    cin >> n >> TC;
    Tire tire;
    for (string s; n; n--) {
        cin >> s;
        vi a;
        for (auto c: s) a.push_back(c - 'a' + 1);
        a.push_back(0);
        tire.insert(a);
    }

    while (TC--) solve();
    return 0;
}

标签:Contest,int,vi,sum,Regional,cin,Asia,long,using
From: https://www.cnblogs.com/PHarr/p/17879590.html

相关文章

  • [Codeforces Round 855 (Div. 3)](https://codeforces.com/contest/1800)
    CodeforcesRound855(Div.3)A.IsItaCat?为什么这个A这么麻烦#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn;strings;cin>>n>>s;s=""+s;......
  • AtCoder Beginner Contest 331
    A-Tomorrow(abc331A)题目大意给定一年的月数和一月的天数,以及当天日期,问次日的日期。解题思路一个简单的进制加法运算,超出进制数则向前加一。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_st......
  • The 13th Shandong ICPC Provincial Collegiate Programming Contest
    A.Orders按照订单的结束时间排序,然后遍历一遍即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingpii=pair<int,int>;usingi32=int32_t;voidsolve(){intn,k;cin>>n>>k;vector<pii>p(n);f......
  • [Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/con
    EducationalCodeforcesRound159(RatedforDiv.2)好困,差点没打A-BinaryImbalance#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){ strings; intn; cin>>n; cin>>s; if(n==......
  • AtCoder Beginner Contest 328
    AtCoderBeginnerContest328链接:ToyotaProgrammingContest2023#7(AtCoderBeginnerContest328)-AtCoderA题意:给定n个数,将小于等于x的数加起来输出。#include<bits/stdc++.h>#defineintlonglong#defineendl'\n';usingnamespacestd;voidsolve(){......
  • AtCoder Beginner Contest 331
    AtCoderBeginnerContest331这场状态好差,下午的校赛也打的好差。A-Tomorrow#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intM,D;inty,m,d;cin>>M>>D>>y>>m>&......
  • AtCoder Beginner Contest 331 G Collect Them All
    洛谷传送门AtCoder传送门设数字\(i\)第一次拿到的时间为\(t_i\),所求即为\(E(\max\limits_{i=1}^mt_i)\)。施min-max容斥,有:\[\begin{aligned}E(\max\limits_{i=1}^mt_i)&=\sum\limits_{T\subseteq[1,m]\landT\ne\varnothing}(-1)^{|T|-1}E(\min\l......
  • 2023-2024 CTU Open Contest
    A.Beth'sCookiesn=int(input())s=input()res=[]foriins:ifres==[]:res.append(i)elifi=='(':ifres[-1]==')':res.append("*")res.append(i)else:......
  • AtCoder Beginner Contest 331
    B-BuyOneCartonofMilk难度:⭐题目大意选择有三种套餐,6个鸡蛋S元,8个鸡蛋M元,12个鸡蛋L元;问如果要买至少N个鸡蛋,最少花费多少钱;解题思路一道入门级dp;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false......
  • The 13th Shandong ICPC Provincial Collegiate Programming Contest
    Preface昨天VP的那场没有字符串还没有原形毕露,今天遇到一个后期字符串直接和祁神大眼瞪小眼了最后一个半小时祁神狂冲F成功写出两个version的假算法,而我已经滚去补之前欠下的题目了赛后被徐神狠狠拷打了,评价为徐神是我们的红太阳,没有他我们都不能活A.Orders签到,按截止时间......