Citation引证/Equilateral Triangle等边三角形/ 字符串旋转/F.小红的区间修改（二）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
int a[102];
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + n + 1, [](const int a,const int b) {return a > b;});for (int i = n; i >= 0; i--) {if (i<=a[i]) {cout << i << endl;break;}}return 0;
}

思路： 

这题的数据相当于差分，累加取模得到位置，记录位置的点数。

这题有等边三角型的前提是l是3的倍数，这样才能在均分圆时有60度的可能。

然后它成三角形的三个点就是i+0*l/3       i+1*l/3       i+2*l/3  的乘积和就是它的答案

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, l;
int a[300005];
long long sum = 0, pq = 1;
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> l;a[0]++;int q = 0, p;for (int i = 0; i < n - 1; i++) {cin >> p;q = (q + p) % l;a[q]++;}if (l % 3 != 0) {cout << 0 << endl;}else {int j = l / 3;for (int i = 0; i < j; i++) {pq = 1;for (int z = 0; z < 3; z++) {pq *= a[i + j * z];}sum += pq;}cout << sum << endl;}return 0;
}

D - 字符串旋转

 思路：

他这个只能左移一个单位，所以他字典序最小就是当出现第一个a[i]>a[i+1]时移动直到a[i]<a[i+j];结束，然后输出时我感觉我的还是比较好的。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n;while (n--) {cin >> m;cin >> s;bool gg = false;for (int i = 0; i < m; i++) {if (i + 1 < m) {if (gg) {cout << s[i];continue;}if (s[i] <= s[i + 1]) {cout << s[i];}else {char f = s[i];i++;while (i<m&&s[i] <= f) {cout << s[i];i++;}cout << f;i--;gg = true;}}else {cout << s[i];}}cout << endl;}return 0;
}

F.小红的区间修改（二）

 思路：

我一看到这题就想到了线段树，但要注意它那个a[i]的标记问题

if (a[i]==2 || (a[i * 2 + 1] ==2&& a[i * 2]==2)) {
        a[i] = 2;
    }
    else if (a[i]>0||a[i*2+1]>0||a[i*2]>0) {
        a[i] = 1;
    } 

这样在查找时可以方便判断

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[3000000];
int MAX = 1;
int Pan(int l,int r,int i,int x,int y) {if (x>=l&&y<=r) {return a[i]>0;}int mid = (x+y) / 2;if (a[i] == 2) {a[i * 2 + 1] = 2;a[i * 2] = 2;}bool pan = false;if (mid >= l) {pan = Pan(l, r, i * 2, x, mid)>0 ? true : pan;}if (pan) {return true;}if (mid+1 <= r) {pan = Pan(l, r, i * 2+1, mid+1, y)>0 ? true : pan;}return pan;
}
void Fu(int l, int r, int i, int x, int y) {if (x >= l && y <= r) {a[i] = 2;return ;}int mid = (x+y) / 2;if (mid >= l) {Fu(l, r, i * 2, x, mid);}if (mid + 1 <= r) {Fu(l, r, i * 2 + 1, mid+1, y);}if (a[i]==2 || (a[i * 2 + 1] ==2&& a[i * 2]==2)) {a[i] = 2;}else if (a[i]>0||a[i*2+1]>0||a[i*2]>0) {a[i] = 1;}
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定int q, l, r;cin >> q;while(q--){cin >> l >> r;if (Pan(l, r, 1, 1, 300000)) {cout << MAX << endl;}else {Fu(l, r, 1, 1, 300000);MAX = MAX > r-l + 2 ? MAX :r-l + 2;cout << MAX << endl;}}return 0;
}