代码部落 20250629 CSP-S复赛 模拟赛

网址：代码部落

密码 666888（所有CSP-J/S比赛密码）

一： T1    做法： 二次差分

二： T2   吉祥区间   

        思路：主要是倍增，处理ST表 ，f[i][j]表示以i为起点，往右延2^j次幂区间里面的

 吉祥区间的个数，通过f数组就log2N的复杂度求解区间[l,r]里面的吉祥区间个数

番外：一开始我的思路正确，但在代码时，把倍增打炸了，在计算过程中超过了范围，

        代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,q,a[N],f[N][21];
void solve(){cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}int j=1;unordered_map<int,int> st;for(int i=1;i<=n;i++){while(j<=n&&st.size()<8){st[a[j]]++,j++;}if(j==n+1&&st.size()<8)break;f[i][0]=j-1;st[a[i]]--;if(!st[a[i]]) st.erase(a[i]);} for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){if(f[i][j-1]!=0){f[i][j]=f[f[i][j-1]+1][j-1];}}}for(int i=1;i<=q;i++){int l,r,ans=0;cin>>l>>r;for(int j=20;j>=0;j--){if(f[l][j]!=0&&r>=f[l][j]){l=f[l][j]+1;ans+=1<<j;}}cout<<ans<<endl;}
}
signed main(){solve();return 0;
}

三：黑白的交替整数

        首先观察黑白交替数的数量：

        二位数有9*5个交替   三位数有9*5*5个交替数   n位数有9*5^(n-1)个交替数

        可以在1~10^18里面进行二分，查看1~mid里面的交替数的数量是否大于n，

满足左移，不满足右移，从而定位第n位的交替数

        问题转化为给定数x 如何寻找1~x里面有多少个交替数，定义f（x,-1）函数

处理1~x 有多少个交替数，第二个参数是对最高位的约束，-1 是无，0表示必须为偶数，1表示必须为 奇数， 时间复杂度：O(2^log10n)   

        特殊： 当最高位是奇数，只有4*5^(n-1）种可能性，

        代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=25;
int n;
ll n10[N],n5[N];
int glen(ll n){int l=0;while(n){n/=10;l++;}return l;
} 
ll cal(ll n,int len,int x){if(len<1) return 0;if(len==1){if(x==-1) return 0;int t=0;for(int i=0;i<=n;i++){if(i%2==x) t++;}return t;}int h=n/n10[len-1];if(x==-1){ll res=(h-1)*n5[len-1];res+=cal(n10[len-1]-1,len-1,-1);res+=cal(n%n10[len-1],len-1,1-h%2);return res;}else{ll res=0;for(int i=0;i<h;i++){if(i%2==x){res+=n5[len-1];}}if(h%2==x){res+=cal(n%n10[len-1],len-1,1-h%2);}return res;}}
int main(){n10[0]=n5[0]=1;for(int i=1;i<=18;i++){n10[i]=n10[i-1]*10;n5[i]=n5[i-1]*5;}ll n;cin>>n;ll l=1,r=1e18;while(l<=r){ll mid=l+r>>1;if(cal(mid,glen(mid),-1)>=n){r=mid-1;}else {l=mid+1;}}cout<<l<<endl;return 0;
}

 四： 黑白的矩形网格：

        注意到涂格子的方式，可以表示为写上长度为n,m的01串x,y

对应某格子的颜色为cij=xi XOR yj   ，无限制情况下，01串可任取，总方案数为

2^(n+m-1)  同时，我们将颜色转化：

        1.若c[i][j]=0,有xi==yj   

        2. 若c[i][j]=1 有xi!=yj.

        没有限制的位置可以任意填0,1 离散化成图，若一连通块不冲突，则有2种

否则答案为0，时间复杂度O（n log n）;

        代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int> 
const ll mod=998244353;
const int N=3e5+10;
struct node{int x,y,c;bool operator< (const node &nd)const{if(x!=nd.x) return x<nd.x;if(y!=nd.y) return y<nd.y;return c<nd.c;}bool operator==(const node &nd) const{return x==nd.x&&y==nd.y&&c==nd.c;}
}a[N];
int n,m,k,xx[N],yy[N];
vector<pii> ve[2*N];
bool vis[2*N];
int val[2*N];
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1) r=r*a%mod;a=a*a%mod;n>>=1;}return r;
}
bool dfs(int u){vis[u]=1;for(pii &p: ve[u]){int &v=p.first,&w=p.second;if(vis[v]){if((val[u]^w)!=val[v]){return 0;}continue;}val[v]=val[u]^w;if(!dfs(v)) return 0;}return 1;
}
int main(){cin>>n>>m>>k;for(int i=1;i<=k;i++){cin>>a[i].x>>a[i].y>>a[i].c;xx[i]=a[i].x;yy[i]=a[i].y;}sort(a+1,a+k+1);sort(xx+1,xx+k+1);sort(yy+1,yy+k+1);int kk,nn,mm;kk=unique(a+1,a+k+1)-(a+1);nn=unique(xx+1,xx+k+1)-(xx+1);mm=unique(yy+1,yy+k+1)-(yy+1);for(int i=1;i<=kk;i++){a[i].x=lower_bound(xx+1,xx+nn+1,a[i].x)-xx;a[i].y=lower_bound(yy+1,yy+mm+1,a[i].y)-yy;ve[a[i].x].push_back(pii(a[i].y+nn,a[i].c));ve[a[i].y+nn].push_back(pii(a[i].x,a[i].c));}int cnt=n+m-nn-mm;for(int i=1;i<=nn+mm;i++){if(vis[i]) continue;if(dfs(i)) cnt++;else {cout<<0<<endl;return 0;}}cout<<qpow(2,cnt-1)<<endl;
}