2022.08.24 模拟赛小结
题面
(这个链接只是为了自己方便找，页面设置权限了，不要尝试访问)
更好的阅读体验戳此进入
（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）
赛时思路
T1
原题是 LG-P1533 可怜的狗狗，但是数据弱化了，$ n \le 2 \times 10^4, m \le 1 \times 10^4 $，本来是一道很明显的主席树区间第 k 大（不过 std 用的是莫队+线段树），但是这个数据量的话似乎 $ O(nm) $ 随便切，于是考虑到排序后遍历整个数组找到第 k 个序号符合要求的即可，于是切掉了，不过 luogu 上只有 60pts。
Code:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define PI M_PI
#define E M_E
#define npt nullptr
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef long long ll;
typedef unsigned long long unll;
template <typename T = int>
inline T read(void);
int N, M;
// priority_queue < pair< int, int >, vector < pair < int, int > >, greater < pair < int, int > > >a;
vector < pair < int, int > > a;
int main(){
freopen("dog.in", "r", stdin);
freopen("dog.out", "w", stdout);
N = read(), M = read();
for(int i = 1; i <= N; ++i)a.push_back(make_pair(read(), i)); //a.push(make_pair(read(), i));
sort(a.begin(), a.end());
while(M--){
int f = read(), t = read(), k = read();
int cnt(0);
for(auto i : a){
if(f <= i.second && i.second <= t)++cnt;
if(cnt == k){printf("%d\n", i.first); break;}
}
}
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
T flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = 1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/* Examples:
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1
*/
T2
是一道状压 DP，从数据量就可以很显然的看出来，但是赛时没考虑到用最短路来写，因为过程中是可以重复访问已经经过的点，就被这一点卡住了没写出来转移方程，最后没什么想法了就写了个 BFS + 乱搞 + 卡时，20pts，原题是 HDU5418 Victor and World。
Code:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define PI M_PI
#define E M_E
#define npt nullptr
#define MAXJ ((1 << i) - 1)
#define MAXTIME (1.90000)
#define SUBTIME ((MAXTIME / (double)_T) * 0.90000)
// #define MAXK ((1 << i) - 1)
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef long long ll;
typedef unsigned long long unll;
template <typename T = int>
inline T read(void);
int T, _T;
int G[20][20];
// int dp[20][1 << 16];
// int dp[20][20][100 * 20];
int N, M;
bool used[20];
int ans(INT_MAX);
void Clear(void){
memset(G, -1, sizeof(G));
// memset(dp, 0x3f, sizeof(dp));
memset(used, 0, sizeof(used));
ans = INT_MAX;
}
struct que{
int pos;
int pri;
bitset < 17 > used;
que(int _pos, int _pri):pos(_pos), pri(_pri){used.reset();}
void operator=(que x){
this->pos = x.pos;
this->pri = x.pri;
this->used = x.used;
}
};
void BFS(void){
double begT = (double)clock() / CLOCKS_PER_SEC;
queue < que > q;
que top(1, 0);
top.used[1] = true;
q.push(top);
while( ( (double)clock() / CLOCKS_PER_SEC - begT ) <= SUBTIME && !q.empty()){
// printf("BFS\n");
for(int i = 1; i <= 100 && !q.empty(); ++i){
auto tmp = q.front(); q.pop();
if((int)tmp.used.count() == N && tmp.pos == 1){
// printf("FIND ANS pos = %d, cost = %d\n", tmp.pos, tmp.pri); cout<<tmp.pri<<endl;
ans = min(ans, tmp.pri);
continue;
}
for(int j = 1; j <= N; ++j){
auto tmpp = tmp;
if(~G[tmpp.pos][j]){
tmpp.pri += G[tmpp.pos][j];
tmpp.used[j] = 1;
tmpp.pos = j;
q.push(tmpp);
}
}
}
}
}
// void DFS(int dep, int pos, int cost){
// if(dep > N)return (void)(ans = min(ans, cost));
// for(int i = 1; i <= N; ++i){
// if(~G[pos][i] && !used[i]){
// used
// }
// }
// }
int main(){
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
T = read();
_T = T;
while(T--){
Clear();
// printf("TEST: %d\n", dp[1][1]);
N = read(), M = read();
for(int i = 1; i <= M; ++i){
int f = read(), t = read(), w = read();
if(!~G[f][t])G[f][t] = G[t][f] = w;
else G[f][t] = G[t][f] = min(G[f][t], w);
}
BFS();
// printf("%.6lf", (MAXTIME / (double)T));
printf("%d\n", ans);
// for(int i = 1; i <= N; ++i){
// for(int j = 0; j <= MAXJ; ++j){
// // for(int k = 0; k <= MAXJ; ++k){
// // dp[i][j] = min(dp[i][j], dp[i - 1][])
// // }
// for(int k = 0; k < i; ++k){
// if(dp[])
// }
// }
// }
// for(int i = 1; i <= N; ++i){
// for(int j = 1; j <= N; ++i){
// }
// }
}
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
T flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = 1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/* Examples:
*/
T3
一道根号分治的数学题，因为看到输入数据只有一个数所以考虑本地 $ O(n^2) $ 跑结果然后写个数据库拿部分分（外加随机生成的几个大数据碰运气），不过因为本地电脑性能和代码长度限制打的表并不大，不过最后因为求 log 的时候没有手写用的换底公式，精度炸了，导致直接爆零。
原题是 ICPC2019 银川 F，似乎在计蒜客上有，链接。
Code:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define PI M_PI
#define E M_E
#define npt nullptr
#define MOD 998244353
#define logg(a, b) ((double)log(b) / log(a))
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef long long ll;
typedef unsigned long long unll;
template <typename T = int>
inline T read(void);
ll CAL(int N){
ll ans(0ll);
for(int a = 2; a <= N; ++a){
ll tmp(0);
for(int b = a; b <= N; ++b){
tmp = ( tmp + (int)(floor(logg(a, b)) * ceil(logg(b, a))) % MOD ) % MOD;
}
ans = (ans + (a * tmp) % MOD ) % MOD;
}
return ans;
}
int ans[6000010] = {0, 0, 2,7,18,34,56,85,124,175,236,308,392,489,600,726,874,1039,1222,1424,1646,1889,2154,2442,2754,3096,3464,3862,4288,4743,5228,5744,6294,6877,7494,8146,8840,9571,10340,11148,11996,12885,13816,14790,15808,16871,17980,19136,20340,21600,22910,24271,25684,27150,28670,30245,31876,33564,35310,37115,38980,40906,42894,44945,47074,49268,51528,53855,56250,58714,61248,63853,66530,69280,72104,75003,77978,81030,84160,87369,90658,94040,97504,101051,104682,108398,112200,116089,120066,124132,128288,132535,136874,141306,145832,150453,155170,159984,164896,169907,175028,
//这中间是不到1e4条数据，太长了我就删了
943867507,971865423,1626469,29639352,57659720,85687574,113722915,141765744,169816062,197873870,225939169,254011960,282092244,310180022,338275295};
int main(){
freopen("function.in", "r", stdin);
freopen("function.out", "w", stdout);
ans[10483]=423591818,ans[18804]=371933020,ans[21915]=628094753,ans[15108]=922305915,ans[28044]=8382477,ans[15834]=992863592,ans[13795]=451174431,
//这中间也是很多数据，太长了我就删了
ans[22615]=477214908,ans[10408]=323781780,ans[12145]=205002082,ans[14837]=486795542,ans[29535]=195266508,ans[24719]=232233760,
ans[26203]=282953812,ans[18512]=447383303,ans[20765]=214864064,ans[21034]=75964550,ans[26885]=9951939,ans[26692]=628205313;
int tmp = read();
if(ans[tmp]){printf("%d\n", ans[tmp]); return 0;}
printf("%lld\n", CAL(tmp));
// printf("%d\n", ans[read()]);
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);fflush(stderr);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
T flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = 1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/* Examples:
*/
T4
这题本来我还以为能切掉了呢，非常显然的网络流求最小割和最小割集（或者说不需要割集，算边数就行）。没想到一次 Dinic 的做法所以写了个两次 Dinic 的，理论上是可以切的不过在第二次 Dinic 的时候，对于如何改边权有点问题所以炸了，最后 40pts。
原题 LG-P1344 [USACO4.4]追查坏牛奶Pollutant Control
Code:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define PI M_PI
#define E M_E
#define npt nullptr
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef long long ll;
typedef unsigned long long unll;
template <typename T = int>
inline T read(void);
int N, M;
struct Edge{
Edge* nxt;
Edge* rev;
int to;
ll val;
void* operator new(size_t);
Edge(Edge* _nxt, Edge* _rev, int _to, ll _val):nxt(_nxt), rev(_rev), to(_to), val(_val){;}
Edge(void) = default;
}eData[3100];
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
Edge *head[50], *cur[50];
int S = 1, T;
int dep[50];
ll dfs(int p = S, ll curFlow = INT_MAX){
if(p == T)return curFlow;
ll cost(0);
for(auto &i = cur[p]; i; i = i->nxt){
if(i->val > 0 && dep[i->to] == dep[p] - 1){
ll icost = dfs(i->to, min(curFlow - cost, i->val));
cost += icost;
i->val -= icost;
i->rev->val += icost;
}
if(cost == curFlow)break;
}
if(!cost)dep[p] = INT_MAX;
return cost;
}
bool bfs(void){
copy(head + 1, head + N + 1, cur + 1);
memset(dep, 0, sizeof(dep));
queue < int > q;
q.push(T);
dep[T] = 1;
while(!q.empty()){
int t = q.front(); q.pop();
for(auto i = head[t]; i; i = i->nxt){
if(!dep[i->to] && i->rev->val > 0){
dep[i->to] = dep[t] + 1;
q.push(i->to);
}
}
}
return dep[S];
}
ll Dinic(void){
ll ret(0), tmp;
while(bfs())while((tmp = dfs()))ret += tmp;
return ret;
}
int main(){
freopen("control.in", "r", stdin);
freopen("control.out", "w", stdout);
N = read(), M = read();
T = N;
for(int i = 1; i <= M; ++i){
int f = read(), t = read(), v = read<ll>();
head[f] = new Edge(head[f], npt, t, v);
head[t] = new Edge(head[t], npt, f, 0);
head[f]->rev = head[t];
head[t]->rev = head[f];
}
printf("%lld", Dinic());
for(int i = 1; i <= N; ++i){
for(auto j = head[i]; j; j = j->nxt){
if(!j->val && !j->rev->val)j->rev->val = 1, j->val = 0;
}
}
for(int i = 1; i <= N; ++i){
for(auto j = head[i]; j; j = j->nxt){
// if(!j->val && !j->rev->val)continue;
if(!j->val)j->val = 1;
else j->val = 0;
}
}
printf(" %lld\n", Dinic());
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
T flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = 1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/* Examples:
*/
正解
T4
别问为什么不是按顺序来的
主要是出现了以下几个问题
- 第二次 Dinic 应该判断是否为反悔边并分类讨论。
- 数据应该因为是随机生成的，所以会有自环的存在，因为我用的存图方式的问题，自环会 RE。
- Luogu 的数据有一个点是错的，N 点的值有问题，需要特判。
AC Code:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define PI M_PI
#define E M_E
#define npt nullptr
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef long long ll;
typedef unsigned long long unll;
template <typename T = int>
inline T read(void);
int N, M;
struct Edge{
Edge* nxt;
Edge* rev;
int to;
ll val;
bool isRev;
void* operator new(size_t);
Edge(Edge* _nxt, Edge* _rev, int _to, ll _val):nxt(_nxt), rev(_rev), to(_to), val(_val), isRev(false){;}
Edge(void) = default;
}eData[3100];
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
Edge *head[50], *cur[50];
int S = 1, T;
int dep[50];
ll dfs(int p = S, ll curFlow = INT_MAX){
if(p == T)return curFlow;
ll cost(0);
for(auto &i = cur[p]; i; i = i->nxt){
if(i->val > 0 && dep[i->to] == dep[p] - 1){
ll icost = dfs(i->to, min(curFlow - cost, i->val));
cost += icost;
i->val -= icost;
i->rev->val += icost;
}
if(cost == curFlow)break;
}
if(!cost)dep[p] = INT_MAX;
return cost;
}
bool bfs(void){
copy(head + 1, head + N + 1, cur + 1);
memset(dep, 0, sizeof(dep));
queue < int > q;
q.push(T);
dep[T] = 1;
while(!q.empty()){
int t = q.front(); q.pop();
for(auto i = head[t]; i; i = i->nxt){
if(!dep[i->to] && i->rev->val > 0){
dep[i->to] = dep[t] + 1;
q.push(i->to);
}
}
}
return dep[S];
}
ll Dinic(void){
ll ret(0), tmp;
while(bfs())while((tmp = dfs()))ret += tmp;
return ret;
}
int main(){
// freopen("control.in", "r", stdin);
// freopen("control.out", "w", stdout);
N = read(), M = read();
for(int i = 1; i <= M; ++i){
int f = read(), t = read(), v = read<ll>();
N = max(N, max(f, t));
if(f == t)continue;
head[f] = new Edge(head[f], npt, t, v);
head[t] = new Edge(head[t], npt, f, 0);
head[f]->rev = head[t];
head[t]->rev = head[f];
head[t]->isRev = true;
}
T = N;
printf("%lld", Dinic());
for(int i = 1; i <= N; ++i){
for(auto j = head[i]; j; j = j->nxt){
if(!j->isRev && !j->val)j->val = 1, j->rev->val = 0;
else if(!j->isRev && j->val)j->val = 32767, j->rev->val = 0;
}
}
printf(" %lld\n", Dinic());
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
T flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = 1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/* Examples:
*/
T1
对于 Luogu 上的数据，由于这题主席树是在太裸了，所以直接交以前写的板子就行。
(该说不说这题 128MB 如果用主席树的话空间卡的特别死，用指针写法可能会 MLE，没有 oop 的感觉了很烦)
AC Code:
#include <bits/stdc++.h>
using namespace std;
#define lV lastVersion
#define rn realN
#define oarr origin_array
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
#define MAXN 310000
template<typename T = int>
inline T read(void);
struct Tree{
int ls, rs, val;
}t[MAXN << 5];
int root[MAXN];
int tot(0);
int Build(int l, int r){
int vert(++tot);
t[vert].val = 0;
if(l == r)return vert;
int mid = (l + r) >> 1;
t[vert].ls = Build(l, mid);
t[vert].rs = Build(mid + 1, r);
return vert;
}
int Create(int l, int r, int val, int lV){
int vert(++tot);
t[vert].val = t[lV].val + 1, t[vert].ls = t[lV].ls, t[vert].rs = t[lV].rs;
if(l == r)return vert;
int mid = (l + r) >> 1;
if(val <= mid)t[vert].ls = Create(l, mid, val, t[vert].ls);
else t[vert].rs = Create(mid + 1, r, val, t[vert].rs);
return vert;
}
int Query(int l, int r, int qx, int qy, int k){//return position
if(l == r)return l;
int leftVal(t[t[qy].ls].val - t[t[qx].ls].val);
int mid = (l + r) >> 1;
if(k <= leftVal)return Query(l, mid, t[qx].ls, t[qy].ls, k);
else return Query(mid + 1, r, t[qx].rs, t[qy].rs, k - leftVal);
}
int N, M;
// vector<int>arr;
// vector<int>oarr;
int arr[310000], oarr[310000];
int main(){
// freopen("in.txt", "r", stdin);
N = read(), M = read();
for(int i = 1; i <= N; ++i)arr[i] = oarr[i] = read();
sort(arr + 1, arr + N + 1, less<int>());
int rn = unique(arr + 1, arr + N + 1) - (arr + 1);
root[0] = Build(1, rn);
for(int i = 1; i <= N; ++i){
int pos = lower_bound(arr + 1, arr + rn + 1, oarr[i]) - arr;
root[i] = Create(1, rn, pos, root[i - 1]);
}
for(int i = 1; i <= M; ++i){
int l = read(), r = read(), k = read();
printf("%d\n", arr[Query(1, rn, root[l - 1], root[r], k)]);
}
// for(int i = 1; i <= N; ++i)arr.push_back(read()), oarr.push_back(arr.at(i - 1));
// sort(arr.begin(), arr.end());
// int rn = unique(arr.begin(), arr.end()) - arr.begin();
// printf("%d\n", arr.end() - arr.begin());
// root[0] = Build(1, rn);
// for(int i = 1; i <= N; ++i){
// int pos = lower_bound(arr.begin(), arr.begin() + rn, oarr.at(i - 1)) - arr.begin();
// root[i] = Create(1, rn, pos, root[i - 1]);
// }
// for(int i = 1; i <= M; ++i){
// int l = read(), r = read(), k = read();
// // int pos1 = lower_bound(arr.begin(), arr.end(), oarr.at(l - 1 - 1)) - arr.begin();
// // int pos2 = lower_bound(arr.begin(), arr.end(), oarr.at(r - 1)) - arr.begin();
// printf("Query: %d\n", Query(1, rn, root[l - 1], root[r], k));
// printf("%d\n", oarr.at(Query(1, rn, root[l - 1], root[r], k) - 1));
// }
return 0;
}
template<typename T>
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T3
这题感觉挺好的（所以单独写了一篇题解）
T2
咕咕咕
UPD
update-2022_08_25 初稿 别问我为什么8.24模拟赛8.25初稿