当前位置:   article > 正文

Codeforces Round #698 (Div. 2)_codeforces round 698 (div. 2)

codeforces round 698 (div. 2)

A. Nezzar and Colorful Balls

标签:思维

  • 题意:T个样例下,每个样例输入n和n个整数a1—an(保证a1≤a2≤…≤an)。代表n个球和球上的数字。
    给每个球上不同的色,要求同一种颜色的球上的数字严格递增,求:最少需要的颜色个数。
  • 思路:因为序列ai是非递减的,值相等的球必须涂上不同的颜色,找出其中相等元素的最大值即是答案。
  • 代码
#include<bits/stdc++.h>
#define ll long long
#define LL unsigned long long
#define up_b upper_bound
#define low_b lower_bound
#define all(a) begin(a),end(a)
#define mem(a,n) memset(a,n,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
priority_queue <int,vector<int>,less<int> > QM;
const int INF= 0x3f3f3f3f;
const int maxn= 2e5+5;

int a[110];
void solve()
{
	int n;cin>>n;
	a[0]=-INF;
	int sum=0,ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]==a[i-1])
			sum++;
		else
			ans=max(ans,sum),sum=1;
	}
	ans = max(ans,sum);
	cout<<ans<<endl;
}
int main()
{
	IOS;
	int t;cin>>t;
	while(t--){ solve(); }
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

B. Nezzar and Lucky Number

标签:数论

  • 题意:T个样例下,每个样例输入n和d(1≤d≤9),接下来是a1—an。定义:某个数的十进制下至少有一位是d,则称它为幸运数字。
    问:对于所有输入的所有ai(1≤i≤n),判断它是否能由任意数量个幸运数字相加构成。
  • 思路:若ai <= d×10,暴力判断,想怎么来怎么来。关键是ai > d×10,举例,d为7。
    1、ai∈[ 71,79 ],显然直接就是幸运数字。
    2、ai∈[ 80,max),均可由区间[ 71,79 ]内的幸运数字加上一个7的倍数来构成。

n = (d×10+k) + d×m → n = (d×10+d×m-d×m%10)+(d×m%10 + k)
此处的k∈[1,9],且m可取任意正整数,显然这个等式恒成立
证明:因为余数n%d ∈ [1,d-1],此时这个余数就对应式子中的((d×m)%10+k),而n的十位及以上的都可由(d×10+d×m-d×m%10)来消去。

  • 代码
#include<bits/stdc++.h>
#define ll long long
#define LL unsigned long long
#define up_b upper_bound
#define low_b lower_bound
#define all(a) begin(a),end(a)
#define mem(a,n) memset(a,n,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
priority_queue <int,vector<int>,less<int> > QM;
const int INF= 0x3f3f3f3f;
const int maxn= 2e5+5;

int n,d,a[maxn];
bool check(int x)
{
	if(x>=10*d)	return 1;
	
	if(x%10==0)
		x-=d;
	while(x%10!=0 && x>=d)
		x-=d;
	if(x%10==0)	return 1;
	return 0;
}
void solve()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(check(a[i]))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
}
int main()
{
	IOS;
	int t;cin>>t;
	while(t--){ solve(); }
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

C. Nezzar and Symmetric Array

标签:排序 数学

  • 题意:T个样例下,每个样例输入n和2n个整数(d【1】—d【2n】)。(1≤n≤1e5),(0≤di≤1e12)
    原序列a【1】—a【2n】,每个数都不等,且每个ai都对应存在一个j (1 ≤ j ≤ 2n),a【i】= - a【j】。
    di则表示在原序列中,ai与其他所有元素差值的绝对值总合。
    问:是否存在这样一个原序列ai,每一位上与其他元素差值的绝对值总和等于给定的di序列,存在输出yes,反正则输出no。
  • 思路:显然原序列是ai,-ai,一对一对存在的,且序列中不存在相等的元素。
    将ai排个序,a1—an为正数且递增,an+1—a2n分别为对应的相反数。
    根据di的定义列出di的公式,再根据ai序列的特征可得出如下结果:
    假定现在n=6,升序排列后的di如下

d1=d2 = 2×(a1+a2+a3+a4+a5+a6)
d3=d4 = 2×(a2+a2+a3+a4+a5+a6)
d5=d6 = 2×(a3+a3+a3+a4+a5+a6)
d7=d8 = 2×(a4+a4+a4+a4+a5+a6)
d9=d10 = 2×(a5+a5+a5+a5+a5+a6)
d11=d12 = 2×(a6+a6+a6+a6+a6+a6)

结果已经出来了,根据di的特征可知,特判di必定是两个两个相等的偶数。倒序依次推出a6—a1即可,期间特判ai必须为整数且大于0

  • 代码
#include<bits/stdc++.h>
#define ll long long
#define LL unsigned long long
#define up_b upper_bound
#define low_b lower_bound
#define all(a) begin(a),end(a)
#define mem(a,n) memset(a,n,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
priority_queue <int,vector<int>,less<int> > QM;
const int INF= 0x3f3f3f3f;
const int maxn= 2e5+5;

ll d[maxn],a[maxn],Q[maxn];
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=2*n;i++)	cin>>d[i];
	sort(d+1,d+1+2*n);
	
	ll sum=0;
	for(ll i=n;i>=1;i--)
	{
		if(d[i*2]!=d[i*2-1] || d[i*2]%2==1)
		{
			cout<<"NO"<<endl;
			return ;
		}
		Q[i] = d[i*2]/2;
		if((Q[i]-sum)%i!=0 || Q[i]<=sum)
		{
			cout<<"NO"<<endl;
			return ;
		}
		a[i] = (Q[i]-sum)/i;
		if(a[i]>=a[i+1] && i!=n)
		{
			cout<<"NO"<<endl;
			return ;
		}
		sum += a[i];
	}
	cout<<"YES"<<endl;
}
int main()
{
	IOS;
	int t;cin>>t;
	while(t--){ solve(); }
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/75415
推荐阅读
相关标签
  

闽ICP备14008679号