A - CQXYM Count Permutations(思维)
对于排列(p)，如果它的对数是(k)，那么可以构造({2n-p_i})，使得它的对数变为(2n-1-k)。如果(kge n)，就有(2n-k-1 < n)。即每个对数大于等于(n)的排列都可以构造一个小于(n)的排列，一共有((2n)!)。因此答案为(frac{(2n)!}{2})。
// pass
B - Diameter of Graph
分类讨论
// pass
C - Portal (前缀和)
枚举地狱门的宽度的左右边界，然后中间部分可以枚举下边界，用一些前缀和计算代价。设当前下边界在第(i)行，有最小代价(minlimits_{j=0}^{i-1}(g_i-f_j))，即(g_i-maxlimits_{j=0}^{i-1}(f_j))。维护(f)的前缀最大值即可。至于(f)和(g)的计算，用行列前缀和维护。
注意地狱门缺四角也是合法的。时间复杂度(O(m^2n))
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 5e2 + 10;
const double eps = 1e-5;
int costr[N][N];
int costc[N][N];
char s[N][N];
int mx[N];
int main() {
IOS;
int t;
cin >> t;
while(t--) {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> s[i] + 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
costr[i][j] = costr[i][j - 1] + s[i][j] - '0';
}
}
for(int j = 1; j <= m; j++) {
for(int i = 1; i <= n; i++) {
costc[j][i] = costc[j][i - 1] + ((s[i][j] - '0') ^ 1);
}
}
int ans = INF;
for(int len = 4; len <= m; len++) {
for(int l = 1; l + len - 1 <= m; l++) {
mx[0] = -INF;
int r = l + len - 1;
int rsum = 0;
for(int i = 1; i <= n; i++) {
int d = costr[i][r - 1] - costr[i][l];
int rd = r - l - 1 - d;
mx[i] = costc[l][i] + costc[r][i] + rsum + d - rd;
mx[i] = max(mx[i], mx[i - 1]);
if(i - 4 > 0) {
ans = min(ans, rsum + costc[l][i - 1] + costc[r][i - 1] + rd - mx[i - 4]);
}
rsum += d;
}
}
}
cout << ans << endl;
}
}
D - Mathematics Curriculum(动态规划)
见：CF1581D - Mathematics Curriculum(动态规划)
E - Train Maintenance(暴力)
-
如果(x_i+y_i > sqrt{m})，那么其中正在维护的时间段不超过(sqrt{m})段。直接在差分数组上对每一段区间加。由于询问时间是递增的，直接边修改边累加即可。稍微注意一下删除的情况就可以。
-
如果(x_i+y_i le sqrt{m})，如果(i)号车是第(s_i)天进入的，当前是第(t)天。令(a=x_i+y_i)那么(i)号车维护的条件就是((t-s_i) mod a =kge x_i)，即(t mod a =(k+s_i) mod a, k in [x_i, a))。所以创建(sqrt{m})个数组，对((k+s_i) mod a, k in [x_i, a))暴力修改即可，查询累加每个数组的(t mod a)项即可。
注意删除操作要根据其加入那天来修改，而不是当前天数。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 3e5 + 10;
const int M = 1e3 + 10;
const double eps = 1e-5;
typedef pair<int, int> PII;
PII ts[N];
int cnt1[M][M];
int cnt2[N];
int sqn;
int n, m;
int si[N];
void upd1(int x, int y, int s, int val) {
int a = x + y;
assert(a <= sqn);
for(int i = x + 1; i <= a; i++) {
cnt1[a][(i - 1 + s) % a] += val;
}
}
int que1(int p) {
int res = 0;
for(int i = 1; i <= sqn; i++) {
res += cnt1[i][p % i];
}
return res;
}
void ad(int x, int y, int id, int s) {
si[id] = s;
for(int i = s + x; i <= m; i += x + y) {
cnt2[i] += 1;
if(i + y <= m) cnt2[i + y] -= 1;
}
}
void mi(int x, int y, int id, int ts, int &res) {
int s = si[id];
for(int i = s + x; i <= m; i += x + y) {
cnt2[i] -= 1;
if(i + y <= m) cnt2[i + y] += 1;
if(ts >= i && ts < i + y) res--;
}
}
int main() {
IOS;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> ts[i].first >> ts[i].second;
}
sqn = sqrt(n);
int ans = 0;
for(int i = 1; i <= m; i++) {
ans += cnt2[i];
int op, k;
cin >> op >> k;
int x = ts[k].first, y = ts[k].second;
if(op == 1) {
if(x + y <= sqn) {
si[k] = i;
upd1(x, y, i, 1);
} else ad(x, y, k, i);
} else {
if(x + y <= sqn) upd1(x, y, si[k], -1);
else mi(x, y, k, i, ans);
}
cout << ans + que1(i) << endl;
}
}
F - Subsequence(st表，dp，笛卡尔树)
化一下式子可得
可以发现，(f)和区间最小值有有关，假设一个序列涉及到的区间为([l,r])，这个序列最小值所在的位置是(p)，(p)的左边有序列的(k_1)个数，右边有(k_2)个，那么序列中横跨(p)的贡献就是(-a_pcdot k_1 cdot k_2)，就是上面式子中第二项的一部分。然后剩余的贡献就会被分为左右两部分，可以分治下去，最后求得序列的值。
由此可以提出一个dp，设(f(l,r,k))为区间([l,r])中长度为(k)的序列的最大的值是多少，容易得到转移方程
以及
(f(l,r,k))取两者中的较大值，上下两式分别代表(a_p)不在序列中和(a_p)在序列中，(p)代表区间([l,r])最小值的编号。
看起来会超时，实则不然。不同的((l,r))只有(O(n))个，而且因为有(kle r-l+1)的限制，所以枚举(i)的个数可以不是(k)，可以优化到区间的长度。因此直接记忆化搜索，时间复杂度为(O(n^2))。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f3f3f3f3f
const int M = 5e3 + 10;
const int N = 4e3 + 10;
const double eps = 1e-5;
ll arr[N];
int mipos[20][N];
ll dp[M][N];
bool vis[M][N];
int id[N][N];
int n, m, si;
int que(int l, int r) {
int k = log2(r - l + 1);
int p1 = mipos[k][l], p2 = mipos[k][r - (1 << k) + 1];
return arr[p1] < arr[p2] ? p1 : p2;
}
void init(int l, int r) {
if(l > r) return ;
if(id[l][r]) return ;
if(l == r) return ;
id[l][r] = ++si;
int mid = que(l, r);
init(mid + 1, r);
init(l, mid - 1);
}
ll solve(int l, int r, int k) {
if(k > r - l + 1) return 0;
if(l > r) return 0;
if(k == 0) return 0;
if(l == r) {
return (m - 1) * arr[l];
}
int ind = id[l][r];
if(vis[ind][k]) return dp[ind][k];
ll res = 0;
int mid = que(l, r);
for(int i = max(0, k + mid - r); i <= min(k, mid - l + 1); i++) {
res = max(res, solve(l, mid - 1, i) + solve(mid + 1, r, k - i) - 1ll * 2 * i * (k - i) * arr[mid]);
if(i) res = max(res, solve(l, mid - 1, i - 1) + solve(mid + 1, r, k - i) + (m - 1) * arr[mid] - 1ll * 2 * (i * (k - i + 1) - 1) * arr[mid]);
}
vis[ind][k] = 1;
return dp[ind][k] = res;
}
int main() {
IOS;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
mipos[0][i] = i;
}
for(int i = 1; i < 20; i++) {
for(int j = 1; j <= n; j++) {
int p1 = mipos[i - 1][j], p2 = mipos[i - 1][min(n, j + (1 << (i - 1)))];
mipos[i][j] = arr[p1] < arr[p2] ? p1 : p2;
}
}
init(1, n);
cout << solve(1, n, m) << endl;
}
根据题解，序列的值可以化为类似树上若干个点两点间距离和的形式。因此可以直接建立笛卡尔树，在树上跑(k)个点距离和最大的dp，本质上和上面的做法一模一样，殊途同归了属于是。
笛卡尔树就是treap中随机数换成点的权值，关键字换成点的下标，即treap是笛卡尔树的一种。笛卡尔树中取若干点之间两两距离和，就是本题中相应序列的值。