Codeforces Round 970 (Div. 3)
#include <iostream>
#include <cmath>
using namespace std;// 函数 is 用于判断给定的字符串 s 是否表示一个满足条件的正方形数。
bool is(const string &s, int n) {// 首先计算 n 的平方根 k。int k = sqrt(n); // 如果 k 的平方不等于 n，那么 n 不是完全平方数，返回 false。if (k * k != n)return false;// 检查字符串 s 的最外层和最内层是否都是 '1'。for (int i = 0; i < k; i++)if (s[i] != '1' || s[n-k+i] != '1') return false;// 检查字符串 s 的最内层和最外层之间的位是否都是 '0'。for (int i = 1; i < k-1; i++) {// 检查第 i 行的开始和结束是否为 '1'。if (s[i*k] != '1' || s[(i+1)*k-1] != '1') return false;// 检查第 i 行除了开始和结束之外的所有位是否都是 '0'。for (int j = 1; j < k-1; j++) { if (s[i*k + j] != '0') { return false;}}}// 如果所有的检查都通过了，返回 true。return true;
}int main() {int t;cin >> t; while (t--) {int n;string s;cin >> n >> s; // 调用函数 is 来判断 s 是否表示一个满足条件的正方形数。if (is(s, n)) {cout << "Yes" << endl; } else {cout << "No" << endl; }}return 0;
}
#include <iostream>
#include <cmath>
using namespace std;long long solve(long long l, long long r) {long long k = 1; // 初始化增加量long long a = l; // 当前构造的元素while (a + k <= r) { // 检查是否会超出上界a += k; // 增加当前元素k++; // 增加增加量}return k;
}int main() {int t;cin >> t;while (t--) {long long l, r;cin >> l >> r;cout << solve(l, r) << endl;}return 0;
}这个问题要求找出在给定的上下界 ll 和 rr 内，可以构成的最长“好”数组的长度。一个“好”数组的定义是：
- 数组是递增的，即对于所有 2≤i≤n2≤i≤n，有 ai−1<aiai−1<ai。
- 相邻元素之间的差值也是递增的，即对于所有 2≤i<n2≤i<n，有 ai−ai−1>ai+1−aiai−ai−1>ai+1−ai。
思路分析
要满足上述两个条件，数组中的每个元素 aiai 必须比前一个元素 ai−1ai−1 大，并且增加的量必须比前一对相邻元素的增加量要大。这意味着，如果我们从一个给定的 ll 开始，我们每次增加的量 kk 必须比上一次增加的量要大。
算法实现
- 初始化：从 ll 开始，初始化 kk 为 1，表示我们首先增加 1 到 ll 得到下一个元素。
- 循环增加：在每一步中，我们将当前的元素 aa 增加 kk 来尝试构造下一个元素。同时，kk 也增加 1，以满足差值递增的条件。
- 检查边界：在每次增加后，我们需要检查新构造的元素是否超出了上界 rr。如果超出了，就不能再继续增加了。
- 计算长度：每次成功构造一个元素，数组的长度就增加 1。最终，这个长度就是我们要找的最长“好”数组的长度。