专栏文章

xcpc春季训练记录

午午尘
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipvsll0
此快照首次捕获于
2025/12/03 18:45
3 个月前
此快照最后确认于
2025/12/03 18:45
3 个月前
查看原文

第三周 2023.3.9

The 2022 ICPC Asia Taoyuan Regional Programming Contest

和lyx,ljl一起训的……

签到：C

CPP
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=200005;
int n,m,a[N],ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int m; cin>>m;
    while (m--) {
        int n; cin>>n; ans=0;
        for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=n;i++) {
            for (int j=i+1;j<=n;j++) {
                if (a[i]>a[j]) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

签到：A

唤起了沉睡的高中生物记忆(doge)……
CPP
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=200005;
int n,m,a[N],ans;
map <string,string> mp;
bool sstop(string st) {
    if (st=="UAA"||st=="UAG"||st=="UGA") return 1;
    return 0;
}
string gett(string sss) {
    return mp[sss];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
mp["UUU"]="F"; mp["UUC"]="F";
mp["UUA"]="L"; mp["UUG"]="L"; mp["CUU"]="L"; mp["CUC"]="L"; mp["CUA"]="L"; mp["CUG"]="L";
mp["AUU"]="I"; mp["AUC"]="I"; mp["AUA"]="I";
mp["AUG"]="M";
mp["GUU"]="V";  mp["GUC"]="V";mp["GUA"]="V";mp["GUG"]="V"; 
mp["UCU"]="S";mp["UCC"]="S";mp["UCA"]="S";mp["UCG"]="S";mp["AGU"]="S";mp["AGC"]="S";
mp["CCU"]="P";mp["CCC"]="P";mp["CCA"]="P";mp["CCG"]="P";
mp["ACU"]="T";mp["ACC"]="T";mp["ACA"]="T";mp["ACG"]="T";
mp["GCU"]="A";mp["GCC"]="A";mp["GCA"]="A";mp["GCG"]="A";
mp["UAU"]="Y"; mp["UAC"]="Y";
mp["CAU"]="H"; mp["CAC"]="H";
mp["CAA"]="Q"; mp["CAG"]="Q";
mp["AAU"]="N"; mp["AAC"]="N";
mp["AAA"]="K"; mp["AAG"]="K";
mp["GAU"]="D"; mp["GAC"]="D";
mp["GAA"]="E"; mp["GAG"]="E";
mp["UGU"]="C"; mp["UGC"]="C";
mp["UGG"]="W";
mp["CGU"]="R"; mp["CGC"]="R"; mp["CGA"]="R"; mp["CGG"]="R"; mp["AGA"]="R"; mp["AGG"]="R";
mp["GGU"]="G";  mp["GGC"]="G";mp["GGA"]="G";mp["GGG"]="G"; 
    int T; cin>>T;
    while (T--) {
        string st; cin>>st;
        string ans="";
        for (int i=0;i+2<(int)st.size();i+=3) {
            string t="";
            t+=st[i];
            t=t+st[i+1]+st[i+2];
            if (sstop(t)) {
                break;
            }        
            ans+=gett(t);
        }
        cout<<ans<<endl;
    }
    return 0;
}

B：数学+矩阵快速幂

要点：
  • //!!!处，指数应与 MOD−1MOD-1 取模（也可以不取），但是不能用 MODMOD 取模！
方法：
  • 将算这个图形的方案数分为两个子问题：内部的这个环形，和外部的矩形。
  • 对于矩形，我们可以用递推式+排列组合推得答案。
  • 对于环形，我们钦定第 11 个颜色为 11 ，然后用 f[i][0]f[i][0] 来表示第 ii 个颜色不为 11 的方案数，用 f[i][1]f[i][1] 来表示第 ii 个颜色为 11 的方案数，然后列出公式，用矩阵快速幂计算即可。
CPP
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int MOD=1e9+7;
int n,k,m,ans;

struct qwq{
    int a[3][3];
}res,s,z,qwqq;

void cl(qwq &z) {
    for (int i=1;i<=2;i++) {
        for (int j=1;j<=2;j++) {
            z.a[i][j]=0;
        }
    }
}

qwq operator *(const qwq &x, const qwq &y) {
    cl(z);
    for (int k=1;k<=2;k++) {
        for (int i=1;i<=2;i++) {
            for (int j=1;j<=2;j++) {
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%MOD)%MOD;
            }
        }
    }
    return z;
}

int mi(int aa,int bb) {
    int tt=1;
    while (bb) {
            if (bb&1) tt=tt*aa%MOD;
            aa=aa*aa%MOD;
            bb>>=1;
    }
    return tt;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while (T--) {
        cin>>n>>k>>m;
        if (m<=1) {
            cout<<0<<endl;
            continue;
        }
        s.a[1][1]=m-2,s.a[1][2]=m-1;
        s.a[2][1]=1,s.a[2][2]=0;
        res.a[1][1]=1,res.a[1][2]=0;
        res.a[2][1]=0,res.a[2][2]=1;
        int b=k-1;
        while (b) {
            if (b&1) res=res*s;
            s=s*s;
            b>>=1;
        }
        qwqq.a[2][1]=1;
        res=res*qwqq;
        int t=res.a[1][1];
        int dishu=((m-1)*(m-1)%MOD-(m-2)%MOD)+MOD;
        dishu%=MOD;
        ans=t*mi(dishu,(n-1)*k)%MOD; //!!!
        ans=ans*m%MOD;
        ans%=MOD;
        if (ans<0) ans=0;
        cout<<ans<<endl;    
    }
     
    return 0;
}

第四周 2025.3.16

M: 签到，dfs

CPP
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=20004;
int ans,n,p[N],t[N][4];
string st[N];
vector<int>vec;
int js(){
    vec.clear();
    for (int i=1;i<=n;i++) {
        int x=p[i];
        if (t[i][x]!=-1) {
            vec.push_back(t[i][x]);
        }
    }
    sort(vec.begin(),vec.end());
    int now=0,cnt=0;
    for (int i=0;i<(int)vec.size();i++) {
        if (now+vec[i]<=300) {
            now+=vec[i]; cnt++;
        }
        else {
            break;
        }
    }
    return cnt;
}
void dfs(int x) {
    if (x==n) {
        int t=js();
        ans=max(ans,t);
        return ;
    }
    p[x+1]=1;
    dfs(x+1);
    p[x+1]=2;
    dfs(x+1);
    p[x+1]=3;
    dfs(x+1);
    
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>st[i]; 
        cin>>t[i][1]>>t[i][2]>>t[i][3];
    }
    dfs(0);
    cout<<ans<<'\n';
    return 0;
}

I：签到，好玩题

大概算……交互题？不过好像不是我恐惧的那种qwq……
很好玩的题目！ 嘻嘻！
要点：
  • 用endl，别用\n！
  • 可以跑个程序验证一下结果！一开始和 zpc 讨论，我们俩的策略都还是太保守了qwqq……
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,m,b;
string st;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while (T--) {
        string st; cin>>st;
        cin>>m>>b;
        if (b<=m/4) {
            cout<<"PLAY"<<endl;
        }
        else {
            cout<<"SKIP"<<endl;
        }
    }
    return 0;
}

第五周 2025.3.23

The 2nd Universal Cup. Stage 25: Shenzhen

第九届中国大学生程序设计竞赛 深圳站（CCPC 2023 Shenzhen Site）

AIFG

第六周 2025.3.30

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...