AtCoder Beginner Contest 402

这场上绿了。评价为手速场，E题难。23分钟之后就写不了了，但是起码不会让自己太坐牢。

A

写成了 <= ，罚了一发，下次也不要急成这样了，你看，又急。

void ChatGptDeepSeek() // Date: 2025-04-19
{                      // Time: 20:00:30 
    string s;
    cin>>s;
    for(auto x:s){
        if(x<'a') cout<<x;
    }
}

B

void ChatGptDeepSeek() // Date: 2025-04-19
{                      // Time: 20:05:15 
    int n;
    cin>>n;
    queue<int>q;
    for(int i=1;i<=n;i++){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            q.push(x);
        }else{
            cout<<q.front()<<'\n';
            q.pop();
        }
    }
}

C

直接按每种成分更新值就行。

void ChatGptDeepSeek() // Date: 2025-04-19
{                      // Time: 20:09:18 
    int n,m;
    cin>>n>>m;
    vector<vi>v(n+1);
    vi cnt(m+1);
    int ans=0;
    for(int i=1;i<=m;i++){
        int k;
        cin>>k;
        for(int j=1;j<=k;j++){
            int x;
            cin>>x;
            v[x].push_back(i);
        }
        cnt[i]=k;
    }
    for(int i=1;i<=n;i++){
        int B;
        cin>>B;
        for(auto x:v[B]){
            if(--cnt[x]==0) ans++;
        }
        cout<<ans<<'\n';
    }
}

D

水题。只用找对于每根线和它不平行的数量，观察给的图，发现 $x+y$ 相同的一定是平行，否则一定不平行。这题属于是，不给图的话难度会高一个档次感觉。

void ChatGptDeepSeek() // Date: 2025-04-19
{                      // Time: 20:20:08 
    int n,m;
    cin>>n>>m;
    vi cnt(n);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cnt[(x+y)%n]++;
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=1LL*(m-cnt[i])*cnt[i];
    }
    cout<<ans/2<<'\n';
}

E

明天学习。

题意

有 $n$ 个题目，每个题目的分数为 $s_i$ ，每题每次提交花费 $c_i$ 元，每次提交这题的正确的概率是 $p_i$ % 。每道题只能得一次分，求最大的得分的期望。

Code

由于 $n\le 8$ ，应该得看出来可以枚举 $2^n$ 的状态的。但是没想到也很正常。可以枚举当前处理过的题目和花费的钱数，$d{p}_{i,j}$ 为 $i$ 状态下，花费 $j$ 元的最大得分的期望。

代码里的状态 $j$ 表示，为 $1$ 的位都是已处理过的，那么我们就枚举当前去处理哪一题。但是要注意，一题是可以提交多次的，而且一题是不会有重复得分。

好吧，其实这题还是懂得不是特别透，但是也差不多了（）

void ChatGptDeepSeek() // Date: 2025-04-20
{                      // Time: 14:46:23
    int n, X;
    cin >> n >> X;
    vi s(n + 1), c(n + 1);
    vector<double> p(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> c[i] >> p[i], p[i] /= 100;
    vector<vector<double>> dp(1 << n, vector<double>(X + 1));
    for (int j = 0; j < (1 << n); j++)
    {
        for (int k = 0; k <= X; k++)
        {
            for (int i = 1; i <= n; i++)
            {
                if (k < c[i])
                    continue;
                if (j >> (i - 1) & 1)
                {
                    int last = j ^ (1 << (i - 1));
                    dp[j][k] = max(dp[j][k], (dp[last][k - c[i]] + s[i]) * p[i] + max(dp[j][k - c[i]], dp[last][k - c[i]]) * (1 - p[i]));
                }
            }
        }
    }
    cout << fixset(16) << dp[(1 << n) - 1][X] << '\n';
}