【周8道题】4.24完成

2021/4/24 10:25:20

本文主要是介绍【周8道题】4.24完成,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

额,这八道题算法有些重复,其中单调类和DP似乎比较多,不过总体来说还是很有写的必要滴
我在做这些题时用到的算法有:单调类(单调队列、数组)、dp(区间dp、状压dp)、莫队、tarjin
由于比较忙碌,没有探究多种解法,谁有想法可以评论啊
我标了推荐指数,指数为*表示强烈不建议做,***表示一般题目,*****表示强烈建议去做。

[luogu]P2034 选择数字

推荐指数:***
算法:队列

先考虑dp。f[i][j]表示对于前i个数,结尾连续选了j个数时最大的数(1<=i<=n, 0<=j<=k)。那么f[i+1][j]=f[i][j-1]+a[j],f[i+1][0]=max{f[i][0],f[i][1],...,f[i][k]}。

显然f数组的求取是O(N*K)的,太慢了。但是转移过程是可以转化成队列的。
f[i][0]到f[i][k-1]只是往后顺一位加上同一个数成为f[i+1][1]到f[i+1][k],只有f[i+1][0]的计算略复杂一些。这就相当于维护一个长度为k+1的队列,每次从队尾删去一个数,从队头添加一个数。对于转移时加的那些数字,我们用sum存一下就好了。

我是用的multiset维护这个队列。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=100000+10;

int n, k;
int a[N];
LL b[N];
multiset<LL> S;

int main(){
	cin>>n>>k;
	for(int i=1; i<=n; ++i){
		scanf("%d", a+i);
	}
	
	LL ans=0, sum=0;
	S.insert(0);
	b[0]=0;
	for(int i=1; i<=n; ++i){
		sum+=a[i];
		//maxx存的是队列中的最大值
		multiset<LL>::iterator maxx=S.end(); maxx--;
                //b[i]是队列中添加的第i个元素,可以用来查找要删除的数字
		b[i]=-a[i]+*maxx;
		S.insert(b[i]);
		if(i-k>0){
			multiset<LL>::iterator tmp=S.find(b[i-k-1]);
			S.erase(tmp);
		}
		maxx=S.end(); maxx--;
		ans=max(ans,sum+*maxx);
	}
	cout<<ans<<endl;
}

[luogu]P4163 [SCOI2007]排列

推荐指数:****
算法:状压DP
一开始想的是搜索,结果TLE了。看了题解才发现是状压DP。

S的长度不超过10,这就说明S的排列不超过1024个。令f[t][i]表示以各种方式排状态t包含的这些数字时,膜d得i得结果有多少个(我们先不考虑选择了相同的数字带来的影响)
转移方程为:f[t][(j*10+s[k])%d]+=f[t^(1<<k)][j]

所以说,以后看到小数据就考虑下状压吧。不过,抛开数据范围,这题真有那么容易看出来是状压吗?我认为这道题能使用状压的原因有:

  1. 注重元素选择的顺序
  2. 计算满足交换律、结合律 i+j=j+i, i+(j+k)=(i+j)+k
  3. 数据范围小到可以O(2^n)
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL f[1<<10][1010];
char s[15]; int d;
LL fact3[15];
int num[15];

int main(){
	
	fact3[0]=1;
	for(int i=1; i<=10; ++i) fact3[i]=fact3[i-1]*i;
	
	int T; cin>>T;
	while(T--){
		cin>>s>>d;
		int len=strlen(s);
		for(int i=0; i<10; ++i) num[i]=0;
		for(int i=0; i<len; ++i){
			s[i]-='0';
			num[s[i]]++; 
		}
		f[0][0]=1;
		
		int t=1<<len;
		for(int p=1; p<t; ++p){
			for(int i=0; i<len; ++i){
				if(p&(1<<i)){
					for(int j=0; j<d; ++j){
						f[p][(j*10+s[i])%d]+=f[p^(1<<i)][j];
					}
				}
			}
		}
		
		LL tmp=1;
		for(int i=0; i<10; ++i){
			tmp*=fact3[num[i]];
		}
		cout<<f[t-1][0]/tmp<<endl;
		for(int p=0; p<t; ++p){
			for(int i=0; i<d; ++i) f[p][i]=0;
		}
	}
	
}

[luogu] [国家集训队]数颜色 / 维护队列

推荐指数:*****
算法:莫队

我之前不会莫队,因此通过这道题学习了莫队。
当然莫队的教程哪里都找得到,因此我就说下我对这道题的理解。
知道了[L,R]内的颜色数,可以O(1)推出[L+1,R][L-1,R][L,R+1][L,R-1]的颜色数,那么我们就可以利用这点,用一个区间的答案推出另一个区间的答案。这样一来,时间消耗的主要地方就是区间之间的转移。于是我们用分块来将转移的总消耗控制在一定范围内。

不知道你们有没有,反正我在思考这道题的时候,有一瞬间是萌发了这种想法,但另一瞬间就被否定了,也许是自己觉得不可能实现吧,毕竟区间之间的转移太扯了。然而,正解却就是如此。所以当我们陷入思考的瓶颈时,不妨大胆一些,设法想一想那些“异想天开”的思路吧。

不过还有一点是,这是带修改的莫队,blocksize的大小计算得很玄学。这块我还不是很了解,因此以后可能会写一篇学习篇之类的?

#include<bits/stdc++.h>
using namespace std;

const int V=2000000+10, N=2000000+10;//N=133333+10;
int c, n, m, tota, totb;
int blocksize;
int a[N], p[V], ans[N];

struct change{
	int pre, place, suf;
}cg[N];

struct query{
	int l, r, pre, id, bll, blr;
}q[N];

bool cmp(query a, query b){
	return a.bll!=b.bll?a.bll<b.bll:(a.blr!=b.blr?a.blr<b.blr:a.pre<b.pre);
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i){
		scanf("%d", a+i); a[i]%=V;
	}
	char sss[5];
	for(int i=1, l, r; i<=m; ++i){
		scanf("%s%d%d", &sss, &l, &r);
		if(sss[0]=='R'){
			r%=V;
			cg[++tota].place=l; cg[tota].suf=r;
			cg[tota].pre=a[cg[tota].place];
			a[cg[tota].place]=cg[tota].suf;
		}else{
			if(l>r) swap(l,r);
			q[++totb].l=l; q[totb].r=r; q[totb].pre=tota; q[totb].id=totb;
		}
	}
	blocksize=pow(n,0.666);
//	if(blocksize<1) return 0;
	for(int i=1; i<=totb; ++i){
		q[i].bll=(q[i].l-1)/blocksize+1;
		q[i].blr=(q[i].r-1)/blocksize+1;
	}
	for(int i=tota; i>=1; --i){
		a[cg[i].place]=cg[i].pre;
	}
	sort(q+1,q+totb+1,cmp);
	
	int l=1, r=1, num=1, t=0; p[a[1]]++;
	for(int i=1; i<=totb; ++i){
		int ll=q[i].l, rr=q[i].r, tt=q[i].pre;
		while(ll<l) num+=!p[a[--l]]++;
		while(rr>r) num+=!p[a[++r]]++;
		while(ll>l) num-=!--p[a[l++]];
		while(rr<r) num-=!--p[a[r--]];
		while(tt<t){
			int pla=cg[t].place;
			if(l<=pla && pla<=r) num-=!--p[a[pla]];
			a[pla]=cg[t--].pre;
			if(l<=pla && pla<=r) num+=!p[a[pla]]++;
		}
		while(tt>t){
			int pla=cg[++t].place;
			if(l<=pla && pla<=r) num-=!--p[a[pla]];
			a[pla]=cg[t].suf;
			if(l<=pla && pla<=r) num+=!p[a[pla]]++;
		}
		if(q[i].id<N) ans[q[i].id]=num;
	}
	for(int i=1; i<=totb; ++i) printf("%d\n", ans[i]);
}

[SCOI2006]整数划分

推荐指数:***
算法:高精度,数论

我数论不好,这道题有些做不来......

定理:n只能分成2、3、4这三种数。即若n>4,则n分成n-3和3,这样不断分下去,直到n<=4。
证明:若n分成的数中有一个是k(k>4),那么(k-3)*3-k=2k-9>=2*5-9>0即(k-3)*3>k,也就是把k分成k-3和3更好。

剩下的只要高精度算就好了,也不需要整什么傅里叶变换(我当初就是看到这个标签才选的这道题,害)

#include<bits/stdc++.h>
using namespace std;

const int N=31000;

struct Number{
	int a[5010], sz, M;
	Number(){
		M=10000;
		sz=1;
		a[1]=1;
	}
	
	void Mul(int t){
		int jin=0;
		for(int i=1; i<=sz; ++i){
			a[i]=jin+a[i]*t;
			jin=a[i]/M;
			a[i]%=M;
		}
		if(jin){
			a[++sz]=jin;
		}
	}
}res;

int main(){
	int n; cin>>n;
	while(n>4){
		res.Mul(3);
		n-=3;
	}
	if(n==4) res.Mul(4);
	else if(n==3) res.Mul(3);
	else res.Mul(2);
	
	int tmp=res.a[res.sz];
	int cnt=0;
	while(tmp){
		cnt++;
		tmp/=10;
	}
	cout<<res.sz*4-4+cnt<<endl;
	cout<<res.a[res.sz]; int sum=cnt; 
	for(int i=res.sz-1; sum<100&&i>0; --i){
		if(sum<96){
			//cout<<res.a[i];
			printf("%04d", res.a[i]);
			sum+=4;
		}else{
			int tmp=10000, resa=res.a[i];
			for(; sum<100; ++sum){
				tmp/=10;
				cout<<resa/tmp;
				resa%=tmp;
			}
		}
	}
}

[luoguP3916]图的遍历

推荐指数:**** (可以学下tarjin)
算法:tarjin、反向建图

方法一:tarjin
我一开始就想的这个方法,然后就没再深入地思考了。如果这是一棵树的话,直接dfs就完事了,所以缩点就行了。

方法二:反向建边
直接反向建边,dfs就完事了,按序号从高到低枚举每个点,把它能到达的点标记上就行了,更加简单。

tarjin:

#include<bits/stdc++.h>
using namespace std;

const int N=100000+10;

struct Graph{
	struct Edge{
		int to, next;
		Edge(int to=0, int next=0):to(to),next(next){}
	}e[N];
	int en, h[N];
	Graph(){
		en=0;
		memset(h,0,sizeof(h));
	}
	
	void add(int u, int v){
		e[++en]=Edge(v,h[u]);
		h[u]=en;
	}
}g1, g2;

int ord=1, top=0;
int dfn[N], low[N], belong[N], sta[N], rep[N];
bool vis[N];
int num;
void Tarjin(int u){
	dfn[u]=low[u]=++ord;
	vis[u]=true;
	sta[++top]=u;
	int TOP=top;
	for(int p=g1.h[u]; p; p=g1.e[p].next){
		int v=g1.e[p].to;
		if(!dfn[v]){
			Tarjin(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		num++;
		for(int i=TOP; i<=top; ++i){
			vis[sta[i]]=false;
			belong[sta[i]]=num;
			rep[num]=max(rep[num],sta[i]);
		}
		top=TOP-1;
	}
}

int n, m;

int res[N];

void dfs(int u){
	vis[u]=true;
	res[u]=rep[u];
	for(int p=g2.h[u]; p; p=g2.e[p].next){
		int v=g2.e[p].to;
		if(!vis[v]) dfs(v);
		res[u]=max(res[u],res[v]);
	}
}

int main(){
	cin>>n>>m;
	for(int i=1, u, v; i<=m; ++i){
		scanf("%d%d", &u, &v);
		g1.add(u,v);
	}
	
	for(int i=1; i<=n; ++i){
		if(!dfn[i]) Tarjin(i);
	}

	for(int i=1; i<=n; ++i){
		int u=belong[i];
		for(int p=g1.h[i]; p; p=g1.e[p].next){
			int v=g1.e[p].to; v=belong[v];
			if(u!=v) g2.add(u,v);
		}
	}
	
	for(int i=1; i<=n; ++i){
		if(!vis[belong[i]]) dfs(belong[i]);
	}
	
	for(int i=1; i<=n; ++i){
		printf("%d ", res[belong[i]]);
	}
	return 0;
}

反向建边:

#include<bits/stdc++.h>
using namespace std;

const int N=100000+10;
vector<int> V[N];

int n, m;
int a[N];
int res[N];

void dfs(int u, int cur){
	res[u]=cur;
	for(int i=V[u].size()-1; ~i; --i){
		int v=V[u][i];
		if(res[v]) continue;
		dfs(v,cur);
	}
}

int main(){
	int n, m;
	cin>>n>>m;
	for(int i=1, u, v; i<=m; ++i){
		scanf("%d%d", &u, &v);
		V[v].push_back(u);
	}
	
	for(int i=n; i>=1; --i){
		if(!res[i]) dfs(i,i);
	}
	for(int i=1; i<=n; ++i){
		printf("%d ", res[i]);
	}
}

[cf793D] Presents in Bankopolis

推荐指数:***
算法:区间dp

题意:一条街道上从左往右有n个路口。有m个自行车道的单向道路,他们都有一个起点u和终点v(不能从u、v之间离开道路)和一个困难程度d。现在你要在k个路口放置礼物,如果你在某个路口放置了礼物,那么你之后就不能再经过这个路口。经过一个路口的定义是,这个路口在你走的自行车道的起点和终点之间。现在你能从任意一个路口出发,请问你最少要经历多少困难程度才能完成目标?(最终的困难程度是你走过的路的困难程度之和,且你只能走k-1条道路)如果不能实现,输出-1。
1<=n,k<=80 0<=m<=2000 1<=d_i<=1000

思路:根据不能经过同一个路口的条件,如果我们当前的道路是l->r,那么下次只能选r->k或是t<-r(t>l)。这些区间之间的关系是包含或相切,因此可以用区间dp。令f[l][r][k][0或1]表示在区间[l,r]上已经选了k条路且端点为左边(0为左边,1为右边)时最少的困难程度。
转移方程为f[l][r][k][0]=min{f[t][r][k-1][1]+d[l][r],f[t][r][k-1][0]+d[l][t]},t在l和r之间。具体请看代码。

#include<bits/stdc++.h>
using namespace std;
 
const int INF=1000000007;
const int N=81;
 
int n, m, p;
int c[N][N], f[N][N][N][2];
 
int main(){
	cin>>n>>p>>m;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j) c[i][j]=INF;
	}
	for(int i=1, x, y, dis; i<=m; ++i){
		scanf("%d%d", &x, &y);
		scanf("%d", &dis);
		c[x][y]=min(dis,c[x][y]);
	}
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			for(int k=0; k<=p; ++k){
				f[i][j][k][0]=f[i][j][k][1]=INF;
			}
		}
	}
	for(int i=1; i<=n; ++i){
		f[i][i][1][0]=f[i][i][1][1]=0;
	}
	for(int d=1; d<n; ++d){
		for(int i=1; i+d<=n; ++i){
			int j=i+d;
			for(int k=2; k<=p; ++k){
				for(int i2=i+1; i2<j; ++i2){
					f[i][j][k][0]=min(f[i][j][k][0],f[i2][j][k-1][0]+c[i][i2]);
					f[i][j][k][0]=min(f[i][j][k][0],f[i2][j][k-1][1]+c[i][j]);

				}
				f[i][j][k][0]=min(f[i][j][k][0],f[j][j][k-1][0]+c[i][j]);
				for(int j2=j-1; j2>i; --j2){
					f[i][j][k][1]=min(f[i][j][k][1],f[i][j2][k-1][1]+c[j][j2]);
					f[i][j][k][1]=min(f[i][j][k][1],f[i][j2][k-1][0]+c[j][i]);
				}
				f[i][j][k][1]=min(f[i][j][k][1],f[i][i][k-1][1]+c[j][i]);
			}
		}
	}
	int ans=INF;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			ans=min(ans,f[i][j][p][0]);
			ans=min(ans,f[i][j][p][1]);
		}
	}
	cout<<(ans==INF?-1:ans)<<endl;
}

[cf359C] Prime Number

推荐指数:***
算法:数论

题目挺短的,而且公式也多,就不翻译了。

一道数论唬人题目,只要不被吓住,就没什么难度。
由于x是质数,因此gcd一定是x的幂。我们只需要看分子的指数就好了。
实在过于简单,懒得写了...

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=100000+10;
const LL M=1e9+7;

LL n, x, sum;
LL a[N], b[N], val[N], cnt[N];

LL power(LL x, LL p){
	LL res=1, tmp=x;
	while(p){
		if(p&1) res=res*tmp%M;
		tmp=tmp*tmp%M;
		p>>=1;
	}
	return res;
}

int main(){
	cin>>n>>x;
	for(int i=1; i<=n; ++i){
		scanf("%lld", a+i);
		sum+=a[i];
	}
	for(int i=1; i<=n; ++i){
		b[i]=sum-a[i];
	}
	sort(b+1,b+n+1);
	int valn=0;
	val[++valn]=b[1]; cnt[valn]=1;
	for(int i=2; i<=n; ++i){
		if(b[i]==val[valn]){
			cnt[valn]++;
		}else{
			val[++valn]=b[i];
			cnt[valn]=1;
		}
	}
	int vall=1;
	while(cnt[vall]%x==0){
		if(vall<valn && val[vall+1]==val[vall]+1){
			cnt[vall+1]+=cnt[vall]/x;
			vall++;
		}else{
			val[vall]++;
			cnt[vall]/=x;
		} 
	}
	printf("%lld\n", power(x,min(val[vall],sum)));
	return 0;
}

[cf629D] Babaei and Birthday Cake

推荐指数:***
算法:单调数组(我想大概就叫这个名字)

题意:你有n块蛋糕,编号1到n且每块都有一个体积v_i。你能把第i块放到第j块之上的条件是i>j且v_i>v_j。现在问你最大能摞成多大体积。

根据第一个限制i>j,我们按编号从小到大考虑。根据第二个限制v_i>v_j,我们可以维护一个单调数组。假设已经考虑了前i个蛋糕,我们把他们组成的最优解排序。各个最优解都有两个值last和vol,分别表示放在最上面的蛋糕的体积和总的蛋糕的体积,可以发现last越大,vol就越大。因此我们把这些最优解按last从小到大排序。那么加入第i+1块蛋糕后,就需要更新这个数组。假设t.last是最优解中最大的小于v_{i+1}的last,那么我们可以向数组中加入一个最优解,它的last=v_{i+1},vol=t.vol+v_{i+1}。然后我们还需要删去一些解,来维护“last越大,vol越大”这个性质。所有上面这些操作,可以用set实现。

总的来说还是比较简单的。

#include<bits/stdc++.h>
const double PI=acos(-1);
using namespace std;

struct Data{
	double last, vol;
	bool operator<(const Data&t)const{
		return last<t.last;
	}
};

const int N=100010;
int n;
double v[N];
set<Data> S;

int main(){
	cin>>n;
	for(int i=1, r, h; i<=n; ++i){
		scanf("%d%d", &r, &h);
		v[i]=PI*r*r*h;
	}
	Data d;
	d.last=d.vol=0;
	S.insert(d);
	d.last=PI*10000*10000*10010; d.vol=d.last*N;
	S.insert(d);
	for(int i=1; i<=n; ++i){
		d.last=v[i];
		set<Data>::iterator it=S.lower_bound(d);
		it--;
//		printf("--- %lf\n", v[i]);
		d.vol=it->vol+v[i];
		it++;
		if(it!=S.end()){
			for(set<Data>::iterator it2=it++; it2->vol<d.vol; it2=it++){
				S.erase(it2);
				if(it==S.end()) break;
			}
		}
		S.insert(d);
//		printf("+++ %lf %lf\n", d.last, d.vol);
	}
	set<Data>::iterator it=S.end();
	printf("%.10lf\n", (--(--it))->vol);
}


这篇关于【周8道题】4.24完成的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程