526互联

比赛总结：Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324)

发布时间 2023-10-17 20:56:49作者: 一只傲娇璇

比赛：Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324)

A-same

1.常规方法

int main()
{
	int n;
	cin >> n;
	vector<int> s(n);//利用vector容器可以不需要确定内存大小
	for (auto &n : s)
	{
		cin >> n;
	}
	for (int i = 0; i < n - 1; i++)
	{
		if (s[i] != s[i + 1])
		{
			cout << "No" << endl;
			return 0;//如果不相等就直接退出程序，否则输出"Yes"
		}
	}
	cout << "Yes" << endl;
	return 0;
}

总结：

1.对于这类数组大小动态变化的题目，利用vector容器，就可以动态的改变数组的大小，不需要去确定数组大小，比较方便

2.再main函数中去写，利用return 0;随时退出程序，结束循环。就不需要考虑利用其它变量，在循环结束后再去判断输出内容

3.利用auto &n : s;输入数据，简化代码量（auto缺点：必须遍历完整个容器，无法遍历到某一中间值然后就退出）

2.a faster way

int main()
{
	int n, s;
	cin >> n >> s;
	for (int i = 0; i < n - 1; i++)
	{
		int s2;
		cin >> s2;
		if (s2 != s)
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

总结：

在输入时就做出判断。先输入第一个数，然后通过循环，在每次输入数据时就做出判断，就不需要遍历数组了

其余同常规方法

B - 3-smooth Numbers

1.数学基础

题目中对x,y的限制是整数，但由于给定的数字N>=1,所以并不需要考虑x,y<0，（即if (x<0||y<0);N<1;）,proof is under：

1.if we assume that x<0 and y<0,then
0 < N = 2x*3y<1.
so x<0 and y<0 is not satisfied this condition.

2.if we assume that x>0 and y<0,then
N*2xϵ(2k,kϵZ);
3xϵ(2k+1,kϵZ)
it is obvious that equation is fause.in a similar way,if we assume y>0 and x<0,

the equation is fause still.

therefore we have shown if (x<0||y<0),N<1.

2.代码实现

void test01()
{
	long long N;//根据所给数据点，需要用long long 来储存
	cin >> N;
	while (N % 3 == 0)//如果是3的倍数，就除3
	{
		N /= 3;
	}
	while (N % 2 == 0)//同理
	{
		N /= 2;
	}
	if (N == 1)最后只有1和其他两种情况
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
}

总结：利用while，避免了利用for循环的复杂

C - Error Correction

思路：根据题目的操作，可以用输入的string的长度将输入的字符串分为三类，根据三种情况分别进行讨论

void test01()
{
	long long n,time = 0,k[999999],q = 0;//注意数据范围
	cin >> n;
	string t,s;
	cin.get();//char ch = getchar();//前面接收了一个数字，缓冲区中还有一个空格，需要清除
	getline(cin, t);//利用getline(cin,变量名)去接收一个含有空格的字符串
	for (int i = 0; i < n; i++)
	{
		getline(cin, s);
		 //如果两string长度相等，那么有两种情况，相等和更改一个字符
		if (t.size() == s.size())
		{
			int a = 2;//利用a去判断有几个字符是不相等的
			for (int j = 0; j < t.size(); j++)
			{
		//根据题意，最多有一个字符不相等，所以当a==0时，即两个点不相等，就退出
				if (a == 0)
				{
					break;
				}
				if (t[j] != s[j])//不相等就a--
				{
					a--;
				}
				//当循环将要结束时，判断是否满足条件
				//为防止最后一位才不满足条件，所以要加上a>=1
				if (j == t.size() - 1&& a >= 1)
				{
					time++;//次数加1
					k[q] = i + 1;//将下标输入数组中
					q++;//数组位置后移
				}
			}
		}
		//如果t的长度大于s,那么只能是删除了一个字符
		else if(t.size()  == s.size()+1)
		{
			int l = 2;
			//用h,j分别控制t和s后移
			for (int j = 0,h = 0; j < t.size();h++, j++)
			{
				if (l == 0)
				{
					break;
				}
				if (t[j] != s[h])
				{
					l--;
       //如果到了不相同的那一位，就令s该位不动，j++，然后令s和t的下一位进行比较
					h--;
				}
				if (j == t.size() - 1 && l == 1)
				{
					time++;
					k[q] = i + 1;
					q++;
				}
			}
		}
        //这种情况同第二种
		else if (t.size() == s.size()-1)
		{
			int m = 2;
			for (int j = 0, h = 0; j < t.size(); h++, j++)
			{
				if (m == 0)
				{
					break;
				}
				if (t[j] != s[h])
				{
					m--;
					j--;
				}
				if (j == t.size() - 1 && m>= 1)
				{
					time++;
					k[q] = i + 1;
					q++;
				}
			}
		}
	}
    //正常输出
	cout << time << endl;
	for (int i = 0; i < q; i++)
	{
		cout << k[i] << ' ';
	}
}

D - Square Permutation

思路：题目中说明最终要得到的数是一个完全平方数，那就列举10000000以内的平方数，看他们是否可以由输入的四个数字经过全排列得到

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <ctype.h>
#include <ctime>
#include <stack>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;

//n:输入的数字个数，bug:储存输入数字中含有数字1-9的个数，dig:储存完全平方数中含有数字1-9的个数，ans:结果
int n, dig[10], bug[10],ans;
string s;
int main()
{
	ios::sync_with_stdio(false);

	cin >> n >> s;//因为输入的各个数据是连续输入，所以用字符串进行储存
	for (int i = 0; i < n; i++)
	{
		bug[s[i]%48]++;//利用ASCII将每一个字符转化为数字
	}
    //因为数据上限是10的13次方，所以循环到10的7次就结束循环
	for (int i = 0; i < 10000000; i++)
	{
		memset(dig, 0, sizeof(dig));//初始化dig数组为0
//利用i*i构建完全平方数
//（1）因为数据上限超出int类型，所以用long long 去储存
//（2）为防止数据越界，所以先将i转化为long long 类型，然后再进行计算
//（3）注意要先将i转化为long long 类型，所以要用1ll*i*i,而不是i*i*1ll;
//第二种方式在计算i*i时就已经炸掉了，这时再去转化为long long 类型就已经没用了
		long long x = 1ll*i * i;
//下面去获取每一位数字
/*这里有一个细节，我默认的位数就是字符串的长度，所以当x的长度小于默认位数时，就会多记录0的个数，然而因为数字位数不相等时结论肯定不成立，所以该种情况并不需要特殊考虑*/
		for (int j = 0; j <n; j++)
		{
			dig[x % 10]++;
			x /= 10;
		}
		if (x)continue;//if(x!=0)也就是x不等于0，就不去进行下面的判断
		for (int k = 0; k < 10; k++)
		{
			if (dig[k] != bug[k])
			{
				ans--;//如果不满足，就ans--;使ans的值不被改变
				break;
			}
		}
		ans++;//如果上面的循环不退出循环，也就是相等，就对ans++
	}
	cout << ans << endl;
	return 0;
}