CSP2025模拟赛4

2025年8月9日 ooliver OI

S+CSP2025模拟赛4

A. 奥数题

直接暴搜所有出现的字母可能代替的数字即可，注意除法是正常的除法，不取整。

#include
using namespace std;
string a,b,c,d="0";
map m;
int t[6],tag[15];
int ans,n;
int toint(string e){
    int rtn=0;
    for(int i=0;i1&&m[a[0]]==0) return 0;
    if(b.size()>1&&m[b[0]]==0) return 0;
    if(c.size()>1&&m[c[0]]==0) return 0;
    int n1=toint(a),m1=toint(b),k=toint(c);
    int rtn=0;
    if(n1+m1==k) rtn++;
    if(n1-m1==k) rtn++;
    if(n1*m1==k) rtn++;
    if(m1!=0) if(n1*1.0/m1==k*1.0) rtn++;
    return rtn;
}
void dfs(int step){
    if(step==n){
        ans+=check();
        return;
    }
    for(int i=0;i>a>>b>>c;
    for(int i=0;i

`#include
using namespace std;
string a,b,c,d="0";
mapchar,int> m;
int t[6],tag[15];
int ans,n;
int toint(string e){
    int rtn=0;
    for(int i=0;ie.size();i++) rtn=rtn*10+m[e[i]];
    return rtn;
}
int check(){
    if(a.size()>1&&m[a[0]]==0) return 0;
    if(b.size()>1&&m[b[0]]==0) return 0;
    if(c.size()>1&&m[c[0]]==0) return 0;
    int n1=toint(a),m1=toint(b),k=toint(c);
    int rtn=0;
    if(n1+m1==k) rtn++;
    if(n1-m1==k) rtn++;
    if(n1*m1==k) rtn++;
    if(m1!=0) if(n1*1.0/m1==k*1.0) rtn++;
    return rtn;
}
void dfs(int step){
    if(step==n){
        ans+=check();
        return;
    }
    for(int i=0;i10;i++){
        if(!tag[i]){
            tag[i]=1,m[d[step+1]]=i;
            dfs(step+1);
            tag[i]=0;
        }
    }
}
int main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    cin>>a>>b>>c;
    for(int i=0;ia.size();i++) if(!t[a[i]-'A']) t[a[i]-'A']=1,n++,d+=a[i];
    for(int i=0;ib.size();i++) if(!t[b[i]-'A']) t[b[i]-'A']=1,n++,d+=b[i];
    for(int i=0;ic.size();i++) if(!t[c[i]-'A']) t[c[i]-'A']=1,n++,d+=c[i];
    dfs(0);
    cout
    return 0;
}`

C++

B. 互质卡片

因为 $A - B \leq 72$ ，所以 $g c d (A, B) \leq 72$ ，可以尝试状压dp，二进制数每一位表示 $72$ 以内每个质数是不是该数的因数，所以当两数按位和为 $0$ 时，表示是合法的，代码非常简短：

#include
using namespace std;
#define int long long
const int P[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
int l,r,dp[1>l>>r;
    dp[0]=1;
    for(int k=l;k

`#include
using namespace std;
#define int long long
const int P[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
int l,r,dp[120],ans;
main(){
    freopen("coprime.in","r",stdin);
    freopen("coprime.out","w",stdout);
    cin>>l>>r;
    dp[0]=1;
    for(int k=l;k
        int st=0;
        for(int i=0;i20;i++) if(k%P[i]==0) st|=(1
        for(int s=0;s120);s++) if((s&st)==0) dp[s|st]+=dp[s];
    }
    for(int s=0;s120);s++)ans+=dp[s];
    cout
}`

C++

C. 押韵字符串

可以想到建立后缀字典树，对于每个点，当前节点最优的子节点，当前节点次优的子节点，以该节点结尾的单词数量，从该节点开始能形成的最长序列长度。答案相当于统计找到最大的对于一个点的最大子节点+次大子节点+以该节点结尾的字符串数量+以除了最大与次大子节点为结尾的字符串的数量，代码如下：

#include
#define ll long long
using namespace std;
const ll N=3e6+5;
ll n,tot,ans;
ll tr[N][26],mx[N],cnt[N],sc[N],f[N];
string a[N];

void update(string s,ll m){
    ll u=0;
    for(int i=0;i>n;
    for(int i=1;i>a[i];
    for(int i=1;i

`#include
#define ll long long
using namespace std;
const ll N=3e6+5;
ll n,tot,ans;
ll tr[N][26],mx[N],cnt[N],sc[N],f[N];
string a[N];

void update(string s,ll m){
    ll u=0;
    for(int i=0;i
        if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;
        u=tr[u][s[i]-'a'];
    }
    cnt[u]++;
}

void dfs(ll u){
    ll siz=0;
    for(int i=0;i26;i++){
        ll v=tr[u][i];
        if(!v) continue;
        dfs(v);
        if(f[sc[u]]f[v]||sc[u]==0) sc[u]=v;
        if(f[mx[u]]f[sc[u]]||mx[u]==0) swap(mx[u],sc[u]);
        siz+=cnt[v];
    }
    if(cnt[u]) f[u]=f[mx[u]]+max(siz,1ll);
    ans=max(ans,f[mx[u]]+f[sc[u]]+cnt[u]+max(siz-2,0ll));
}

int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    cin>>n;
    for(int i=1;i>a[i];
    for(int i=1;i
        reverse(a[i].begin(),a[i].end());
        update(a[i],a[i].size());
    }
    dfs(0);
    cout
    return 0;
}`

C++

扫描线

【模板】扫描线 & 矩形面积并

扫描线的模板，直接上代码：

#include
using namespace std;
#define ll long long
#define lc p>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}
void update(int p,int l,int r,int tag){
    if(tr[p].l>=l&&tr[p].r>1;
    update(lc,l,r,tag);
    update(rc,l,r,tag);
    pushup(p);
}
main(){
    cin>>n;
    for(int i=1;i>x1>>y1>>x2>>y2;
        li[i]={x1,x2,y1,1};
        li[i+n]={x1,x2,y1,-1};
        x[i]=x1,x[i+n]=x2;
    }
    n*=2;
    sort(li+1,li+1+n);
    sort(x+1,x+1+n);
    int nn=unique(x+1,x+1+n)-x-1;
    build(1,1,nn-1);
    ll ans=0;
    for(int i=1;i

`#include
using namespace std;
#define ll long long
#define lc p
#define rc p
const int N=1e5+5;
int n;
int x[N];
struct line{
    int x1,x2,y,tag;
    bool operator  (line b){
        return yb.y;
    }
}li[N];
struct tree{
    int l,r;
    int cnt,len;
}tr[N3];
void pushup(int p){
    int r=tr[p].r,l=tr[p].l;
    if(tr[p].cnt) tr[p].len=x[r+1]-x[l];
    else tr[p].len=tr[lc].len+tr[rc].len;
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}
void update(int p,int l,int r,int tag){
    if(tr[p].l>=l&&tr[p].r
        tr[p].cnt+=tag;
        pushup(p);
        return;
    }
    int mid=l+r>>1;
    update(lc,l,r,tag);
    update(rc,l,r,tag);
    pushup(p);
}
main(){
    cin>>n;
    for(int i=1;i
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        li[i]={x1,x2,y1,1};
        li[i+n]={x1,x2,y1,-1};
        x[i]=x1,x[i+n]=x2;
    }
    n*=2;
    sort(li+1,li+1+n);
    sort(x+1,x+1+n);
    int nn=unique(x+1,x+1+n)-x-1;
    build(1,1,nn-1);
    ll ans=0;
    for(int i=1;i
        int l=lower_bound(x+1,x+1+nn,li[i].x1)-x;
        int r=lower_bound(x+1,x+1+nn,li[i].x2)-x;
        update(1,l,r-1,li[i].tag);
        ans+=tr[1].len*(li[i+1].y-li[i].y);
    }
    cout
}`

C++