vp打到后面打不动了，好在压线银牌。

[SDCPC2023] Matching

给定长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，我们将从该序列中构造出一张无向图 $G$。具体来说，对于所有 $1 \le i < j \le n$，若 $i - j = a_i - a_j$，则 $G$ 中将存在一条连接节点 $i$ 与 $j$ 的无向边，其边权为 $(a_i + a_j)$。
求 $G$ 的一个匹配，使得该匹配中所有边的边权之和最大，并输出最大边权之和。
请回忆：无向图的匹配，指的是从该无向图中选出一些边，使得任意两条边都没有公共的节点。特别地，不选任何边也是一个匹配。

考了个常见的转化：$i - j = a_i - a_j$改为$i - a_i = j - a_j$然后把权值一样的放在一起就行。
可以开一个map<int,vector<int>>来存储，并且注意到后面压进去的一定是a比较大的，所以从后往前遍历如果两两配对就能找到最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	map<int, vector<int>> m;
	for (int i = 0; i < n; ++i) cin >> a[i], m[i - a[i]].push_back(a[i]);
	int ans = 0;
	for (auto [x, v] : m)
		for (int i = v.size() - 1; i > 0; i -= 2) {
			int k = v[i] + v[i - 1];
			if (k <= 0)break;
			ans += k;
		}
	cout << ans << endl;
}

[SDCPC2023] Fast and Fat

您正在参加一场团体越野比赛。您的队伍共有 $n$ 名队员，其中第 $i$ 名队员的速度为 $v_i$，体重为 $w_i$。
比赛允许每名队员独立行动，也允许一名队员背着另一名队员一起行动。当队员 $i$ 背着队员 $j$ 时，如果队员 $i$ 的体重大于等于队员 $j$，则队员 $i$ 的移动速度不会变化，仍然为 $v_i$；如果队员 $i$ 的体重小于队员 $j$，则队员 $i$ 的移动速度会减去两者的体重差值，即变为 $v_i - (w_j - w_i)$。如果队员 $i$ 的移动速度将变为负数，则队员 $i$ 无法背起队员 $j$。每名队员最多只能背负另一名队员，被背负的队员无法同时背负其他队员。
所有未被背负的队员中，最慢的队员的速度，即为整个队伍的速度。求整个队伍能达到的最大速度。

经典二分作为铜牌题。
这个范围(1≤_n_≤10^5)就已经在提示要用O(nlogn)的复杂度过。
最大化最小值，那么考虑二分。
首先二分答案，那么速度这个维度就已经定下来了，考虑把速度v作为已知条件，check函数要求在O(n)时间内判断。
那么考虑将队员分为两类，第一类是速度达到要求的，那么他们可以背起最重为$w_i+(v_i-v)$的，速度不达标的队员。先记录$w_i+(v_i-v)$，
第二类是速度不达标的，需要达标的队员背。考虑贪心的去背，不达标的最重的交给能背起的重量最大的队员背，那就是一个很明显的排序，排完之后再判断一下是不是合法即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void solve() {
	int n, maxn = -1;
	cin >> n;
	vector<int> v(n), w(n);
	for (int i = 0; i < n; ++i) 
		cin >> v[i] >> w[i],maxn = max(maxn, v[i]);
	auto check = [&](int x)->bool{
		vector<int> can, cant;
		for (int i = 0; i < n; ++i) 
			if (v[i] >= x) can.push_back(w[i] + (v[i] - x));
			else cant.push_back(w[i]);
		if (si(can) < si(cant))return false;
		sort(all(can), greater<int>());
		sort(all(cant), greater<int>());
//		debug
//		cerr<<x<<endl;
//		for(auto i: can) cerr<<i<<" \n"[i == can.back()];
//		for(auto i: cant) cerr<<i<<" \n"[i == cant.back()];
		int p1 = 0, p2 = 0;
		while (p1<si(can) && p2<si(cant)){
			if(can[p1] >= cant[p2]){
				p1++,p2++;
			}else return false;
		}
		return p2 == si(cant);
	};
	int l = 0, r = maxn + 1;
//	cerr<<l<<' '<<maxn<<endl;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid;
		else r = mid;
	}
	cout << l << endl;
}

心态崩了：vp的时候思路确实很快就想到了，没想到二分答案写挂了。。右边界一开始定的maxn，后来wa了之后跑了对拍发现是maxn是可以被取到的，所以边界应该是maxn+1，还有没开longlong喜提两次罚时。

[SDCPC2023] Puzzle: Sashigane

给定一个 $n$ 行 $n$ 列的网格，网格中包含恰好一个黑色方格，其余方格均为白色。令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子，这个黑色方格位于 $(b_i, b_j)$。
您需要用若干 L 形覆盖所有白色格子，使得每个白色格子都恰好被一个 L 形所覆盖，同时唯一的黑色方格不能被任何 L 形覆盖。L 形不能超过网格的边界。
更正式地，网格中的一个 L 形由四个整数 $(r, c, h, w)$ 唯一确定，其中 $(r, c)$ 确定了 L 形的转折点，$h$ 和 $w$ 确定了 L 形两臂的方向和长度。四个整数满足 $1 \le r, c \le n$，$1 \le r + h \le n$，$1 \le c + w \le n$，$h \ne 0$，$w \ne 0$。

  • 若 $h < 0$，则所有满足 $r + h \le i \le r$ 的格子 $(i, c)$ 均属于该 L 形；否则若 $h > 0$，则所有满足 $r \le i \le r + h$ 的格子 $(i, c)$ 均属于该 L 形。
  • 若 $w < 0$，则所有满足 $c + w \le j \le c$ 的格子 $(r, j)$ 均属于该 L 形；否则若 $w > 0$，则所有满足 $c \le j \le c + w$ 的格子 $(r, j)$ 均属于该 L 形。

下图展示了几种 L 形。

构造模拟题，思路也是很好想的，因为一开始有一个方块已经被填了不能填，所以考虑将它周围的也填上，使填上的位置是一个2*2的方块，然后可以将2*2的周围接着填变成3*3的……所以这样就可以了。可以证明这个一定是有解的。
实现的时候可以从外往里去填。
队伍里有模拟仙人，讲了思路就扔给队友写了，队友的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

int n,bi,bj;

struct Node{
    int x,y;
}a,b,c,d;

bool ok(Node x){
    if(x.x>=1 and x.x<=n and x.y>=1 and x.y<=n)return true;
    return false;
}

void solve(){
    cin>>n>>bi>>bj;
    a=b=c=d={bi,bj};

    vector<array<int,4>>ans;
    int anscnt=0;
    //往右上角填
    while(true){
        Node nxt={b.x-1,b.y+1};
        if(ok(nxt)){
            b.x--,b.y++;
            d.y++;
            a.x--;

            int len=d.x-b.x;
            ans.push_back({b.x,b.y,len,-len});
            anscnt++;
        }else break;
    }
    //往右下角填
    while(true){
        Node nxt={d.x+1,d.y+1};
        if(ok(nxt)){
            d.x++,d.y++;
            c.x++;
            b.y++;

            int len=d.x-b.x;
            ans.push_back({d.x,d.y,-len,-len});
            anscnt++;
        }else break;
    }
    //往左上角填
    while(true){
        Node nxt={a.x-1,a.y-1};
        if(ok(nxt)){
            a.x--,a.y--;
            c.y--;
            b.x--;

            int len=c.x-a.x;
            ans.push_back({a.x,a.y,len,len});
            anscnt++;
        }else break;
    }
    //往左下角填
    while(true){
        Node nxt={c.x+1,c.y-1};
        if(ok(nxt)){
            c.x++,c.y--;
            a.y--;
            d.x++;

            int len=c.x-a.x;
            ans.push_back({c.x,c.y,-len,len});
            anscnt++;
        }else break;
    }
    cout<<"Yes"<<endl;
    cout<<anscnt<<endl;
    for(auto i:ans){
        for(auto j:i)cout<<j<<" ";
        cout<<endl;
    }
}

[SDCPC2023] Math Problem

给定两个正整数 $n$ 和 $k$，您可以进行以下两种操作任意次（包括零次）：

  • 选择一个整数 $x$ 满足 $0 \leq x < k$，将 $n$ 变为 $k\cdot n+x$。该操作每次花费 $a$ 枚金币。每次选择的整数 $x$ 可以不同。
  • 将 $n$ 变为 $\lfloor \frac{n}{k} \rfloor$。该操作每次花费 $b$ 枚金币。其中 $\lfloor \frac{n}{k} \rfloor$ 表示小于等于 $\frac{n}{k}$ 的最大整数。

给定正整数 $m$，求将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币，无解输出-1。请注意：$0$ 是任何正整数的倍数。

比赛没切，有点累剩一个小时吃饭去了。
可以发现一定是先除后乘，不然会浪费掉乘法的操作。
当时也没细想后来一看这个除法和乘法都是log级别的，那直接枚举就行
设除完之后的数是n，那么在经过m次乘法之后，能取到的值是一个区间：$[n^m,n^m+k^m-1]$然后只要判断这个范围内有没有m的倍数即可，做完了。
还有就是要开__int128不然会爆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
	int n,k,m,a,b;
	cin>>n>>k>>m>>a>>b;
	if(n%m==0) return cout<<0<<endl,void();
	if(k==1) return cout<<-1<<endl,void();
	int division = 1,ans = INT64_MAX,cost = 0;
	while(true){
		if(!n){
			ans = min(ans , cost);
			break;
		}
		__int128 l = n , r = n;
		int cnt = 0;
		while(l % m && l / m == r / m){
			r = r*k + k-1;
			l *= k;
			cnt++;
		}
		ans = min(ans , cost + cnt*a);
		n /= k;
		cost += b;
	}
	cout<<ans<<endl;
}

先这样吧有空再把GDCPC还有剩下几道金银牌题补了。

还要加训不然很危险，还剩一个月ZJCPC再炸真就考虑退役了。