省选模拟19

本文主要是介绍省选模拟19，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

看到了题目之后知道自己可能做过两道，一道是弱化版，一道好像有感觉

可是就是想不到该怎么做，也就是说，我根本就记不住自己做过的题，啊，好伤心

然后想要自己且掉......毫无疑问失败了，于是悲观的认为别人都切了我要垫底了

第一题，我想到了是网络流，却是需要跑Q遍，并且没有正确性，能有暴力分也是奇迹

第二题，认为异常的熟悉，式子化到最后了，但是不会求了，写了个40就走了，然而最后交的时候忘记freopen了☺

第三题，卡常卡到家了，写了个莫队还没分......

T1 游行

可以看出是最小路径覆盖，也就是用最小权的路径覆盖所有的点

然而这里还有几个限制，可以合并，变成一条边覆盖终点不覆盖起点

这样每次费用流只增广一个点，并且花费是递增的，于是可以二分了

注意连边连的是最短路，因为有可能一个点经过两次，这样的情况在网络流中是无法表示的

所以我们用最短路，表示直接跨越那个点......

AC_code

#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
	int s=0,t=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
	return s*t;
}
const int N=1005;
const int M=1e6+5;
const int inf=0x3f3f3f3f;
int n,m,Q,C,s=501,t=502;
int d[N][N];
struct E{int to,nxt,val,cot;}e[M*2];
int head[N],rp;
void add_edg(int x,int y,int z,int w){
	e[++rp].to=y;e[rp].nxt=head[x];
	e[rp].val=z;e[rp].cot=w;head[x]=rp;
}
int dis[N],pre[N],epr[N],flo[N];
bool vis[N];
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	queue<int> q;while(!q.empty())q.pop();
	q.push(s);dis[s]=0;flo[s]=inf;
	while(!q.empty()){
		int x=q.front();q.pop();vis[x]=false;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(!e[i].val||dis[y]<=dis[x]+e[i].cot)continue;
			dis[y]=dis[x]+e[i].cot;
			flo[y]=min(e[i].val,flo[x]);
			epr[y]=i;pre[y]=x;
			if(!vis[y])q.push(y),vis[y]=true;
		}
	}
	return (dis[t]!=inf);
}
int ji[N],cj,sum,cst[N];
void sol(){
	int sum=0;memset(head,0,sizeof(head));rp=1;
	fo(i,1,n){
		add_edg(s,i,1,0);add_edg(i,s,0,0);
		add_edg(i+n,t,1,0);add_edg(t,i+n,0,0);
	}
	fo(i,1,n)fo(j,1,n){
		add_edg(i,j+n,inf,d[i][j]);
		add_edg(j+n,i,0,-d[i][j]);
	}
	while(spfa()){
		int now=t;sum+=flo[t];
		ji[sum]=dis[t];
		cst[sum]=cst[sum-1]+dis[t];
		while(now!=s){
			e[epr[now]].val-=flo[t];
			e[epr[now]^1].val+=flo[t];
			now=pre[now];
		}
	}
}
signed main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n=read();m=read();Q=read();
	fo(i,1,n)fo(j,1,n)d[i][j]=100000;
	fo(i,1,m){
		int x=read(),y=read(),z=read();
		d[x][y]=min(d[x][y],z);
	}
	fo(k,1,n)fo(i,1,n)fo(j,1,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	sol();
	while(Q--){
		C=read();int pos=lower_bound(ji+1,ji+n+1,C)-ji;
		printf("%d\n",cst[pos-1]+(n-pos+1)*C);
	}
	return 0;
}

T2 暴力题

就不写式子了，挺好推的

最后分治一下，对n的范围分治

AC_code

#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
	int s=0,t=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
	return s*t;
}
const int N=1e5+5;
const int bas=20;
const int mod=998244353;
int ksm(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}return ret;
}
int T,n,m,ans;
int p[N],cnt,phi[N],mu[N];
bool vis[N];
int f[N],iph[N];
vector<int> sn[N],s[bas+1][bas+1];
void init(){
	phi[1]=iph[1]=mu[1]=1;
	fo(i,2,100000){
		if(!vis[i])p[++cnt]=i,phi[i]=i-1,mu[i]=-1;
		for(int j=1;j<=cnt&&i*p[j]<=100000;j++){
			vis[i*p[j]]=true;
			if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];mu[i*p[j]]=0;break;}
			else phi[i*p[j]]=phi[i]*(p[j]-1),mu[i*p[j]]=-mu[i];
		}
		iph[i]=1ll*i*ksm(phi[i],mod-2)%mod;
	}
	fo(i,1,100000){
		int now=0;sn[i].push_back(0);
		for(int j=i;j<=100000;j+=i){
			f[j]=(f[j]+1ll*iph[i]*mu[j/i]+mod)%mod;
			now=(now+phi[j])%mod;sn[i].push_back(now);
		}
	}
	fo(j,1,bas)fo(k,1,bas){
		int len=100000/max(j,k);s[j][k].resize(len+1);
		fo(i,1,len)s[j][k][i]=(s[j][k][i-1]+1ll*sn[i][j]*sn[i][k]%mod*f[i])%mod;
	}
}
signed main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	//cerr<<(sizeof(s)>>20)<<endl;
	T=read();init();
	cerr<<(sizeof(s)+sizeof(sn)>>20)<<endl;
	while(T--){ans=0;
		n=read();m=read();
		for(int l=1,r;l<=min(n,m);l=r+1){
			r=min(n/(n/l),m/(m/l));
			if(max(n/l,m/l)>bas)fo(i,l,r)ans=(ans+1ll*sn[i][n/i]*sn[i][m/i]%mod*f[i]%mod)%mod;
			else ans=(ans+1ll*(s[n/l][m/l][r]-s[n/l][m/l][l-1]+mod))%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}

T3 卡常题

考场上沉迷于log做法无法自拔......

根号的话，一切皆可预处理，于是很好做了

AC_code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline ll read(){
	ll s=0,t=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch^48);ch=getchar();}
	return s*t;
}
const int N=1e5+5;
const int SQ=600;
int n,m,typ,a[N];ll ans;
struct BIT{
	int tr[N];
	inline void ins(int x,int v){for(int i=x;i<=n;i+=(i&-i))tr[i]+=v;}
	inline int query(int x){int ret=0;for(int i=x;i;i-=(i&-i))ret+=tr[i];return ret;}
	inline void clear(int x){for(int i=x;i<=n;i+=(i&-i)){if(!tr[i])break;tr[i]=0;}};
}bit;
struct DIT{
	int tr[N];
	inline void ins(int x,int v){for(int i=x;i;i-=(i&-i))tr[i]+=v;}
	inline int query(int x){int ret=0;for(int i=x;i<=n;i+=(i&-i))ret+=tr[i];return ret;}
	inline void clear(int x){for(int i=x;i;i-=(i&-i)){if(!tr[i])break;tr[i]=0;}};
}dit;
int bl[N],sq,le[SQ][N],sm[SQ][N],su[SQ];
int lv[N],rv[N];
signed main(){
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	n=read();m=read();typ=read();sq=pow(n,0.45);
	cerr<<sq<<endl;
	fo(i,1,n)a[i]=read(),bl[i]=(i-1)/sq+1;
	fo(i,1,bl[n]){
		fo(j,(i-1)*sq+1,min(i*sq,n))le[i][a[j]]++;
		fo(j,1,n)le[i][j]+=le[i][j-1];
		fo(j,1,(i-1)*sq)sm[i][j]=sm[i][j-1]+le[i][a[j]];
		fo(j,(i-1)*sq+1,min(i*sq,n))sm[i][j]=sm[i][j-1];
		fo(j,i*sq+1,n)sm[i][j]=sm[i][j-1]+(sq-le[i][a[j]]);
		fu(j,min(i*sq,n),(i-1)*sq+1)su[i]+=bit.query(a[j]),bit.ins(a[j],1),rv[j]=su[i];
		fo(j,(i-1)*sq+1,min(n,i*sq))bit.clear(a[j]);
		dit.ins(a[(i-1)*sq+1],1);fo(j,(i-1)*sq+2,min(i*sq,n))lv[j]=lv[j-1]+dit.query(a[j]),dit.ins(a[j],1);
		fo(j,(i-1)*sq+1,min(i*sq,n))dit.clear(a[j]);
	}
	cerr<<(1.0*clock()/CLOCKS_PER_SEC)<<endl;
	while(m--){
		int l=read()^(ans*typ),r=read()^(ans*typ);ans=0;
		if(bl[l]==bl[r]){
			fu(i,r,l)ans+=bit.query(a[i]),bit.ins(a[i],1);
			fo(i,l,r)bit.clear(a[i]);printf("%lld\n",ans);
			continue;
		}
		fo(i,bl[l]+1,bl[r]-1){
			ans+=su[i];
			ans+=sm[i][(i-1)*sq]-sm[i][l-1];
			ans+=sm[i][r]-sm[i][(bl[r]-1)*sq];
		}ans+=rv[l]+lv[r];
		fu(i,r,(bl[r]-1)*sq+1)bit.ins(a[i],1);
		fu(i,bl[l]*sq,l)ans+=bit.query(a[i]);
		fu(i,r,(bl[r]-1)*sq+1)bit.clear(a[i]);
		printf("%lld\n",ans);
	}
	return 0;
}

这篇关于省选模拟19的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

省选模拟19

T1 游行

T2 暴力题

T3 卡常题

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯