A：K 阶恒星系

思路分析：

我们先讨论 $p_i$ 左侧的情况，右侧按照同样的逻辑做处理就可以了：

注意到，我们只关心有没有至少 $k$ 个元素，而不关心是哪些元素小于 $p_i$。因此，我们可以贪心地维护到当前位置时，最小的 $k$ 个元素。如果这 $k$ 个元素中最大的数字小于 $p_i$，则说明可以选出 $k$ 个来。否则不满足，并且 $p_i$ 可以替换掉原来的$k$ 个元素中的最大数。

从上面可以看出，我们要动态地维护 $k$ 个元素，并且要频繁查询、删除最大值，和插入一个元素，用优先队列（大根堆）即可。

时间复杂度：$O(n\log n)$

空间复杂度：$O(n)$

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, k, p[N], ans;
bool f[N], g[N];
priority_queue<int> qf, qg;  // 维护到当前位置前最小的 k 个元素
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        if(qf.size() < k) qf.push(p[i]), f[i] = false;
        else if(p[i] > qf.top()) f[i] = true;
        else qf.pop(), qf.push(p[i]), f[i] = false;
    }
    for(int i = n; i >= 1; i--) {
        if(qg.size() < k) qg.push(p[i]), g[i] = false;
        else if(p[i] > qg.top()) g[i] = true;
        else qg.pop(), qg.push(p[i]), g[i] = false;
    }
    for(int i = 1; i <= n; i++) {
        if(f[i] && g[i]) ans++;
    }
    cout << ans;
    return 0;
}

当然本题还有另外一种更简单的写法，用树状数组，每次动态查询前$p_i$的比我小的元素有多少个，值域树状数组即可。

B：德州扑克

没什么好说的，一道模拟题，按照题意分类讨论即可

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target ("avx")
#pragma GCC optimize ("inline")

#include <bits/stdc++.h>

#define ios_close std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr)

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;

struct Brand{
    int num, type;
    Brand(){}
}a[6];

void solve(){
    std::map<int, int> ty;
    std::map<int, int> cnt;
    for(int i = 1; i <= 5; i ++ ){
        std::cin >> a[i].num;
        cnt[a[i].num] ++;           
    }
    for(int i = 1; i <= 5; i ++ ){
        std::cin >> a[i].type;
        ty[a[i].type] ++;
    }
    if(ty.size() == 1){
        bool ok = true;
        for(int i = 2; i <= 5; i ++ ){
            if(a[i].num - a[i - 1].num != 1){
                ok = false;
            }
        }
        if(ok && a[5].num == 14){
            puts("ROYAL FLUSH");
        } else if(ok){
            puts("STRAIGHT FLUSH");
        } else {
            puts("FLUSH");
        }
    } else {
        bool four = false;
        bool three = false;
        bool two = false;
        bool five = false;
        for(auto [n, c] : cnt){
            if(c == 4){
                four = true;
            } else if(c == 3){
                three = true;
            } else if(c == 2){
                two = true;
            } else if(c == 5){
                five = true;
            }
        }
        bool ok = true;
        for(int i = 2; i <= 5; i ++ ){
            if(a[i].num - a[i - 1].num != 1){
                ok = false;
            }
        }
        if(five || four){
            puts("FOUR OF A KIND");
        } else if(three && two){
            puts("FULL HOUSE");
        } else if(ok){
            puts("STRAIGHT");
        } else {
            puts("FOLD");
        }
    }
}

C：极速返航

思路分析：

最大值最小，首先考虑二分，验证答案是否具有二分性，显然随着可能的最大值变大，花费时间会减少，随着可能最大值减小，花费时间会变大，具有二分性质。

所以二分出一个可能的最大时间，去检验即可。注意左右边界问题即可。

最大值显然是 数组中最大值，最小值显然是0，但是由于我的二分取不到最小值0，所以代码中$l = -1$

时间复杂度：$O(n\log(max(a_i))$

赋一个核心code

bool check(i64 mid){
    long long ans = w;
    for(int i = 1; i <= n; i ++ ){
        if(a[i] > mid){
            ans -= (a[i] - mid) * p;
        }
    }
    return ans < 0;
}

void solve(){
    cin >> n >> p >> w;
    for(int i = 1; i <= n; i ++ ){
        std::cin >> a[i];
    }
    long long l = -1, r = *std::max_element(a + 1, a + 1 + n);
    while(l + 1 < r){
        i64 mid = (l + r) >> 1;
        if(check(mid)){
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << r;
}

当然本题还有一个贪心解法，留给读者自己思考。

D：方格取数[Easy]

看到题中描述的行走规则我们起始可以猜出，正解是典型的二维的线性 DP。

对于 $k \le 20$ 的部分，我们可以设 $f[x][y][z]$ 表示从起点走到 $(x,y)$ 且乘积模 $k$ 后值为 $z$ 的方案数。则有 $f[1][1][a_{1,1}\% k]=1$，采用主动转移的方式可得：

$$f[x][y + 1][z\times a_{x,y + 1}\%k]+=f[x][y][z]\\ f[x + 1][y][z\times a_{x + 1,y}\%k]+=f[x][y][z] $$

时间复杂度：$O(n^2k)$

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int p = 0; p < k; p++) {
            t = p*a[i][j+1] % k;
            f[i][j+1][t] = (f[i][j+1][t]+f[i][j][p]) % mod;
            t = p*a[i+1][j] % k;
            f[i+1][j][t] = (f[i+1][j][t]+f[i][j][p]) % mod;
        }

答案为 $f[n][n][0]$。

E：分析

$偶数 \times 偶数或者奇数 = 偶数$，所以两个数字有一个是偶数即可。

F：吃奶酪

暴力搜索每种可能即可。正解是状态压缩DP。

$solve1$是全排列枚举

$solve2$是dfs搜索

$solve3$是状态压缩DP

double dis(double x1, double y1, double x2, double y2){
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

struct Point {
	double x, y;
	Point(){

	}
	Point(double _x, double _y) : x(_x), y(_y) {}
};

Point a[20];

int n;
double res = 1e18;

bool vis[20];

void dfs(int u, int fa, double s){
	if(s >= res){
		return;
	}
	if(u > n){
		res = std::min(res, s);
		return;
	}
	for(int i = 1; i <= n; i ++ ){
		if(!vis[i]){
			vis[i] = true;
			dfs(u + 1, i, s + dis(a[i].x, a[i].y, a[fa].x, a[fa].y));
			vis[i] = false;
		}
	}
}

double dp[20][1 << 16];
double dist[20][20];

void solve3(){
	std::cin >> n;
	a[0].x = 0, a[0].y = 0;
    rep(i, 1, n){
    	std::cin >> a[i].x >> a[i].y;
    }
    memset(dp, 127, sizeof dp);
    rep(i, 0, n){
    	rep(j, i + 1, n){
    		dist[j][i] = dist[i][j] = dis(a[i].x, a[i].y, a[j].x, a[j].y);
    	}
    }
    // dp[i][j] 表示现在在i点，状态为j
    rep(i, 1, n){
    	dp[i][1 << (i - 1)] = dist[0][i];
    }
    for(int k = 1; k < (1 << n); k ++ ){
    	for(int i = 1; i <= n; i ++ ){
    		if((k & (1 << (i - 1))) == 0){
    			continue;
    		}
    		for(int j = 1; j <= n; j ++ ){
    			if(i == j){
    				continue;
    			}
    			if((k & (1 << (j - 1))) == 0){
    				continue;
    			}
    			dp[i][k] = std::min(dp[i][k], dp[j][k - (1 << (i - 1))] + dist[j][i]);
    		}
    	}
    }
    std::cout << std::fixed << std::setprecision(2);
    double ans = 1e18;
    rep(i, 1, n){
    	ans = std::min(ans, dp[i][(1 << n) - 1]);
    }
    std::cout << ans;
}

void solve2(){
	std::cin >> n;
	a[0].x = 0, a[0].y = 0;
    rep(i, 1, n){
    	std::cin >> a[i].x >> a[i].y;
    }
    dfs(1, 0, 0);
    std::cout << std::fixed << std::setprecision(2);
    std::cout << res;
}

void solve(){
	std::cout << std::fixed << std::setprecision(2);
    std::cin >> n;
    a[0].x = 0, a[0].y = 0;
    rep(i, 1, n){
    	std::cin >> a[i].x >> a[i].y;
    }
    std::vector<int> p;
    rep(i, 1, n){
    	p.pb(i);
    }
    double ans = 1e18;
    do {
    	double s = 0;
    	bool ok = true;
    	rep(i, 0, n - 1){
    		if(!i){
    			s += dis(a[p[i]].x, a[p[i]].y, a[0].x, a[0].y); 
    		} else {
    			s += dis(a[p[i]].x, a[p[i]].y, a[p[i - 1]].x, a[p[i - 1]].y);
    		}
    		if(s >= ans){
    			ok = false;
    			break;
    		}
    	}
    	if(ok){
    		ans = s;
    	}
    }while(std::next_permutation(p.begin(), p.end()));
    std::cout << ans;
}

G：排序疑惑

考虑到我们一次可以使得小于$n$的区间有序，那么我们一定选择长度为$n - 1$的区间最好，那么也就是说我们可以翻转$[1,n-1]或者[2,n]$，于是等价于判断$a_1是不是最小值或者a_n是不是最大值即可$

H：谎言 Ⅱ

暴力美学——珂朵莉树：他们队伍写了一个贪心的写法：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
struct node{
	int a, b, k;
}p[N];
int vis[N];

bool cmp(node x, node y)
{
	return x.a >= y.a;
}
int main()
{
	int n, k;
	cin >> n >> k;
	
	for(int i = 1; i <= n; ++i){
		cin >> p[i].a >> p[i].b >> p[i].k;
	}
	
	for(int i = 1; i <= n; ++i){
		if(p[i].b != -1 && vis[i] != 1){
			if(p[i].a >= p[p[i].b].a){
				p[p[i].b].a -= p[p[i].b].k;
				vis[p[i].b] = 1;
				vis[i] = 1;
			}
			else{
				p[i].a -= p[i].k;
				vis[p[i].b] = 1;
				vis[i] = 1;
			}
		}
	}
	sort(p + 1, p + 1 + n, cmp);
	
	int sum = 0;	
	for(int i = 1; i <= n; ++i){
		if(p[i].a <= 0)
			continue;
		if(k <= 0)
			break;
		
		k -= p[i].a;
		++sum;
	}
	
	if(k > 0)
		puts("you will die");
	else
		cout << sum << "\n";
	return 0;
}

正解是我们可以先分类，然后做分组背包即可，把冲突谎言放到一组背包中，选择即可。

void solve(){
	memset(dp, 127, sizeof dp);
	int n, m;
	std::cin >> n >> m;
	std::map<int, int> vis;
	int cnt = 0;
	std::vector<int> a(n + 1), b(n + 1), k(n + 1);
	for(int i = 1; i <= n; i ++ ){
		std::cin >> a[i] >> b[i] >> c[i];
	}
	for(int i = 1; i <= n; i ++ ){
		if(b[i] == -1){
			e[ ++ cnt].push_back({1, a[i]});
			e[cnt].push_back({0, 0});
		} else {
			if(vis[i]){
				continue;
			}
			vis[b[i]] = true;
			e[++ cnt].push_back({0, 0});
			e[cnt].push_back({1, a[i]});
			e[cnt].push_back({1, a[b[i]]});
			e[cnt].push_back({2, std::max(0, a[i] + a[b[i]] - c[i])});
		}
	}
	dp[0] = 0;
	for(int i = 1; i <= cnt; i ++ ){
		for(int j = m; j >= 0; j -- ){
			for(auto x : e[i]){
				int v = x.first, w = x.second;
				dp[j] = std::min(dp[j], dp[std::max(0, j - w)] + v);
			} 
		}
	}
	if(dp[m] == 0x127127127127){
		std::cout << "you will die";
	} else {
		std::cout << dp[m];
	}
}

I：小球染色

没什么说的，统计次数后选择次数最小的几个即可，选择到种类等于$k$即可。

J：聪聪买书

依照题目模拟即可。讨论清楚所有情况就好。

K：Bye 2023，Hello 2024

字符串，只需要看字符串末尾是不是$3$，是的话把他改为$4$即可。

L： 线性代数

依照题目模拟即可。注意开$long\ \ long$。

M：迷宫

本场比赛防$AK$题目，线段树优化建图。