比赛: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;
}