首页 > 其他分享 >CSP集训题解

CSP集训题解

时间：2022-09-06 14:13:10浏览次数：82  
标签：typedef int 题解 Rep long 集训 maxn CSP define

CSP集训题解

Summer已经完结了于是新开一个，而且旧的已经很卡了

9.5CSP-S短赛1（开小灶1）

T1ZZH的游戏

实际上把策略想明白就很简单。以一次连续的移动为一个阶段，每个阶段都必定都扩展到一个更小的点，类似贪心。

我们可以每次贪心的把能走的小点都走了，于是我们现在就被一圈大点圈起来了，这时候必定有一个人需要走一个大点来打破僵局，因为我们需要到达1。于是我们贪心的选一个所有备选点的最小的点走(同时另一个人移动到它已经扩展过的最小的点)，然后同样的贪心把能走的小点都走了，再考虑大点即可。这样保证每次都是答案尽量小的增长，两边都扩展到了1就停止。所以比较裸的就是直接拿一个优先队列维护所有备选点，这样做是\(O(n \log n)\)的，但是由于那只log是STL造成的，于是开了O2就有无限可能(实际上比线性快)。线性做法就是把优先队列换成桶，从小往大扫就行了。

点击查看代码 


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=1e6+10;

int Lim,ans;
int n;
int tex;
int Gs,Fs;

struct Graph{
	struct eg{int from,to,next;}e[maxn*2];
	int len,head[maxn];bool vis[maxn];
	priority_queue< int,vector<int>,greater<int> >q;
	void lqx(int from,int to)
	{ e[++len].from=from;e[len].to=to,e[len].next=head[from],head[from]=len; }
	void Clear(){Rep(i,1,n)head[i]=0,vis[i]=0;len=0;priority_queue< int,vector<int>,greater<int> >temp;q=temp;}
	void Extend(int u){
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;if(vis[v])continue;
			q.push(v);
		}
	}
}G,F;

void Sol(){
	while(!G.q.empty() || !F.q.empty()){
		if(G.vis[1] && F.vis[1])break;
		if(G.q.empty()){
			int u=F.q.top();F.q.pop();
			ans=max(ans,Gs+u);Fs=min(Fs,u);
			F.Extend(u);
			continue;
		}
		if(F.q.empty()){
			int u=G.q.top();G.q.pop();
			ans=max(ans,Fs+u);Gs=min(Gs,u);
			G.Extend(u);
			continue;
		}
		int u=G.q.top(),v=F.q.top();
		if(Gs+v<Fs+u){
			F.q.pop();
			ans=max(ans,Gs+v);Fs=min(Fs,v);
			F.Extend(v);
		}
		else{
			G.q.pop();
			ans=max(ans,Fs+u);Gs=min(Gs,u);
			G.Extend(u);
		}
	}
	cout<<ans<<"\n";
}

void solve(){
	cin>>n;G.Clear(),F.Clear();int x,y;
	Rep(i,2,n)cin>>x>>y,G.lqx(x,y),G.lqx(y,x);
	Rep(i,2,n)cin>>x>>y,F.lqx(x,y),F.lqx(y,x);
	cin>>Gs>>Fs;ans=Gs+Fs;
	G.Extend(Gs),F.Extend(Fs);
	Sol();
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }

T2ZZH的背包

稍劣一点的是5e8的双指针，考虑折半把两边的所有方案都预处理出来然后合并，就是枚举其中一边的选法，然后在另一边二分查找合法区间，然后由于两边都是有序的，所以左右边界都是单调不升的，双指针即可。

正解是1e7的神奇做法，首先预处理出一边的方案，用归并达到\(O(n)\)，然后枚举另一边的每个物品选不选。把询问离线下来拆成两个小于等于，然后在一边选就相当于在另一边的询问变小了，把所有在另一边的询问跑出来，然后单指针扫一遍统计贡献就行了。由于做法诡异需要卡空间。

点击查看代码 


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=1e2+10;

int n,q;
ll v[maxn];
ll a[1<<20|1],b[1<<20|1];
int na,nb,Va,Vb;

void solve(){
	cin>>n>>q;Rep(i,1,n)cin>>v[i];
	na=n>>1,nb=n-na;
	Va=1<<na,Vb=1<<nb;
	for(int i=0;i<Va;++i) for(int j=0;j<na;++j)a[i+1]+=((i>>j)&1)*v[j+1];
	for(int i=0;i<Vb;++i) for(int j=0;j<nb;++j)b[i+1]+=((i>>j)&1)*v[na+j+1];
	sort(a+1,a+Va+1),sort(b+1,b+Vb+1);
	while(q--){
		ll l,r;cin>>l>>r;ll ans=0;
		int pl=lower_bound(b+1,b+Vb+1,l)-b,pr=upper_bound(b+1,b+Vb+1,r)-b-1;
		if(pr>=pl)ans+=pr-pl+1;
		Rep(i,2,Va){
	//		while(pl<=n && a[i]+b[pl]<l)++pl;
			while(pl>1 && a[i]+b[pl-1]>=l)pl--;
	//		while(pr<n && a[i]+b[pr]<r)++pr;
			while(pr>=1 && a[i]+b[pr]>r)pr--;
			if(pr>=pl)ans+=pr-pl+1;
		}
		cout<<ans<<"\n";
	}
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }

9.4CSP-S模拟2

T1谜之阶乘

下降幂的长度最长是二十，于是可以枚举长度，二分下降幂的起点找。

另一种是长度为d的下降幂一定在n开d次根的附近浮动，于是直接暴力\(d^2\)判一遍就行，注意pow的精度问题

点击查看代码 


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define int ll
using namespace std;

const int maxn=1e18;

int tex;
int n;

vector<pii>ans;

void Check(int n,int x){
	int lim=pow(n,1.0/x);
	for(int i=max(2LL,lim-x);i<=lim;++i){
		int now=1;
		for(int j=i;j<=lim+x;++j){
			now*=j;if(now>n || now<0)break;
			if(now==n){ans.emplace_back(j,i-1);break;}
		}
	}
}

void solve(){
	cin>>n;if(n==1)return cout<<"-1\n",void();
	ans.clear();
	Dwn(i,14,1)Check(n,i);
	ans.emplace_back(n,n-1);
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout<<ans.size()<<"\n";
	for(auto it : ans)cout<<it.fir<<" "<<it.sec<<"\n";
}

#undef int
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }

T2子集

构造题，在子集siz为偶数时有较好的性质，于是考虑把奇数情况变成偶数即可，单独处理前三个k，将前两个k配对构造成公差为1的等差数列，与第三列倒序匹配，那么前三列就解决了，于是问题退化成偶数情况。判一下非法就行了

点击查看代码 


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=1e6+10;

int tex,n,K,siz;

void Work1(){
	cout<<"Yes\n";
	int now=0;int lim=n>>1;
	Rep(i,1,lim){
		cout<<i<<" "<<n-i+1<<" ";
		now+=2;
		if(now==siz){now=0;cout<<"\n";}
	}
}

bool cmp(pii a,pii b){return a.fir+a.sec>b.fir+b.sec;}

pii a[maxn];

void Work2(){
	cout<<"Yes\n";
	Rep(i,1,K)a[i].fir=(i+(K>>1)-1)%K+1,a[i].sec=i+K;
	sort(a+1,a+K+1,cmp);
	int pl=3*K+1,pr=n;
	Rep(i,1,K){
		cout<<a[i].fir<<" "<<a[i].sec<<" "<<2*K+i<<" ";
		int now=3;
		while(now<siz){
			cout<<pl<<" "<<pr<<" ";++pl,--pr;
			now+=2;
		}
		cout<<"\n";
	}
}

void solve(){
	cin>>n>>K;
	siz=n/K;
	if(n==1)return cout<<"Yes\n1\n",void();
	if(siz==1)return cout<<"No\n",void();
	if(siz%2==0)return Work1();
	if(!(K&1))cout<<"No\n",void();
	else return Work2();
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }

T3混凝土粉末

发现每次修改操作的编号与高度都是单增的，于是考虑二分答案，找到这个位置上第一次超过阈值的时刻。常数较大且空间复杂度错误的做法是主席树，可以擦边拿到89分或95分(有一个点看常数和运气)。正解就是把主席树换掉，把操作离线下来，像扫描线一样差分，然后只在一颗树上干就行了，树状数组上二分不太会，但是6秒显然是想把两只log放过去。写线段树就一只log了

点击查看代码 


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define int ll
using namespace std;

const int maxn=1e6+10;

#define gc if(++ip==ie)fread(ip=buf,1,SZ,stdin)
static const int SZ=1<<22;char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int read(){ gc;while(*ip<'-')gc; bool f=*ip=='-';if(f)gc; int x=*ip&15;gc; while(*ip>'-'){x*=10;x+=*ip&15;gc;} return f ? -x : x; }
inline ll readL(){ gc;while(*ip<'-')gc; bool f=*ip=='-';if(f)gc; ll x=*ip&15;gc; while(*ip>'-'){x*=10;x+=*ip&15;gc;} return f ? -x : x; }

int n,q;
int chk[maxn];
bool vis[maxn];
int cnt;
struct tumplex{
	int fir,sec,thi;
	tumplex(){}
	tumplex(int a,int b,int c):fir(a),sec(b),thi(c){}
};

vector<tumplex>vec[maxn],que[maxn];
int ans[maxn];

struct BIT{
	#define lowbit(x) (x&-x) 
	int c[maxn];
	void Add(int x,int d){for(;x<=q;x+=lowbit(x))c[x]+=d;}
	int Query(int x){int res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
}T;

int tot;

int Sol(int x,ll w){
	int l=1,r=x,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(T.Query(mid)>=w)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}

void solve(){
	n=read(),q=read();int opt,x,y;
	ll w;
	Rep(i,1,q){
		opt=read();
		if(opt==1){
			x=read(),y=read(),w=readL();
			chk[++chk[0]]=i;
			vec[x].emplace_back(chk[0],w,i),vec[y+1].emplace_back(chk[0],-w,i);
		}else{ x=read(),w=readL();que[x].emplace_back(++tot,w,i); }
	}
	Rep(i,1,n){
		for(auto it : vec[i])T.Add(it.thi,it.sec);
		for(auto it : que[i])ans[it.fir]=Sol(it.thi,it.sec);
	}
	Rep(i,1,tot)printf("%d\n",ans[i]);
}
#undef int
int main (){ return solve(),0; }

T4排水系统

其实挺简单的，主要是想明白转移的意义。不难设出经过断边和没经过断边两种状态，发现我们必须要一条边断掉，于是我们在不断边的基础上进行流的修正即可。

点击查看代码 


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=2e5+10,maxm=5e5+10,Mod=998244353;

int pw(int x,int p){int res=1,base=x;while(p){if(p&1)res=1LL*res*base%Mod;base=1LL*base*base%Mod;p>>=1;}return res;}
int Inv(int x){return pw(x,Mod-2);}

int f[maxn][2];
int n,m,r,k;
int inv[maxm];
int nowany,nownone,P,iP;

struct Graph{
	struct eg{int from,to,next,a,p;}e[maxm];
	int len,head[maxn];int ins[maxn],ous[maxn],vis[maxn];
	void lqx(int from,int to,int a)
	{ ++ins[to],++ous[from];e[++len].from=from,e[len].to=to,e[len].next=head[from],e[len].a=a,head[from]=len; }
	queue<int>q;
	void TopoDp(){
		Rep(i,1,len)e[i].p=1LL*e[i].a*iP%Mod;
		Rep(i,1,m)q.push(i),f[i][0]=f[i][1]=1;
		while(!q.empty()){
			int u=q.front();q.pop();
			cerr<<u<<" \n";
			int nany=0;
			for(int i=head[u];i;i=e[i].next){
				int v=e[i].to;
				nany=(nany+e[i].p)%Mod,++vis[v];
				if(vis[v]==ins[v])q.push(v);
			}
			for(int i=head[u];i;i=e[i].next){
				int v=e[i].to;
				f[v][0]=(f[v][0]+1LL*f[u][0]*inv[ous[u]])%Mod;
				f[v][1]=(f[v][1]+1LL*f[u][0]*inv[ous[u]]%Mod*(nany-e[i].p+Mod)%Mod*inv[ous[u]-1])%Mod;
				f[v][1]=(f[v][1]+1LL*f[u][1]*inv[ous[u]])%Mod;
				f[v][1]=(f[v][1]+1LL*(Mod-1)*f[u][0]%Mod*inv[ous[u]]%Mod*e[i].p)%Mod;
			}
		}
	}
}G;

void solve(){
	cin>>n>>m>>r>>k;int x,y,w;inv[0]=inv[1]=1;
	Rep(i,2,k)inv[i]=1LL*(Mod-Mod/i)*inv[Mod%i]%Mod;
	Rep(i,1,k)cin>>x>>y>>w,P=(P+w)%Mod,G.lqx(x,y,w);
	iP=Inv(P);G.TopoDp();
	Rep(i,n-r+1,n)cout<<f[i][1]<<" ";
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }

标签：typedef,int,题解,Rep,long,集训,maxn,CSP,define
From： https://www.cnblogs.com/Delov/p/16661553.html

相关文章

  • CF1615F LEGOndary Grandmaster 题解
    CF1615FLEGOndaryGrandmaster对于两个长度为\(n\)的\(01\)串\(s,t\)，你可以对\(s\)进行两种操作：把相邻两个\(0\)变成\(1\)或把相邻两个\(1\)变成\(0\)，......
  • CF1717A题解
    题目\[\text{lcm}(a,b)=\frac{a\timesb}{\gcd(a,b)}\]\[\frac{\text{lcm}(a,b)}{\gcd(a,b)}=\frac{a}{\gcd(a,b)}\times\frac{b}{\gcd(a,b)}\]\[\frac{a}{\gcd(a,b)}\t......
  • 题解【P2466 [SDOI2008] Sue 的小球】
    题目传送门。一眼丁真，鉴定为原题。现将所有点按照\(x\)排序，区间\([l,r]\)的终点一定是\(l\)或\(r\)，否则会跑冤枉路。设\(f_{i,j,0/1}\)表示在区间\([i,j]\)......
  • 1217F 不是题解
    图，动态，连通性，假装强制在线但并不是。 线段树分治是什么？沿着时间建线段树，把logn个操作插到线段树里面，然后就可以简单的增/删了这一题，把可能的两条边都插入线段树。到......
  • 【题解】做题记录（2022.9）
    可能会断断续续的，是因为可能有的时候忘记了写记录9.5今天搞了一天的平衡树，但大部分都是比较基础的操作[SHOI2009]会场预约题目分析：set大法吼啊我们考虑重新定义两个......
  • noi.ac#15 题解
    做了一下午还多，完全独立完成。题意很简单：给树加一条边使得最大匹配数增加1。什么样的边\((a,b)\)满足条件呢？很明显，当且仅当存在一个最大匹配不选\(a,b\)。此时加上\(......
  • P5664[CSP-S2019] Emiya 家今天的饭 （dp + 计数）
     P5664[CSP-S2019]Emiya家今天的饭（dp+计数）题目传送门题目大意：给定一个大小为\(n*m\)的表格，其中\(a_{i，j}\)表示用第\(i\)种烹饪方式并且有第\(j\)......
  • 【题解】[SDOI2009] 虔诚的墓主人
    题意传送门\(N\timesM\)的矩形，格点是共\(W\)棵常青树或墓地。对于一块墓地，它的虔诚度为让它正上下左右各恰有\(k\)棵常青树的方法数量。求出整个矩形公墓的虔诚度总......
  • 题解【CF1025D Recovering BST】
    题目传送门肉眼观察题。设\(f_{i,j,k}\)表示区间\([i,j]\)的根为\(k\)时能否还原。这样枚举一个根\(k\)，分别枚举两个儿子在两个区间的位置转移就好了，由于两个儿子......
  • CSP-S开小灶1
    居然敢嫌弃Cat的文化课不让Cat来参加半集训！？哼这是不可能的Cat哭给你看！……A.ZZH的游戏WA15：emmm想到了二分，然后判断的时候我没有想到让它贪心地走到尽量小的节点，而是让......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99