A
模拟题,不多说。
时间复杂度\(O(3)\)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
const char ch[] = {'L', 'M', 'S'};
std::string s[2];
std::map<char, int> mp1, mp2;
int t;
void check() {
for (int i = 0; i < 3; i++) {
if (mp1[ch[i]] == 0 && mp2[ch[i]] == 0) continue;
if (mp1[ch[i]] > 0 && mp2[ch[i]] == 0) {
puts(">");
return;
}
if (mp1[ch[i]] == 0 && mp2[ch[i]] > 0) {
puts("<");
return;
}
if (mp1[ch[i]] > 0 && mp2[ch[i]] > 0) {
if (ch[i] == 'S') {
if (mp1['X'] > mp2['X']) {
puts("<");
return;
}
if (mp1['X'] < mp2['X']) {
puts(">");
return;
}
if (mp1['X'] == mp2['X']) {
puts("=");
return;
}
}
if (ch[i] == 'L') {
if (mp1['X'] > mp2['X']) {
puts(">");
return;
}
if (mp1['X'] < mp2['X']) {
puts("<");
return;
}
if (mp1['X'] == mp2['X']) {
puts("=");
return;
}
}
if (ch[i] == 'M') {
puts("=");
return;
}
}
}
}
int main() {
scanf("%d", &t);
while (t--) {
std::cin >> s[0] >> s[1];
mp1.clear();
mp2.clear();
for (int i = 0; i < s[0].length(); i++) mp1[s[0][i]]++;
for (int i = 0; i < s[1].length(); i++) mp2[s[1][i]]++;
check();
}
return 0;
}
B
令\(a_i=n-i+1\),若\(a_i=i\),将其与其他位置交换。
还有更简单的构造,我比赛时瞎写了一堆,简直不能看。
时间复杂度\(O(n)\)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
const int maxn = 2e5 + 7;
int t, n;
int a[maxn], b[maxn];
bool check;
int main() {
scanf("%d", &t);
while (t--) {
check = 0;
scanf("%d", &n);
for (int i = n; i >= 1; i--) a[n - i + 1] = i;
for (int i = 1; i <= n; i++) {
if (a[i] == i && i + 2 != n) { std::swap(a[i + 1], a[i]); }
if (a[i] == i && i + 2 == n) std::swap(a[i], a[i + 2]);
}
for (int i = 2; i < n; i++) {
if (a[i - 1] != a[i] + 1 && a[i - 1] != a[i] - 1 && a[i + 1] != a[i] + 1 && a[i + 1] != a[i] - 1) check = 1;
}
if (a[1] != a[2] + 1 && a[1] != a[2] - 1) check = 1;
if (a[n] != a[n - 1] + 1 && a[n] != a[n - 1] - 1) check = 1;
if (check) puts("-1");
if (!check) {
for (int i = 1; i <= n; i++) std::cout << a[i] << " ";
std::cout << std::endl;
}
}
return 0;
}
C
GDOI2018 T1的弱化版。
满足条件的区间和一定是[1,n]区间和的因数。
考虑因数分解,每次分解判断是否有若干区间满足和相等,并更新最小的最大区间长。
其实一眼二分题,但我打暴力了。
时间复杂度\(O(nlogn)\)
#include<iostream>
#include<cstdio>
#include<cstring>
const int maxn = 2000 + 5;
int T;
int n;
int a[maxn], sum[maxn];
int Sum, cnt;
int dp[maxn];
int check2(int _sum) {
int nowsum = 0;
int maxlength = 0, i = 1;
for (int j = 1; j <= n; j++) {
nowsum += a[j];
if (nowsum == _sum) {
nowsum = 0;
maxlength = std::max(maxlength, j - i + 1);
i = j + 1;
}
if (nowsum > _sum) return -1;
}
return maxlength;
}
int check() {
int minlength = n;
for (int i = 1; i * i <= Sum; i++) {
if (Sum % i != 0) continue;
int len = check2(i);
if (len != -1) minlength = std::min(minlength, len);
int len2 = check2(Sum / i);
if (len2 != -1) minlength = std::min(minlength, len2);
}
return minlength;
}
int main() {
scanf("%d", &T);
while (T--) {
Sum = 0;
cnt = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Sum += a[i];
std::cout << check() << std::endl;
}
}
D
满足交换的条件一定是\(a[l,mid].min=a[mid+1,r].max+1\)
如果差额不为1,无论怎么交换左右子树都不能严格递增。
在push_up()里一边维护区间最大最小值,一边判断条件即可(不用真交换)。
时间复杂度\(O(nlogn)\)
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
const int N = 3e5 + 7;
int a[N], ans;
int T, n;
bool check;
struct node {
int l, r, Maxn, Minn;
} t[N << 2];
void push_up(int p) {
bool flag=0;
if (t[p << 1].Minn == t[p << 1 | 1].Maxn + 1) ans++,flag=1;// 45 23
if (t[p << 1].Maxn == t[p << 1 | 1].Minn - 1) flag=1;// 23 45
if(!flag) check = 1;//无法构造beautiful tree
t[p].Maxn = std::max(t[p << 1].Maxn, t[p << 1 | 1].Maxn);
t[p].Minn = std::min(t[p << 1].Minn, t[p << 1 | 1].Minn);
}
void build(int p, int l, int r) {
t[p].l = l;
t[p].r = r;
if (l == r) {
t[p].Maxn = t[p].Minn = a[l];
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
push_up(p);
}
int main() {
scanf("%d", &T);
while (T--) {
check = 0;
ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
if (check) puts("-1");
else std::cout << ans << std::endl;
}
}
剩下的没做,看什么时候有空再做吧...
标签:include,return,int,ch,mp2,mp1,康复训练,Div.3,826 From: https://www.cnblogs.com/MrWangnacl/p/16784866.html