526互联

CF1029

发布时间 2023-10-27 15:34:32作者: jt0007

A Many Equal Substrings

很容易想到要找border，一看数据范围n<=50,kmp,直接暴力找就行了

#include<bits/stdc++.h>
using namespace std;
int n,k;
char s[55]; 
int maxid;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>s[i];
	maxid=n+1;
	for(int i=2;i<=n;i++){
		bool flag=1;
		for(int j=1;j<=n-i+1;j++){
//			if(i==6) cout<<i<<" "<<j<<" "<<s[i]<<" "<<s[j]<<'\n';
			if(s[i+j-1]!=s[j]) flag=0;
		}
		if(flag){
			maxid=i;
			break;
		}
	}
	for(int i=1;i<=k;i++){
		if(i==1){
			for(int j=1;j<=n;j++) cout<<s[j];
		}	
		else {
			for(int j=1+(n-maxid+1);j<=n;j++) cout<<s[j];
		}
	}
	return 0;
}

B Creating the Contest

注意翻译有误，实际题意是在这个子集中每个元素的二倍比其后元素大就行，这样就很简单了，顺着扫一遍就过了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int n;
int a[maxn];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int j=1;
	int ans=0;
	for(int i=1;i<=n;i++){
		j=max(i,j);
		while(a[j+1]<=a[j]*2&&j+1<=n) j++;
		ans=max(j-i+1,ans);
	}
	cout<<ans;
	return 0;
}

C Maximal Intersection

我们枚举不选哪个区间然后 \(O(1)\) 计算不选后的交集就可以了。
如何计算呢，我们考虑找交集的过程，即为左端点取最大值，右端点取最小值，那么直接记录一个前缀交集和一个后缀交集，不就可以计算了吗，于是本题就做完了

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
struct node{
	int ll,lr,rr,rl;
	int l,r;
}p[maxn];
int n;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].l>>p[i].r;
	int nowl=-1,nowr=1e9+5;
	for(int i=1;i<=n;i++){
		p[i].ll=nowl;
		p[i].lr=nowr;
		nowl=max(p[i].l,nowl);
		nowr=min(p[i].r,nowr);
	} 
	nowl=-1,nowr=1e9+5;
	for(int i=n;i;i--){
		p[i].rl=nowl;
		p[i].rr=nowr;
		nowl=max(p[i].l,nowl);
		nowr=min(p[i].r,nowr);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,min(p[i].rr,p[i].lr)-max(p[i].ll,p[i].rl));
	}
	cout<<ans;
	return 0;
}

D Concatenated Multiples

注意这狗题卡常，不能用map只能用unordered_map,然后预处理乘\(10^x\)模数为每个值的个数，然后再暴力统计加去重就可以了

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

const int maxn=2e5+5;
#define int long long
unordered_map<int,int>mp[11];
int a[maxn],mo[maxn],n,k;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline int w(int x){
	return (int)log10(x)+1;
}
int shi[11]={0,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000};
signed main()
{
	n=read();
	k=read();
	for(int i=1;i<=n;i=-~i){
		a[i]=read();
		mo[i]=a[i]%k;
	}
	shi[10]%=k;
	for(int i=1;i<=n;i=-~i){
		for(int j=1;j<=10;j=-~j){
			mp[j][(shi[j])*mo[i]%k]++;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i=-~i){
		int ww=w(a[i]);
		ans+=mp[ww][(k-mo[i])%k];
		if(shi[ww]*mo[i]%k==(k-mo[i])%k) ans--;
	} 
	cout<<ans;
	return 0;
}