A、B 略，相信大家都会做 _

C. Exam in BerSU

题意

给你一个长度为 \(n\) 的序列 \(a_i\) 。对于每个 \(i\in [1,N]\) 求 \([1,i-1]\) 中删去至少多少个数能满足剩余 \([1,i]\) 中数的和小于 \(M\) 。

\(n\le 2\cdot 10^5, M\le 2\cdot 10^7, a_i\le 100\) 。

Solution

看到值域 \(\le 100\) ，直接用桶记每个数出现多少次，然后从大到小暴力扫一遍桶就做完了。。。

code

#include<cstdio>

const int N=2e5+5;

int a[N],t[233],n,m,sum;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

	for(int i=1;i<=n;++i)

	{

		sum+=a[i];

		if(sum<=m)

		{

			++t[a[i]];

			printf("0 ");

			continue;

		}

		int ans=0,tmp=sum;

		for(int j=100;j&&tmp>m;--j)

		{

			if(tmp-t[j]*j<=m)

			{

				printf("%d ",ans+(tmp-m-1)/j+1);

				break;

			}

			else tmp-=t[j]*j,ans+=t[j];

		}

		++t[a[i]];

	}

}

D. Extra Element

题意

给一个长度为 \(n\) 的数列，删去一个数使得原数列重排后是等差数列。 \(n\le 2\cdot 10^5\) 。

Solution

……不知道有什么好说的，如果差不等了直接删掉就行了。前 3 个数可能要特判一下。

code

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=2e5+5;

int a[N],id[N];

bool cmp(int x, int y) {

	return a[x]<a[y];

}

int main()

{

	int n; scanf("%d",&n);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]),id[i]=i;

	sort(id+1,id+1+n,cmp);

	sort(a+1,a+1+n);

	if(n<=3)

	{

		puts("1");

		return 0;

	}

	int del=0,cha;

	if(a[3]-a[2]!=a[2]-a[1])

	{

		if(a[3]-a[2]==a[4]-a[3])

		{

			del=1;

			cha=a[3]-a[2];

		}

		else if(a[3]-a[1]==a[4]-a[3])

		{

			del=2;

			cha=a[3]-a[1];

		}

		else if(a[2]-a[1]==a[4]-a[2])

		{

			del=3;

			cha=a[2]-a[1];

		}

		else

		{

			puts("-1");

			return 0;

		}

	}

	else cha=a[2]-a[1];

	for(int i=del?4:3;i<=n;++i)

	{

		int l=(del==i-1?i-2:i-1);

		if(a[i]-a[l]!=cha)

		{

			if(del)

			{

				puts("-1");

				return 0;

			}

			del=i;

		}

	}

	printf("%d",!del?id[1]:id[del]);

}

E. Polycarp and snakes

题意

……题目冗余复杂，还是直接看原题面吧……

Solution

也不知道有什么好说的，直接按题意模拟即可。注意一些细节。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=2005;

char s[N][N];

int x1[N],x2[N],y1[N],y2[N];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n,m,mx=0;

		scanf("%d%d",&n,&m);

		for(int i=1;i<=n;++i) scanf("%s",s[i]+1);

		bool flag=true;

		for(int a=0;flag&&a<26;++a)

		{

			for(int i=1;i<=n;++i)

				for(int j=1;j<=m;++j)

				{

					if(s[i][j]!=a+'a') continue;

					if(!x1[a]&&!y1[a]) x1[a]=x2[a]=i,y1[a]=y2[a]=j;

					else

					{

						x1[a]=min(x1[a],i),x2[a]=max(x2[a],i);

						y1[a]=min(y1[a],j),y2[a]=max(y2[a],j);

					}

				}

			if(x1[a]!=x2[a]&&y1[a]!=y2[a])

			{

				flag=false;

				break;

			}

			if(x1[a]) mx=a+1;

			else continue;

			if(x1[a]==x2[a])

			{

				for(int j=y1[a];j<=y2[a];++j)

				{

					if(s[x1[a]][j]<a+'a') {

						flag=false;

						continue;

					}

				}

			}

			else

			{

				for(int j=x1[a];j<=x2[a];++j)

				{

					if(s[j][y1[a]]<a+'a') {

						flag=false;

						continue;

					}

				}

			}

		}

		if(!flag)

		{

			puts("NO");

			for(int i=0;i<26;++i) x1[i]=y1[i]=x2[i]=y2[i]=0;

			continue;

		}

		printf("YES\n%d\n",mx);

		for(int a=0;a<mx;++a)

		{

			if(!x1[a])

			{

				bool f=true;

				for(int i=1;f&&i<=n;++i)

					for(int j=1;f&&j<=m;++j)

					{

						if(s[i][j]>a+'a')

						{

							printf("%d %d %d %d\n",i,j,i,j);

							f=false;

						}

					}

				continue;

			}

			printf("%d %d %d %d\n",x1[a],y1[a],x2[a],y2[a]);

			x1[a]=y1[a]=x2[a]=y2[a]=0;

		}

	}

}

F. Two Pizzas

题意

有 \(n\) 个人，每个人有若干喜欢的配料；有 \(m\) 个披萨，每个披萨有一个价格和若干个配料。现在要你买两个披萨，使得满足的人尽量多的前提下价钱尽量少。一个人能被满足当且仅当他所有喜欢的配料在两个披萨上出现过。

配料种数不超过 \(9\) 。 \(n,m\le 2\cdot 10^5\) 。

Solution

显然，披萨和人的种数不会超过 \(2^9\) ，直接用桶记一下每种人有多少个，每种披萨的最小/次小价格和其编号。然后 \((2^9)^3\) 枚举两个披萨和人即可。注意一些细节。

code

#include<cstdio>

#include<cstring>

const int N=515;

int a[N],b[N],id[N],b2[N],xid[N],id1,id2,ans,cost;

inline int gi()

{

	char c=getchar(); int x=0;

	for(;c<'0'||c>'9';c=getchar());

	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

	return x;

}

int main()

{

	int n=gi(),m=gi();

	for(int i=1;i<=n;++i)

	{

		int x=gi(),s=0;

		while(x--) s|=(1<<gi()-1);

		++a[s];

	}

	memset(b,0x3f,sizeof(b));

	memset(b2,0x3f,sizeof(b2));

	for(int i=1;i<=m;++i)

	{

		int c=gi(),x=gi(),s=0;

		while(x--) s|=(1<<gi()-1);

		if(c<b[s]) b[s]=c,id[s]=i;

		else if(c<b2[s]) b2[s]=c,xid[s]=i;

	}

	cost=2e9+5;

	for(int s1=0;s1<512;++s1)

		for(int s2=0;s2<512;++s2)

		{

			if(!id[s1]||!id[s2]) continue;

			int tid1,tid2,tcost;

			if(s1==s2) tid1=id[s1],tid2=xid[s1],tcost=b[s1]+b2[s1];

			else tid1=id[s1],tid2=id[s2],tcost=b[s1]+b[s2];

			int ret=0;

			for(int s3=0;s3<512;++s3)

				if(((s1|s2)&s3)==s3) ret+=a[s3];

			if(ret>ans||(ret==ans&&cost>tcost)) cost=tcost,ans=ret,id1=tid1,id2=tid2;

		}

	printf("%d %d",id1,id2);

}

G. Playlist for Polycarp

题意

给你 \(n\) 个数，每个数类型为 \(a/b/c\) ，每个数有一个权值 \(t_i\) 。从中选出若干个数并排列，使它们权值和为 \(T\) 且没有两个数相邻。求合法排列方案数。

\(n\le 50, t_i\le 50, T\le 2500\) .

Solution

设 \(f(v,i,j,k)\) 表示选出 \(i,j,k\) 个 \(a,b,c\) 类型的数，和为 \(v\) 的方案数。转移显然是个背包。

设 \(g(0/1/2,i,j,k)\) 表示选出 \(i,j,k\) 个 \(a,b,c\) 类型的数，最后一个数是 \(a/b/c\) 类型的数的方案数，转移也比较显然。

那么 \(ans=\sum f(T,i,j,k)\times g(0/1/2,i,j,k)\) 。

复杂度 $O(n^4T) $ 。

注意一些细节，比如 \(f\) 数组直接开开不下，可使用 vector 。

#include<bits/stdc++.h>

using namespace std;

const int N=55,Mod=1e9+7,iMod=Mod+1>>1;

vector<vector<vector<int>>> f[2505];

int g[3][N][N][N],n,T,a[N],b[N],c[N],ans,t;

int main()

{

	scanf("%d%d",&n,&T);

	for(int i=1;i<=n;++i)

	{

		scanf("%d%d",&a[i],&b[i]);

		++c[--b[i]];

	}

	for(int i=0;i<=T;++i)

	{

		f[i].resize(c[0]+1);

		for(int j=0;j<=c[0];++j)

		{

			f[i][j].resize(c[1]+1);

			for(int k=0;k<=c[1];++k) f[i][j][k].resize(c[2]+1);

		}

	}

	c[0]=c[1]=c[2]=0,f[0][0][0][0]=1;

	for(int i=1;i<=n;++i)

	{

		c[b[i]]++;

		t+=a[i]; if(t>T) t=T;

		for(int j=c[0];j>=(b[i]==0);--j)

		for(int k=c[1];k>=(b[i]==1);--k)

		for(int l=c[2];l>=(b[i]==2);--l)

			for(int v=t;v>=a[i];--v)

				f[v][j][k][l]=(f[v][j][k][l]+f[v-a[i]][j-(b[i]==0)][k-(b[i]==1)][l-(b[i]==2)])%Mod;

	}

	g[0][0][0][0]=g[1][0][0][0]=g[2][0][0][0]=1;

	for(int i=0;i<=c[0];++i)

		for(int j=0;j<=c[1];++j)

			for(int k=0;k<=c[2];++k)

			{

				if(i) g[0][i][j][k]=1ll*i*(g[1][i-1][j][k]+g[2][i-1][j][k])%Mod;

				if(j) g[1][i][j][k]=1ll*j*(g[0][i][j-1][k]+g[2][i][j-1][k])%Mod;

				if(k) g[2][i][j][k]=1ll*k*(g[0][i][j][k-1]+g[1][i][j][k-1])%Mod;

				ans=(ans+1ll*(1ll*g[0][i][j][k]+g[1][i][j][k]+g[2][i][j][k])%Mod*f[T][i][j][k])%Mod;

			}

	printf("%d",1ll*ans*iMod%Mod);

}

最新文章

  1. C++ 11学习和掌握 ——《深入理解C++ 11：C++11新特性解析和应用》读书笔记(一)
  2. UVA 12549 - 二分图匹配
  3. 在Linux上安装最新版java的JDK
  4. Linux系统安装时分区的选择（推荐）
  5. ios使用webview浏览指定网页
  6. HBase 安装过程记录
  7. Mac OS X 配置 Apache+Mysql+PHP 详细教程
  8. VB 核心编程及通用模块开发 笔记1
  9. Android开源项目（转载）
  10. RHCS集群理论暨最佳实践
  11. laravel扩展包开发步骤总结
  12. C# 文件读写异常“正由另一进程使用，因此该进程无法访问该文件”
  13. 单片机C 语言与汇编语言混合编程
  14. es6 模板字变量和字符串占位符
  15. bootstrap&mdash;&mdash;bootstrap-table（2）
  16. First Scala
  17. 利用redis + lua解决抢红包高并发的问题
  18. taotao商城遇到的问题
  19. 逆向工程vgenerator(三)
  20. 《vue.js快跑》总结：为什么选择VUE

热门文章

  1. MYSQL---外键 primary key 作用
  2. leetcode网解题心得——61. 旋转链表
  3. 解决sublime不能安装packages的问题
  4. WPF TreeGrid Binding 简易实现方式
  5. Dart语言学习(十三) Dart Mixins 实现多继承
  6. Caused by: java.lang.NoClassDefFoundError: org/apache/commons/pool2/impl/GenericObjectPoolConfig
  7. vue element 表单多个验证时，滚动到验证提示的位置
  8. MySQL之可视化软件
  9. 借助工具解决DNS污染
  10. spring boot中不能识别RestController