A题 温暖的签到题，一眼秒了
L题 第二个就开了L题，因为看上去是个打表，写了个bfs打表，发现规律和%4的余数有关（1，3要特判），31分钟1A
此时队友给我读了D和M题，我去开D，他们写M 。然而他们拒绝了我的二分，非要写最短路 。然后半小时后发现算法假了，在我苦苦哀求之下写了二分+bfs
M题 二分升级次数，假设二分到mid，边权小于mid*d的可以通过，否则不能通过，总共可以通过mid*e条边 。那就相当于是一个边权为1的最短路，问1到n的距离是否小于等于mid*e 。既然边权都为1了，直接线性的bfs就行了 。87分钟1A
D题队友不告诉我每个数字都能被100整除 。。。我赛后才知道 。。。每个数字能整除100，那大小就是500，200个数字，开个200*1e5的DP数组即可 。事实上在赛前一天热身赛回去的路上为了解乏我随便出了一道题（和这个题一模一样）给大家做 。然后大家都会DP了 。
整理一下思路：设A为第一个人最终的分数，B为第二个人最终的分数 。先bfs把图01染色，然后算出被染成1的点之和 与 被染成0的点之和 的差值 。对于某一差值x，可以给A或者给B，也就是使A-B的值增加x或者减少x 。（DP的两种转移）DP的值为1时代表存在这种状态，否则不存在 。最后从小到大枚举，直到找到一个DP值为1的地方（即存在这个差值）为最小差值 。
然而我不知道数字能被100整除，就上了离散化背包，用set存储 。先01染色将集合求出来，初始set塞入0代表刚开始差值为0，每次取set的值，将下一位塞入当前值+x和当前值-x即可 。然后剪枝了一下，先将差值从大到小排序，如果当前set里的值大于后缀和，那么就直接减去后缀和再跳出 。保证不会超时 。复杂度约为n3？玄学，不懂 。
文章插图
由于数组没清零wa了一发，144分钟2A 。（如果不用离散化背包的话，那我15分钟内就能过QAQ）
下面是比赛AC的代码（注释是之后加的，其他都是AC了打印下来，应该没抄错吧QAQ）
#include using namespace std;#define pb push_back#define mp make_pair#define fi first#define se secondconst int maxn = 210;sets[maxn];vectorff[maxn];int co[maxn], dqs[maxn], cnt = 0, ww[maxn];//dqs存后缀和，ww存每个集合的差值bool vis[maxn];bool cmp(int a, int b) {return a > b;}void bfs(int qwq) {int a1 = 0;queue >q;//pair第二维代表颜色，01两种while(!q.empty()) q.pop();q.push(mp(qwq,1));vis[qwq] = 1;while(!q.empty()) {pair now = q.front();q.pop();if(now.se == 1) a1 += co[now.fi];else a1 -= co[now.fi];for(auto i : ff[now.fi]) {if(vis[i]) continue;vis[i] = 1;q.push(mp(i, 1 - now.se));}}ww[++cnt] = abs(a1);//存入集合差值}int main() {int n, m, t;cin >> t;while(t--) {cin >> n >> m;int sum = 0;cnt = 0;memset(vis,0,sizeof vis);memset(dqs,0,sizeof dqs);for(int i = 1; i <= n; i++)s[i].clear(), ff[i].clear();for(int i = 1; i <= n; i++)cin >> co[i], sum += co[i];for(int i = 1; i <= m; i++) {int a, b;cin >> a >> b;ff[a].pb(b);ff[b].pb(a);}for(int i = 1; i <= n; i++)if(!vis[i]) bfs(i);//找连通块sort(ww+1, ww+1+cnt, cmp);for(int i = cnt; i >= 1; i--)dqs[i] = dqs[i+1] + ww[i];s[1].insert(0);for(int i = 1; i <= cnt; i++) {set::iterator it;for(it = s[i].begin(); it != s[i].end(); it++) {if(*it >= dqs[i]) { //大于后缀和，那么减去后缀和直接breaks[cnt+1].insert(*it - dqs[i]);break;}}s[i+1].insert(*it + ww[i]);//转移1，加上当前值if(abs(*it) > dqs[i]) { //小于前缀和，就加上前缀和然后下一步s[cnt+1].insert(dqs[i] + *it);continue;}s[i+1].insert(*it - ww[i]);//转移2，减去当前值}set::iterator it;int minn = 1e9;for(it = s[cnt+1].begin(); it != s[cnt+1].end(); it++)minn = min(minn, abs(*it));cout
- 2019年，二月不再来
- 涪陵创新计算机学校纪录片,涪陵创新计算机学校2019年春期期末考试简报
- 2019年高县沙河豆腐美食文化节又来啦 沙河豆腐吉尼斯记录
- 2019年上半年火锅品牌周年庆盘点：大龙燚、集渔都是这么玩的 集渔吉尼斯记录
- 乘用车销量排行榜2020,2019年12月汽车销量排行榜：朗逸突破6万 帕萨特同比涨74%
- 2019年最新孕妇护肤品十大品牌排行榜新鲜出炉 世界孕妇装十大名牌
- 2019年新中国首富诞生：王健林225亿美元排第六，第一身价2416亿 世界十大首富2019
- 2019年举重世界杯邓薇夺金并打破三项世界纪录 2020举重吉尼斯记录
- 思想有多远，吉尼斯就有多“野”：盘点2019年吉尼斯世界纪录 牙签破吉尼斯记录
- 中国福布斯排行榜2019,2019年福布斯中国名人榜出炉，排名前三的都有谁？