A.Sakurako's Exam
算法：模拟
具体思路：
a个1，b个2 ，使他们的和为 0 ；
规律：
1.当两个数中，一个数不存在时，另一个数的个数必须要有偶数个
2.当1有偶数个时，2可以有奇数个或者是偶数个
3.当1有奇数个时，如何都不满足；
反思：不要着急，慢慢想
AC Code
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
int main() {
scanf("%d",&n);
while(n--) {
scanf("%d%d",&a,&b);
if(a == 0) {
if(b % 2) puts("NO");
else puts("YES");
}
else if(b == 0){
if(a % 2) puts("NO");
else puts("YES");
}
else if(a % 2) puts("NO");
else puts("YES");
}
return 0;
}
B.Square or Not
算法：模拟
具体思路：
1.首先读入的字符串长度是否能够成正方形
n != sqrt(n) * sqrt(n)
2.枚举字符串找是否满足条件；
边界上的值是否为1，里面的是否为 0，即可
字符串到矩阵的转换 s[(i-1) * sqrt(n) + j]
反思：
还是需要多做题，需要经验值
AC Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T,n;
char a[N];
void solve() {
scanf("%d",&n);
scanf("%s",a+1);
int len = sqrt(n);
if(n != len * len) {
puts("No");
return;
}
for(int i = 1; i <= len; i++) {
for(int j = 1; j <= len; j++) {
int op = 0;
//边界上值全部为 1
if(i == 1 || i == len || j == 1 || j == len) op = 1;
if((a[(i-1) * len + j] - '0' )!= op) {
puts("No");
return;
}
}
}
puts("Yes");
return;
}
int main() {
scanf("%d",&T);
while(T--) {
solve();
}
return 0;
}
C. Longest Good Array
算法：贪心
具体思路：
1.题目要求：数组时递增的且相邻的元素之间的差也是递增的
贪心的令相邻的间隔最小且递增
第一个数为 L, 第 $n + 1$ 个数为 $ L + n (n + 1)/2 <= R $
通过二分查找 n ；
知识点：1+2+3+...+n = n * (n+1)/2
反思：
没想到等差数列
AC Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T;
int a,b;
void solve() {
scanf("%d%d",&a,&b);
int len = b - a ;
//二分查找 n的值
int l = 0, r = 1e9;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(1LL* mid * (mid + 1) / 2 <= len) l = mid;
else r = mid - 1;
}
printf("%d\n",l + 1);
}
int main() {
scanf("%d",&T);
while(T--) {
solve();
}
return 0;
}
D.Sakurako's Hobby
算法： dfs
具体思路：
同一个置换环上的点可以相互到达，并查集合并维护置换环上的点
ans[N] : 存放每一个 i 能够到达黑色格子的数量
1.对于每一个i， i--> p[i] ；
如果p[i]是黑色，那么 cnt ++;
2.dfs(a[p[i]]) i = p[i];
dfs找环，当跳到的格子是已经访问过的说明我们已经找到环了，返回达到黑色格子的数量 cnt;
反思：
没有理解题面 i--> p[i] , 即 i = p[i] ;
AC Code
E.
算法：
具体思路：
反思：
AC Code
F.
算法：
具体思路：
反思：
AC Code
G.
算法：
具体思路：
反思：
AC Code
H.
算法：
具体思路：
反思：
AC Code