浅谈考试（24/10/7）
很显然，我的精神状态也是很症猖的啊
T1 P1776 宝物筛选
这道题一眼板子题，就是多重背包转01背包，整体思路不难。但是这道题有个很恶心的问题： 很容易TLE on #9 #10。
解决办法有两个，第一个就是快读快写，但是不知道为什么我是过不了的，甚至会
掉（我的快读快写）；第二个方法（正解）就是二进制优化，我看到 @fairfriendZ 写出来了，但是问题是我不会，所以只能打到80pts。
T2 P1347 排序
这道题，就是拓扑排序嘛，在第一种情况下就是一个优雅的 else 就可以了。
因为这道题我
#include "bits/stdc++.h"
using namespace std;
const int Xe = 30;
int n, m, pa[Xe];
vector <int> ve[Xe];
bool vis[Xe][Xe];
queue <int> q;
void dfs(int x){
if (pa[x]) dfs(pa[x]);
cout << char(x + 'A' - 1);
}
void bfs(int k){
int s[Xe];
memset(s, 0, sizeof(s));
s[0] = 1;
q.push(0);
while(!q.empty()){
int u = q.front();
q.pop();
for (int i = 0; i < ve[u].size(); i++){
int v = ve[u][i];
if (s[v] < s[u] + 1){
pa[n + 1] = v;
pa[v] = u;
s[v] = s[u] + 1;
q.push(v);
}
if (s[v] > n + 2){
cout << "Inconsistency found after " << k << " relations.";
exit(0);
}
}
}
if (k == m && s[n + 1] != n + 2) cout << "Sorted sequence cannot be determined.";
if (s[n + 1] == n + 2){
cout << "Sorted sequence determined after " << k << " relations: ";
dfs(pa[n + 1]);
cout << ".";
exit(0);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++){
ve[0].push_back(i);
ve[i].push_back(n + 1);
}
for (int i = 1; i <= m; i++){
char a, b, c;
cin >> a >> b >> c;
if (!vis[a - 'A' + 1][c - 'A' + 1]){
ve[a - 'A' + 1].push_back(c - 'A' + 1);
vis[a - 'A' + 1][c - 'A' + 1] = 1;
}
bfs(i);
}
return 0;
}感觉自己的马蜂比较凉嚎
T3 P1025 数的划分
我？暴力20pts
似乎这道题 dfs 和 dp 都能过，不过用大法师的话一定要剪枝，不然可能会
，但是动规（或者这里算递推？）可以更加简短一点
也不知道是谁打了50多行纯暴力，仅仅加了一点点优化，结果还是只有20pts，肯定连暴力算法都出问题了
T4 P5322 排兵布阵
我？依旧是暴力20pts，完全因为算法出问题，骗分骗到的20分。
直接把别人说的题解搬过来好了：
比较好想的DP，设
dp[i][j] 表示第i 个城堡时，已派出j 个士兵。决策时，贪心派出恰好严格大于某一玩家派出的数量的两倍（不然浪费）。我们发现又可以排序预处理出a[i][j] 表示第i 个城堡，出兵数量第j 大的人出兵数量（因为这样可以很容易算出贡献，即为k \times i ）
转移方程：
反正就是，这次比赛我一共拿了220pts，还算可以，赶紧备战CSP-S二轮吧，说不定还要去打NOIP。
本次闲话到此结束，我继续去题目里挣扎了。