欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020 CCPC-Wannafly Winter Camp Day1 总结

程序员文章站 2022-07-12 15:06:54
...

部分题目列表:

题号 题目 算法
B题 密码学 签到题,字符串处理
H题 最大公约数 数学、gcd、大数
F题 乘法 较为巧妙的使用二分
A题 期望逆序对 -
C题 染色图 -
I题 K小数查询 在线线段树套权值线段树

B题 密码学

签到题,就是一个字符串的计算,可耻的WA了一发是因为忘记了解码要倒着去解(iimm00)

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int a[maxn], b[maxn];
string str[maxn];
int s[maxn][105];

void dde(int k)
{
    for (int i = 0; i < str[k].size(); i++) {
        if (str[k][i] > 'Z')
            s[k][i] = str[k][i] - 'a';
        else
            s[k][i] = str[k][i] - 'A' + 26;
    }
}

int main(void)
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d%d", &a[i], &b[i]);
    for (int i = 1; i <= n; i++)
        cin >> str[i];
    
    for (int i = m - 1; i >= 0; i--) {
        int x = a[i], y = b[i];
        string aa = str[x], bb = str[y];
        while (str[x].size() < str[y].size())
            str[x] = str[x] + str[x];
 
        for (int j = 0; j < str[y].size(); j++) {
            dde(x), dde(y);
            int kkk = s[y][j] - s[x][j];
            kkk = (kkk + 52) % 52;
            if (kkk < 26)
                bb[j] = kkk + 'a';
            else
                bb[j] = kkk - 26 + 'A';
        }

        str[x] = aa;
        str[y] = bb;
    }

    for (int i = 1; i <= n; i++)
            cout << str[i] << endl;
    return 0;
}

H题 最大公约数

Java大数走起

题干:有三个人 A,B,CA,B,C,其中 AABB 共享了一个神秘的数字 kk,已知 1kn1≤k≤n, 现在 AACC 说:“kk 的值等于 xx”。
CC 不太信任 AA,于是想向 BB 确认一下 kk 是否真的等于 xxBB 虽然不想直接把 kk 的值告诉 CC,但是 BB 允许 CC 给出一个正整数 yy(注意 yy 可以大于 nn),然后 BB 会回答 gcd(k,y)gcd(k,y)
现在给出 k,nk,n,你需要帮助 CC 决定这样的 yy 的取值,使得 CC 一定可以通过 BB 的回答来判断 AA 有没有撒谎。如果这样的 yy 有多个,你需要输出最小的那个。

输入第一行是一个整数 T(1T50)T(1≤T≤50)
对于每组数据,输入一行两个整数 n,k(1kn500)n,k(1≤k≤n≤500)

对于每组数据,输出一行一个整数,表示答案。如果满足条件的 yy 不存在,则输出 −1。

// package Main;
import java.util.*;
import java.math.*;
public class Main {
    static BigInteger arr[] = new BigInteger[505];
    static BigInteger m(int a) {
        return new BigInteger(a + "");
    }
    static boolean isP(int x) {
        for (int i = 2; i * i <= x; i++) 
            if (x % i == 0) 
                return false;
        return true;
    }
    static void init() {
        arr[1] = BigInteger.ONE;
        for (int i = 2; i <= 500; i++) {
            if (isP(i)) 
                arr[i] = arr[i - 1].divide(arr[i - 1].gcd(m(i))).multiply(m(i));
            else 
                arr[i] = arr[i - 1];
        }
    }
    public static void main(String[] args) {
        init();
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- != 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            BigInteger ans = arr[n / k].multiply(m(k));
            System.out.println(ans);
        }
    }
}

F题 乘法

题意:给出一个长度为 nn 的数列和一个长度为 mm 的数列, 可以构造得到一个 n×mn×m 的矩阵 CC,其中 Ci,j=Ai×BjC_{i,j}=A_{i}×B_{j}, 给出整数 KK,你需要求出 CC 中第 KK 大的数的值。(1n,m1051≤n,m≤10^{5}, 1Kn×m1≤K≤n×m)

思路:二分的找,需要额外注意当数为负数和零时候的情况

#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int maxn = 1e5 + 5;

ll ef = 1e12;
ll n, m, k;
vector<ll> a, b;

ll update_a(ll x, ll mid, ll l, ll r)
{
    if (l == r)
        return l;
    int m = (l + r + 1) >> 1;
    if (x * b[m] <= mid)
        return update_a(x, mid, m, r);
    else
        return update_a(x, mid, l, m - 1);
}

ll update_b(ll x, ll mid, ll l, ll r)
{
    if (l == r)
        return l;
    int m = (l + r) >> 1;
    if (x * b[m] <= mid)
        return update_b(x, mid, l, m);
    else
        return update_b(x, mid, m + 1, r);
}

ll Binary_Search(ll l, ll r) 
{
    if (l == r)
        return l;
    ll mid = (l + r) >> 1;

    ll ans = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] < 0)
            ans += m - update_b(a[i], mid, 0, b.size());
        else
            ans += update_a(a[i], mid, -1, b.size() - 1) + 1;
    }

    if (ans >= k)
        return Binary_Search(l, mid);
    else
        return Binary_Search(mid + 1, r);
}

int main(void)
{
    IO;
    cin >> n >> m >> k;
    k = n * m - k + 1;

    ll tmp;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        a.push_back(tmp);
    }
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        b.push_back(tmp);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    cout << Binary_Search(-ef, ef) << endl;

    return 0;
}

A题 期望逆序对

题意:生成一个每个数aia_{i}是从 [li,ri][l_{i}, r_{i}] 中生成的整数,aa 中不存在相同的数字,求逆序对个数的期望的最小值, 数组范围至5e35e3.
输出一行一个整数,表示答案对 998244353 取模后的值。假设答案的最简分数表示是 ab\frac{a}{b}, 你需要输出一个整数 kk 满足 x×yx  mod  998244353x \times y \equiv x \; mod \;998244353

#include<bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int maxn = 5050;

struct section {
    int l, r;
    void read() {
        scanf("%d%d", &l, &r);
    }
    bool operator < (const section& s1) {
        return l + r < s1.l + s1.r;
    }
}a[maxn];

int n, b[maxn];

int quick(int x, int y)
{
    int z = 1;
    while (y) {
        if (y & 1)
            z = 1ll * z * x % mod;
        y >>= 1;
        x = 1ll * x * x % mod;
    }
    return z;
}

int cal(section x, section y)
{
    int l = max(x.l, y.l);
    if (l > x.r)
        return 0;
    int r = min(x.r, y.r);
    int ans = 1ll * (l - y.l + r - y.l) * (r - l + 1) / 2 % mod;
    ans = (ans + 1ll * (x.r - r) * (y.r - y.l + 1)) % mod;
    return ans;
}

int main(void)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        a[i].read();
    sort(a + 1, a + n + 1);

    int ans = 0;
    for (int i = 1; i <= n; i++)
        b[i] = quick(a[i].r - a[i].l + 1, mod - 2);

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            ans = (ans + 1ll * b[i] * b[j] % mod * cal(a[i], a[j])) % mod;

    printf("%d\n", ans);
    return 0;
}

C题 染色图

—待补—

I题 K小数查询

树套树之线段树套权值线段树,在线维护

—待补—