Codeforces Round #833 (Div. 2) 做题记录
A.The Ultimate Square
略过
B.Diverse Substrings
思路：
我们发现字符数只有0~9十种字符，也就是说，如果我们固定一个左端点\(l\),那么最多向右扩展\(10*10\)次后就会不满足条件，直接暴力枚举即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int T,n;
int a[maxn],t[maxn];
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);getchar();
for(int i=1;i<=n;i++){
char x;
scanf("%c",&x);
a[i]=x-'0';
}
int ans=0;
for(int i=1;i<=n;i++){
int l=i,sum=0,mx=0;
for(int j=0;j<10;j++)t[j]=0;
while(l<=n){
t[a[l]]++;
if(t[a[l]]==1)sum++;
mx=max(mx,t[a[l]]);
if(mx<=sum)ans++;
if(mx>10)break;
l++;
}
}
printf("%lld\n",ans);
}
return 0;
}
C.Zero-Sum Prefixes
题意：
有一个数组\(a_i\)，长度为\(n\)
你可以将其中\(a_i\)为0的值改为任意数。求最后满足\(\sum_{i=1}^{k}a_i=0\)的\(k\)的最多个数
\((1≤n≤2⋅10^5,−10^9≤a_i≤10^9)\)，均为整数
思路：
易知，每两个零都是独立的。上一个0的取值并不会影响到下一个0的取值。
我们设\(p1,p2\)为\(a_i\)为0的位置，且\(p1<p2\)。\(p1,p2\)在0的位置上相邻
那么，在\(p1\)时，我们需要选择一个数字，使得\(p1\)到\(p2-1\)中满足条件的\(k\)最多，实际上就是找一个前缀和众数，找到\(sum[p1]\)到\(sum[p2-1]\)中出现最多的一个数字，我们就可以通过调整0达到目的。\(sum[i]\)=\(\sum_{k=p1}^{i}a_k\)
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define int long long
int t,n;
int a[maxn],sum[maxn];
map<int,int>q;
signed main(){
cin>>t;
while(t--){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
int ans=0,s=0;
for(int i=1;i<=n;i++){
if(a[i]!=0)s+=a[i];
else break;
if(s==0)ans++;
}
for(int i=1;i<=n;i++){
if(a[i]==0){
int l,r=-1;
l=i;
for(int j=i+1;j<=n;j++){
if(a[j]==0){r=j;break;}
}
if(r==-1)r=n+1;
sum[l-1]=0;
int flag=1;
for(int j=l;j<r;j++)sum[j]=sum[j-1]+a[j];
q.clear();int mx=0;
for(int j=l;j<r;j++)q[sum[j]]++,mx=max(mx,q[sum[j]]);
flag=flag+mx-1;
ans=ans+flag;
}
}
printf("%lld\n",ans);
}
return 0;
}
D.ConstructOR
题意：
有三个整数\(a,b,d\),求一个整数\(x\),使得其满足以下三个条件：
\(0\leq x<2^{60}\)\(a|x\)能被\(d\)整除
\(b|x\)能被\(d\)整除
\(1\leq a,b,d<2^{30}\)
其中的\(|\)符号代表或运算
思路：
我们先考虑无解的情况，先考虑特殊情况。
易知，当\(a\)或\(b\)为奇数，而\(d\)为偶数的时候一定无解
我们将这个式子推广一下，若\(a,b,d\)不成立，那么\(2a,2b,2d\)也定然不成立，相当于你把这三个数左移一位，不会有影响。
那么，我们初步无解的条件就判断出来了：当\(min(low(a),low(b))< low(d)\)时一定无解，其中\(low(x)\)代表的是\(x\)最右边一位为1的位置
我们设\(a,b,d\)最右边\(k\)个数均为0，那么\(a,b,d\)有效位置便为\((30-k)\)位 不妨将这些数先全部右移\(k\)位，得到\(a',b',d'\)
我们考虑一种构造方法：使得\(a|x=x,b|x=x\)
那么在右移的数上便是使得\(a'|x'=x',b'|x'=x'\)
我们可以先设置\(x'=2^{30-k}-1\),这样就保证了上述两个条件
那么我们还要满足\(p*2^{30-k}+2^{30-k}-1\)为\(d\)的倍数，便是求一个\(p\)出来
将式子化简：\((p+1)*2^{30-k}-1\)为\(d\)的倍数，等价于\((p+1)*2^{30-k}\equiv1\pmod{d}\)
有点不直观？我们再化简一下，设\(a=p+1,x=2^{30-k}\),则原式变成\(ax\equiv1\pmod{d}\)
直接扩展欧几里得求解即可。记得\(a\)要大于-1
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,A,B,d;
int a,b,s1,s2;
int qpow(int x,int y){
if(y==0)return 1;
if(y&1)return x*qpow(x,y-1);
else return qpow(x*x,y/2);
}
void exgcd(int x,int y){
if(y==0){
s1=1,s2=0;
return ;
}
exgcd(y,x%y);
int temp=s1;
s1=s2;
s2=temp-s2*(x/y);
}
int work(int x){
for(int i=0;i<31;i++){
if((x>>i)&1){
return i;
}
}
}
void check(){
int x=min(work(A),work(B));
int y=work(d);
if(x<y){
printf("-1\n");
return ;
}
int k=min(x,y);
a=qpow(2,30-k);b=d/qpow(2,k);
exgcd(a,b);
int p=((s1-1)%b+b)%b;
int res=p*qpow(2,30-k)+qpow(2,30-k)-1;
printf("%lld\n",res*qpow(2,k));
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&A,&B,&d);
check();
}
return 0;
}
E.Yet Another Array Counting Problem
题意：
数组\(x=[x1,x2,...,xn]\)的\([l;r]\)段上最左边的最大值的位置是最小的整数\(i\)，使得\(l≤i≤r\)且\(xi=max(xl,xl+1,...,xr)\)。
给你一个长度为\(n\)的数组\(a=[a1,a2,...,an]\)，求满足下列条件的长度为n的整数组\(b=[b1,b2,...,bn]\)的数量。
\(1≤bi≤m\)，所有\(1≤i≤n\)。
对于所有一对整数\(1≤l≤r≤n\)，数组\(b\)的\([l;r]\)段上最左边的最大值的位置等于数组\(a\)的\([l;r]\)段上最左边的最大值的位置。
由于答案可能非常大，请打印其余数模\(10^9+7\)。\(2\leq n,m\leq2*10^{5} ,n*m\leq 10^6,a_i\leq m\),均为整数
思路：
我们考虑到底什么样的\(b\)序列才能合法
不妨先设\(m\)为\(a_i\)的最大值且最靠前的位置，\(i\in[1,n]\)
设\(f(l,m-1)=p1=max(a_i),i\in[1,m-1]\) \(f(m+1,n)=p2=max(a_i),i\in[m+1,n]\)
那么先决条件便是\(b[p1]<b[m],b[p2]\leq b[m]\)
在满足的情况下，这个序列便一分为二，可以继续递归求解
我们不妨构造一棵二叉树，对于节点\(x=f(l,r)\),他的两个儿子分别是\(f(l,x-1)\)和\(f(x+1,r)\),对于每一个\(x\in[1,n]\)
当然，不是所有的节点都有两个儿子。对于\(x=l\)的点，没有左儿子;对于\(x=r\)的点，没有右儿子。
我们设一个\(dp[i][j]\)表示为目前是第几个数 这个数的大小是多少。自然，我们的转移是根据我们这棵树的结构来确定的，这是一个树形DP
具体而言：
如果\(x\)有一个左边的孩子且\(x=1\)，那么\(dp[x][val]=0\)。
否则，如果\(x\)有两个孩子，那么\(dp[x][val]=（\sum_{i=1}^{x-1}dp[p1][i]）⋅（\sum_{i=1}^{x}dp[p2][i]）\)。
如果\(x\)只有一个左边的孩子，那么\(dp[x][val]=\sum_{i=1}^{x-1}dp[p1][i]\)。
如果\(x\)只有一个右边的孩子，那么\(dp[x][val]=\sum_{i=1}^{x}dp[p2][i]\)。
如果\(x\)没有孩子，那么\(dp[x][val]=1\)。
当然，我们发现这样时间是过不了的。但是对于求和操作我们可以使用前缀和数组\(sum\)来优化即可通过此题
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
const int mod=1e9+7;
int t,n,m;
int a[maxn],tr[maxn<<2];
vector<int>dp[maxn];//位置 取值
void add(int l,int r,int rt,int x,int val){
if(l==r){
tr[rt]=val;
return ;
}
int mid=(l+r)/2;
if(x<=mid)add(l,mid,rt*2,x,val);
else add(mid+1,r,rt*2+1,x,val);
tr[rt]=max(tr[rt*2],tr[rt*2+1]);
}
int query(int l,int r,int rt,int L,int R){
if(L<=l&&r<=R){
return tr[rt];
}
int mid=(l+r)/2;
int mx=-1;
if(L<=mid)mx=max(mx,query(l,mid,rt*2,L,R));
if(R>mid)mx=max(mx,query(mid+1,r,rt*2+1,L,R));
return mx;
}
int cxk(int l,int r,int rt,int L,int R,int val){
if(l==r)return l;
int mid=(l+r)/2;
int id=-1;
if(L<=mid&&tr[rt*2]>=val)id=cxk(l,mid,rt*2,L,R,val);
if(R>mid&&tr[rt*2+1]>=val){
if(id==-1)id=cxk(mid+1,r,rt*2+1,L,R,val);//先左后右
}
return id;
}
int solve(int l,int r){
if(l>r)return -1;
int mid=cxk(1,n,1,l,r,(query(1,n,1,l,r)));//位置
int p1=solve(l,mid-1);
int p2=solve(mid+1,r);
for(int i=1;i<=m;i++){
int ans=0;
if(p1>=0&&i==1)ans=0;
else ans=((p1>=0)?dp[p1][i-1]:1ll)*((p2>=0)?dp[p2][i]:1ll)%mod;ans%=mod;
dp[mid][i]+=(dp[mid][i-1]+ans)%mod;
}
return mid;
}
void work(){
for(int i=1;i<=n;i++)add(1,n,1,i,a[i]);
for(int i=1;i<=n;i++)dp[i].resize(m+2);
for(int i=1;i<=n;i++)dp[i].clear();
solve(1,n);
int mid=cxk(1,n,1,1,n,(query(1,n,1,1,n)));
printf("%lld\n",dp[mid][m]);
}
signed main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
work();
}
return 0;
}
F.Circular Xor Reversal
摆了，明天补
标签：833,p1,return,val,int,Codeforces,mid,Div,dp From： https://www.cnblogs.com/c20230507/p/16894388.html