S+CSP2025模拟赛4
A. 奥数题
直接暴搜所有出现的字母可能代替的数字即可，
注意除法是正常的除法，不取整。
#include<bits/stdc++.h>
using namespace std;
string a,b,c,d="0";
map<char,int> m;
int t[6],tag[15];
int ans,n;
int toint(string e){
int rtn=0;
for(int i=0;i<e.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;i<10;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;i<a.size();i++) if(!t[a[i]-'A']) t[a[i]-'A']=1,n++,d+=a[i];
for(int i=0;i<b.size();i++) if(!t[b[i]-'A']) t[b[i]-'A']=1,n++,d+=b[i];
for(int i=0;i<c.size();i++) if(!t[c[i]-'A']) t[c[i]-'A']=1,n++,d+=c[i];
dfs(0);
cout<<ans;
return 0;
}B. 互质卡片
因为 $A-B≤72$，所以 $gcd(A,B)≤72$，
可以尝试状压dp，二进制数每一位表示 $72$ 以内每个质数是不是该数的因数，
所以当两数按位和为 $0$ 时，表示是合法的，代码非常简短：
#include<bits/stdc++.h>
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<<20],ans;
main(){
freopen("coprime.in","r",stdin);
freopen("coprime.out","w",stdout);
cin>>l>>r;
dp[0]=1;
for(int k=l;k<=r;k++){
int st=0;
for(int i=0;i<20;i++) if(k%P[i]==0) st|=(1<<i);
for(int s=0;s<(1<<20);s++) if((s&st)==0) dp[s|st]+=dp[s];
}
for(int s=0;s<(1<<20);s++)ans+=dp[s];
cout<<ans;
}C. 押韵字符串
可以想到建立后缀字典树，
对于每个点，当前节点最优的子节点，当前节点次优的子节点，以该节点结尾的单词数量，从该节点开始能形成的最长序列长度。
答案相当于统计找到最大的对于一个点的最大子节点+次大子节点+以该节点结尾的字符串数量+以除了最大与次大子节点为结尾的字符串的数量，
代码如下：
#include<bits/stdc++.h>
#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<m;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;i<26;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<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
reverse(a[i].begin(),a[i].end());
update(a[i],a[i].size());
}
dfs(0);
cout<<ans;
return 0;
}扫描线
【模板】扫描线 & 矩形面积并
扫描线的模板，直接上代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lc p<<1
#define rc p<<1|1
const int N=1e5+5;
int n;
int x[N];
struct line{
int x1,x2,y,tag;
bool operator < (line b){
return y<b.y;
}
}li[N];
struct tree{
int l,r;
int cnt,len;
}tr[N<<3];
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<=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<=n;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<n;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<<ans;
}
Comments NOTHING