Codeforces Round #762 (Div. 3) A-C题解

发布于 2021-12-21  161 次阅读


A - A. Square String?

题目描述:

A string is called square if it is some string written twice in a row. For example, the strings "aa", "abcabc", "abab" and "baabaa" are square. But the strings "aaa", "abaaab" and "abcdabc" are not square.
For a given string s
s determine if it is square.

题意理解:

题目理解起来就是判断该字符串是否可以分割成两个一模一样的字符子串,因为一个字符只能分到一个子串中,所以每个字符就只能用一遍,所以,就可以确定原字符串的长度为奇数时 一定无法被分为两个一样的子串, 然后当长度为偶数时,再将其从中破开,用双指正来判断子串是否相同即可;

#include<iostream>
#include<string.h>
using namespace std;
char s[10000];
int main()
{
	
	int t;
	cin>>t;
	while(t--)
	{
	cin>>s;
	int n=strlen(s);
	int flag=0;
	if(n%2!=0)
	{
	cout<<"NO\n";
	flag=1; 
}	else
	{
		n/=2;
		n--;
		for(int i=0;i<=n;i++)
		{
			if(s[i]!=s[i+n+1])
			{
				flag=1;
				cout<<"NO\n";
				break;
			}
		}
	}	
	if(!flag)cout<<"YES\n";
	}
	
	return 0;
 } 

B. Squares and Cubes

题目描述:

Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: 1, 4, 8, 9, ....

For a given number nn, count the number of integers from 11 to nn that Polycarp likes. In other words, find the number of such xx that xx is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).

题意理解及思路:

题意很简单,就是找出1-n之间的平方数与立方数的个数。因为n的最大值为1e9,所以我们需要预处理一下,将1-1e9的所有平方数与立方数找到并存在一个数组内,将其排序,使用现成的二分查找函数(lower_bound)就可以找到第一个不小于n的值在数组中的第几个,那么就总共有多少个平方数与立方数,如果第一个不小于n的值等于n那么个数就需要++。

预处理1,

先将所有的平方数与立方数存入数组中,这个时候,平方数是有可能和立方数重复,所以也需要去重,由于数字比较大我们就使用map进行标记,被标记过的就是已经放入过数组的。

void yu1()
{
p[0]=1;
e++;
for(int i=2;i*i<=1e9;i++)
{
if(s[i*i]!=1)
{
s[i*i]=1;
p[e]=i*i;
e++;
}
}
} 
 
void yu2()
{
for(int i=2;i*i*i<=1e9;i++)
{
	
if(s[i*i*i]!=1)
{
s[i*i*i]=1;
p[e]=i*i*i;
e++;
}
}
} 

预处理2

因为要使用的lower_bound是二分查找,所以我们需要对数组进行排序,当然很简单,sort就完事儿了

sort(p,p+e);

AC代码

#include<iostream>
#include<string.h>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
map<int,int>s;
int p[100000];
int e=0;
void yu1()
{
	p[0]=1;
	e++;
	for(int i=2;i*i<=1e9;i++)
	{
		if(s[i*i]!=1)
		{
			s[i*i]=1;
			p[e]=i*i;
			e++;
		}
			
			
	}
 } 

void yu2()
{
		for(int i=2;i*i*i<=1e9;i++)
	{
		
				if(s[i*i*i]!=1)
		{
			s[i*i*i]=1;
			p[e]=i*i*i;
			e++;
		}	
	}
 } 
int main()
{
yu1();
yu2();
int n;
	//cout<<p[e-1];
cin>>n;
while(n--)
{
	int m;
	cin>>m;
	sort(p,p+e);
	int t=lower_bound(p,p+e,m)-p;

	if(p[t]==m)t++;
	cout<<t<<"\n";
	
	
}
	return 0;
 } 

C. Wrong Addition

题目描述:

题目理解及思路

这道题的题意其实很简单,一个数c=a+b按照题目中的法则,给你c,a让你求出b,其实这道题就是一个单纯的模拟,不过需要在意的细节比较多罢了。

由于我的代码很丑,所以我就不详细赘述了。

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

char s1[20];
char s2[20];
char s3[20];
char ans[20];
int main()
{

int n;
cin>>n;
while(n--)
{
scanf(" %s %s",s1,s2);
getchar();
//cout<<s1<<" "<<s2<<"\n";
if(strlen(s2)<strlen(s1))
{
puts("-1");	
continue;
}
int d1=strlen(s1);
int d2=strlen(s2);
if(strlen(s1)<=strlen(s2))
{
	for(int i=strlen(s2)-1;i>=0;i--)
	{
		if(d1>0)
		s3[i]=s1[d1-1];
		else
		s3[i]='0';
		d1--;
	}
}
int e=0;
int f=0;
int i,j;
for(i=strlen(s2)-1,j=strlen(s3)-1;i>=0&&j>=0;i--,j--)
{
	if(s2[i]-s3[j]>=0)
	{
		ans[e]=s2[i]-s3[j]+'0';
		e++;
	}
	else
	{
		if(i-1<0){
			f=1;
			puts("-1");
			break;
		}
		if(s2[i-1]!='1'){
			f=1;
		puts("-1");
		break;
		}
		
		if(((s2[i-1]-'0')*10+(s2[i]-'0')-(s3[j]-'0'))>0)
		{
		ans[e]=((s2[i-1]-'0')*10+(s2[i]-'0')-(s3[j]-'0'))+'0';
		e++;
		i--;
		}
	}
}
while(j>=0&&!f)
{
	if(s3[j]>'0'&&s3[j]<'9')
	{
		puts("-1");
		f=1;
	}
	j--;
}
if(f)
{
memset(s3,'\0',sizeof(s3));	
memset(ans,'\0',sizeof(ans));
continue;
}
while(ans[e]>'9'||ans[e]<='0')e--;
for(int i=e;i>=0;i--)
{
	cout<<ans[i];
	ans[i]='\0';
}
cout<<"\n";
memset(s3,'\0',sizeof(s3));

}
	return 0;
 }