站长圈

codeforces round #713 (div. 3)

  • 计算机/互联网
  • 来源:站长圈
  • 编辑:站长圈
  • 时间:2021-06-01 10:46
  • 阅读:371

C.回文串处理:https://codeforces.com/contest/1512/problem/C

题意

给一个字符串s和两个数字a和b。s由‘0’,‘1’和‘?’组成,要求将s中的‘?’替换成‘1’或者‘0’,同时要求s中的‘0’的个数严格等于a,s中国‘1’的个数严格等于b,请问是否存在这样的回文串s,如果存在就输出处理好的回文串s,不存在就输出-1。

思路

双指针两头遍历,然后判断是不是回文串已经a和b是否用完。

代码

#include <bits/stdc++.h>using namespace std;int main(){
	int t, n, k, a, b, l; cin>>t;
	while(t--){
		cin>>a>>b;
		string str; cin>>str;
		n = a+b;
		for(int i=0; i<n; i++){
  			//如果两边都是'?'就不变
     		//如果一边是'?'就变成另一边的字符
       		//这样字符串中就没有不对称的'?'了
			if(str[i]=='?')str[i] = str[n-i-1];
		}
		//对a和b减去字符串中已有的'0'和'1'的个数
		a -= count(str.begin(), str.end(), '0');
		b -= count(str.begin(), str.end(), '1');
		for(int i=0; i<=n/2; i++){
  			//如果有对称的'?'就用剩有多于1个的'0'或者'1'来代替
			if(i!=n-i-1 && str[i]=='?'){
				if(a>1)str[i]=str[n-i-1]='0', a-=2;
				else if(b>1)str[i]=str[n-i-1]='1', b-=2;
			}
   			//如果是奇数长度,那么正中间如果是'?',就用剩的'0'或者'1'来代替   			
			else if(str[i]=='?'){
				if(a)str[i]='0',a--;
				else str[i]='1',b--;
			}
		}
		
		string vec=str;
  		//检验是否是回文串
		reverse(vec.begin(), vec.end());
  		//检验a和b是否恰好用完
		if(vec==str && a==0 && b==0)cout<<str<<'n';
		else cout<<"-1"<<endl;
	}}

全选代码

复制

E.找连续正整数序列:https://codeforces.com/contest/1512/problem/E

题意

给四个数n,l,r和s。n表示有一个正整数序列从1到n,问这个序列(无序的)中的下标闭区间[l,r]的值的和能不能等于s。如果存在这样的闭区间满足就输出这个序列,没有就输出-1。

思路

考虑1到n这样一个数集,找一个大小为r-l+1的子集使得子集元素和为s,设len=r-l+1,可以抽象为有len个箱子,往里面一共放入s个小球且每个箱子放的小球数不一样。假设第i个箱子放i个小球,那么一共可以放k = len*(len+1)/2个小球。根据抽屉原理,这时第i个箱子最少要放(s-k)/len+i个小球,同时如果(s-k)%len!=0,那么需要在后面的箱子里面补小球(不在前面补是避免后面的箱子和前面的箱子小球数相同)。这时需要补m=(s-k)%len个小球,就在len-m+1的位置开始补。

代码

#include <bits/stdc++.h>using namespace std;const int N = 510;int tt,n,l,r,s;int vis[N];int main(){
    scanf("%d",&tt);
    while(tt--)
	{
		scanf("%d%d%d%d",&n,&l,&r,&s);
		memset(vis,0,sizeof vis);
		
		int len = r-l+1,x = len*(len+1)/2;
		if(s<len*(len+1)/2||s>(n+n-len+1)*len/2) cout<<-1<<endl;
		else
		{
			int k = s-x;
			for(int i=1;i<=len;i++)
			{
				//抽屉原理
    			int h = k/len+i;
       			//补小球
				if(k%len&&k%len>len-i) h++;
				vis[h] = 1;
			}
			int t = 1,f = 1;
			for(int i=1;i<=n;i++)
			{
				if(i<l||i>r)
				{
					while(f<=n&&vis[f]==1) f++;
					printf("%d ",f++);
				}
				else
				{
					while(t<=n&&vis[t]==0) t++;
					printf("%d ",t++);
				}
			}
			puts("");
		}
		
	}
    return 0;}

全选代码

复制

F.买电脑:https://codeforces.com/contest/1512/problem/F

题意

给两个数n和c,两个数组a[n],b[n-1]。c表示电脑的价格,a[i]表示在第i个职位一天可以赚多少钱,b[i]表示想要去第i+1个职位需要花的用来学习的钱。求最少多少天可以攒够c块钱去买电脑。

思路

模拟+暴力。从第1个职位开始遍历,用rem存手上剩下的钱,p存天数,ans存答案。在第i个职位先判断钱够不够买电脑,如果够的话算一下ans=min(ans,p),如果不够的话假如我不学习,之后一直在这个职位需要多少天才能买到电脑,也就是ans = min(ans,p+(c-rem)/a[i]+((c-rem)%a[i]!=0))。如果已经到了第n个职位就可以退出循环了,因为这里上面一直在这个职位这一步处理了。接下来模拟,如果剩的钱大于学习开销,就学习然后去下一个职位,如果不够就计算需要打工多少天才够,也就是p += (b[i]-rem)/a[i]+((b[i]-rem)%a[i]!=0),然后再更新剩的钱。

代码

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 200010;LL ans,t,p,rem,a[N],b[N],n,c;int main(){
	cin>>t;
    while(t--)
    {
    	cin>>n>>c;
    	p = -1,rem = 0,ans = 1e9+10;
    	for(int i=1;i<=n;i++) scanf("%d",a+i);
    	for(int i=1;i<n;i++) scanf("%d",b+i);
    	int k = 1;
    	for(int i=1;i<=n;i++)
    	{
    		p++;
    		if(c<=rem) ans = min(ans,p);
    		else ans = min(ans,p+(c-rem)/a[i]+((c-rem)%a[i]!=0));
    		
    		if(i==n) break;
    		
    		if(rem>=b[i])
    		{
    			rem-=b[i];
    			continue;
			}
    		
    		p += (b[i]-rem)/a[i]+((b[i]-rem)%a[i]!=0);
    		
    		if((b[i]-rem)%a[i]!=0) rem = a[i]-(b[i]-rem)%a[i];
    		else rem = 0;
		}
    	cout<<ans<<endl;
	}
    return 0;}

全选代码

复制

G.因数和:https://codeforces.com/contest/1512/problem/G

题意

给一个数c,使数n满足n所有因数的和等于c,问这样的n最小是多少。

思路

打表。类似于筛质数,开一个数组yz[],将每个数的对应倍数位置加上这个数,等循环到这个位置的时候恰好它存的数就是这个位置所有因数的和,然后用ans[]数组来把下标为因数和的位置存为这个数。

代码

#include <bits/stdc++.h>using namespace std;const int N=1e7;int t, n, yz[N], ans[N];int main() {
	for(int i=1; i<=N; ++i) {
		for(int j=i; j<=N; j+=i)
			yz[j]+=i;
		if(yz[i]<=N&&!ans[yz[i]])
			ans[yz[i]]=i;
	} cin>>t;
	while(t--) {
		cin>>n;
		cout<<(ans[n]==0?-1:ans[n])<<endl;
	} return 0;}


全部评论(0)
资讯详情页最新发布上方横幅
推荐阅读
  • ripro主题Logo加闪光效果
  • ripro主题Logo加闪光效果
  • 最近看到很多的网站LOGO都有个闪光的效果,怎么做的呢?小编也研究了下,适合所有网站,下面把代码分享给大家/*ZZHUTI网站LOGO 流光*/.logo-wrapper {    position: relative;    font-size:2em;    font-
  • 计算机/互联网
  • 来源:站长圈
  • 编辑:站长圈
  • 时间:2021-08-10 14:34
  • 阅读:640
  • 关于windows server2008r2激活密钥及激活的方法
  • 关于windows server2008r2激活密钥及激活的方法
  • Server2008r2激活密钥分两种,分别是server2008永久密钥和kms安装密钥其中server2008永久密钥有激活次数限制,可能失效。kms激活密钥是微软官方提供,没有激活次数限制,永久有效我选择没有限制次数的方法,即使用kms方式,我安装的是datacenter,激活时选择第五个windowsserver2008/R2批量授权版KMS安装密钥1、WindowsServer2008R2WindowsServe
  • 计算机/互联网
  • 来源:站长圈
  • 编辑:站长圈
  • 时间:2021-08-06 11:51
  • 阅读:595
  • AList 基于阿里云盘的个人网盘目录列表程序
  • AList 基于阿里云盘的个人网盘目录列表程序
  • 今天再给大家推荐一个利用阿里云盘来搭建的个人分享网盘程序!相对于Teambition 主要是利用Cookie模拟用户登陆,然后调用相关接口。本文代码使用的是标准的OAuth2实现接口的调用,相对来说更稳定一些!开源仓库原作者:https://github.com/Xhofe/alist下面的项目是博主为了部署方便整合了一个仓库,且支持了Docker部署!https://github.com/malaohu/alist-onec
  • 计算机/互联网
  • 来源:站长圈
  • 编辑:站长圈
  • 时间:2021-06-01 14:46
  • 阅读:862
  • php在线打包工具源码
  • php在线打包工具源码
  • 支持PHP5.6-PHP7。说明:点开始打包,之后,就是耐心等待打包完成了,根据网站文件多少,需要的时间可能会很长。打包完成之后,压缩包会存放在要打包的站点目录下,以打包时间+不定长随机字符串+jackfeng.zip这样命名,请登陆ftp后下载。
  • 计算机/互联网
  • 来源:站长圈
  • 编辑:站长圈
  • 时间:2021-06-01 14:44
  • 阅读:460
底部广告
网站首页  |   关于我们  |   广告合作  |   联系我们  |   隐私条款  |   免责声明  |   网站地图
CopyRight 2014-2024 站长圈 | ICP证:粤ICP备16065033号-15
联系客服
技术咨询 售前小郑 客服明明 联系客服
0769-33314958
手机版

扫一扫进手机版
返回顶部