比赛地址, 博客

@TOC
+ B
+ E
+ F
+ G
+ I
+ J
+ L

B - 抓球

题目描述

一个箱子里有n个黑球，m个白球，小王想要连续q次从箱子里随机的取出k个球（每次取出k个后立即放回），连续q次取球k个都为黑球的概率是多少，结果对1e9+7取模。

输入格式

第一行给出一个t，代表t组测试数据。（1<=t<=100000）

每组测试数据给出n，m，k，q。（1<=n,m,k<=1e5，k<=n+m，1<=q<=1e12）

输出格式

对于每组测试数据输出一个结果代表概率。

思路

这个取球游戏就真的就是组合数学了, 可能存在的套路为k < n?
另外, 在样例说明了明确说明了要用逆元

代码

#include <iostream>

using namespace std;
typedef long long LL;

const int N = 2e5 + 10, mod = 1e9 + 7;

LL n, m, k, q;

LL fac[N], infac[N];

LL C(LL n, LL m) {
    if (n < m || m < 0) return 0;
    return (fac[n] * infac[m] % mod) * infac[n - m] % mod;
}

LL qmi(LL a, LL b) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * i % mod;
    infac[N - 1] = qmi(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i --) infac[i] = infac[i + 1] * (i + 1) % mod;

    int T;
    cin >> T;
    while (T --) {
        cin >> n >> m >> k >> q;
        if (k > n) cout << 0 << endl;
        else cout << qmi(C(n, k), q) * qmi(qmi(C(n + m, k), q), mod - 2) % mod << endl;
    }
    return 0;
}

E - gk的字符串

题目描述

gk 最近在学习后缀数组，他做题的时候遇到了一个奇怪的字符串问题，于是想请xyxy来帮助他解决这个问题。
字符串由 ?? 和小写字母 (a-z)(a−z) 组成，你必须要把所有的 ?? 替换成小写字母，使最终的字符串不包含相邻且相同的字母，怎么替换才能使最终的字符串字典序最小呢？

输入格式

第一行T表示一共有 TT 组测试数据 (1 \leq T \leq 100)(1≤T≤100)

接下来T行输入只包含小写字母和问号的字符串 s($1 \leq len(s) \leq 1e5$)
$\sum_{i=1}^Tlen(s)\leq1e6$

输出格式

对于每一组数据输出字典序最小的解 (可以保证解是唯一的) 。

思路

字典序最小, 那必然就是填a了, 但是不能和临近的相同, 旁边有a就得填b, 有a和b就得填c, 否则一定填a, 因为只会和两个有接触, 所以只填这几个就ok

代码

#include <iostream>
#include <string>

using namespace std;

bool check(string x, int u, char e) {
    if (u < 0 || u >= x.length()) return true;
    else if (x[u] == e) return false;
    return true;
}

int main() {
    int T;
    cin >> T;
    while (T --) {
        string x;
        cin >> x;
        for (int i = 0; i < x.length(); i ++ ) {
            if (x[i] == '?') {
                if (check(x, i - 1, 'a') && check(x, i + 1, 'a')) x[i] = 'a';  
                else if (check(x, i - 1, 'b') && check(x, i + 1, 'b')) x[i] = 'b';
                else x[i] = 'c';
            }
        }
        cout << x << endl;
    }
    return 0;
}

F - gk的树

题目描述

jyq天天在公司摸鱼，感觉很无聊，突然想起了gk之前问过他的一个关于树的问题。
给你一颗树，每次操作你可以删掉一条边，最少需要多少次操作使得每个节点的度数都 <=k?

输入格式

第一行 T 表示一共有 T 组测试数据 ($1 \leq T \leq 100000$)
接下来一行输入给出的树的节点数 n 和度数限制 k ($1\leq n,k\leq 100000$)
接下来 n−1 行输入相邻的两个节点 (u,v)。
$\sum n \leq 1e^5$

输出格式

对于每一组测试数据输出最少的操作次数。

思路

要删除最少的边, 那么如果有两个度数都超过k的点相邻, 那么一定要删去他们之间的边
当没有点相邻时, 就要删去一些和不相关点之间的边
正面太麻烦了, 我们要枚举一个度数超过k的点, 然后对所有子节点进行排序, 从大到小删除, 目测复杂度应该不行也许可以试试
那么反过来, 所有点都删去边, 但是一些边会重复删除(两个点的度数都超过k), 这时我们删去重复删除的边, 同时要防止多删除边

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int n, k;
int h[N], e[M], ne[M], idx;
int d[N];
int ans;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;

        dfs(j, u);
        if (d[u] > k && d[j] > k) ans --, d[j] --, d[u] --;
    }
}

int main() {
    int T;
    cin >> T;
    while (T --) {
        memset(h, -1 , sizeof h);
        memset(d, 0, sizeof d);
        idx = ans = 0;

        cin >> n >> k;
        for (int i = 1; i < n; i ++ ) {
            int a, b;
            cin >> a >> b;
            add(a, b);
            add(b, a);
            d[a] ++, d[b] ++;
        }

        for (int i = 1; i <= n; i ++ )
            ans += max(0, d[i] - k);

        dfs(1, -1);
        cout << ans << endl;
    }
    return 0;
}

G - gk的数字游戏

题目描述

链接：https://ac.nowcoder.com/acm/contest/30825/G
来源：牛客网

gk 最近沉迷上了数字游戏，于是它邀请 brbr 和 zxzx 一起来玩。游戏规则是这样的:

1. 首先给两人两个正整数 nn 和 mm 。
2. 执行操作 $\begin{cases} n=n-m,&n>=m \\ m=m-n,&n<m \end{cases}$
3. 一直执行步骤2直到有一个数字变成0。

gkgk 想知道他俩需要执行多少次操作才能将其中一个数字变成0?

输入格式

第一行T表示一共有 TT 组测试数据 ($1 \leq T \leq 2000$)

接下来T行输入给出的两个正整数n和m ($0 \leq n,m \leq 1e9$)

输出格式

对于每一组测试数据输出需要执行多少次操作才能将其中一个数字变成0。

思路

更相减损法询问操作次数, 硬枚举没有试过, 但是每次做减法一定是减到不能再减去为止, 可以用除法来优化

代码

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int main() {
    int T;
    cin >> T;
    while (T --) {
        int a, b;
        cin >> a >> b;
        int ans = 0;
        while (a != b && a != 0 && b != 0) {
            if (a < b) swap(a, b);
            ans += a / b;
            a = a % b;
        }
        cout << ans + (a != 0 && b != 0) << endl;
    }
    return 0;
}

I - 又AK了

题目描述

“gkgk又akak了” 但是很可惜，由于罚时的原因gkgk没有拿到rk1rk1。 现给出gkgk每道题的通过时间，gkgk想知道如果他合理的安排做题顺序后，他的最少罚时是多少。

PSPS：由于gkgk太强了，所以当gkgk看到一道题时，只有在将这题ACAC之后才会去看其他的题。（看题的顺序取决于gkgk的心情）

罚时的计算方式为：每道题的提交ACAC时刻时间的总和

输入格式

第一行T表示一共有 TT 组测试数据 (1 \leq T \leq 20)(1≤T≤20)

每组测试数据有两行，第一行一个整数nn代表有nn道题目，第二行有n个整数表示gkgk在a[i]a[i]时刻通过了ii题 ($1 \leq n \leq 20，1 \leq a[i] \le 300$)

输出格式

输出一个整数表示最少罚时。

思路

不准倒开, 做的越快的题, 越应该最开始做
我们将每道题的做题时间排序, 然后计算罚时

代码

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int a[30];

int main() {
    int T;
    cin >> T;
    while (T --) {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        sort(a + 1, a + n + 1);
        for (int i = n; i >= 1; i -- ) a[i] -= a[i - 1];
        sort(a + 1, a + n + 1);
        int ans = 0;
        for (int i = 1; i <= n; i ++ ) {
            a[i] += a[i - 1];
            ans += a[i];
        }
        cout << ans << endl;
    }
    return 0;
}

J - 大数乘法

题目描述

给定整数x,y，你需要输出$x^y mod p$ 的值

输入格式

第一行一个整数t（$1 \leq t \leq 10$）,表示接下来有t组测试用例，每个测试用例有三行整数x,y,px,y,p
${0 \leq x \leq 100000, 0 \leq y \leq 10^{100000}, 100000 \leq p \leq 10000000070}$

输出格式

输出t行，每行一个整数代表$x^y mod p$的值。

思路

欧拉降幂, 就不说了

代码

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int MAX=1000010;
ll  fastPow(ll  a,ll b,ll mod)
{
    ll ans=1;
    a %= mod;
    while(b)
    {
        if(b&1)
        {
            ans = (ans*a)%mod;
        }
        b >>= 1;
        a = (a*a)%mod;
    }
    return ans;
}
ll  eulerFunction(ll x)
{
    ll eulerNumbers = x;
    for(ll i = 2; i*i <= x; i++)
    {
        if(x % i == 0)
        {
            eulerNumbers = eulerNumbers / i * (i-1);
            while(x % i == 0)
            {
                x /= i;
            }
        }
    }
    if(x > 1)
    {
        eulerNumbers = eulerNumbers / x * (x-1);
    }
    return eulerNumbers;
}
ll eulerDropPow(ll a,char b[],ll c)
{
    ll eulerNumbers = eulerFunction(c);
    ll descendingPower=0;
    for(ll i=0,len = strlen(b); i<len; ++i)
    {
        descendingPower=(descendingPower*10+b[i]-'0') % eulerNumbers;
    }
    descendingPower += eulerNumbers;
    return fastPow(a,descendingPower,c);
}
int main()
{
    ll a,c;
    char b[MAX];
    int T;
    cin >> T;
    while(T --)  
    {
        scanf("%lld%s%lld",&a,b,&c);
        if (b[0] == '0') printf("1\n");
        else printf("%lld\n",eulerDropPow(a,b,c));
    }
    return 0;
}

L - NP-hard

题目描述

gk喜欢1，所以他想问你在nn的xx进制和nn的yy进制表示中哪个1多？如果nn的xx进制表示中1的个数大于nn的yy进制表示中1的个数输出>>,等于输出==，小于输出<<

输入格式

第一行一个整数TT表示接下来有TT组测试样例.
接下来T行，每行有三个整数n,x,yn,x,y
($1 \leq t \leq 10000, 2 \leq x,y \leq 10, 1 \leq n \leq 1e9$)

输出格式

对于每一个测试样例输出是大于，小于，还是等于

思路

直接模拟就好了

代码

#include <iostream>

using namespace std;

int get(int n, int a) {
    int ans=  0;
    while (n) {
        if (n % a == 1) ans ++;
        n /= a;
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    while (T --) {
        int n, x, y;
        cin >> n >> x >> y;
        int a = get(n, x), b = get(n, y);
        if (a > b) puts(">");
        else if (a == b) puts("=");
        else puts("<");
    }
    return 0;
}