2022牛客多校训练营X1

E-Everyone is bot

来源: 牛客多校训练营加赛 算法: 博弈论 补完: Yes 完成时间: August 17, 2022

题解

第\(i\)个人作为第\(j\)个复读的人时, 可以获得\(a_{i,j}\)瓶冰红茶, 复读的倒数第\(p\)人获得\(-a_{i,j}\)瓶冰红茶.

若一共有\(n\)人复读, 则倒数第\(p\)人即第\(n-p+1\)人亏, 若此人复读, 则其后的共\(p-1\)人必定复读, 是其成为这次复读的失败者, 故其不会复读, 导致包括其的最后\(p\)人得不到冰红茶.

当第\(n-p+1\)人不会复读后, 其前的\(n-p\)人成为新的复读序列, 新的倒数第\(p\)个复读的人就是第\(n-2p+1\)人, 以同样的逻辑处理, 他也不会复读, 又有新的最后\(p\)人得不到冰红茶.

从导数第\(p\)人开始, 循环此逻辑, 不断有\(p\)个人不能复读得不到冰红茶, 直到复读序列小于\(p\), 才不会有人因可能的游戏失败而不复读, 故最后复读成功的人一共有\(n\%p\)人.

代码

#include<bits/stdc++.h>
using namespace std;
int n,p,a[1005][1005];
int main() {
    cin>>n>>p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin>>a[i][j];
    for (int i = 1; i <= n; i++)
        if (i <= n%p)cout<<a[i][i]<<" ";
        else cout<<"0 ";
    return 0;
}

M-Maimai DX 2077

来源: 牛客多校训练营加赛 算法: 模拟 补完: Yes 完成时间: August 17, 2022

题解

打音游, 有不同的按键类型和打击时机, 组合成不同的得分情况, 问实际得分与最佳得分之比, 模拟得.

代码

#include<bits/stdc++.h>

using namespace std;

double notes[4][5];
double sp, ep, A, B;
double standard[4][5] = {
    {1.0, 1.0, 0.8, 0.5, 0.0},
    {2.0, 2.0, 1.6, 1.0, 0.0},
    {3.0, 3.0, 2.4, 1.5, 0.0},
    {5.0, 5.0, 2.5, 2.0, 0.0}
};
double extra[5] = {
     1.0, 0.5, 0.4, 0.3, 0.0
};

void solve() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 5; j++) {
            cin>>notes[i][j];
            sp += standard[i][j] * notes[i][j];
            A  += standard[i][0] * notes[i][j];
            if (i==3) {
                ep += extra[j] * notes[i][j];
                B  += extra[0] * notes[i][j];
            }
        }
    }
    printf("%.15lf", sp/A*100+ep/B);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}