7.12 模拟赛

wgyhm

2023-07-13

NOIP模拟赛, 线段树优化建图, 随机化

7.12 模拟赛

今天 T3 没卡时，遗憾 rk3。

T1. ha

Description

$1\le n\le 1\times 10^5,1\le m\le 100,l1,l2,r1,r2\le m$

Solution

这题虽然签到，但是重点在于 每次操作之后，都可以看到计数器当前的显示值。所以每一位是要单独计算的。

反着做，每次模拟 $i$ 这个位置两次不同效果的期望值大小。比较取大的即可。前缀和搞一下。

Code

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m;
int l1,r1,l2,r2;
double a[105],suf[105],suf2[105],ans;
signed main(void){
  	freopen("ha.in","r",stdin);
  	freopen("ha.out","w",stdout);
	int i,j,L,R;double sum1,sum2;
	read(n);read(m);read(l1);read(r1);read(l2);read(r2);
	for (i=0;i<m;i++) a[i]=i;
	for (i=1;i<=n;i++) {
		suf[0]=a[0];for (j=1;j<=m;j++) suf[j]=suf[j-1]+a[j];
		for (j=0;j<m;j++) {
			sum1=sum2=0;
			L=((j+l1+m)%m),R=(j+r1+m)%m;
			if (L<=R) {
				if (!L) sum1=suf[R];
				else sum1=suf[R]-suf[L-1]; 
			}
			else sum1=suf[m]-suf[L-1]+suf[R];
			sum1/=(r1-l1+1);
			
			L=((j+l2+m)%m),R=(j+r2+m)%m;
			if (L<=R) {
				if (!L) sum2=suf[R];
				else sum2=suf[R]-suf[L-1]; 
			}
			else sum2=suf[m]-suf[L-1]+suf[R];
			sum2/=(r2-l2+1);
			
			a[j]=max(sum1,sum2);
		}
	}
	printf("%.2lf",a[0]);
	return 0;
}

T2. carve

Description

$1\le n\le 10^6,a_i\le n$

Solution

实际上，题目转化为有两个机器，一个机器如果新加入或者加入和上一个加入的颜色不同，则花费一点代价。求代价最小化。

前几天做到一个这道题的加强版。就是有划分成 $k$ 个有序集合。回到这题，考虑贪心。如果当前节点和原来机器的颜色都不一样，则贪心去机器下一个颜色一样的位置大的机器。证明略。具体看代码。

Code

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,a[maxn];
int sum;
int id1,id2,t[maxn],nex[maxn]; 
signed main(void){
  	freopen("carve.in","r",stdin);
  	freopen("carve.out","w",stdout);
	int i;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=n;i>=1;i--) nex[i]=t[a[i]]==0?n+1:t[a[i]],t[a[i]]=i;
	for (i=1;i<=n;i++) {
		if (a[id1]==a[i]) id1=i;
		else if (a[id2]==a[i]) id2=i;
		else if (!id1) id1=i,sum++;
		else if (!id2) id2=i,sum++;
		else {
			sum++;
			if (nex[id1]>nex[id2]) id1=i;
			else id2=i;
		} 
	}
	printf("%d",sum);
	return 0;
}

T3. sword

Description

给定 $1$ 个长度为 $n$ 的正整数序列 $a$。每次操作可以选择 $a_i$ 加 $1$ 或者减 $1$，但需要满足 $a_i$ 为正数。

求让 $\gcd(a_1,a_2,a_3,…,a_n)>1$ 的最少操作次数。

$n\le 2\times 10^5,a_i\le 1\times 10^{12}$

1s 512MB

Upt on 12.21：CF1305F

Solution

很有意思的题目！

一种显然的想法就是枚举质数 $p$ ，如果答案为 $p$ 的倍数的最小操作次数。这样做是 $O(n)$ 的。

注意到 $p=2$ 时，答案 $\le n$。

考虑使枚举质数 $p$ 的次数变少。观察到操作次数不超过 $1$ 的个数有至少有 $\dfrac{n}{2}$ 个。考虑随机出一个数 $a_i$，枚举 $a_i-1,a_i,a_i+1$ 三个数的质因子。多随几个，保证正确率。随机 $n$ 次的错误率是 $(1/2)^n$。

我的考场做法是枚举 $[a_i-100,a_i+100]$ 的质因子。这样做效率显然是没有上面高的。但是能过/shl

下次随机化必写卡时，警戒

Code1 考场代码

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>N
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,a[maxn],Ans=1e9,Max=0;
inline int calc(int k) {
	int i,sum=0;
	for (i=1;i<=n;i++) 
		if (a[i]<k) sum+=k-a[i];
		else sum+=min(a[i]-a[i]/k*k,(a[i]/k+1)*(k)-a[i]);
	return sum; 
}
int prime[1000005],cnt,vis[1000005];
mt19937 rnd(time(0));
inline void init(int n) {
	vis[1]=1;int i,j;
	for (i=2;i<=n;i++) {
		if (!vis[i]) prime[++cnt]=i;
		for (j=1;j<=cnt&&prime[j]*i<=n;j++) {
			vis[prime[j]*i]=1;
			if (i%prime[j]==0) break;
		}
	}
}
namespace BL{
	inline void main(void) {
		int i;
		for (i=1;i<=cnt&&prime[i]<=Max;i++) {
			Ans=min(Ans,calc(prime[i]));
		} 
		printf("%lld",Ans);
	}
}
namespace STD{
	int p[1000005],tot;
	inline void solve(int x) {
		int i,now=x;
		for (i=1;i<=cnt&&prime[i]*prime[i]<=x;i++) {
			if (now==1) break;
			if (now%prime[i]==0) {
				p[++tot]=prime[i];
				while (now%prime[i]==0) now/=prime[i];
			} 
		}
		if (now>1) p[++tot]=now;
	}
	inline void main(void) {
		int i,id1;
		id1=rnd()%n+1;
		for (i=max(a[id1]-100,1ll);i<=a[id1]+100;i++) solve(i);
		sort(p+1,p+1+tot);
		tot=unique(p+1,p+1+tot)-p-1;
		for (i=1;i<=tot;i++) Ans=min(Ans,calc(p[i]));
		printf("%lld\n",Ans);
	}
}
signed main(void){
	freopen("sword.in","r",stdin);
  	freopen("sword.out","w",stdout);
	int i;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),Max=max(Max,a[i]); 
	init(1e6);
	if (Max<=1e3) BL::main();else 
	STD::main();
	return 0;
}

Code2 std

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,a[maxn],Ans=1e9,Max=0;
inline int calc(int k) {
	int i,sum=0;
	for (i=1;i<=n;i++) 
		if (a[i]<k) sum+=k-a[i];
		else sum+=min(a[i]-a[i]/k*k,(a[i]/k+1)*(k)-a[i]);
	return sum; 
}
int prime[1000005],cnt,vis[1000005];
mt19937 rnd(time(0));
inline void init(int n) {
	vis[1]=1;int i,j;
	for (i=2;i<=n;i++) {
		if (!vis[i]) prime[++cnt]=i;
		for (j=1;j<=cnt&&prime[j]*i<=n;j++) {
			vis[prime[j]*i]=1;
			if (i%prime[j]==0) break;
		}
	}
}
namespace BL{
	inline void main(void) {
		int i;
		for (i=1;i<=cnt&&prime[i]<=Max;i++) {
			Ans=min(Ans,calc(prime[i]));
		} 
		printf("%lld",Ans);
	}
}
namespace STD{
	int p[1000005],tot;
	inline void solve(int x) {
		int i,j,now=x;
		if (x<=0) return ;
		for (i=1;i<=cnt&&prime[i]*prime[i]<=x;i++) {
			if (now==1) break;
			if (now%prime[i]==0) {
				p[++tot]=prime[i];
				while (now%prime[i]==0) now/=prime[i];
			} 
		}
		if (now>1) p[++tot]=now;
		for (j=1;j<=tot;j++) if (p[j]>1) {
			int res=0;
			for (i=1;i<=n;i++) 
				if (a[i]<p[j]) res+=p[j]-a[i];
				else res+=min(a[i]%p[j],p[j]-a[i]%p[j]);
			Ans=min(Ans,res);
		}
	}
	inline void main(void) {
		int i;
		while (1.0*clock()/CLOCKS_PER_SEC<2.0) {
			int x=a[rnd()%n+1];
			solve(x-1);solve(x);solve(x+1);
		}
		printf("%lld\n",Ans);
	}
}
signed main(void){
	int i;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),Max=max(Max,a[i]); 
	init(1e6);
	STD::main();
	return 0;
}

T4. war

Description

$n\le 5\times 10^5$

同 CF798E

注意空间限制。

Solution

方心童说这个东西叫做 “线段树隐式建图”，反正是我没见过的。

空间为 $O(n^2)$ 的暴力是显然的。

Step 1

方便起见，将等于 $-1$ 的 $a_i$ 改成 $n+1$。同时，记 $p_x$ 为满足 $a_i=x$ 的 $i$ （$x$ 的前驱），如果没有就记为 $n+1$。

注意到其实对于所有 $i$ 满足：

$f_{p_i}<f_i$
对于满足 $j<a_i$ 且 $p_j>i$ 的 $j$ ，$f_j<f_i$

注意到建出这两类有向边以后，跑拓扑排序。$f_i$ 即为其拓扑序。容易发现条件是充要的。

Step 2

有一个叫做 dfs 拓扑排序 的东西，过程如下：

建反向边
从 $i$ 进入，由 $i$ 出发的反向边，搜从没有经历过的点
都搜完以后，时间戳 $t\Leftarrow t+1$，作为 $i$ 的拓扑序。

正确性是显然。每条边和每个点只会经过一次，复杂度上是 $O(n+m)$ 的。

Step 3

考虑套用这个过程。

对于第一类边，只有 $O(n)$ 条，直接跑。

对于第二类边，每次不断找 $j<a_i$ 中 $p_j$ 最大的，如果 $>i$ ，则继续搜。由于一个点只会经过一次，找到 $j$ 以后删掉即可。

每个点只会删一次和经过一次，复杂度是 $O(n\log n)$ 的。

空间上，只有线段树和一些线性数组，甚至没有建边，空间复杂度是 $O(n)$ 的。这可能也是 隐式建图 的来源。

Code

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define M 4000005 
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,b[maxn];
int in[maxn],Ans[maxn],times;
int pre[maxn],f[maxn<<2];
inline void Pushup(int rt) {
	if (!f[rt<<1]||!f[rt<<1|1]) f[rt]=f[rt<<1]+f[rt<<1|1];
	else {
		if (pre[f[rt<<1]]>pre[f[rt<<1|1]]) f[rt]=f[rt<<1];
		else f[rt]=f[rt<<1|1]; 
	}  
}
inline void Update(int l,int r,int rt,int head,int k) {
	if (l==r) return f[rt]=k,void();
	int mid=l+r>>1;
	if (head<=mid) Update(l,mid,rt<<1,head,k);
	else Update(mid+1,r,rt<<1|1,head,k);
	Pushup(rt);
}
inline int Query(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt];
	int mid=l+r>>1,tmp1=0,tmp2=0;
	if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
	if (tmp1&&tmp2) {
		if (pre[tmp1]>pre[tmp2]) return tmp1;
		else return tmp2;
	}
	else return tmp1+tmp2;
}
int vis[maxn];
inline void dfs(int x) {
	if (Ans[x]||vis[x]) return ;
	int tmp;vis[x]=1;
	if (pre[x]<=n) dfs(pre[x]);
	if (b[x]>1) {
		while ((tmp=Query(1,n,1,1,b[x]-1))&&pre[tmp]>x) {
			Update(1,n,1,tmp,0);
			dfs(tmp);
		}	
	}
	Ans[x]=++times;
} 
signed main(void){
 	freopen("war.in","r",stdin);
  	freopen("war.out","w",stdout);
	int i;
	read(n);
	for (i=1;i<=n;i++) pre[i]=n+1;
	for (i=1;i<=n;i++) {
		read(b[i]);
		if (b[i]!=-1) pre[b[i]]=i;else b[i]=n+1;
	}
	for (i=1;i<=n;i++) Update(1,n,1,i,i);
	gdb(n);
	for (i=1;i<=n;i++) if (!Ans[i]) dfs(i); 
	for (i=1;i<=n;i++) printf("%d ",Ans[i]);
	return 0;
}