首页 > 其他分享 >CF1105

CF1105

时间:2024-11-06 12:31:02浏览次数:1  
标签:int len 倍数 long 长度 CF1105 MOD

好想睡觉……

A.Salem and Sticks

原题小链接CF

题目大意:

给定长度为n的序列a(1<=n<=1000,1<=a[i]<=100),要求给出一个整数t,使得∑max(abs(a[i]-t)-1,0)最小。

解题思路:

下意识地就开始推,哪怕看到了数据范围还是想着能不能O(n)给解决。但忐忑地翻了下题解后发现这题其实就是一个纯暴力,反正t一定1<=t<=100,直接暴力枚举取最优解就完事了。

不可爱的小代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int n;
int a[N];
int res,sum=0x3f3f3f3f3f3f3f3f;

int _abs(int x)
{
	if (x>0) return x;
	return -x;
}
signed main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (int t=1;t<=100;t++)
	{
		int sm=0;
		for (int i=1;i<=n;i++) sm+=max(_abs(a[i]-t)-1,1LL*0);
		if (sm<sum) res=t,sum=sm;
	}
	printf("%lld %lld",res,sum);
	return 0;
}

B.Zuhair ans Strings

原题小链接CF

题目大意:

给定长度为n(1<=n<=2e5)的字符串s,给出k,求字符串s中最多的长度为k的互不重叠子串的个数,使得所有子串由相同的字母组成。

解题思路:

一眼出。遍历一遍字符串,记录连续相同字符的长度,若长度达到k,那么就记录一下;若字符不相同了,那么长度就归零。怎么统计所有合法子串的最优解呢?用桶数组记录答案,每一个合法子串都放入相应的桶中,最后遍历一遍桶数组,最大值就是答案了。

简简单单的小代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,k;
string s;
int bx[30];
int ans;

signed main()
{
	cin>>n>>k>>s;
	int len=0;
	for (int i=0;i<n;i++)
	{
		if (i>0&&s[i]!=s[i-1]) len=0;
		len++;
		if (len>=k)
		{
			bx[(int)(s[i]-'a')]++;
			len=0;
		}
	}
	for (int i=0;i<26;i++) ans=max(bx[i],ans);
	cout<<ans;
	return 0;
}

C.Ayoub and Lost Array

题目小链接CF

题目大意:

构造一个长度为n(1<=n<=2e5)的序列a,使得序列中∀a[i]∈[l,r],求使序列和为3的倍数的方案数(对1e9+7取模)

解题思路:

第一眼:好难好难

第二眼:好像可以从“3的倍数”下手

第三眼:秒了秒了

若是没有“3的倍数”的限制,我们可以直接做,但这题偏偏有这个限制。那么怎么办呢?我们可以想到:3的倍数可以由另两个3的倍数相加得来,也可以由3的倍数+1和3的倍数+2得来……于是乎,我们可以想到dp转移答案。

设dp[i][j]表示序列长度为i,序列和%3为j的方案构造数。通过余数加法法则可以直接转移。

转移方程如下:
f[i][0]=(f[i-1][1]*a2%MOD+f[i-1][2]*a1%MOD+f[i-1][0]*a0%MOD)%MOD;
f[i][1]=(f[i-1][0]*a1%MOD+f[i-1][1]*a0%MOD+f[i-1][2]*a2%MOD)%MOD;
f[i][2]=(f[i-1][0]*a2%MOD+f[i-1][1]*a1%MOD+f[i-1][2]*a0%MOD)%MOD;

然后就可以写

快乐的小代码啦

#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int MOD=1e9+7;
int n,l,r;
int f[N][3];
int a0,a1,a2;

signed main()
{
	scanf("%lld%lld%lld",&n,&l,&r);
	f[1][0]=a0=(r/3*3-(l+2)/3*3)/3+1;
	f[1][1]=a1=((r+1)/3*3-(l+3)/3*3)/3+1;
	f[1][2]=a2=r-l+1-a0-a1;
	for (int i=2;i<=n;i++)
	{
		f[i][0]=(f[i-1][1]*a2%MOD+f[i-1][2]*a1%MOD+f[i-1][0]*a0%MOD)%MOD;
		f[i][1]=(f[i-1][0]*a1%MOD+f[i-1][1]*a0%MOD+f[i-1][2]*a2%MOD)%MOD;
		f[i][2]=(f[i-1][0]*a2%MOD+f[i-1][1]*a1%MOD+f[i-1][2]*a0%MOD)%MOD;
	}
	printf("%lld",f[n][0]);
	return 0;
}

D.Kilani and the Game

题目大意:

标签:int,len,倍数,long,长度,CF1105,MOD
From: https://www.cnblogs.com/Myyy-L/p/18529734

相关文章