思考之后再看题解，是与别人灵魂之间的沟通与碰撞
题意 给出n个数，问它们向左或者向右是否都能成一个环。比如样例5是从1开始向左绕了一圈 [3, 2, 1, 5, 4] 变成 [1, 2, 3, 4, 5];
思路 我的方法是差分，假如成立，相邻两个数的差的绝对值要么是1要么是n-1。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
int q, n;
int num[202];
int sum[202];
int main()
{
cin >> q;
while(q--){
cin >> n;
memset(sum, 0, sizeof(sum));
for(int i = 0; i < n; i++) cin >> num[i];
bool can = true;
for(int i = 0; i < n; i++){
if(i==0){
sum[i] = num[i] - num[n-1];
}
else {
sum[i] = num[i] - num[i-1];
}
if(abs(sum[i]) != 1 && abs(sum[i]) != n-1) can = false;
}
if(can) cout << "YES
";
else cout << "NO
";
}
return 0;
}
题意 给出n个矩形，问所给出的4n条木棒所组成的矩形的面积是否都相等。
分析 要使面积都相等，则要取中间值。先排个序，然后小的与大的在一起，从两头往中间靠拢。简单的实现。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
int q, n;
int num[402];
int cnt[10004];
int main()
{
cin >> q;
while(q--){
cin >> n;
bool can = true;
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < 4*n; i++) {
cin >> num[i];
cnt[num[i]]++;
}
sort(num, num + 4*n);
for(int i = 1; i <= 10000; i++){
if(cnt[i]&1 == 1){ // 不清楚是否会有奇数边，所以遍历了一遍
can = false;
break;
}
}
if(can){
int sq = num[0] * num[4*n - 1]; // 两头
int l = 2, r = 4*n - 3;
for( ; l <= r; ){
if(num[l] * num[r] != sq){
can = false;
break;
}
l += 2; r -= 2;
}
}
if(can) cout << "YES
";
else cout << "NO
";
}
return 0;
}
题意 求n个数的公约数的个数。
分析 先求最大公约数（gcd），然后求这个最大公约数的约数（花样找质数），注意long long。
小插曲 因为我审题不认真，导致看漏了 Output 里的 "the number of..."，结果卡了很久quq。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b){
if(b == 0) return a;
else return gcd(b, a%b);
}
int n;
LL num[400005];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%I64d", &num[i]);
LL ans = gcd(num[0], num[1]);
for(int i = 2; i < n; i++){
ans = gcd(ans, num[i]);
}
LL cnt = 0;
for(LL i = 1; i*i <= ans; i++){
if(i*i == ans) cnt += 1;
else if(ans%i == 0) cnt += 2;
}
printf("%I64d
", cnt);
return 0;
}
补题 D1. Remove the Substring (easy version)
题意 t是s的子串，问最长可以删去s的连续子串后，仍保持t是s的子串。
分析 注意，“the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". ”。然后因为数据小，可以暴力枚举被删子串的起点与终点。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
string s, t;
int ans;
int main()
{
cin >> s >> t;
for(int i = 0; i < s.size(); i++){ // 被删子串起点
for(int j = i; j < s.size(); j++){ // 被删子串终点
int tt = 0;
// 判断删后的子串是否仍满足条件------------
for(int k = 0; k < s.size(); k++){
if(k == i){ // 遇到被删的起点立即跳到被删的终点
k = j;
continue;
}
if(s[k] == t[tt]){
tt++;
if(tt == t.size()){
break;
}
}
}
// -----------------------------------------
if(tt == t.size()) ans = max(ans, j-i+1);
}
}
cout << ans << endl;
return 0;
}
补题 D2. Remove the Substring (hard version)
题意 与D1一样，只是数据更大，不能暴力。
分析 字符串的配对。经过D1的练手发现，可删去的最长连续子序列分别在t子序列的前、中、尾三个部分。思维有点像尺取法，请配合代码食用。
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string s, t;
int pla[200005];
int main()
{
cin >> s >> t;
int j = 0, k = 1;
pla[0] = -1; // 有趣的操作
for(int i = 0; i < s.size(); i++){
if(j < t.size() && s[i] == t[j]){
pla[k++] = i; // 记录第一个子串的位置
j++;
}
}
for(int i = 0; i < k; i++){
printf("i:%d pla[]:%d
", i, pla[i]);
} cout << endl;
int ans = 0;
for(int i = s.size() - 1, j = 0; i >= 0; i--){
ans = max(ans, i - pla[t.size() - j]);
printf("i:%d j:%d pla[]:%d i-pla[]:%d
", i, j, pla[t.size() - j], i - pla[t.size() - j]);
if(j < t.size() && s[i] == t[t.size() - j - 1]){ // 把t子串的末尾依次往前找
j++; // 请耐心思考一下
}
}
cout << ans << endl;
return 0;
}
补题 E.Boxers
题意 在n个数里，可以对任意数+1或者-1或者不变，但是1不能变成0。问经过处理后的n个数里有多少个不同的数字。
分析 利用桶排，都往下取，因为1不能减为0.（思考一下，非常简单）
小插曲 我又看错题意了quq
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
int n;
int a[1500004];
int main()
{
int num;
cin >> n;
for(int i = 0; i < n; i++){
cin >> num;
a[num]++;
}
int ans = 0;
for(int i = 1; i <= 150001; i++){
if(a[i-1]){
ans++;
}
else if(a[i]){
ans++;
a[i]--; // 减1往下取，因为减1的数没有
}
else if(a[i+1]){
ans++;
a[i+1]--; // 同理
}
}
cout << ans << endl;
return 0;
}
补题 F1. Complete the Projects (easy version)
题意 处理n个事件，每次处理时r必须不能小于(a_i)，处理完后r的值会加上(b_i)的值（(b_i)可以是负数），问是否能处理完n个事件，处理完时r不能小于0。
分析 典型的贪心题目，需要排序。
- 当 (b geq 0) 时，取a小的；
- 当 (b leq 0) 时，取 a+b 大的。
证明请看参考博客
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
struct node{
int a, b;
}pro[102];
int n, r;
node one[102];
node two[102];
bool cmp1(node a, node b){
return a.a < b.a;
}
bool cmp2(node a, node b){
return a.a+a.b > b.a+b.b;
}
int main()
{
cin >> n >> r;
int num, d, cnt1 = 0, cnt2 = 0;
for(int i = 0; i < n; i++) {
cin >> num >> d;
node e; e.a = num; e.b = d;
if(d >= 0){
one[cnt1++] = e;
}
else {
two[cnt2++] = e;
}
}
sort(one, one + cnt1, cmp1);
sort(two, two + cnt2, cmp2);
// cout << endl;
// for(int i = 0; i < cnt1; i++){
// cout << one[i].a << " " << one[i].b << endl;
// } cout << endl;
//
// for(int i = 0; i < cnt2; i++){
// cout << two[i].a << " " << two[i].b << endl;
// } cout << endl;
bool can = true;
for(int i = 0; i < cnt1; i++){
if(r < one[i].a){
can = false;
break;
}
else r += one[i].b;
}
for(int i = 0; i < cnt2; i++){
if(r < two[i].a){
can = false;
break;
}
else r += two[i].b;
}
if(r < 0) can = false;
if(can) cout << "YES
";
else cout << "NO
";
return 0;
}