2024CCPC东北四省邀请赛VP

Problem J. Breakfast

直接根据题意模拟即可:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    double x=32*0.6+20;
    printf("%.2lf",x);
    return 0;
}

ProblemA.PaperWatering

比较考验细心程度吧，观察发现，如果一个数不是平方数，那么取了根号之后再平方的结果与取根号之前的值完全不同，因此只需要判断一下当前的数是否为平方数，是的话加一，不是的话要乘到不能乘为止

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int x,k; cin>>x>>k;
    int cnt=x==1?1:k+1;
    while(x!=1&&k>0){
        int y=sqrt(x);
        cnt++,k--;
        if(y*y==x||y==1){
            x=y;
            continue;
        }
        cnt+=k;
        x=y;
    }
    cout<<cnt;
    return 0;
}

ProblemD.nIMgAME

由于只有１，２，３三种取法，又因为最后的异或值必须为０，那么就可以转化为：所有的数加和为偶数，由此，无论他怎么走，其对手都能破坏当前局面的奇偶性，故其必输

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
void solve(){
    int n; cin>>n;
    cout<<"lose"<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}

ProblemE.Checksum

考虑到 \(k\) 只有 \(20\) 位，我们可以直接去枚举所有的状态，又由于 \(n\) 的限制，所以我们状态要求不大于 \(n+k\)，至此就很显然了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
void solve(){
    int n,k; cin>>n>>k;
    string A; cin>>A;
    int res=0;
    for(auto c:A){
        if(c=='1') res++;
    }
    for(int i=0;i<(1<<k)&&i<=n+k;i++){
        int cnt=0;
        string s="";
        for(int j=k;j>=1;j--){
            if(i&(1<<(j-1))){
                cnt++,s+="1";
            }
            else s+="0";
        }
        if(cnt+res==i){
            cout<<s<<'\n';
            return;
        }
    }
    cout<<"None"<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}

ProblemF.Factor

首先考虑一个性质，若一个数是有限循环小数，那么其一定满足这样一个性质，对于一个除到不能再除的分式 \(\frac{a}{b}\) 来说若是一个有限循环小数，将 \(b\) 分解质因数之后必定有 \(2\) 或 \(5\)，也就是说，在 \(k\) 进制下，\(b\) 分解质因数之后必须有 \(k\) 分解质因数之中的因子才可以
所以我们可以把给定的 \(k\) 和 \(p\) 分解质因数，其中 \(k\) 分解的多一点，因为我们之后需要用它来组合不同的数，接下来考虑枚举分母 \(q\) ，其一定由上面分解质因数之后的幂次方相乘得到，故枚举所有的小于 \(x\) 的数即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int p,x,k; cin>>p>>x>>k;
    unordered_map<int,int>mp;
    auto cacl=[&](int x,int n)->void{
        for(int i=2;i*i<=x;i++){
            while(x%i==0){
                x/=i,mp[i]+=n;
            }
        }
        if(x>1) mp[x]+=n;
    };
    cacl(k,100);
    cacl(p,1);
    vector a(mp.begin(),mp.end());
    function<void(int,int)>dfs;
    int res=0;
    dfs=[&](int i,int n)->void{
        if(i>=a.size()){
            res++;
            return;
        }
        for(int j=0;j<=a[i].second;j++,n*=a[i].first){
            dfs(i+1,n);
            if(n>x/a[i].first) break;            
        }
    };
    dfs(0,1);
    cout<<res;
    return 0;
}

ProblemL.BracketGeneration

观察题意，由于操作二必须需要一个完整的括号，那么我们这里设出()这种括号为小括号，最基本的括号，那么(...)这种即为大括号，通过题意可以知：

• 小括号一定是由操作一得来
• 大括号一定是由操作二得来
• 操作一是有序的，也就是若我们想要的到第 \(i\) 个小括号，那么我们其前面必须要有 \(i-1\) 个小括号才可以
• 操作二是无序的，能够扩大任意一个小括号

至此，由于操作一的次序是一定的，我们要对每个操作一求出所有操作二的次数，这里拿样例二来举例：
((()())()())(()) 那么我们把所有的小括号进行标记，变成了: \(((11)11)(1)\) 小括号序列为:\(11 11 1\)，那么操作二的位置为: \(2,4,5\)，对于位置\(5\)，我们只有一种选择，就是直接把操作\(5\)位置，对于位置\(4\)，我们一开始有: \((4)\) 和 \((45)\) 两种操作，又因为之前对5位置进行了操作，又有:(4(5)) 这一种，故为 \(3\) 种操作，位置2同理，一开始有 \(4\) 种，又因为后面两个位置可以被操作，故为 \(6\) 种，那么总的方案数为：\(1\times3\times6=18\)
进行一遍括号匹配即可:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=998244353;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string s; cin>>s;
    vector<int>v;
    int k=0;
    for(int i=0;i<s.size();i++){
        if(s[i]==')'){
            if(s[i-1]=='(') k++;
            else v.push_back(k);
        }
    }
    int res=1;
    reverse(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        res=(res*(k-v[i]+1+i))%mod;
    }
    cout<<res<<'\n';
    return 0;
}

ProblemI.Password

我们定义 \(dp_i\) 为最后一个排列在位置 \(i\) 结束的方案数，那么 \(dp_n\) 即为答案，可以得到下面的状态转移方程：

这里的 \(f_j\) 是指在某个完整排列\(i\)后面接上 \(j\) 个数字并且不会破坏原来性质的方案数，通俗的来讲，其满足以下性质：

• 对于 \(dp_{i}\) 后面接上 \(j\) 个数，没接之前有: \(a[i-k+1，i]\) 是一个完整排列，接上 \(j\) 之后，满足：\(a[i+j-k+1，i+j]\) 是一个完整排列，这是因为 \(dp_i\) 是最后一个完整排列在 \(i\) 结尾的方案数
• 对于区间 \(\forall j \in [i-k+2, i+j-k+1)\)，均不能满足 \(a[j,j+k-1]\) 是一个完整排列，不然就破坏\(dp_{i+j}\) 的性质，最后一个排列出现的位置不是 \(i+j\) 了

假设我们现在要在长度为 \(5\) 的排列 \({1, 2, 3, 4, 5}\) 后接上 \(j = 3\) 个数字，那么我们一定要满足：

\(b[4, 8] = {4, 5, x, x, x}\)，其中\(x\)为某个数字，一定是一个排列，这样最后一个完整排列的结尾才能变成 \(8\)。

同时，\(b[2, 6] = {2, 3, 4, 5, x}\) 与 \(b[3, 7] = {3, 4, 5, x, x}\) 不能是完整的排列，否则前一个完整排列的结尾就不是 \(5\) 而是别的位置了，转移方程就不符合定义。