1.28号做高铁过去，下午3:00~晚上10:30，累死了喵。

找了个公寓，环境还可以，夜宵吃了一个炒面才睡，那时候已经凌晨1:00了。

第二天早上7:30才出门，路上堵死了，去了雅美阁酒店领取了一个通行证就骑车去南外了。

8:10分到机房，其他人已经开始打比赛了，汗流浃背了。

---

简要题解：

A

easy

#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
#define int unsigned long long
const int MAXN = 2e5 + 10;
const int MR = 10 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int debug = false;
signed main() {
    string s;
    string t;
    cin >> s;
    string tmp = "PER";
    for (int i = 0; i < s.size(); i++) {
        t.push_back(tmp[i % 3]);
    }
    int ans = 0;
    for (int i = 0; i < s.size(); i++) ans += (s[i] != t[i]);
    cout << ans << endl;
    return 0;
}

B

easy

#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int MR = 10 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int debug = false;
int n, x;
int a[MAXN];
signed main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (x * a[i]);
        x = max(1ll, x - 1);
    }
    cout << ans << endl;
    return 0;
}

C

easy

令 $dp[n][i]$ 为完成了 $n$ 个时间段后在位置 $i$。

转移就是 $dp[i][j]\ |=\ dp[i\ -\ 1][j\ -\ a[i]], dp[i][j]\ |=\ dp[i\ -\ 1][j\ +\ a[i]]$

#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 1e4 + 10;
const int MR = 1e3 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int debug = false;

int l, n;
int a[MAXN];
int dp[MR][MAXN];
void solve() {
    memset(dp, 0, sizeof dp);
    cin >> l >> n;
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;
        a[i] = y - x;
    }
    for (int i = 0; i <= l; i++) dp[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= l; j++) {
            if (j - a[i] >= 0)
                dp[i][j] |= dp[i - 1][j - a[i]];
            if (j + a[i] <= l)
                dp[i][j] |= dp[i - 1][j + a[i]];
        }
    }
    bool flag = false;
    for (int i = 1; i <= l; i++) flag |= dp[n][i];
    puts(flag ? "possible" : "impossible");
}
signed main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

D

a 小到大排序，b 大到小排序，答案就是 $\sum (b_i - a_i),a_i \le b_i$

/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int MR = 1e3 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int debug = false;

int n, m;
int a[MAXN], b[MAXN];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m, greater<int>());
    int ans = 0;
    for (int i = 1; i <= min(n, m); i++) {
        if (a[i] >= b[i])
            continue;
        ans += (b[i] - a[i]);
    }
    cout << ans << endl;
    return 0;
}

E

赛时没调出来。

正解线段树，等什么时候有时间补一下题。

F

区间DP。

$dp[i][j]$ 表示 $[i,\ j]$ 这一个区间至少需要加几个括号。

再使用一个 $pre[i][j]$ 表示在哪里开始加括号。

/*****************************************
备注：
******************************************/
#include<queue>
#include<math.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
// #define int long long
const int MAXN = 2e5 + 10;
const int MR = 1e3 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int debug = false;

int n;
int dp[MR][MR], pre[MR][MR];
char s[MR];

void print(int l, int r)
{
	if(l > r)return ;
	if(l == r)
	{
		if(s[l] == '(' || s[l] == ')')cout << "()";
		else cout << "[]";
		return ;
	}
	if(pre[l][r] == -1)
	{
		cout << s[l];
		print(l + 1, r - 1);
		cout << s[r];
		return ;
	}
	int k = pre[l][r];
	print(l, k);
	print(k + 1, r);
	return ;
}
signed main()
{
	cin >> (s + 1);
	n = strlen(s + 1);
	memset(dp, INF, sizeof dp);
	memset(pre, 0, sizeof pre);
	for(int i = 1; i <= n; i++)
	{
		dp[i][i] = 1;
		dp[i + 1][i] = 0;
	}
	for(int len = 2; len <= n; len++)
	{
		for(int l = 1; l + len - 1 <= n; l++)
		{
			int r = l + len - 1;
			if((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']'))
			{
				if(dp[l][r] > dp[l + 1][r - 1])
				{
					dp[l][r] = dp[l + 1][r - 1];
					pre[l][r] = -1;
				}
			}
			for(int k = l; k < r; k++)
			{
				if(dp[l][k] + dp[k + 1][r] < dp[l][r])
				{
					dp[l][r] = dp[l][k] + dp[k + 1][r];
					pre[l][r] = k;
				}
			}
		}
	}
	print(1, n);
	return 0;
}

G

有思路没码出来。

原题链接

H

感觉和 最受欢迎的牛 很类似，但是又两种性别。

考虑两个分别用 tarjin 即可。

码不出来【流泪】

---

午餐吃了一个味千拉面，挺好吃了。

下午2:05左右到机房，人比上午少了一半多一些。

旁边坐了一个老哥，我无聊的时候就帮他调代码，渐渐地就熟起来了（）

5:00下课，润回公寓了。

晚餐吃了一个酸菜鱼，辣死我了/dk

7点左右看了一个化学课程的回放，然后9:15分开始打原，打了一个小时后就睡了。

--END--