Codeforces Round #751 (Div. 1)
CF1601A Array Elimination
洛谷传送门
CF1601A
分析
可以发现每一位可以拆开，也就是每一位的一的个数一定是 \(k\) 的倍数，
直接求 \(\gcd\) 出来，它的约数就是所有 \(k\) 的取值（\(\gcd=0\)就是 \(1\sim n\)）
代码
#include
#include
#include
using namespace std;
const int N=200011; int n,GCD,a[N];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
for (int T=iut();T;--T){
n=iut(),GCD=0;
for (int i=1;i<=n;++i) a[i]=iut();
for (int i=0;i<30;++i){
int C=0;
for (int j=1;j<=n;++j)
if ((a[j]>>i)&1) ++C;
GCD=gcd(GCD,C);
}
for (int i=1;i<=n;++i)
if (gcd(GCD,i)==i) printf("%d ",i);
putchar(10);
}
return 0;
}
CF1601B Frog Traveler
洛谷传送门
CF1601B
代码（线段树优化建图跑Dijkstra）
//直接O(n)贪心更好写
#include
#include
#include
#include
using namespace std;
const int N=1000011; pairheap[N<<1];
struct node{int y,w,next;}e[N*6];
int pre[N],p[N],Cnt,et,n,as[N],cnt,dis[N],b[N],ls[N],rs[N],a[N],root;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(int x){
if (x==n) return; print(pre[x]);
if (x<=n) printf("%d ",p[x]);
}
void add(int x,int y,int w){
e[++et]=(node){y,w,as[x]},as[x]=et;
}
void Push(pairw){
heap[++Cnt]=w;
int x=Cnt;
while (x>1){
if (heap[x]>1])
swap(heap[x],heap[x>>1]),x>>=1;
else return;
}
}
void Pop(){
heap[1]=heap[Cnt--];
int x=1;
while ((x<<1)<=Cnt){
int y=x<<1;
if (yheap[y]) swap(heap[x],heap[y]),x=y;
else return;
}
}
void Dijkstra(int S){
heap[++Cnt]=make_pair(0,S);
for (int i=0;i<=cnt;++i) dis[i]=0x3f3f3f3f; dis[S]=0;
while (Cnt){
int t=heap[1].first,x=heap[1].second;
Pop(); if (t!=dis[x]) continue;
for (int i=as[x];~i;i=e[i].next)
if (dis[e[i].y]>dis[x]+(e[i].w>0)){
dis[e[i].y]=dis[x]+(e[i].w>0),pre[e[i].y]=x,p[e[i].y]=e[i].w;
Push(make_pair(dis[e[i].y],e[i].y));
}
}
}
void build(int &rt,int l,int r){
rt=++cnt;
if (l==r){
add(rt,b[l],l);
return;
}
int mid=(l+r)>>1;
build(ls[rt],l,mid);
build(rs[rt],mid+1,r);
add(rt,ls[rt],0),add(rt,rs[rt],0);
}
void update(int rt,int l,int r,int x,int y,int z){
if (l==x&&r==y){
add(z,rt,0);
return;
}
int mid=(l+r)>>1;
if (y<=mid) update(ls[rt],l,mid,x,y,z);
else if (x>mid) update(rs[rt],mid+1,r,x,y,z);
else update(ls[rt],l,mid,x,mid,z),update(rs[rt],mid+1,r,mid+1,y,z);
}
int main(){
n=iut(),cnt=n,et=0,memset(as,-1,sizeof(as));
for (int i=1;i<=n;++i) a[i]=iut();
for (int i=1;i<=n;++i) b[i]=i+iut();
build(root,0,n);
for (int i=1;i<=n;++i) update(root,0,n,i-a[i],i,i);
Dijkstra(n);
if (dis[0]==0x3f3f3f3f) printf("-1");
else printf("%d\n",dis[0]+1),print(0);
return 0;
}
CF1601C Optimal Insertion
洛谷传送门
CF1601C
分析
首先 \(b\) 中元素在 \(c\) 中一定是从小到大排列的
所以升序依次填入每个数，用线段树维护 \(a\) 每个位置能提供的逆序对，那肯定越小越好
代码
#include
#include
#include
using namespace std;
const int N=1000011; long long ans;
int A[N],a[N],b[N],k,n,m,c[N],lazy[N<<2],rk[N];
struct rec{
int p,w;
}w[N<<2];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
bool cmp(int x,int y){return a[x]y.w?y:x;}
void Update(int x,int y){
for (;x<=k;x+=-x&x) c[x]+=y;
}
int Query(int x){
int ans=0;
for (;x;x-=-x&x) ans+=c[x];
return ans;
}
void ptag(int k,int z){w[k].w+=z,lazy[k]+=z;}
void pdown(int k){
if (lazy[k]){
ptag(k<<1,lazy[k]);
ptag(k<<1|1,lazy[k]);
lazy[k]=0;
}
}
void build(int k,int l,int r){
lazy[k]=0;
if (l==r){
w[k]=(rec){l,0};
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
w[k]=pup(w[k<<1],w[k<<1|1]);
}
void update(int k,int l,int r,int x,int y,int z){
if (l==x&&r==y){
ptag(k,z);
return;
}
int mid=(l+r)>>1; pdown(k);
if (y<=mid) update(k<<1,l,mid,x,y,z);
else if (x>mid) update(k<<1|1,mid+1,r,x,y,z);
else update(k<<1,l,mid,x,mid,z),update(k<<1|1,mid+1,r,mid+1,y,z);
w[k]=pup(w[k<<1],w[k<<1|1]);
}
rec query(int k,int l,int r,int x,int y){
if (l==x&&r==y) return w[k];
int mid=(l+r)>>1; pdown(k);
if (y<=mid) return query(k<<1,l,mid,x,y);
else if (x>mid) return query(k<<1|1,mid+1,r,x,y);
else return pup(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y));
}
int main(){
for (int T=iut();T;--T){
n=iut(),m=iut(),ans=0;
for (int i=1;i<=n;++i) rk[i]=i,A[i]=a[i]=iut();
for (int i=1;i<=m;++i) b[i]=iut();
sort(b+1,b+1+m),sort(rk+1,rk+1+n,cmp);
build(1,0,n+1);
for (int i=1;i<=n;++i) update(1,0,n+1,i,n+1,1);
for (int l=1,r,j=1,last=0;l<=m;l=r+1){
for (r=l;r<=m&&b[r]==b[l];++r); --r;
for (;j<=n&&a[rk[j]] CF1601D Difficult Mountain
洛谷传送门
CF1601D
分析
先按照 \(\max\{s_i,a_i\}\) 升序排序，再按照 \(s_i\) 升序排序，这样贪心可以证明一定是最优的
代码
#include
#include
#include
using namespace std;
const int N=500011;
struct rec{int x,y,mx;}a[N];
int n,A,ans;
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
int max(int a,int b){return a>b?a:b;}
bool cmp(rec x,rec y){
if (x.mx!=y.mx) return x.mx=A){
A=max(A,a[i].y);
++ans;
}
return !printf("%d",ans);
}
CF1601E Phys Ed Online
洛谷传送门
CF1601E
分析
可以发现答案与 \([l,l+ki]\) 的最小值有关，这个可以用ST表预处理出来。
那么答案其实与 \(l\bmod k\) 的值有关，考虑分成 \(k\) 种情况处理。
取出来一定是一段单调递减的位置，从右到左用一个单调递增的单调栈维护。
如果将 \([l,r]\) 的最小值位置 \(mn\) 取出来，那么就是 \([l,mn]\) 是单调栈的答案，\((mn,r]\) 是 \(a[mn]\) 的答案。
直接取出相应的位置计算答案即可。
代码
#include
#include
#include
#include
using namespace std;
const int N=300011; typedef long long lll;
struct rec{int l,r,rk;}; vectorK[N]; lll ans[N],dp[N];
int n,Q,k,f[N][19],lg[N],two[19],a[N],b[N],st[N],Top;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(lll ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int Get(int x,int y){return a[x]>a[y]?y:x;}
int query(int l,int r){
int z=lg[r-l+1];
return Get(f[l][z],f[r-two[z]+1][z]);
}
int main(){
n=iut(),Q=iut(),k=iut(),lg[0]=-1,two[0]=1;
for (int i=1;i<=n;++i) a[i]=iut(),lg[i]=lg[i>>1]+1,f[i][0]=i;
for (int i=1;i<=lg[n];++i) two[i]=two[i-1]<<1;
for (int j=1;j<=lg[n];++j)
for (int i=1;i+two[j]-1<=n;++i)
f[i][j]=Get(f[i][j-1],f[i+two[j-1]][j-1]);
for (int i=1;i<=Q;++i){
int l=iut(),r=iut();
if (l+k>r) ans[i]=a[l];
else K[l%k].push_back((rec){l,r,i});
}
for (int i=0;in)?n:(j+k));
}
for (int j=n/k;~j;--j){
while (Top&&a[b[st[Top]]]>=a[b[j]]) --Top;
dp[j]=dp[st[Top]]+1ll*(st[Top]-j)*a[b[j]];
st[++Top]=j;
}
int len=K[i].size();
for (int j=0;j CF1601F Two Sorts
洛谷传送门
CF1601F
分析
可以发现字典序的第几个很难求，考虑将排列转换成第几个字典序
考虑折半搜索，如果将 \(n\) 的后六位去除，前若干位就是一个关键字，
只要小于 \(\left\lfloor\frac{n}{10^6}\right\rfloor\) 的非零数都能当作关键字
这些关键字后面可以放任意不超过六位的数字，这个预处理出来就可以了。
如果不作为关键字直接暴力就可以了，注意取模很阴间，所以要二分多少个数需要减去模数。
代码
#include
#include
#include
using namespace std;
const int mod=998244353,MOD=1000000007;
typedef long long lll; vectorK[7];
lll s[7],siz[7],n,kth; int ans,ten[8],Kth;
void dfs1(int dep,int now){
if (dep==7) return;
int t=(Kth-now+mod)%mod;
K[dep].push_back(t),s[dep]+=t,++Kth;
for (int i=0;i<10;++i)
dfs1(dep+1,now*10+i);
}
void dfs2(int dep,lll now){
if (now>n) return;
if ((now+1)*ten[6]-1<=n&&now*ten[7]>n){
for (int i=0;i<7;++i){
int t=((kth-now*ten[i])%mod+mod)%mod;
int pos=lower_bound(K[i].begin(),K[i].end(),mod-t)-K[i].begin();
ans=(ans+s[i]+t*siz[i]-mod*(siz[i]-pos))%MOD;
}
kth+=Kth;
return;
}
int t=((kth-now)%mod+mod)%mod;
ans=(ans+t)%MOD,++kth;
for (int i=!dep;i<10;++i)
dfs2(dep+1,now*10+i);
}
int main(){
ios::sync_with_stdio(0);
cin>>n,ten[0]=1,dfs1(0,0);
for (int i=1;i<=7;++i) ten[i]=ten[i-1]*10;
for (int i=0;i<7;++i) sort(K[i].begin(),K[i].end()),siz[i]=K[i].size();
dfs2(0,0);
cout<