A - Another Chess Problem
咕
B - Beauty Of Unimodal Sequence
咕
C - Coefficient
咕
D - Double Tree
咕
E - Everything Is Generated In Equal Probability
咕
F - Fantastic Magic Cube
咕
G - Game
咕
H - Harmonious Army
咕
I - I Love Palindrome String
咕
J - Just Skip The Problem
签到题。每一次询问最多只能获得一位的信息,有询问次数下界为 n,可构造询问:第 i 个询问为 y_i=000\dots010\dots000(只有第 i 位为1),显然可行,并且该询问方案的任意排列均可行,共 n! 个。现证明其它询问方案不能达到理论下界:当存在 y_i 与 y_j 在某一位上均为1时,若 x 在该位上位0,则这两个询问最多可获得一位的信息,因此达不到下界。所以答案为 n!,由于模数 p=10^6+3,所以当 n\ge p 时直接输出0,否则暴力计算即可。
K - Keen On Everything But Triangle
用主席树维护权值,对于每个询问,暴力查找可以构成三角形的最大的三个数。由于斐波那契数列的性质,最多暴力 \log n 次,每次复杂度为 O(n\log n),所以总复杂度 O(n\log^2 n)。
L - Longest Subarray
咕
Code
A - Another Chess Problem
B - Beauty Of Unimodal Sequence
C - Coefficient
D - Double Tree
E - Everything Is Generated In Equal Probability
F - Fantastic Magic Cube
G - Game
H - Harmonious Army
I - I Love Palindrome String
J - Just Skip The Problem
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MOD 1000003
#define int long long
using namespace std;
int n;
signed main() {
ios::sync_with_stdio(false);
while (cin >> n) {
if (n >= MOD) {
cout << 0 << endl;
} else {
int ans = 1;
for (int i = 2; i <= n; i++) {
ans = ans * i % MOD;
}
cout << ans << endl;
}
}
}
K - Keen On Everything But Triangle
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 100005
#define MAX_T 4000005
#define int long long
using namespace std;
int n, q, tot;
int a[MAX_N];
int rt[MAX_N];
int L[MAX_T];
int R[MAX_T];
int sum[MAX_T];
vector<int> v;
int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void build(int o, int &k, int l, int r, int p) {
k = ++tot;
sum[k] = sum[o] + 1;
if (l == r) {
return;
}
int m = (l + r) >> 1;
if (p <= m) {
R[k] = R[o];
build(L[o], L[k], l, m, p);
} else {
L[k] = L[o];
build(R[o], R[k], m + 1, r, p);
}
}
int getx(int o, int &k, int l, int r, int rk) {
if (l == r) {
return l;
}
int m = (l + r) >> 1, s = sum[L[k]] - sum[L[o]];
if (rk <= s) {
return getx(L[o], L[k], l, m, rk);
}
return getx(R[o], R[k], m + 1, r, rk - s);
}
signed main() {
while (scanf("%lld%lld", &n, &q) != EOF) {
v.clear();
for (int i = 1; i <= n; i++) {
scanf("%lld", a + i);
v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0; i <= tot; i++) {
L[i] = R[i] = sum[i] = 0;
}
for (int i = 0; i <= n; i++) {
rt[i] = 0;
}
tot = 0;
int N = v.size();
for (int i = 1; i <= n; i++) {
build(rt[i - 1], rt[i], 1, N, getid(a[i]));
}
int l, r;
while (q--) {
scanf("%lld%lld", &l, &r);
if (r - l + 1 < 3) {
printf("-1\n");
} else {
int rk = r - l + 1;
int a = getx(rt[l - 1], rt[r], 1, N, rk) - 1;
int b = getx(rt[l - 1], rt[r], 1, N, rk - 1) - 1;
int c = getx(rt[l - 1], rt[r], 1, N, rk - 2) - 1;
while (rk > 3 && v[a] >= v[b] + v[c]) {
rk--, a = b, b = c;
c = getx(rt[l - 1], rt[r], 1, N, rk - 2) - 1;
}
if (v[a] < v[b] + v[c]) {
printf("%lld\n", v[a] + v[b] + v[c]);
} else {
printf("-1\n");
}
}
}
}
}
L - Longest Subarray