\(Preface\)
评价：最近网络流学魔怔了
感觉学长很喜欢\(AtCoder\)。。。其实题的质量似乎确实很好
\(Rank34/43\)
\(5pts + 10pts + 5pts + 0pts = 20pts\)
话说只要水到55pts就能\(Rank3\)/oh
今天的题是\(\color{blue}{蓝}\ \color{purple}{紫}\ \color{purple}{紫}\ \color{black}{黑}\)
\(\mathfrak{T1}\ 选举\)
因为早上复习了网络流感觉自己很彳亍，赛时上来直接按着T1莽网络流，然后想了两个小时的建图也没想出来。
最后没时间了快速写了个十分shab的假做法扔了上去水到了5pts
值得一提的是赛后写了个随机撒点水到了\(16pts\)/oh
16pts，在赛时算是挺高的了。
正解是dp，我贺的题解。。。
T1
// 删掉了一些调试信息.jpg
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 505
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
int n, K, truenum;
double final_ans(1145141919);
double f[N][N], sum[N][N];// f[i][j] 前i个州有j个州招人
struct Man{int ai, bi;};
struct Man a[N];
inline bool comp1(Man A, Man B){return ((A.bi == B.bi) ? (A.ai < B.ai) : (A.bi < B.bi));}
inline bool comp2(Man A, Man B){return A.ai < B.ai;}
#include <cstring>
void work(){
cin >> n >> K;
for (re i = 1 ; i <= n ; ++ i)
{cin >> a[i].ai >> a[i].bi; a[i].bi = ((a[i].bi == -1) ? (1145141919) : (a[i].bi));}
sort(a+1, a+n+1, comp1);
for (re i = n ; i >= 1 ; -- i){
sort(a+i, a+n+1, comp2);
for (re j = i ; j <= n ; ++ j)
sum[i][j-i+1] = sum[i][j-i] + a[j].ai;
}
sort(a+1, a+n+1, comp1);
for (re mannum = 0 ; mannum <= K-1 ; ++ mannum){
for (re i = 0 ; i <= K ; ++ i)
for (re j = 0 ; j <= mannum ; ++ j)
f[i][j] = 1145141919;
f[0][0] = 0;
for (re i = 1 ; i <= K ; ++ i){
f[i][0] = f[i-1][0] + (double)a[i].ai/(mannum+1);
for (re j = 1 ; j <= mannum ; ++ j)
f[i][j] = MIN(f[i-1][j-1] + (double)a[i].bi/j, f[i-1][j] + (double)a[i].ai/(mannum+1));
}
for (re i = 0 ; i <= K ; ++ i)
final_ans = MIN(final_ans, f[i][mannum] + sum[i+1][K-i]/(mannum+1));
}
cout.setf(ios::fixed), cout.precision(12);
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T2}\ 港口设施\)
推规律。把重叠但不相交的两个线段连边，发现答案就是\(2^{联通块的个数}\)。
联通块就是每个点都能到达每个点，不一定每个点之间都有边直接相连。(我看网上好像没这玩意的定义？)
然后因为需要判无解，所以可以进行二分图染色。跑网络流的爬@char_phi(我自己)。你染色跑个\(barbar\)网络流。
具体建边就是枚举两个线段，判断他们的左右端点的位置关系，决定是否建边。
但是发现建边是\(O(n^2)\)的，所以考虑优化这个过程。
优化过程我不会，我挂@kiritokazuto大佬的博客，\(kirito\)说因为我缠着他问还专门画了张图挂在博客耶
T2
#include <iostream>
#include <cstring>
#include <unistd.h>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 4000005
#define P 1000000007
#define mod %
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
struct star{int v, nxt;};
int n, star_cnt, available, cnt;
int a[N<<1], plc[N], fa[N<<1], nxt[N<<1], head[N<<1], lf[N], col[N];
struct star e[N<<2];
inline void star_add(int u, int v){e[++ star_cnt].v=v, e[star_cnt].nxt=head[u], head[u]=star_cnt;}
inline int find(int x){return ((fa[x] == x) ? (x) : (fa[x] = find(fa[x])));}
void dfs(int x){
for (re i = head[x] ; i ; i = e[i].nxt){
int v = e[i].v;
if (col[v] == col[x])
{cout << 0 << '\n'; exit(0);}
else if (col[v] == -1)
{col[v] = col[x]^1; dfs(v);}
}
}
inline int ksm(long long A, int B){
int res(1);
while (B != 0){
if ((B & 1) == 1) res = res * A mod P;
A = A * A mod P;
B >>= 1;
}
return res;
}
void work(){
cin >> n;
for (re i = 1, Front, Back ; i <= n ; ++ i)
{cin >> Front >> Back; a[Front] = a[Back] = i;}
n <<= 1;
for (re i = 1 ; i <= n ; ++ i)
fa[i] = i, nxt[i] = i;
for (re i = 1 ; i <= n ; ++ i){
if (plc[a[i]] == 0)
{plc[a[i]] = ++ cnt, lf[cnt] = a[i]; continue;}
fa[plc[a[i]]] = find(plc[a[i]]+1); // 往右跳
for (re j = fa[plc[a[i]]], k ; j <= cnt ; j = k){
star_add(a[i], lf[j]), star_add(lf[j], a[i]);
k = find(nxt[j]+1), nxt[j] = cnt;
}
}
n >>= 1;
memset(col, -1, sizeof(col));
for (re i = 1 ; i <= n ; ++ i)
if (col[i] == -1)
{col[i] = 1, available ++; dfs(i);}
cout << ksm(2, available) << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T3}\ 幽深府邸\)
这个题思路简单
\(Q\)很大，考虑预处理后\(O(1)\)回答询问。
那么就可以处理一个『每一个点能够到达的最左边和最右边』，\(O(1)\)回答询问。
考虑如何处理。
预处理出一个lkey[]和rkey[]分别表示打开当前门所需钥匙最近在左边的哪里、在右边的哪里，然后在拓展的时候只需要判断是否在当前拓展到的区间内即可。
然而发现会\(T\)掉，原因是有特殊构造数据卡你算法，你拓展的时候很费劲。那么我们只需要把拓展的顺序shuffle一下即可，有点像随机化\(spfa\)随机入队。
T3
#include <iostream>
#include <set>
#include <random>
#include <cstring>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 500005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
啥，随机化？
这玩意我喜欢
*/
int n, Q;
char vis[N];
int need[N], lkey[N], rkey[N], plc[N], order[N], Lmargin[N], Rmargin[N];
set<int> s[N];
set<int>::iterator it;
random_device seed; mt19937 myrand(seed());
inline void prework(){
for (re i = 1 ; i <= n-1 ; ++ i){
for (it = s[i].begin() ; it != s[i].end() ; ++ it)
plc[*it] = i;
lkey[i] = plc[need[i]];
}
memset(plc, 0x5f, sizeof(plc));
for (re i = n ; i >= 1 ; -- i){
for (it = s[i].begin() ; it != s[i].end() ; ++ it)
plc[*it] = i;
rkey[i-1] = plc[need[i-1]];
}
for (re i = 1 ; i <= n ; ++ i)
order[i] = i;
}
inline void Ream(int who){
int l(who), r(who), doa(true), dob(true);
vis[who] = true;
while (doa == true or dob == true){
doa = dob = false;
while (rkey[l-1] >= l and rkey[l-1] <= r and l > 1){
l --, doa = true;
if (vis[l] == true)
l = MIN(Lmargin[l], l), r = MAX(Rmargin[l], r);
}
while (lkey[r] <= r and lkey[r] >= l and r < n){
r ++, dob = true;
if (vis[r] == true)
l = MIN(Lmargin[r], l), r = MAX(Rmargin[r], r);
}
}
Lmargin[who] = l, Rmargin[who] = r;
}
void work(){
cin >> n;
for (re i = 1 ; i <= n-1 ; ++ i)
cin >> need[i];
for (re i = 1, num, w ; i <= n ; ++ i){
cin >> num;
for (re j = 1 ; j <= num ; ++ j)
{cin >> w; s[i].insert(w);}
}
prework();
/*for (re i = 1 ; i <= n ; ++ i)
cerr << "Debug: " << lkey[i] << _ << rkey[i] << '\n';*/
shuffle(order+1, order+n+1, myrand);
for (re i = 1 ; i <= n ; ++ i)
Ream(order[i]);// 精髓
cin >> Q;
int st, ed;
while (Q --){
cin >> st >> ed;
if (st == ed)
cout << "YES" << '\n';
else {
if (Lmargin[st] <= ed and Rmargin[st] >= ed)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
}
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T4}\ 长途巴士\)
咕
标签：21,int,cout,bi,re,HZOI,include,CSP,define From： https://www.cnblogs.com/charphi/p/16722260.html