CF Codeforces Round #560 (Div. 3) May/14/2019

第一天打CF,感觉体验还是很好的,虽然做的时候只出了俩题(毕竟我是newbie)。
原题连接:
CF Codeforces Round #560 (Div. 3) ](https://codeforces.com/contest/1165)

总结:比赛的时候还是要好好读题,本次的时间全浪费在了题目上面。

A题:
最大的坑就是在除的时候你不能把后面的0给去掉,否则就会余数为1,永远得不到结果。

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int main()
{
	int n,x,y;
	char s[200004];
	cin>>n>>x>>y;
	cin>>s;
	int falg=0,pos=0,ans=0;
	for(int i=strlen(s)-1;i>=0;i--,pos++)
	{
		if(pos<y)
		{
			if(s[i]=='1')ans++;
		}
		if(pos==y)
		{
			if(s[i]=='0')ans++;
		}
		if(pos>y&&pos<x)
		{
			if(s[i]=='1')ans++;
		}
		if(pos==x)
		{
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

看懂题目,一次过。

B题:

还是题目的问题,我的坑就是我第一次认为题目的意思是必须第i天做i道题,原来只要能够满足第i天做的题目数大于i就行。

一个sort排序就完事了。

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int main()
{
	int n,x,y;
	int v[200005]={0};
	cin>>n;
	int falg=0,pos=0,ans=0;
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
	}
	sort(v,v+n);
	for(int i=1;i<=n;i++)
	{
		int t=lower_bound(v,v+n,i)-v;
		if(t==n)break;
		else
		{
			ans++;
			v[t]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

C题:

答案字符串要满足的条件是在奇数位置上的字母不能等于它的下一位的字母。所以说当答案数组的个数为偶数时,直接可以把该字符存入答案数组,否则就要判断是不是与前一个字符重复,重复的话就要删掉,ans++,不重复就存进来。最后判断一下,如果我这个答案数组里一个字符没有,输出空行。否则就看一下答案数组里的字符个数,如果是奇数个,就要删掉一次ans++;最终输出ans和字符答案数组就可以了。

#include <iostream>
#include <string.h>
using namespace std;

int main() 
{
	int n,j;
	cin>>n;
	char s[200005];
	char v[200005];
	cin>>s;
	int ans=0,k=0;
	v[k++]=s[0];
	for(int i=1;i<strlen(s);i++)
	{
	   if(k%2==0)
	   {
	       v[k++]=s[i];
	   }
	   else
	   {
	       if(v[k-1]!=s[i])v[k++]=s[i];
	       else ans++;
	   }
	}
	if(k%2==1)
	{
	    k--;
	    ans++;
	}
	cout<<ans<<endl;
	if(k==0)cout<<endl;
	else
	{
	    for(int i=0;i<k;i++)
	    cout<<v[i];
	}
	return 0;
}

D题:

这题补题的时候,又理解错了题目。总体来说就是根据因子推原数。并且有条件的:1.推出来的数必须让数组里的数全是它的因子。2.这个数的所有除了1和它本身的因子全部在这个数组里。知道这两条就可以了(当时忽略了第二条)。这个最小的数肯定是这个数组里最大和最小的乘积。一个sort排序找到这个数,然后直接暴力判断第1个条件。判断第二个条件时,可以把这个数的所有除了它本身和1以外的所有因子个数求出来。然后进行比较就可以了。相等满足条件2,不相等,就为-1。还卡了一个地方就是在求因子个数时,你不能用i*i<=x来找因为i*i可能导致超出long long范围。必须用i<=sqrt(x)。

#include <bits/stdc++.h>
using namespace std;
vector<long long>a;
int main() 
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
    	int n;
    	long long x;
    	scanf("%d",&n);
    	a.clear();
    	for(int i=0;i<n;i++)
    	{
    		scanf("%lld",&x);
    		a.push_back(x);
		}
		sort(a.begin(),a.end());
		long long ans,min;
		min=a[0]*a[n-1];
		int j;
		for(j=0;j<n;j++)
		{
			if(min%a[j]!=0)
			{
				printf("-1\n");
				break;
			}
		}
		if(j!=n)continue;
			ans=0;
			long long i;
			for(i=2;i*i<min;i++)
			{
				if(min%i==0)
				{
					ans+=2;
				}
			}
			if(i*i==min)ans++;
			if(ans!=n)printf("-1\n");
			else printf("%lld\n",min);
	}
	return 0;
}

E题:

也没有技巧吧,在本子上写一写,找一找规律。就会发现,第一个数的基值为1*n,第二个数的基值为2*(n-1)······第n个数为n*(1)。然后把基值乘进a数组里面。接着把a数组从小到大排序,b数组从大到小排序。互相乘起来相加。该题中每次的乘和加操作最好都取余,否则可能导致溢出。

#include <bits/stdc++.h>
#define modd 998244353
using namespace std;
long long a[200005]={0},b[200005]={0};
bool cmp(long long x,long long y)
{
	return x>y;
}
int main()
{
    long long n;
    cin>>n;

    for(long long i=1;i<=n;i++)
    {
    	cin>>a[i];
    	a[i]=a[i]*i*(n-i+1);
	}
	for(long long i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	long long ans=0;
	sort(a+1,a+n+1);
	sort(b+1,b+n+1,cmp);
	for(long long i=1;i<=n;i++)
	{
		ans=(ans+a[i]%modd*b[i]%modd)%modd;
	}
	cout<<ans<<endl;
	return 0;
}

 

上一篇:560.和为k的子数组


下一篇:560 div3 F2. Microtransactions (hard version)