首页 > 其他分享 >2024 洛谷月赛(柒)

2024 洛谷月赛(柒)

时间:2024-07-21 21:09:25浏览次数:15  
标签:洛谷 int 反转 scanf long 2024 LL define

月赛

GGrun %%%

T1 在相思树下 I

签到题QWQ,找规律易得。证明未知

每次一定会删掉一半的数,所以第 \(i\) 次操作都会提供一个 \(1<<i-1\) 的贡献。

这个贡献就是下一次会往后跳多少个位置。

假如一开始确定留下的是第一个,那删偶数不会有影响,而删奇数需要往后跳。

code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int t;
LL n,k;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&k)	;
		LL ans=1;
		for(int i=0;i<k;i++)
		{
			int x; scanf("%d",&x);
			if(x==1) ans+=(1ll<<i);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

T2 01-string

一眼 dp,可以开 \(f[i][4]\) 表示完成前 \(i\) 位的代价,\(4\) 表示反转,一,零覆盖,不动四种操作,记录上一次的操作。

注意如果是 \(0,1\),虽然可能不需要操作,但是由于区间连续的原因,可能进行覆盖操作更优,所以也要更新。

代码在这,但是假了。

假code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5+5;
int T;
int n,f[N][4];
char s[N],t[N];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(f,0x3f,sizeof(f));
		scanf("%s%s",(s+1),(t+1));
		n=strlen(s+1); f[0][0]=0;
		for(int g=1;g<=3;g++)
		for(int i=1;i<=n;i++)
		{
			if(s[i]==t[i]) f[i][0]=min({f[i-1][0],f[i-1][1],f[i-1][2],f[i-1][3],f[i][0]});
			else f[i][3]=min({f[i-1][0]+1,f[i-1][1]+1,f[i-1][2]+1,f[i-1][3],f[i-1][3]});
			if(t[i]=='1') f[i][1]=min({f[i-1][0]+1,f[i-1][1],f[i-1][2]+1,f[i-1][3]+1,f[i-1][1]});
			if(t[i]=='0') f[i][2]=min({f[i-1][0]+1,f[i-1][1]+1,f[i-1][2],f[i-1][3]+1,f[i-1][2]});
		}
		printf("%d\n",min({f[n][0],f[n][1],f[n][2],f[n][3]}));
	}
	return 0;
}

假好像不那么明显,因为找了好久都没有找到反例。

我们进行的线性 dp,它不会考虑操作区间交叉的情况,也就是一个字符只会被操作一次。

而由于反转操作的存在,是有一些情况必须先进行反转然后再统一覆盖的,并且一定是先反转再覆盖。

因为如果先覆盖再反转,可以用反转后再覆盖乘相反的代替,这两种是等价的。

所以既然会出现两种操作同时存在,并且是一种反转一种覆盖,那么我们可以把反转单开出来记。

分讨情况暴增。

code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5+5;
int T;
int n,f[N][3][2];
char s[N],t[N];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(f,0x3f,sizeof(f));
		scanf("%s%s",(s+1),(t+1));
		n=strlen(s+1);
		f[0][2][0]=0;
		for(int i=1;i<=n;i++)
		{
			if(s[i]==t[i])
			{
				f[i][2][0]=min({f[i-1][2][0],f[i-1][0][0],f[i-1][1][0],f[i-1][2][1],f[i-1][0][1],f[i-1][1][1]});
				if(s[i]=='0')
					f[i][0][0]=min({f[i-1][2][0]+1,f[i-1][0][0],f[i-1][1][0]+1,f[i-1][2][1]+1,f[i-1][0][1],f[i-1][1][1]+1});
				else
					f[i][1][0]=min({f[i-1][2][0]+1,f[i-1][0][0]+1,f[i-1][1][0],f[i-1][2][1]+1,f[i-1][0][1]+1,f[i-1][1][1]});	
			}
			else
			{
				if(s[i]=='0')
					f[i][1][0]=min({f[i-1][2][0]+1,f[i-1][0][0]+1,f[i-1][1][0],f[i-1][2][1]+1,f[i-1][0][1]+1,f[i-1][1][1]});
				else
					f[i][0][0]=min({f[i-1][2][0]+1,f[i-1][0][0],f[i-1][1][0]+1,f[i-1][2][1]+1,f[i-1][0][1],f[i-1][1][1]+1});	
			}
			if(s[i]!=t[i])
			{
				f[i][2][1]=min({f[i-1][2][0]+1,f[i-1][0][0]+1,f[i-1][1][0]+1,f[i-1][2][1],f[i-1][0][1],f[i-1][1][1]});
				if(s[i]=='0')
					f[i][0][1]=min({f[i-1][2][0]+2,f[i-1][0][0]+1,f[i-1][1][0]+2,f[i-1][2][1]+1,f[i-1][0][1],f[i-1][1][1]+1});
				else
					f[i][1][1]=min({f[i-1][2][0]+2,f[i-1][0][0]+2,f[i-1][1][0]+1,f[i-1][2][1]+1,f[i-1][0][1]+1,f[i-1][1][1]});	
			}
			else
			{
				if(s[i]=='0')
					f[i][1][1]=min({f[i-1][2][0]+2,f[i-1][0][0]+2,f[i-1][1][0]+1,f[i-1][2][1]+1,f[i-1][0][1]+1,f[i-1][1][1]});
				else
					f[i][0][1]=min({f[i-1][2][0]+2,f[i-1][0][0]+1,f[i-1][1][0]+2,f[i-1][2][1]+1,f[i-1][0][1],f[i-1][1][1]+1});		
			}
		}
		printf("%d\n",min({f[n][0][0],f[n][0][1],f[n][1][1],f[n][1][0],f[n][2][0],f[n][2][1]}));
	}
	return 0;
}

T3 在相思树下 II

尝试用英文写未果

其实还算好想的一道题,我们用近似线段树的方式递归,然后统计限制就好了。

容易看出 \(max\) 和 \(min\) 其实就是规定至少有多少个人比他小/大,

因此我们在统计的时候可以记录每个点到达这一高度的限制,由于我们可以随意安排人的位置,所以最终取这一棵子树的最小限制作为递归的结果。

最终我们的得到的是一个范围,即如果第 \(i\) 个人想到达 \(d\) 层所在区间应是 \([s[i].fi+1,num-s[i].se]\),把合法的修改成 \(1\),用差分数组维护区间修改。

code
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e6+5,L = __lg(N)+5;
int n,m,num,c[N],f[L][N];
pair<int,int> s[N];
pair<int,int> dfs(int k,int l,int r,int d)
{
	if(l==r) return {0,0};
	int mid=l+r>>1;
	pair<int,int> sl=dfs(k<<1,l,mid,d-1),sr=dfs(k<<1|1,mid+1,r,d-1),ans={num,num};
	if(c[k]==1)
	{
		for(int i=l;i<=mid;i++) s[i].fi+=sr.fi+1;
		for(int i=mid+1;i<=r;i++) s[i].fi+=sl.fi+1;
	}
	else 
	{
		for(int i=l;i<=mid;i++) s[i].se+=sr.se+1;
		for(int i=mid+1;i<=r;i++) s[i].se+=sl.se+1;
	}
	for(int i=l;i<=r;i++)
	{
		ans.fi=min(s[i].fi,ans.fi); ans.se=min(ans.se,s[i].se);
		++f[d][s[i].fi+1]; --f[d][num-s[i].se+1];
	}
	return ans;																									
}
int main()
{
	scanf("%d%d",&n,&m); num=1<<n;
	for(int i=1;i<num;i++) scanf("%d",&c[i]);
	dfs(1,1,num,n);	f[0][0]=1;
	for(int i=0;i<=n;i++) for(int j=1;j<=num;j++) f[i][j]+=f[i][j-1];
	while(m--)
	{
		int x,y; scanf("%d%d",&x,&y);
		printf("%s\n",f[y-1][x]>0?"Yes":"No");
	}
	return 0;
}

T4 落月摇情

大力分讨,咕咕咕。。。

标签:洛谷,int,反转,scanf,long,2024,LL,define
From: https://www.cnblogs.com/ppllxx-9G/p/18301347

相关文章

  • 2024暑假总结1
    总结记得26号来见到了一些新同学,还考了一场试,题目都很基础,但是我清楚地记得我把图论大部分内容都忘了,第二题计数题也没调出来。这次经历让我深深感受到半年不碰OI再次上手时原来如此乏力,脑海中搜索出的知识结构图也只有空荡荡的框架而无多少内容。看到一个知识只是粗略知道它的原......
  • A Bit More Common (2024牛客多校1 B)
    进入博客阅读体验更佳:ABitMoreCommon(2024牛客多校1B)|付诺の小站(funuo0728.github.io)ABitMoreCommon题目大意给定两个整数n和m(1\len,m\le5000),在所有长度为n且元素取值范围为[0,2^m)的序列中,计算存在两个合法子序列的序列个数。其中,合法子序列是指......
  • SMU 2024 ptlks的周报Week 9 (7.15-7.21)
    这周学了启发式合并,prim算法,对图有了进一步的理解。树题意:给一棵根为1的有根树,点i具有一个权值\(A_i\)定义一个点对的值f(u,v)=max(\(A_u\),\(A_v\))×∣\(A_u\)-\(A_v\)∣。你需要对于每个节点i,计算\(ans_i=\displaystyle\sum_{u,v∈subtree(i)}f(u,v)\),其中subtre......
  • 2024牛客多校1
    2024牛客多校12024年第一场多校赛,打的很一般,多校之前vp的几场多校成绩还不错,一场比赛直接打回原形。赛时队友做的签到题C、H,吃了两发罚时,我自己推的A,出的很快,可惜没注意取模,吃了发罚时,长个记性吧。A给定n,m,p,问长度为n,并且都由小于\(2^m\)的数组成,存在一个子序列的按位且等......
  • NOI 2024
    省流:100+264+180=544,rk45极限进队。赛前状态感觉还行,gzy天天在模拟赛里爆标,给他磕头了。day0开幕式。很想喷【】【】【】【】【】【】,算了不喷了。笔试,开场10s大家就开始笑,笔试把答案发下来了。”我们题目的配置出了一点问题,大家稍安勿躁“。致敬传奇出题人。推迟15......
  • 2024大模型安全实践白皮书(可下载)
    以上是资料简介和目录,如需下载,请前往星球获取:https://t.zsxq.com/qd9rs......
  • vue3 ts 项目增加eslint插件实现命令行报错提示和vscode 报错提示,eslint 最新版本9.x
    快速开始安装eslintyarnaddeslint-D然后运行初始化eslintnpxeslint--init接着上面命令会自动生成一个新文件eslint.config.jseslint.config.jsimportglobalsfrom"globals";importpluginJsfrom"@eslint/js";importtseslintfrom"typescript-eslint......
  • 2024.7.20
    模拟赛昨天的题解还在咕。。。今天的又来了。。。T1SimpleMath2签到题,推一推式子就好了。\[\lfloor{\frac{a^b}{c}}\rfloor\modc=x\]\[\lfloor{\frac{a^b}{c}}\rfloor=k\timesc+x\]\[\frac{a^b-(a^b\modc)}{c}=k\timesc+x\]\[a^b-(a^b\modc)=k......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......