cf_global_round7

Codeforces Global Round 7

A

题意：寻找一个n位数的s,并且s不难被其任何一位数整除，如果不存在输出-1（只有n=1时才不存在）比如239不能被2，或3，或9整除，则当n=3，时239符合。

题解：
大佬教我的方法，if((n-1)%3==0) 输出n-2个2，然后两个3
否则直接输出n-1个2和3
emmmmmm，一开始不明白，之后发现就是一种凑质数的方法。
然后想出了233333333333333，首先输出一个2然后输出n-1个3，大哥NB
我发现277777777777777777好像也可以。

代码：

#include <iostream>
using namespace std;
int main()
{
	int n,t;
	cin>>t;
	while(t--){
		cin>>n;
		if(n==1) {
		puts("-1");continue;
		}
		cout<<2;
		for(int i=1;i<=n-1;i++)
			cout<<7;
	}
	return 0;
}

B

题意：已知规则𝑎={0,1,2,0,3} , 𝑏={0−0,1−0,2−1,0−2,3−2}={0,1,1,−2,1}，𝑏𝑖=𝑎𝑖−𝑥𝑖 ，𝑥𝑖=𝑚𝑎𝑥(0,𝑎1,…,𝑎𝑖−1) ，bi为每次ai-xi，xi为a的前i-1项的最大值，现告诉你bi，让你还原ai

思路：设前最大项m=0，易知a[1]=b[1],a[2]=b[2]+m 然后m=max(m,a[2])
,直到最后一项就还原了

代码:

#include<iostream>
using namespace std;
const int maxn=2e5+10;
int a[maxn],b[maxn];
int main()
{
	int n,m=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>b[i];
	a[1]=b[1];
	m = a[1];
	for(int i=2;i<=n;i++)
	{
		a[i]=b[i]+m;
		m = max(m,a[i]);
	}
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	return 0;
}

C

题意：输入个n，和k，然后给1～n的随机排列，这些排列可以按照区间分成k个，问这些区间每段的最大和是多少，还有能构成最大和的划分区间方式有多少种？输出最大和，和划分方式。

思路：
比如：7 3
2 7 3 1 5 4 6
下标为 1 2 3 4 5 6 7
最大和就是前k个数
可以划分为区间【1，2 】【3，5】【6，7】或【1，2】【3，6】【7，7】或【1，3】【4，5】【6，7】或【1，3】【4，6】【7，7】或【1，4】【5，5】【6，7】或【1，4】【5，6】【7，7】，易知划分方式就是前k个数位置差的乘积，

注意！！！：取余仅对第二个数取余，并且得开long long
代码：

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll n,k,ans=1,sum,t;
vector<ll> v;
ll mod=998244353;
int main()
{
	cin>>n>>k;
	ll flag=n-k;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		if(t>flag){
			sum+=t;
			v.push_back(i);
		}
	}
	for(int i=1;i<v.size();i++)
		ans = ans*(v[i]-v[i-1])%mod;
	cout<<sum<<" "<<ans<<endl;
	return 0;
}

D1

~~马拉车？额~~ 暴力吧

题意：给你个字符串，问从两边开始的最长回文字符子串，思路，如果两端相等，就–，直到不相等，在中间寻找回文串，加上即可。

题解：感人大暴力
回顾几个知识点吧：关于string的
string s,temp;
temp = s.substr(pos,len) ;表示从pos位置开始向后截取len长度的字符子串，
reverse(s.begin(),s.end())，表示反转整个字符串。
reverse(s+0,s+6) 表示反转s[0] ~ s[5] 注意左闭右开，然后就行了

代码：

#include<iostream>
#include<algorithm>
using namespace std;
string s,str,tl,tr,temp;
string ad1,ad2,adl,adr;
int l,r;
void pdl()
{
	for(int i=1;i<=r-l;i++)
	{
		tl=s.substr(l,i);
		str=tl;
		reverse(str.begin(),str.end());
		if(tl==str)
			adl=tl;
	}
	return;
}
void pdr()
{
	temp=s;
	reverse(temp.begin(),temp.end());
	for(int i=1;i<=r-l;i++)
	{
		tr=temp.substr(l,i);
		str=tr;
		reverse(str.begin(),str.end());
		if(tr==str)
			adr=tr;
	}
	return;	
}
int main()
{
	int t,flag=0;
	cin>>t;
	while(t--){
		flag=0;
		cin>>s;
		if(s.size()==1){
			cout<<s<<endl;
			continue;
		}
		l=0,r=s.size()-1;
		if(s[l]==s[r]){
			while(s[l]==s[r]){
				l++;r--;
				if(l==r || l>r){
					cout<<s<<endl;
					flag=1;
					break;
				}
			}
			if(flag==0){
				ad1 = s.substr(0,l);
				ad2 = ad1;
				reverse(ad2.begin(),ad2.end());
				pdl();pdr();
				if(adl.size()>=adr.size()){
					str = ad1 + adl + ad2;
				}else
					str = ad1 + adr + ad2;
				cout<<str<<endl;				
			}
		}else{
			if(flag==0){
				pdl();pdr();
				if(adl.size()>=adr.size())
					cout<<adl<<endl;
				else
					cout<<adr<<endl;				
			}
		}
	}
	return 0;
}

D2

显然暴力过不了了，补马拉车吧……

加油！！！