CSP2025模拟赛4 · ooliver

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≤72，所以 gcd(A,B)≤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++