【比賽記錄】2025CSP+NOIP 沖刺模擬賽合集Ⅲ
2025CSP-S模擬賽67（CSP-S模擬42）
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 60(70) | 25 | 30 | 5 | 120 | 5/14(7/34) |
A. 乘篩積
對于單次查詢，我們可以直接枚舉 \(x\) 算出對應的 \(y\) 貢獻答案，時間復雜度 \(O(\frac{C}{\max(p,q)})\)。根號分治即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5,mod=998244353;
int n,m,kk,T,a[maxn],b[maxn],f[550][550];
il int solve(int p,int q,int *a,int *b,int n,int m){
if(p<q){
swap(p,q),swap(a,b),swap(n,m);
}
int ans=0;
for(int i=1;i<=n&&i*p<=kk;i++){
if((kk-i*p)%q==0){
int j=(kk-i*p)/q;
if(j>0&&j<=m){
ans=(ans+a[i]*b[j])%mod;
}
}
}
return ans;
}
int main(){
freopen("sedge.in","r",stdin);
freopen("sedge.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>kk;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
for(int i=1;i<=547;i++){
for(int j=1;j<=547;j++){
f[i][j]=solve(i,j,a,b,n,m);
}
}
cin>>T;
while(T--){
int p,q;
cin>>p>>q;
if(max(p,q)<=547){
cout<<f[p][q]<<'\n';
}else{
cout<<solve(p,q,a,b,n,m)<<'\n';
}
}
return 0;
}
}
signed main(){return asbt::main();}
B. 放進去
首先對于每個奢侈品單獨考慮，不妨令 \(a_{i,p_1}\le a_{i,p_2}\le a_{i,p_3}\le\dots\le a_{i,p_m}\)。假設我們最終選的店鋪集合是 \(S\)，那么對于 \(i\) 我們必然選擇 \(S\) 中 \(a\) 最小（也就是最靠前）的 \(p_j\)。考慮差分，即對于所有 \(k<j\)，給答案加上 \(a_{i,p_{k+1}}-a_{i,p_k}\)。考慮 SOSDP，于是我們只需要給所有 \(\{p_1,p_2,\dots,p_k\}\) 的答案加上 \(a_{i,p_{k+1}}-a_{i,p_k}\)，最后再做一遍高維前綴和即可。記這個和為 \(f_S\)，\(\sum_{i\in S}b_i=g_S\)，于是 \(S\) 的答案即為 \(g_S+f_{\complement_US}\)。時間復雜度 \(O(nm\log m+m2^m)\)，輕微卡常。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=(1<<25)+5,inf=1e18;
il int pls(int x,int y){
return x+y<inf?x+y:inf;
}
il void add(int &x,int y){
x=pls(x,y);
}
int n,m,b[30],f[maxn],g[maxn];
struct node{
int p,v;
il bool operator<(const node &x)const{
return v<x.v;
}
}a[30];
int main(){
freopen("putin.in","r",stdin);
freopen("putin.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[j].v;
a[j].p=j;
}
sort(a+1,a+m+1);
a[m+1]={m+1,inf};
for(int j=1,S=0;j<=m+1;j++){
// cout<<a[j].p<<' '<<a[j].v<<'\n';
add(f[S],a[j].v-a[j-1].v);
S|=1<<(a[j].p-1);
}
}
for(int i=1;i<=m;i++){
for(int S=0;S<1<<m;S++){
if(S>>(i-1)&1){
continue;
}
add(f[S|1<<(i-1)],f[S]);
}
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
int ans=inf;
for(int S=0;S<1<<m;S++){
g[S]=pls(g[S^(S&-S)],b[__lg(S&-S)+1]);
ans=min(ans,g[S]+f[((1<<m)-1)^S]);
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
C. 最長路徑
重要結論：最長路徑上相鄰的點必然滿足 \(|x_i-x_j|=1\lor|y_i-y_j|=1\)。顯然成立。
考慮 DP。設 \(f_{i,j}\) 表示以 \((i,j)\) 為結尾的最長路徑長度，\(g_{i,j}\) 表示以 \((i,j)\) 結尾的最長路徑長度的數量，顯然只會從左上方的一個 _| 形區域轉移過來。如果我們能求出它的范圍，就可以用單調隊列優化了。
我們要求的就是 \(i\) 上一行的最左端的轉移點，和前一列最上面的轉移點，這里以最左端轉移點為例。此時對于所有點 \(([r_1+1,r_2],[c_1+1,c_2])\)，它們對應的轉移點都應為 \(c_1\)。顯然不能直接全部賦值，考慮只給 \(([r_1+1,r_2],c_2)\) 賦值，最后再做一遍后綴取 \(\min\)。時間仍然不正確，考慮掃描線，將所有矩形按 \(c_1\) 排序，給每一列開一個并查集，將已經賦過值的合并起來，這樣在未來賦值時可以直接跳過這一段。每個位置最多被賦值一次，于是時間復雜度正確。
然后就是單隊 DP 了。我們對于每一行和每一列都維護單調隊列，再給每一行和每一列都開一個桶維護隊列中 \(f\) 值為 \(x\) 的 \(g\) 的總和即可。注意 \((i-1,j-1)\) 的貢獻可能被計算兩遍，減掉就好了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e3+5,maxm=5e5+5,mod=1e9+7;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int mns(int x,int y){
return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){
x=mns(x,y);
}
il void chkmin(int &x,int y){
x=min(x,y);
}
il void chkmax(int &x,int y){
x=max(x,y);
}
int T,n,m,q,f[maxn][maxn],g[maxn][maxn];
int b1[maxn][maxn],b2[maxn][maxn];
int q1[maxn][maxn],hd1[maxn],tl1[maxn];
int q2[maxn][maxn],hd2[maxn],tl2[maxn];
int s1[maxn][maxn],s2[maxn][maxn];
struct jux{
int x1,x2,y1,y2;
}a[maxm];
struct{
int fa[maxn];
il void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
fa[find(u)]=find(v);
}
}d[maxn];
il void solve(){
cin>>n>>m>>q;
for(int i=1;i<=q;i++){
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
b1[i][j]=j,b2[i][j]=i;
}
}
sort(a+1,a+q+1,[](jux x,jux y){return x.y1<y.y1;});
for(int i=1;i<=m;i++){
d[i].init(n+1);
}
for(int i=1;i<=q;i++){
int x1=a[i].x1,x2=a[i].x2,y1=a[i].y1,y2=a[i].y2;
for(int j=d[y2].find(x1+1);j<=x2;j=d[y2].find(j)){
chkmin(b1[j][y2],y1);
d[y2].merge(j,j+1);
}
}
// puts("***********************************************************");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<b1[i][j]<<' ';
// }
// cout<<'\n';
// }
// puts("***********************************************************");
sort(a+1,a+q+1,[](jux x,jux y){return x.x1<y.x1;});
for(int i=1;i<=n;i++){
d[i].init(m+1);
}
for(int i=1;i<=q;i++){
int x1=a[i].x1,x2=a[i].x2,y1=a[i].y1,y2=a[i].y2;
for(int j=d[x2].find(y1+1);j<=y2;j=d[x2].find(j)){
chkmin(b2[x2][j],x1);
d[x2].merge(j,j+1);
}
}
for(int i=n;i;i--){
for(int j=m;j;j--){
if(j<m){
chkmin(b1[i][j],b1[i][j+1]);
}
if(i<n){
chkmin(b2[i][j],b2[i+1][j]);
}
}
}
// puts("***********************************************************");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<b1[i][j]<<' ';
// }
// cout<<'\n';
// }
// puts("***********************************************************");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<b2[i][j]<<' ';
// }
// cout<<'\n';
// }
// puts("***********************************************************");
for(int i=0;i<n;i++){
hd1[i]=1,tl1[i]=0;
}
for(int i=0;i<m;i++){
hd2[i]=1,tl2[i]=0;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
s1[i][j]=s2[j][i]=0;
}
}
int ans1=0,ans2=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
while(hd1[i-1]<=tl1[i-1]&&f[i-1][j-1]>f[i-1][q1[i-1][tl1[i-1]]]){
sub(s1[i-1][f[i-1][q1[i-1][tl1[i-1]]]],g[i-1][q1[i-1][tl1[i-1]]]);
tl1[i-1]--;
}
add(s1[i-1][f[i-1][j-1]],g[i-1][j-1]);
q1[i-1][++tl1[i-1]]=j-1;
while(hd1[i-1]<=tl1[i-1]&&q1[i-1][hd1[i-1]]<b1[i][j]){
sub(s1[i-1][f[i-1][q1[i-1][hd1[i-1]]]],g[i-1][q1[i-1][hd1[i-1]]]);
hd1[i-1]++;
}
while(hd2[j-1]<=tl2[j-1]&&f[i-1][j-1]>f[q2[j-1][tl2[j-1]]][j-1]){
sub(s2[j-1][f[q2[j-1][tl2[j-1]]][j-1]],g[q2[j-1][tl2[j-1]]][j-1]);
tl2[j-1]--;
}
add(s2[j-1][f[i-1][j-1]],g[i-1][j-1]);
q2[j-1][++tl2[j-1]]=i-1;
while(hd2[j-1]<=tl2[j-1]&&q2[j-1][hd2[j-1]]<b2[i][j]){
sub(s2[j-1][f[q2[j-1][hd2[j-1]]][j-1]],g[q2[j-1][hd2[j-1]]][j-1]);
hd2[j-1]++;
}
if(hd1[i-1]>tl1[i-1]){
if(hd2[j-1]>tl2[j-1]){
f[i][j]=g[i][j]=1;
}else{
f[i][j]=f[q2[j-1][hd2[j-1]]][j-1]+1;
g[i][j]=s2[j-1][f[q2[j-1][hd2[j-1]]][j-1]];
}
}else{
if(hd2[j-1]>tl2[j-1]){
f[i][j]=f[i-1][q1[i-1][hd1[i-1]]]+1;
g[i][j]=s1[i-1][f[i-1][q1[i-1][hd1[i-1]]]];
}else{
int x=f[i-1][q1[i-1][hd1[i-1]]],y=f[q2[j-1][hd2[j-1]]][j-1];
if(x>y){
f[i][j]=x+1,g[i][j]=s1[i-1][x];
}else if(x<y){
f[i][j]=y+1,g[i][j]=s2[j-1][y];
}else{
f[i][j]=x+1,g[i][j]=pls(s1[i-1][x],s2[j-1][y]);
if(f[i-1][j-1]==x){
sub(g[i][j],g[i-1][j-1]);
}
}
}
}
if(ans1<f[i][j]){
ans1=f[i][j],ans2=g[i][j];
}else if(ans1==f[i][j]){
add(ans2,g[i][j]);
}
}
}
// puts("------------------------------------------------");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<f[i][j]<<' ';
// }
// cout<<'\n';
// }
// puts("------------------------------------------------");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<g[i][j]<<' ';
// }
// cout<<'\n';
// }
// puts("------------------------------------------------");
cout<<ans1<<' '<<ans2<<'\n';
}
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
/*
1
7 9 3
1 4 4 4
1 3 4 5
3 1 5 4
3 8
*/
D. 生成樹的傳說
2025CSP-S模擬賽68
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 37 | 40 | 25 | 202 | 5/14 |
A. 三角形
直接枚舉 \(A\) 的所有 \(6\) 種狀態，計算答案并取最小值即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int n;
struct sjx{
int a[15][15];
il int*operator[](int x){
return a[x];
}
il void xz(){
sjx b;
for(int i=1;i<=n;i++){
for(int j=1,ii=n,jj=i;j<=i;j++,ii--,jj--){
b[i][j]=a[ii][jj];
}
}
*this=b;
}
il void dc(){
for(int i=1;i<=n;i++){
for(int l=1,r=i;l<=r;l++,r--){
swap(a[i][l],a[i][r]);
}
}
}
il int operator-(sjx b)const{
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
res+=a[i][j]^b[i][j];
}
}
return res;
}
}a,b;
int main(){
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>b[i][j];
}
}
int ans=a-b;
a.dc(),ans=min(ans,a-b),a.dc();
a.xz(),ans=min(ans,a-b);
a.dc(),ans=min(ans,a-b),a.dc();
a.xz(),ans=min(ans,a-b);
a.dc(),ans=min(ans,a-b);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=i;j++){
// cout<<a[i][j]<<' ';
// }
// cout<<'\n';
// }
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
B. 子段異或
假設第一個 \(1\) 的位置為 \(p\)，我們一定要選的一個串是 \(f_S(p,n)\)。考慮其后第一段連續的 \(0\)，我們希望把它們也變成 \(1\)。假設那一段 \(0\) 的開頭是 \(q\)，長度為 \(len\)，我們希望其后的第二段 \(1\) 不受影響，也就是用這一段 \(0\) 來和它們匹配，于是第二個串的開頭為 \(\max(p,q-len)\)。再特判一些 corner case 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e7+5;
int T,n;
string s;
il bool chk1(){
for(char i:s){
if(i=='0'){
return 0;
}
}
return 1;
}
il bool chk0(){
for(char i:s){
if(i=='1'){
return 0;
}
}
return 1;
}
int main(){
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>s;
if(chk1()){
cout<<string(n-1,'1')<<0<<'\n';
continue;
}
if(chk0()){
cout<<0<<'\n';
continue;
}
int p=0;
while(p<n&&s[p]=='0'){
p++;
}
int q=p;
while(q<n&&s[q]=='1'){
q++;
}
if(q==n){
cout<<string(n-p,'1')<<'\n';
continue;
}
int t=q;
while(t<n&&s[t]=='0'){
t++;
}
string a=s.substr(p,n-p);
string b=string(q-p,'0')+s.substr(max(2*q-t,p),n-q);
for(int i=0;i<a.size();i++){
cout<<(int)(a[i]^b[i]);
}
cout<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
C. 三等分
記 \(a_i\) 表示 \(i\) 的個數。不妨只考慮 \((x,x+1,x+2)\) 三元組，將所有 \(a_i\) 變為三的倍數。
記 \(f_{i,x,y}\) 表示考慮到 \(i\)，有 \(x\) 個 \((i,i+1,i+2)\)，\(y\) 個 \((i-1,i,i+1)\) 的方案數。于是有轉移：
\[f_{i,x,y}=\sum_{x+y+z\le a_i\land x+y+z\equiv a_i\pmod{3}}f_{i-1,y,z}
\]
時空復雜度都是 \(O(n^3)\)。滾動數組 + 前綴和優化即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5,mod=1e9+7;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int mns(int x,int y){
return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){
x=mns(x,y);
}
int n,m,a[maxn],f[2][maxn][maxn],g[maxn][maxn][3];
int main(){
freopen("three.in","r",stdin);
freopen("three.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,x;i<=n;i++){
cin>>x;
a[x]++;
}
f[0][0][0]=g[0][0][0]=1;
for(int i=1,p=1,q=0;i<=m;i++,p^=1,q^=1){
for(int x=0,xx=min({a[i],a[i+1],a[i+2]});x<=xx;x++){
for(int y=0,yy=min({a[i]-x,a[i+1]-x,a[i-1]});y<=yy;y++){
f[p][x][y]=g[y][min({a[i]-x-y,a[i-1]-y,i>1?a[i-2]:0})][(a[i]-x-y)%3];
}
}
for(int x=0,xx=min({a[i],a[i+1],a[i+2]});x<=xx;x++){
for(int y=0,yy=min({a[i]-x,a[i+1]-x,a[i-1]});y<=yy;y++){
g[x][y][0]=y?g[x][y-1][0]:0;
g[x][y][1]=y?g[x][y-1][1]:0;
g[x][y][2]=y?g[x][y-1][2]:0;
add(g[x][y][y%3],f[p][x][y]);
}
}
}
cout<<f[m&1][0][0];
return 0;
}
}
int main(){return asbt::main();}
D. 二叉樹遍歷
答辯，我跟你爆了。
我們要求的是在 \(x\) 前面遍歷到的 \(y\) 的數量。考慮哪些 \(y\) 能產生貢獻（\(op_x\) 表示 \(x\) 的遍歷方式，\(tr_x\) 表示 \(x\) 的子樹，\(ls_x,rs_x\) 表示 \(x\) 的左右子樹）：
- \(op_x=0,y\in ls_x\)
- \(op_x=1,y\in tr_x\)
- \(\exist z,y\in ls_z,x\in rs_z\)
- \(op_y=-1,x\in tr_y\)
- \(op_y=0,x\in rs_y\)
前兩類可以直接 \(O(1)\) 求，第三類能預處理出來。后兩類不是非常好維護，考慮按編號分塊。可以將塊分成兩類：第一類為整個塊的遍歷方式相同的塊，第二類為整個塊遍歷方式不同的塊。
對于第一類，我們只需要知道 \(x\) 是這個塊內多少個點的子樹/右子樹，也可以預處理。考慮用數據結構維護第二類塊的貢獻。
對于區間推平操作，會將中間的整塊變成一類塊，兩端的散塊變成二類塊。由于二類塊最多一共只有 \(O(n)\) 個，考慮直接遍歷內部的點在數據結構上修改。這樣我們會修改 \(O(n\sqrt{n})\) 次，查詢 \(O(n)\) 次，再按 dfn 分塊，將區間加改為差分即可。時間復雜度 \(O(n\sqrt{n})\)。
Code
// 答辯，我跟你爆了
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5,B=320,maxb=325;
int n,m,ls[maxn],rs[maxn],szl[maxn];
int dfn[maxn],cnt,stk[maxn],sz[maxn];
int bnm,bg[maxb],ed[maxb],bel[maxn];
il void dfs(int u,int x){
if(!u){
return ;
}
dfn[u]=++cnt,stk[cnt]=u,szl[u]=x;
dfs(ls[u],x),dfs(rs[u],x+sz[ls[u]]);
sz[u]=sz[ls[u]]+sz[rs[u]]+1;
}
namespace B2{
/*
just a declaration
*/
il void add(int,int,int);
il int query(int);
}
namespace B1{
/*
這個分塊的對象是 y，按照編號分塊
需要記錄每一塊的類型，以及 1 類塊的標記和所有位置的標記
支持的操作是區間修改，和查詢
需要調用 B2(？有毒吧)
*/
int cnts[maxn][maxb] ,cntr[maxn][maxb];
// i 是 j 塊中多少點的子樹，i 是 j 塊中多少點的右子樹
int typ[maxb],opt[maxn],tag[maxb];
il void dfs(int u){
for(int i=1;i<=bnm;i++){
if(ls[u]){
cnts[ls[u]][i]+=cnts[u][i];
cntr[ls[u]][i]+=cntr[u][i];
}
if(rs[u]){
cnts[rs[u]][i]+=cnts[u][i];
cntr[rs[u]][i]+=cntr[u][i];
}
}
if(ls[u]){
cnts[ls[u]][bel[u]]++;
dfs(ls[u]);
}
if(rs[u]){
cnts[rs[u]][bel[u]]++;
cntr[rs[u]][bel[u]]++;
dfs(rs[u]);
}
}
il void build(){
dfs(1);
for(int i=1;i<=n;i++){
tag[i]=-1;
}
for(int i=1;i<=bnm;i++){
typ[i]=1;
}
}
il void upd(int l,int r,int x){
int pl=bel[l],pr=bel[r];
if(pl==pr){
if(typ[pl]==1){
typ[pl]=2;
for(int i=bg[pl];i<=ed[pl];i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(tag[pl]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,1);
}else if(tag[pl]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,1);
}
opt[i]=tag[pl];
}
}
for(int i=l;i<=r;i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(opt[i]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,-1);
}else if(opt[i]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,-1);
}
opt[i]=x;
if(opt[i]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,1);
}else if(opt[i]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,1);
}
}
return ;
}
for(int i=pl+1;i<pr;i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(typ[i]==2){
for(int j=bg[i];j<=ed[i];j++){
// cout<<"f "<<__LINE__<<' '<<j<<'\n';
if(opt[j]==-1){
B2::add(dfn[j]+1,dfn[j]+sz[j]-1,-1);
}else if(opt[j]==0){
B2::add(dfn[j]+sz[ls[j]]+1,dfn[j]+sz[j]-1,-1);
}
}
typ[i]=1;
}
tag[i]=x;
}
if(typ[pl]==1){
typ[pl]=2;
for(int i=bg[pl];i<=ed[pl];i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(tag[pl]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,1);
}else if(tag[pl]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,1);
}
opt[i]=tag[pl];
}
}
for(int i=l;i<=ed[pl];i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(opt[i]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,-1);
}else if(opt[i]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,-1);
}
opt[i]=x;
if(opt[i]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,1);
}else if(opt[i]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,1);
}
}
if(typ[pr]==1){
typ[pr]=2;
for(int i=bg[pr];i<=ed[pr];i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(tag[pr]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,1);
}else if(tag[pr]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,1);
}
opt[i]=tag[pr];
}
}
for(int i=bg[pr];i<=r;i++){
// cout<<"f "<<__LINE__<<' '<<i<<'\n';
if(opt[i]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,-1);
}else if(opt[i]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,-1);
}
opt[i]=x;
if(opt[i]==-1){
B2::add(dfn[i]+1,dfn[i]+sz[i]-1,1);
}else if(opt[i]==0){
B2::add(dfn[i]+sz[ls[i]]+1,dfn[i]+sz[i]-1,1);
}
}
}
il int query(int x){
// for(int i=1;i<=bnm;i++){
// cout<<typ[i]<<' ';
// }
// cout<<'\n';
int res=B2::query(dfn[x])+szl[x]+1;
int optx=typ[bel[x]]==1?tag[bel[x]]:opt[x];
if(optx==0){
res+=sz[ls[x]];
}else if(optx==1){
res+=sz[x]-1;
}
for(int i=1;i<=bnm;i++){
if(typ[i]==1){
if(tag[i]==-1){
res+=cnts[x][i];
}else if(tag[i]==0){
res+=cntr[x][i];
}
}
}
return res;
}
}
namespace B2{
/*
implementation
用來維護二類塊的貢獻，是按照 dfn 分塊的
區間加、單點查，但為了平衡時間改為差分
*/
int tag[maxb][maxb];
il void add(int l,int r,int x){
if(l>r){
return ;
}
// cout<<"a "<<l<<' '<<r<<' '<<x<<'\n';
int pl=bel[l],pr=bel[r];
if(pl==pr){
tag[pl][l-bg[pl]+1]+=x,tag[pl][r-bg[pl]+2]-=x;
return ;
}
tag[pl+1][0]+=x,tag[pr][0]-=x;
tag[pl][l-bg[pl]+1]+=x,tag[pl][ed[pl]-bg[pl]+2]-=x;
tag[pr][1]+=x,tag[pr][r-bg[pr]+2]-=x;
}
il int query(int x){
int res=0;
for(int i=1;i<=bel[x];i++){
// cout<<tag[i][0]<<' ';
res+=tag[i][0];
}
// cout<<'\n';
// cout<<"p "<<res<<'\n';
for(int i=1;i<=x-bg[bel[x]]+1;i++){
res+=tag[bel[x]][i];
// cout<<tag[bel[x]][i]<<' ';
}
// cout<<'\n';
// cout<<"q "<<res<<'\n';
return res;
}
}
int main(){
freopen("traversing.in","r",stdin);
freopen("traversing.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>ls[i]>>rs[i];
}
dfs(1,0);
// for(int i=1;i<=n;i++){
// cout<<i<<' '<<sz[i]<<' '<<ls[i]<<' '<<rs[i]<<' '<<szl[i]<<'\n';
// }
bnm=n/B;
for(int i=1;i<=bnm;i++){
bg[i]=ed[i-1]+1,ed[i]=ed[i-1]+B;
}
if(ed[bnm]<n){
bg[bnm+1]=ed[bnm]+1,ed[bnm+1]=n;
bnm++;
}
for(int i=1;i<=bnm;i++){
for(int j=bg[i];j<=ed[i];j++){
bel[j]=i;
}
}
B1::build();
while(m--){
int opt;
cin>>opt;
if(opt==1){
int l,r,x;
cin>>l>>r>>x;
B1::upd(l,r,x);
}else{
int x;
cin>>x;
cout<<B1::query(x)<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
2025CSP-S模擬賽65
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 100 | 20 | 20 | 240 | 2/7 |
為啥還在打 CSP 模擬賽啊
A. 翻牌
二分答案 \(mid\)，將 \(\ge mid\) 的設為 \(1\)，\(<mid\) 的設為 \(-1\)，則當且僅當和 \(>0\) 時 \(ans\ge mid\)。找出 \(b_i-a_i\) 的最大子段和即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,a[maxn],b[maxn],c[maxn],d[maxn];
il bool check(int x){
int sum=0,mx=0;
for(int i=1;i<=n;i++){
sum+=a[i]>=x?1:-1;
c[i]=c[i-1]+(b[i]>=x?1:-1)-(a[i]>=x?1:-1);
mx=max(mx,c[i]-d[i-1]);
d[i]=min(d[i-1],c[i]);
}
return sum+mx>0;
}
int main(){
// freopen("flip.in","r",stdin);
// freopen("flip.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
int l=1,r=1e9;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<l;
return 0;
}
}
int main(){return asbt::main();}
B. 塔
考慮如果知道了這個序列，怎么求最小操作次數：從左往右掃，如果 \(a_i>a_{i-1}\)，則要增加 \(a_i-a_{i-1}\) 次，否則不用增加。于是設 \(f_{i,j}\) 表示考慮了前 \(i\) 個，\(a_i=j\) 的最小操作次數，于是有轉移：
\[f_{i,j}=\min(\min_{k=0}^{j-d_{i-1}}\{f_{i-1,k}+j-k\},\min_{k=j+d_{i-1}}^{10^5}\{f_{i-1,k}\})
\]
前后綴最小值優化即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=105,maxm=1e5+5,inf=1e9,B=1e5;
int n,a[maxn],f[maxn][maxm],pre[maxm],suf[maxm];
int main(){
// freopen("tower.in","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
cin>>a[i];
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
pre[0]=f[i-1][0];
for(int j=1;j<=B;j++){
pre[j]=min(pre[j-1],f[i-1][j]-j);
}
suf[B]=f[i-1][B];
for(int j=B-1;~j;j--){
suf[j]=min(suf[j+1],f[i-1][j]);
}
for(int j=0;j<=B;j++){
f[i][j]=min(j<a[i]?inf:pre[j-a[i]]+j,j+a[i]>B?inf:suf[j+a[i]]);
}
}
int ans=inf;
for(int i=0;i<=B;i++){
ans=min(ans,f[n][i]);
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
C. 圖
設點集大小為 \(k\)，于是由于最大度數不超過 \(3\)，邊數最多為 \(\frac{3}{2}k\)。由于要求紅、藍均連通，邊數至少為 \(2(k-1)\)。于是有不等式：\(\frac{3}{2}k\ge2(k-1)\)，解集為 \(k\le4\)。于是我們只需要考慮 \(k\in[1,4]\) 的情況。
于是直接枚舉所有可能合法的紅邊連通的點集。以每個點為根跑出一棵 dfs 樹即可。考慮如果一個點連了三條邊，那么這個點集不可能藍邊連通，于是這個點集在搜索樹上必然是一條根鏈。會算重，用 set 去重即可。時間復雜度 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,fa[maxn],faz[maxn],p[maxn];
bool vis[maxn],pp[maxn];
vector<int> e[2][maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
struct node{
int a[4];
node(){}
node(int u){
a[0]=a[1]=a[2]=a[3]=0;
int p=0;
while(u){
// cout<<u<<'\n';
a[p++]=u,u=faz[u];
}
sort(a,a+4);
// for(int i=0;i<=3;i++){
// cout<<a[i]<<' ';
// }
// cout<<'\n';
}
il bool operator<(const node &x)const{
if(a[0]!=x.a[0]){
return a[0]<x.a[0];
}
if(a[1]!=x.a[1]){
return a[1]<x.a[1];
}
if(a[2]!=x.a[2]){
return a[2]<x.a[2];
}
return a[3]<x.a[3];
}
};
set<node> ans;
il void dfs(int u,int fth,int dep){
// cout<<u<<'\n';
if(dep>4){
return ;
}
faz[u]=fth,vis[u]=1;
int x=u,cnt=0;
while(x){
p[++cnt]=x,x=faz[x];
}
for(int i=1;i<=cnt;i++){
fa[p[i]]=p[i],pp[p[i]]=1;
}
for(int i=1;i<=cnt;i++){
int u=p[i];
for(int v:e[1][u]){
if(pp[v]){
fa[find(u)]=find(v);
}
}
}
bool flag=0;
// cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++){
// cout<<p[i]<<' '<<find(p[i])<<'\n';
if(find(p[i])==p[i]){
if(!flag){
flag=1;
}else{
goto togo;
}
}
}
ans.insert(node(u));
// puts("666");
togo:;
for(int i=1;i<=cnt;i++){
pp[p[i]]=0;
}
for(int v:e[0][u]){
if(!vis[v]){
dfs(v,u,dep+1);
}
}
vis[u]=0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v,c;i<=m;i++){
cin>>u>>v>>c;
e[c][u].pb(v),e[c][v].pb(u);
}
for(int i=1;i<=n;i++){
// cout<<i<<'\n';
dfs(i,0,1);
}
cout<<ans.size();
return 0;
}
}
int main(){return asbt::main();}
D. 勇士斗惡龍
首先考慮 \(b_i\) 都為 \(0\) 的情況，設 \(dp_i\) 表示惡龍血量為 \(i\) 的答案，有轉移：
\[dp_i=\sum_{j=1}^{100}dp_{i-j}cnt_j
\]
其中 \(cnt_j\) 表示 \(a_i=j\) 的法術的數量。設 \(ans_i=\begin{bmatrix} dp_i&dp_{i-1}&\cdots&dp_{i-99} \end{bmatrix}\)，于是可以設計出轉移矩陣：
\[ans_i=ans_{i-1}\times\begin{bmatrix}
cnt_1&1&0&\cdots&0\\
cnt_2&0&1&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
cnt_{99}&0&0&\cdots&1\\
cnt_{100}&0&0&\cdots&0
\end{bmatrix}
\]
矩陣快速冪即可。
考慮 \(b_i\) 的限制，有新的轉移方程：
\[f_i=\sum_{j=1}^{100}\sum_{k=0}^{60}[i\equiv0\pmod{2^k}]f_{i-j}cnt_{j,k}
\]
其中 \(cnt_{j,k}\) 表示 \(a_i=j,b_i=k\) 的法術的數量。
考慮依然用矩陣優化，將 \(n\) 拆位，我們希望求出 \(f_i\) 表示 \(0\) 到 \(2^i\) 的轉移矩陣，因為較高的冪次不會影響低冪次的轉移，所以有：
\[ans_n=\prod_{i=60}^{0}[\operatorname{bit}_i(n)=1]f_i
\]
其中 \(\operatorname{bit}_i(n)\) 表示 \(n\) 在二進制下的第 \(i\) 位。
考慮求 \(f_i\)。設 \(bas_i\) 表示考慮了 \(2\) 的 \(0\sim i\) 次冪的法術的轉移矩陣，\(g_i\) 表示 \(0\) 到 \(2^i-1\) 的轉移矩陣，于是有：
\[\begin{cases}
g_i=f_{i-1}\times g_{i-1}\\
f_i=g_i\times bas_i
\end{cases}
\]
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int mod=1e9+7;
int m;
ll n;
struct juz{
int a[105][105];
juz(){
memset(a,0,sizeof(a));
}
il int*operator[](int x){
return a[x];
}
il juz operator*(juz b)const{
juz c;
for(int i=1;i<=100;i++){
for(int j=1;j<=100;j++){
for(int k=1;k<=100;k++){
c[i][j]=(a[i][k]*1ll*b[k][j]+c[i][j])%mod;
}
}
}
return c;
}
}bas[65],f[65],g[65],ans;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,a,b;i<=m;i++){
cin>>a>>b;
do{
bas[b++][a][1]++;
}while(b<=60);
}
for(int i=1;i<100;i++){
for(int j=0;j<=60;j++){
bas[j][i][i+1]=1;
}
}
f[0]=bas[0];
for(int i=1;i<=100;i++){
g[0][i][i]=ans[i][i]=1;
}
for(int i=1;i<=60;i++){
g[i]=f[i-1]*g[i-1];
f[i]=g[i]*bas[i];
}
for(int i=60;~i;i--){
if(n>>i&1){
ans=ans*f[i];
}
}
cout<<ans[1][1];
return 0;
}
}
int main(){return asbt::main();}
HZOJ NOIP2025模擬1
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 30 | 40 | 50 | 50 | 170 | 8/27 |
A. 公司的供應鏈
題意是要不斷刪環直到圖變成 DAG。
暴力的做法是顯然的，每次找出一個環然后刪掉即可，時間復雜度 \(O(m^2)\)。它的問題在于每條邊會重復走許多次，不夠優秀。
考慮當找到了一個環時，先將它回溯出來，然后從這個環的起點（也就是 dfs 序最小的點）開始繼續向下搜索。那么直接記錄每個點上一次遍歷到了第幾條邊即可。這樣每條邊只會遍歷一次，時間復雜度 \(O(m)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
ifstream cin("dag.in");
ofstream cout("dag.out");
const int maxn=3e5+5,maxm=6e5+5;
int n,m,enm,hd[maxn];
bool vis[maxn],ban[maxm];
struct{
int u,v,nxt;
}e[maxm];
il void addedge(int u,int v){
e[++enm]={u,v,hd[u]};
hd[u]=enm;
}
il int dfs(int u){
// cout<<u<<'\n';
vis[u]=1;
for(int &i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]){
ban[i]=1,vis[u]=0,i=e[i].nxt;
return v;
}
int x=dfs(v);
if(x){
ban[i]=1;
if(u!=x){
vis[u]=0,i=e[i].nxt;
return x;
}
}
}
vis[u]=0;
return 0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
addedge(u,v);
}
for(int i=1;i<=n;i++){
dfs(i);
}
int cnt=0;
for(int i=1;i<=m;i++){
if(!ban[i]){
cnt++;
}
}
cout<<cnt<<'\n';
for(int i=1;i<=m;i++){
if(!ban[i]){
cout<<e[i].u<<' '<<e[i].v<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
B. 宇宙的卷積
考慮對于每個 \(i\) 求出 \(\max\limits_{(k-i)\subseteq j\subseteq k}b_j\)。
設 \(f_{i,j}(j\subseteq\overline{i})\) 表示滿足 \(x\cap\overline{i}=j\) 的 \(x\) 中 \(b_x\) 的最大值，于是 \(i\) 對 \(k\) 的貢獻為 \(a_i+f_{i,k-i}\)。考慮轉移，當我們要從 \(S\) 轉移到 \(T=S\cup\{i\}\) 時，有：
\[f_{T,X}=\max(f_{S,X},f_{S,X\cup\{i\}})
\]
時間復雜度 \(O(3^n)\)。只維護搜索樹根鏈上的 \(f\) 值，空間復雜度 \(O(n2^n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=(1<<18)+5;
int n,a[maxn],f[20][maxn],ans[maxn];
il void dfs(int S,int d,int p){
// cout<<(bitset<3>)S<<'\n';
for(int T=S;T<1<<n;T=(T+1)|S){
ans[T]=max(ans[T],a[S]+f[d][T^S]);
// cout<<(bitset<3>)T<<' ';
}
// cout<<'\n';
for(int i=p;i<n;i++){
int T=S|1<<i,U=((1<<n)-1)^T;
for(int X=U;;X=(X-1)&U){
f[d+1][X]=max(f[d][X],f[d][X|1<<i]);
if(!X){
break;
}
}
dfs(T,d+1,i+1);
for(int X=U;;X=(X-1)&U){
f[d+1][X]=0;
if(!X){
break;
}
}
}
}
int main(){
freopen("juanji.in","r",stdin);
freopen("juanji.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=0;i<1<<n;i++){
cin>>a[i];
}
for(int i=0;i<1<<n;i++){
cin>>f[0][i];
}
dfs(0,0,0);
for(int i=0;i<1<<n;i++){
cout<<ans[i]<<' ';
}
return 0;
}
}
int main(){return asbt::main();}
C. 艦隊的遠征
整條路線可分為從 \(s\) 走到 \(x\)，從 \(x\) 跳到 \(y\)，再從 \(y\) 走到 \(t\) 三段。于是我們先用 dijkstra 跑出 \(s\) 到每個點的最短路 \(dis_i\) 和每個點到 \(t\) 的最短路 \(dit_i\)。于是對于 \((x,y)\)，答案即為：
\[\begin{aligned}
&dis_x+(x-y)^2+dit_y\\
=&(-2xy+x^2+dis_x)+y^2+dit_y
\end{aligned}
\]
括號內的是一條關于 \(y\) 的直線，使用李超線段樹即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
ifstream cin("far.in");
ofstream cout("far.out");
const int maxn=2e5+5,inf=1e18;
int n,m,s,t,dis[maxn],dit[maxn];
bool vis[maxn];
vector<pii> es[maxn],et[maxn];
priority_queue<pii> q;
il void dijkstra(int x,vector<pii> *e,int *dis){
for(int i=1;i<=n;i++){
dis[i]=inf,vis[i]=0;
}
dis[x]=0,q.push(mp(0,x));
while(q.size()){
int u=q.top().sec;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(!vis[v]&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(mp(-dis[v],v));
}
}
}
}
struct line{
int k,b;
line(int k=0,int b=inf):k(k),b(b){}
il int calc(int x){
return k*x+b;
}
}tr[maxn<<2];
il void insert(int id,int l,int r,line x){
int mid=(l+r)>>1;
if(tr[id].calc(mid)>x.calc(mid)){
swap(tr[id],x);
}
int lo=tr[id].calc(l),ro=tr[id].calc(r);
int ln=x.calc(l),rn=x.calc(r);
if(ln<lo){
insert(lid,l,mid,x);
}else if(rn<ro){
insert(rid,mid+1,r,x);
}
}
il int query(int id,int l,int r,int p){
if(l==r){
return tr[id].calc(p);
}
int mid=(l+r)>>1,res=tr[id].calc(p);
if(p<=mid){
res=min(res,query(lid,l,mid,p));
}else{
res=min(res,query(rid,mid+1,r,p));
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>s>>t;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
es[u].pb(mp(v,w));
et[v].pb(mp(u,w));
}
dijkstra(s,es,dis);
dijkstra(t,et,dit);
// for(int i=1;i<=n;i++){
// cout<<i<<' '<<dis[i]<<' '<<dit[i]<<'\n';
// }
for(int i=1;i<=n;i++){
insert(1,1,n,line(-2*i,dis[i]+i*i));
}
int ans=inf;
for(int i=1;i<=n;i++){
ans=min(ans,query(1,1,n,i)+dit[i]+i*i);
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
D. 軍團的陣列線
\(\min\) 前面都是負號，因此我們可以依次給每個序列取相反數，這樣就都求 \(\max\) 即可。于是我們要求的就是這個式子：
\[\sum_{l=1}^{n}\sum_{r=l}^{n}\max_{i=l}^{r}\{A_i\}\times\max_{i=l}^{r}\{B_i\}\times\max_{i=l}^{r}\{C_i\}
\]
考慮掃描線右端點，用線段樹維護這個式子。最大值用單調棧維護，然后在線段樹上維護 \(A,B,C,AB,AC,BC,ABC\) 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
#define a(id) tr[id].a
#define b(id) tr[id].b
#define c(id) tr[id].c
#define ab(id) tr[id].ab
#define ac(id) tr[id].ac
#define bc(id) tr[id].bc
#define abc(id) tr[id].abc
#define ta(id) tr[id].ta
#define tb(id) tr[id].tb
#define tc(id) tr[id].tc
using namespace std;
namespace asbt{
ifstream cin("team.in");
ofstream cout("team.out");
const int maxn=1e5+5;
int n,a[maxn],b[maxn],c[maxn];
int sa[maxn],sb[maxn],sc[maxn];
struct{
unsigned int a,b,c,ab,ac,bc,abc,ta,tb,tc;
}tr[maxn<<2];
il void pushup(int id){
a(id)=a(lid)+a(rid);
b(id)=b(lid)+b(rid);
c(id)=c(lid)+c(rid);
ab(id)=ab(lid)+ab(rid);
ac(id)=ac(lid)+ac(rid);
bc(id)=bc(lid)+bc(rid);
abc(id)=abc(lid)+abc(rid);
}
il void pushta(int id,int l,int r,unsigned int x){
ta(id)+=x,a(id)+=x*(r-l+1);
ab(id)+=x*b(id),ac(id)+=x*c(id),abc(id)+=x*bc(id);
}
il void pushtb(int id,int l,int r,unsigned int x){
tb(id)+=x,b(id)+=x*(r-l+1);
ab(id)+=x*a(id),bc(id)+=x*c(id),abc(id)+=x*ac(id);
}
il void pushtc(int id,int l,int r,unsigned int x){
tc(id)+=x,c(id)+=x*(r-l+1);
ac(id)+=x*a(id),bc(id)+=x*b(id),abc(id)+=x*ab(id);
}
il void pushdown(int id,int l,int r){
int mid=(l+r)>>1;
if(ta(id)){
pushta(lid,l,mid,ta(id));
pushta(rid,mid+1,r,ta(id));
ta(id)=0;
}
if(tb(id)){
pushtb(lid,l,mid,tb(id));
pushtb(rid,mid+1,r,tb(id));
tb(id)=0;
}
if(tc(id)){
pushtc(lid,l,mid,tc(id));
pushtc(rid,mid+1,r,tc(id));
tc(id)=0;
}
}
il void build(int id,int l,int r){
tr[id]={0,0,0,0,0,0,0,0,0,0};
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void adda(int id,int L,int R,int l,int r,unsigned int x){
// cout<<"a "<<id<<' '<<L<<' '<<R<<' '<<l<<' '<<r<<' '<<x<<'\n';
if(L>=l&&R<=r){
pushta(id,L,R,x);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
adda(lid,L,mid,l,r,x);
}
if(r>mid){
adda(rid,mid+1,R,l,r,x);
}
pushup(id);
}
il void addb(int id,int L,int R,int l,int r,unsigned int x){
// cout<<"b "<<id<<' '<<L<<' '<<R<<' '<<l<<' '<<r<<' '<<x<<'\n';
if(L>=l&&R<=r){
pushtb(id,L,R,x);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
addb(lid,L,mid,l,r,x);
}
if(r>mid){
addb(rid,mid+1,R,l,r,x);
}
pushup(id);
}
il void addc(int id,int L,int R,int l,int r,unsigned int x){
// cout<<"c "<<id<<' '<<L<<' '<<R<<' '<<l<<' '<<r<<' '<<x<<'\n';
if(L>=l&&R<=r){
pushtc(id,L,R,x);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
addc(lid,L,mid,l,r,x);
}
if(r>mid){
addc(rid,mid+1,R,l,r,x);
}
pushup(id);
}
il unsigned int solve(){
unsigned int ans=0;
int tpa=0,tpb=0,tpc=0;
build(1,1,n);
for(int i=1;i<=n;i++){
while(tpa&&a[i]>a[sa[tpa]]){
adda(1,1,n,sa[tpa-1]+1,sa[tpa],a[i]-a[sa[tpa]]);
tpa--;
}
while(tpb&&b[i]>b[sb[tpb]]){
addb(1,1,n,sb[tpb-1]+1,sb[tpb],b[i]-b[sb[tpb]]);
tpb--;
}
while(tpc&&c[i]>c[sc[tpc]]){
addc(1,1,n,sc[tpc-1]+1,sc[tpc],c[i]-c[sc[tpc]]);
tpc--;
}
sa[++tpa]=sb[++tpb]=sc[++tpc]=i;
adda(1,1,n,i,i,a[i]);
addb(1,1,n,i,i,b[i]);
addc(1,1,n,i,i,c[i]);
ans+=abc(1);
// cout<<i<<' '<<abc(1)<<'\n';
}
// cout<<ans<<'\n';
return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
cin>>c[i];
}
unsigned int ans=0;
for(int S=0;S<8;S++){
if(S&0b1){
for(int i=1;i<=n;i++){
a[i]=-a[i];
}
}
if(S&0b10){
for(int i=1;i<=n;i++){
b[i]=-b[i];
}
}
if(S&0b100){
for(int i=1;i<=n;i++){
c[i]=-c[i];
}
}
// cout<<bitset<3>(S)<<'\n';
ans+=solve();
if(S&0b1){
for(int i=1;i<=n;i++){
a[i]=-a[i];
}
}
if(S&0b10){
for(int i=1;i<=n;i++){
b[i]=-b[i];
}
}
if(S&0b100){
for(int i=1;i<=n;i++){
c[i]=-c[i];
}
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
HZOJ NOIP2025模擬2
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 0 | 40 | 60 | 200 | 10/29 |
A. 數字(math)
不妨令 \(n\le m\)，于是有 \(a\times b=a(c\times10^{m-n}+d)\)，其中 \(\lg a=\lg c\)。于是我們優先提升 \(ac\)，再提升 \(ad\)。
顯然要將所有數碼從大到小往里填，因此 \(a+c\) 是定值，我們要使 \(|a-c|\) 盡可能的小。考慮如果 \(a\) 更大，則會順帶使 \(ad\) 更大，而 \(c\) 更大則不會有額外的貢獻，因此要求 \(a\ge c\)。于是我們每次取出前兩大的數碼填，如果此前 \(a=c\) 則將較大的填入 \(a\)，否則此時已經滿足 \(a>c\) 了，將較大的填入 \(c\)。最后再將剩下的數碼倒序填入 \(d\) 即可。
需要高精乘，時間復雜度 \(O(nm)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
ifstream cin("math.in");
ofstream cout("math.out");
const int maxn=2e3+5;
int T,n,m,p[maxn],c[maxn];
int main(){
// system("fc ex_math2.out my.out");
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
if(n>m){
swap(n,m);
}
int cnt=0;
for(int i=1,x;i<=9;i++){
cin>>x;
while(x--){
p[++cnt]=i;
}
}
if(!n){
cout<<0<<'\n';
continue;
}
string a,b;
bool flag=0;
while(cnt){
if(a.size()==n){
b+=p[cnt--];
}else{
if(!flag){
if(p[cnt]>p[cnt-1]){
flag=1;
}
a+=p[cnt--],b+=p[cnt--];
}else{
b+=p[cnt--],a+=p[cnt--];
}
}
}
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
a=" "+a,b=" "+b;
// for(int i=1;i<=n;i++){
// cout<<(int)a[i];
// }
// cout<<' ';
// for(int i=1;i<=m;i++){
// cout<<(int)b[i];
// }
// cout<<'\n';
for(int i=0;i<=n+m;i++){
c[i]=0;
}
c[0]=n+m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
c[i+j-1]+=a[i]*b[j];
}
}
for(int i=1;i<=c[0];i++){
c[i+1]+=c[i]/10,c[i]%=10;
}
while(c[0]>1&&!c[c[0]]){
c[0]--;
}
for(int i=c[0];i;i--){
cout<<c[i];
}
cout<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
B. 游戲(game)
考慮如果確定了 \(A\) 和 \(B\) 第一次選的位置，那么 \(B\) 后面的每一步都可以與 \(A\) 相向而行。進而當確定了 \(A\) 的起點 \(x\) 后，\(B\) 可以通過選擇起點來使 \(A\) 最后的區間之和為所有包含了 \(x\) 的長為 \(\lceil\frac{n}{2}\rceil\) 的區間中最小的一個。而 \(A\) 又可以選擇起點，因此用 ST 表求出每個 \(x\) 對應的最小的和，再對每個 \(x\) 的答案取 \(\max\) 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
ifstream cin("game.in");
ofstream cout("game.out");
const int maxn=5e5+5,inf=2e9;
int n,a[maxn<<1],st[maxn][22];
il int query(int l,int r){
if(l>r){
return inf;
}
int p=__lg(r-l+1);
return min(st[l][p],st[r-(1<<p)+1][p]);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=n<<1;i++){
a[i]+=a[i-1];
}
int B=(n+1)/2;
for(int i=1;i<=n;i++){
st[i][0]=i<B?a[i+n]-a[i+n-B]:a[i]-a[i-B];
}
for(int j=1;j<=19;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
int l=i,r=i+B-1;
if(r>n){
r-=n;
}
ans=max(ans,l<=r?query(l,r):min(query(1,r),query(l,n)));
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
C. 海報（posters)
D. 環（ring)
根號分治。設閾值 \(B\)，對于塊長小于 \(B\) 的環，考慮直接用數據結構維護其貢獻。每次修改操作要進行 \(B\) 次單點修改，分塊即可，修改 \(O(B)\)，查詢 \(O(B+\frac{n}{B})\)。
對于較大的環，因為其數量最多有 \(\frac{n}{B}\) 個，一個直接的想法是維護環上的前綴和，二分出查詢區間在環上的位置，單次復雜度 \(O(\frac{n}{B}\log n)\)。考慮離線，對于每個環算出每個位置的前驅后繼，修改過程中記錄偏移量，這樣對于每個詢問就可以 \(O(1)\) 算出這個大環的貢獻，總時間復雜度 \(O((n+q)\frac{n}{B})\)。
取 \(B=\sqrt{n}\)，總時間復雜度 \(O((n+q)\sqrt{n})\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
ifstream cin("ring.in");
ofstream cout("ring.out");
const int maxn=1.5e5+5,B=387,maxb=397;
int n,m,q,a[maxn],b[maxn],c[maxn],ans[maxn];
int bnm,st[maxb],ed[maxb],sm[maxb],bel[maxn];
int sum[maxn<<1],pre[maxn],nxt[maxn];
vector<int> vc[maxn];
struct{
int opt,l,r,x;
}d[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>b[i];
c[b[i]]++,vc[b[i]].pb(i);
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
bnm=n/B;
for(int i=1;i<=bnm;i++){
st[i]=ed[i-1]+1,ed[i]=ed[i-1]+B;
for(int j=st[i];j<=ed[i];j++){
bel[j]=i;
if(c[b[j]]<=B){
sm[i]+=a[j];
}
}
}
if(ed[bnm]<n){
st[bnm+1]=ed[bnm]+1,ed[bnm+1]=n;
bnm++;
for(int i=st[bnm];i<=ed[bnm];i++){
bel[i]=bnm;
if(c[b[i]]<=B){
sm[bnm]+=a[i];
}
}
}
// for(int i=1;i<=n;i++){
// cout<<bel[i]<<' ';
// }
// cout<<'\n';
// for(int i=1;i<=bnm;i++){
// cout<<st[i]<<' '<<ed[i]<<'\n';
// }
for(int i=1;i<=q;i++){
int opt;
cin>>opt;
if(opt==1){
int l,r;
cin>>l>>r;
d[i]={opt,l,r,0};
int pl=bel[l],pr=bel[r];
if(pl==pr){
for(int j=l;j<=r;j++){
if(c[b[j]]<=B){
ans[i]+=a[j];
}
}
}else{
for(int j=pl+1;j<pr;j++){
// cout<<"b "<<j<<' '<<sm[j]<<'\n';
ans[i]+=sm[j];
}
for(int j=l;j<=ed[pl];j++){
if(c[b[j]]<=B){
// cout<<"a "<<j<<' '<<a[j]<<'\n';
ans[i]+=a[j];
}
}
for(int j=st[pr];j<=r;j++){
if(c[b[j]]<=B){
// cout<<"a "<<j<<' '<<a[j]<<'\n';
ans[i]+=a[j];
}
}
}
}else{
int x;
cin>>x;
d[i]={opt,0,0,x};
if(c[x]<=B){
for(int j=0;j<c[x];j++){
sm[bel[vc[x][j]]]+=a[vc[x][j?j-1:c[x]-1]]-a[vc[x][j]];
}
for(int j=c[x]-1;j;j--){
swap(a[vc[x][j]],a[vc[x][j-1]]);
}
}
}
}
// for(int i=1;i<=q;i++){
// if(d[i].opt==1){
// cout<<ans[i]<<'\n';
// }
// }
for(int i=1;i<=m;i++){
if(c[i]<=B){
continue;
}
// cout<<i<<":\n";
int cnt=0;
for(int j=0;j<c[i];j++){
sum[cnt+1]=sum[cnt]+a[vc[i][j]];
cnt++;
}
for(int j=0;j<c[i];j++){
sum[cnt+1]=sum[cnt]+a[vc[i][j]];
cnt++;
}
// for(int j=0;j<=c[i]*2;j++){
// cout<<sum[j]<<' ';
// }
// cout<<'\n';
int p=1;
for(int j=0;j<c[i];j++){
while(p<=vc[i][j]){
nxt[p++]=j+1;
}
}
while(p<=n){
nxt[p++]=c[i]+1;
}
p=n;
for(int j=c[i]-1;~j;j--){
while(p>=vc[i][j]){
pre[p--]=j+1;
}
}
while(p){
pre[p--]=0;
}
// for(int i=1;i<=n;i++){
// cout<<pre[i]<<' ';
// }
// cout<<'\n';
// for(int i=1;i<=n;i++){
// cout<<nxt[i]<<' ';
// }
// cout<<'\n';
cnt=0;
for(int j=1;j<=q;j++){
if(d[j].opt==1){
int l=d[j].l,r=d[j].r;
// cout<<l<<' '<<r<<' ';
l=nxt[l]+c[i],r=pre[r]+c[i];
if(l>r){
continue;
}
l-=cnt,r-=cnt;
// cout<<l<<' '<<r<<' '<<sum[r]-sum[l-1]<<'\n';
ans[j]+=sum[r]-sum[l-1];
}else{
if(d[j].x==i){
cnt=(cnt+1)%c[i];
}
}
}
}
for(int i=1;i<=q;i++){
if(d[i].opt==1){
cout<<ans[i]<<'\n';
}
}
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號