当前位置: 开发笔记 > 前端 > 正文

普及题选讲(zroi)

作者：蓝羽月妞妞 | 来源：互联网 | 2023-09-11 11:46

提取：Day9:https:www.cnblogs.comCDOI-24374p15838867.htmlDay14：https:www.cnblogs.comCDOI-24374

提取：

Day 9: https://www.cnblogs.com/CDOI-24374/p/15838867.html

Day 14：https://www.cnblogs.com/CDOI-24374/p/15871370.html

Day 15：https://www.cnblogs.com/CDOI-24374/p/15874488.html

Day 16：https://www.cnblogs.com/CDOI-24374/p/15880038.html

Day 17：https://www.cnblogs.com/CDOI-24374/p/15884331.html

Day 18：https://www.cnblogs.com/CDOI-24374/p/15887190.html

Day 19：https://www.cnblogs.com/CDOI-24374/p/15888581.html

Day 20：https://www.cnblogs.com/CDOI-24374/p/15894027.html

Day 21：https://www.cnblogs.com/CDOI-24374/p/15911009.html

Day 22：https://www.cnblogs.com/CDOI-24374/p/15924081.html

Difficulty: $1\sim 10$ .

有趣题标记为 $(\color{red}{*})$ 或 $(\color{blue}{*})$，注意「有趣」的定义是包含难度下界的（带很多主观色彩） .

代码语言：C++ (since C++11)

题目原名不做改动 .

缺省源大概是：

#include #include template inline T chkmin(T& x, const T& y){if (x > y) x = y; return x;} template inline T chkmax(T& x, const T& y){if (x

然后实际上可能有区别 .

Day1 T1 Efim与奇怪的成绩 (Dif 2)

题面

一个浮点数，四舍五入至多 $m$ 次，问最后最大是多少 .

浮点数作为字符串的长度 $\le 2\times 10^5$，$m\le 10^9$ .

题解

找出最近的可舍入点然后暴力，此题是细节题 .

代码

int n, m; string s; int main() { scanf("%d%d", &n, &m); cin >> s; s = "$" + s; int pos = s.find("."), p = 0; for (int i=pos+1; i<=n; i++) if (s[i] >= '5'){p = i; break;} for (int i=p; m && (i >= pos+1); i--) if (s[i] >= '5'){s[i] = '\0'; ++s[i-1]; --m;} if (s[pos] != '.'){s[pos] = '.'; ++s[pos-1];} if (s[pos+1] == '\0') s[pos]='\0'; for (int i=pos-1; i; i--) if (s[i] > '9'){s[i] -= 10; ++s[i-1];} if (s[0] == 37) putchar('1'); puts(s.substr(1).c_str()); return 0; } '; ++s[i-1]; --m;} if (s[pos] != '.'){s[pos] = '.'; ++s[pos-1];} if (s[pos+1] == '

int n, m; string s; int main() { scanf("%d%d", &n, &m); cin >> s; s = "$" + s; int pos = s.find("."), p = 0; for (int i=pos+1; i<=n; i++) if (s[i] >= '5'){p = i; break;} for (int i=p; m && (i >= pos+1); i--) if (s[i] >= '5'){s[i] = '\0'; ++s[i-1]; --m;} if (s[pos] != '.'){s[pos] = '.'; ++s[pos-1];} if (s[pos+1] == '\0') s[pos]='\0'; for (int i=pos-1; i; i--) if (s[i] > '9'){s[i] -= 10; ++s[i-1];} if (s[0] == 37) putchar('1'); puts(s.substr(1).c_str()); return 0; } ') s[pos]='

int n, m; string s; int main() { scanf("%d%d", &n, &m); cin >> s; s = "$" + s; int pos = s.find("."), p = 0; for (int i=pos+1; i<=n; i++) if (s[i] >= '5'){p = i; break;} for (int i=p; m && (i >= pos+1); i--) if (s[i] >= '5'){s[i] = '\0'; ++s[i-1]; --m;} if (s[pos] != '.'){s[pos] = '.'; ++s[pos-1];} if (s[pos+1] == '\0') s[pos]='\0'; for (int i=pos-1; i; i--) if (s[i] > '9'){s[i] -= 10; ++s[i-1];} if (s[0] == 37) putchar('1'); puts(s.substr(1).c_str()); return 0; } '; for (int i=pos-1; i; i--) if (s[i] > '9'){s[i] -= 10; ++s[i-1];} if (s[0] == 37) putchar('1'); puts(s.substr(1).c_str()); return 0; }

Day1 T2 美丽的IP地址 (Dif 1)

题面

IP 地址的定义如下：

四个数，每个数在 $[0,256)$ 之间 .

没有前导 $0$ .

不包含给定数位

问回文 IP 地址数量 .

题解

暴搜

代码

const int N = 11^45^14; int n, cut[N], a[N], dight[N], ans; void dfs(int n, int m) { if (n==4){if (cut[m] == -1) ++ans; return ;} if (!cut[m]){a[n] = 0; dfs(n+1,m+1);} else { a[n] = 0; for (int i=m; ~cut[i]; i++) { a[n] = a[n] * 10 + cut[i]; if (a[n] <256) dfs(n+1, i+1); } } } void solve(int l, int r, int val) { if (l <= r) { for (int i=0; i return ; } if (!val) dfs(0, 0); } int main() { scanf("%d",&n); for (int i=0; i for (int i=4; i<=12; i++){cut[i] = -1; solve(0, i-1, (1 < printf("%d\n", ans); return 0; }

Day1 T3 Tic-tac-toe (Dif 1)

题面

三字棋局面判定：

first，现在轮到第一个人下。

second，现在轮到第二个人下。

the first player won，如果第一个人刚刚赢得比赛。

the second player won，如果第二个人刚刚赢得比赛。

illegal，如果这种棋局不可能出现。

draw，如果棋盘已经下满且无法分出胜负。

题解

简单模拟

代码

using namespace std; #define INVALID puts("illegal"), exit(0) string A[3]; bool isOne (const char& c){return c == 'X';} bool isTwo (const char& c){return c == '0';} bool isEmpty(const char& c){return c == '.';} inline int type(const char& c){return isOne(c) ? 1 : (isTwo(c) ? 2 : 0);} inline bool same(const char& c1, const char& c2, const char& c3){return (type(c1) == type(c2)) && (type(c1) == type(c3));} inline bool Win(const char& c1, const char& c2, const char& c3){return (type(c1) == type(c2)) && (type(c1) == type(c3)) && type(c1);} int main() { cin >> A[0] >> A[1] >> A[2]; int c = 0, One= 0, two = 0, ansCount = 0; for (int i=0; i<3; i++) for (int j=0; j<3; j++){one += isOne(A[i][j]); two += isTwo(A[i][j]);} if ((one - two != 0) && (one - two != 1)) INVALID; if (Win(A[0][0], A[0][1], A[0][2])){++ansCount; c = type(A[0][0]);} if (Win(A[1][0], A[1][1], A[1][2])){++ansCount; c = type(A[1][0]);} if (Win(A[2][0], A[2][1], A[2][2])){++ansCount; c = type(A[2][0]);} if (Win(A[0][0], A[1][0], A[2][0])){++ansCount; c = type(A[0][0]);} if (Win(A[0][1], A[1][1], A[2][1])){++ansCount; c = type(A[0][1]);} if (Win(A[0][2], A[1][2], A[2][2])){++ansCount; c = type(A[0][2]);} if (Win(A[0][0], A[1][1], A[2][2])){++ansCount; c = type(A[0][0]);} if (Win(A[0][2], A[1][1], A[2][0])){++ansCount; c = type(A[0][2]);} // if (ansCount > 2) INVALID; if (c == 1) puts("the first player won"), exit(0); if (c == 2) puts("the second player won"), exit(0); if (one + two == 9) puts("draw"), exit(0); if (One== two + 1) puts("second"), exit(0); if (One== two) puts("first"), exit(0); INVALID; return 0; }

Day1 T4 小 X 与煎饼达人 (Dif 2)

题面

长度为 $n$ 的 $01$ 串，初始全 $0$，$m$ 次区间取反，问最后有多少个 $1$ .

$1\le n\le 10^6$，$1\le m\le 10^5$ .

题解

差分维护前缀 xor 和 .

线段树也能过 .

代码

using namespace std; const int N = 1145141; int n, m, a[N], t[N]; int main() { scanf("%d%d", &n, &m); int l, r; while (m--) { scanf("%d%d", &l, &r); t[r] ^= 1; t[l-1] ^= 1; } int ans = 0; for (int i=0; i<=n; i++) a[i] = a[i-1] ^ t[i]; for (int i=0; i<=n; i++) ans += (a[i]); printf("%d\n", ans); return 0; }

Day2 T1 小W与书架 (Dif 1)

题面

小 W 新买了一个书架，宽度为 $L$ .

小 W 想要在书架上从左往右放上书，书：

黑色：宽度为 $1$ 或 $h$ .

白色：宽度为 $1$ .

放书，必须黑白交替放，并且最左最右必须是黑色，问方案数，对 $998244353$ 取模 .

$2\le h\le L\le 10^6$ .

题解

暴力线性递推 .

你愿意叫它 dp 也行，时间复杂度 $O(L)$ .

代码

using namespace std; const int N = 1e6 + 500, P = 998244353; int L, h, _[N], ans; inline int& dp(int x){return _[x + (11^45^14)];} int main() { scanf("%d%d", &L, &h); dp(-1) = 1; for (int i=1; i<=L; i++) { if (i > 0) dp(i) = (dp(i) + dp(i-2)) % P; if (i > h-1) dp(i) = (dp(i) + dp(i-h-1)) % P; ans = (ans + dp(i)) % P; } printf("%d\n", ans); return 0; }

Day2 T2 小W与命题 (Dif 2)

题面

$n$ 个命题，若干个推出关系 $P\Rightarrow Q$，推出关系不成环 .

现在要选出最少的公理，推出所有命题 . 算出最少的公理个数和每个命题至少需要几步才能被推出 .

题解

拓扑排序板子

代码

using namespace std; const int N = 514114; int n, m, in[N], dis[N]; bool vis[N]; vector g[N]; inline void addedge(int u, int v){g[u].emplace_back(v); ++in[v];} inline void toposort() { queue q; for (int i=1; i<=n; i++) if (!in[i]) q.push(i), vis[i] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) if (!vis[v]){vis[v] = true; q.push(v); dis[v] = dis[u] + 1;} } } int main() { scanf("%d%d", &n, &m); for (int i=1, u, v; i<=m; i++) scanf("%d%d", &u, &v), addedge(u, v); int cc = 0; for (int i=1; i<=n; i++) if (!in[i]) ++cc; printf("%d\n", cc); for (int i=1; i<=n; i++) if (!in[i]) printf("%d ", i); puts(""); toposort(); for (int i=1; i<=n; i++) printf("%d ", dis[i]); puts(""); return 0; }

Day2 T3 小W与选座 (Dif 6, $\color{red}{*}$)

题面

题解

第一问非常平凡吧，Dif 2 .

考虑第二问，发现可以大力猜答案！大力猜想答案就是覆盖旅客数最多的区间覆盖的旅客数。具体证明可以用弦图，有兴趣的同学可以自行了解。这样用一个前缀和找一下覆盖最多的区间就行了。
—— Tutorial

经历千辛万苦，我还是不知道为啥是这样的 .

然后 APJ 说显然，我也不知道为啥 .

（原来是 Dif 10 的，后来斟酌了一下改成 Dif 6 了）

代码

using namespace std; const int N = 1145141; int n, m, s[N], t[N], s1[N], s2[N], s3[N], ans1, ans2; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) { scanf("%d%d", s+i, t+i); chkmax(m, t[i]); ++s1[s[i]]; --s1[t[i]]; ++s2[s[i]]; ++s3[t[i]-1]; } for (int i=1; i<=m; i++){s1[i] += s1[i-1]; s2[i] += s2[i-1]; s3[i] += s3[i-1];} for (int i=1; i<=n; i++) chkmax(ans1, s2[t[i] - 1] - s3[s[i] - 1]); for (int i=1; i<=m; i++) chkmax(ans2, s1[i]); printf("%d %d\n", ans1, ans2); return 0; }

Day2 T4 小W与施工 (Dif 8)

题面

一个无环流程图（含起点 $s$，终点 $t$ 的 DAG），$q$ 次询问，每次去掉一条边，问 $s$ 到 $t$ 的最短路是否发生改变

点数边数 $10^5$ 级别 .

题解

支配树口胡里也有这题做法 .

考虑 $s$ 到 $t$ 的最短路图，于是问题变成删边判连通性 .

这个可以 Tarjan 求割边，也可以 DAG 上支配树（注意支配树只能判支配点，需要给每个边建虚点才能判“支配边”），都能过 .

~~不是你普及模拟赛出这玩意？？？~~

Dif 8 的原因是有 Tarjan 做法 .

代码

又臭又长的代码环节（荣获倒数第二长代码，5KB）

代码中整了个边去重，虽然可能没啥用吧 .

~~代码中 same_of 应为 be same as~~

using namespace std; typedef pair pii; typedef long long ll; const int N = 114514, M = N; const ll INF = 1e18; int n, m, q, s, t; unsigned deg[N]; struct Graph { typedef vector

> _; _ g[N]; inline void addedge(int u, int v, ll w){g[u].emplace_back(make_pair(v, w));} inline void ade(int u, int v, ll w){addedge(u, v, w); addedge(v, u, w);} inline _ operator [] (const unsigned& id)const{return g[id];} inline _& operator [] (const unsigned& id){return g[id];} inline void clear(){for (int i=0; i}G, revG; struct uGraph { vector g[N]; inline void addedge(int u, int v){g[u].emplace_back(v); ++deg[v];} inline void ade(int u, int v){addedge(u, v); addedge(v, u);} inline vector operator [] (const unsigned& id)const{return g[id];} inline vector& operator [] (const unsigned& id){return g[id];} inline void clear(){for (int i=0; i}S, D; struct Edge { int u, v, w; Edge(int p, int q){u = p; v = q; w = 114514;} Edge() = default; ~Edge() = default; inline bool operator <(const Edge& rhs)const { if (u == rhs.u) { if (v == rhs.v) return w else return v } return u } inline pii toPair()const{return make_pair(u, v);} inline bool same_of(const Edge& rhs)const{return this->toPair() == rhs.toPair();} }; struct HT { set

x; inline void insert(const pii& _){x.insert(_);} inline bool exists(const pii& _)const{return x.find(_) != x.end();} }sEdge; static Edge ed[M], red[M]; map

eNode; namespace SSSP { vector dis1, dis2, MAX_VEC; inline bool init_v() { MAX_VEC.resize(N); for (int i=0; i return true; } bool vis[N], __R__ = init_v(); inline void spfa(Graph g, vector& dis, int x) { memset(vis, false, sizeof vis); queue q; vis[x] = true; dis = MAX_VEC; dis[x] = 0; q.push(x); while (!q.empty()) { int u = q.front(); q.pop(); for (auto e : g[u]) { int v = e.first, w = e.second; if (dis[v] > dis[u] + w){dis[v] = dis[u] + w; if (!vis[v]) q.push(v), vis[v] = true;} } vis[u] = false; } } inline void create() { memset(deg, 0, sizeof deg); spfa(G, dis1, s); spfa(revG, dis2, t); for (int u=1; u<=n; u++) for (auto e : G[u]) { int v = e.first, w = e.second; if (dis1[u] + w + dis2[v] == dis1[t]) { ++n; S.addedge(u, n); S.addedge(n, v); eNode[make_pair(u, v)] = n; } } } } namespace DAG_DoT { HT onDoT; int dep[N], f[N][22]; inline int lca(int u, int v) { if (dep[u] for (int i=20; i>=0; i--) if (dep[f[u][i]] >= dep[v]) u = f[u][i]; if (u == v) return u; for (int i=20; i>=0; i--) if (f[u][i] != f[v][i]){u = f[u][i]; v = f[v][i];} return f[u][0]; } inline void topsort() { queue q; for (int i=1; i<=n; i++) if (!deg[i]){q.push(i); f[i][0] = 0;} else f[i][0] = -1; while (!q.empty()) { int u = q.front(), fa = f[u][0]; q.pop(); D.addedge(fa, u); dep[u] = dep[fa] + 1; for (int i=1; i<=20; i++) f[u][i] = f[f[u][i-1]][i-1]; for (int v : S[u]) { --deg[v]; if (!deg[v]) q.push(v); if (f[v][0] == -1) f[v][0] = u; else f[v][0] = lca(f[v][0], u); } } } bool mark[N], dnow = false; inline void dfs(int u) { mark[u] = true; if (u == t){dnow = true; return ;} for (int v : D[u]) dfs(v); if (dnow) return ; mark[u] = false; } } inline void InputGraph() { scanf("%d%d%d%d%d", &n, &m, &q, &s, &t); for (int i=0; i stable_sort(ed, ed+m); int ptr = 0, u, v, w; for (int i=0; i { u = ed[i].u; v = ed[i].v; w = ed[i].w; if (!i){G.addedge(u, v, w); revG.addedge(v, u, w); continue;} if (ed[ptr].same_of(ed[i])) { if (ed[ptr].w == ed[i].w){sEdge.insert(ed[ptr].toPair()); sEdge.insert(ed[i].toPair());} continue; } ptr = i; G.addedge(u, v, w); revG.addedge(v, u, w); } } int main() { #ifndef ONLINE_JUDGE // freopen("i.in", "r", stdin); // Sample 1 freopen("j.in", "r", stdin); // Sample 2 #endif InputGraph(); SSSP::create(); DAG_DoT::topsort(); DAG_DoT::dfs(s); for (int i=1, x; i<=q; i++) { scanf("%d", &x); int u = red[x].u, v = red[x].v; if (sEdge.exists(make_pair(u, v))) puts("NO"); else if (DAG_DoT::mark[eNode[make_pair(u, v)]]) puts("YES"); else puts("NO"); } return 0; }

Day3 T1 早锻炼 (Dif 1)

题面

$2\times n$ 的 01 矩阵，求一个最长的 $2\times m$ 全 0 矩形，输出其 0 的个数 .

$1\le n\le 100$ .

题解

naive .

（此题是经典入门题）

代码

const int N = 114514; int n; bool a[N]; int main() { scanf("%d", &n); for (int i=1, x, y; i<=n; i++){scanf("%d%d", &x, &y); a[i] = !x & !y;} int ans = 0, x = 0; for (int i=1; i<=n; i++) { if (a[i]) ++x; else chkmax(ans, x), x = 0; } printf("%d\n", 2 * max(ans, x)); return 0; }

Day3 T2 围栏高度 (Dif 1)

题面

长度为 $n$ 的序列 $a_{1\dots n}$，求极差最小的序列 $b_{1\dots n}$，满足对于严格大于半数个 $i\in[1,n]\cap \mathbb Z$，有 $\{a\}$ 中存在 $b_i$ .

$1\le n\le 10000$ .

题解

贪心策略，排序后选连续半数个即可 .

代码

const int N = 114514; int n, a[N], ans = 2e9; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%d", a+i); sort(a+1, a+1+n); int p = n / 2; for (int l=1; l<=n; l++) { int r = l + p; if (r > n) break; chkmin(ans, a[r] - a[l]); } printf("%d\n", ans); return 0; }

Day3 T3 最接近的分数 (Dif 1)

题面

给一个浮点数 $x$ 和一个整数 $n$，要求找到一个有理数 $\alpha = \dfrac pq$，满足：

$p, q$ 在 $[1, n]\cap \mathbb Z$ 中 .

$|\alpha - x|$ 最小 .

在此前提下，$p$ 最小 .

输出 $p,q$ .

$1\le n\le 10^7$ .

题解

由于 $n$ 只有 $10^7$，于是我们可以枚举分母算出分子来然后统计答案 .

考虑分数的约分性质，可以发现只要 $p$ 最小等价于 $q$ 最小啥的，这说明我们咋枚举都无所谓 .

代码

int n, p, q; double x, ans; int main() { scanf("%d%lf", &n, &x); ans = 1e9; if (abs(x) for (int i=1, m; i<=n; i++) { double _ = x * i, d1, d2; m = max(1., min(1. * n, floor(_))); if (abs(1. * m / i - x) m = max(1., min(1. * n, ceil(_))); if (abs(1. * m / i - x) } printf("%d\n%d", q, p); return 0; }

Day3 T4 Prime Path (Dif 2)

题面

给定两个四位数 $n, m$ . 保证 $n$ 是素数 .

每次能改变 $n$ 中的一个数字，每次改变后的 $n$ 也必须是素数 . (首位不能改成 $0$)

求最少经过多少次改变能使 $n$ 变成 $m$，如果无法改变或 $m$ 是合数输出 -1 .

题解

处理出素数，可以转移就连边，因为边权都为 $1$ 所以可以 BFS .

注意替换成 $0$ 的情况 .

代码

其实有些地方可以打表，我也比较乐意打表的 .

只不过原因有二：

NOI Linux 1.0 比较鬼畜，洛谷在线 IDE 上给列表隐藏了不能编辑，Gedit 一修改就卡的不行，只能 killall 掉 ...

zroi 有代码长度限制，此类打表长度优化强度通常不高（此原因有可能作废）

最终只打了一个素数列表，没打判断素数的表 .

using namespace std; const int N = 114514; const int plist[] = {/*此处应有所有四位素数*/}; int n, m, dis[N]; bool vis[N]; vector g[N]; inline void addedge(int u, int v){g[u].push_back(v);} inline bool isprime(int x) { static bool isp[N], vis[N]; if (vis[x]) return isp[x]; vis[x] = true; if (x == 1) return false; for (int i=2; i*i<=x; i++) if (!(x % i)) return false; return isp[x] = true; } inline int cnum(int a, int b, int c, int d){return a * 1000 + b * 100 + c * 10 + d;} void bfs(int s) { memset(dis, 0x3f, sizeof dis); memset(vis, 0, sizeof vis); queue q; q.push(s); dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); if (vis[u]) continue; vis[u] = true; for (int v : g[u]) { if (vis[v]) continue; q.push(v); dis[v] = min(dis[v], dis[u] + 1); } } } int main() { scanf("%d%d", &n, &m); if (!isprime(m)) puts("-1"), exit(0); for (int x : plist) { int a = x / 1000, b = x / 100 % 10, c = x / 10 % 10, d = x % 10; for (int r=0; r<=9; r++) { int newn = 114514; if (r && (r != a) && isprime(newn = cnum(r, b, c, d))) addedge(x, newn); if ((r != b) && isprime(newn = cnum(a, r, c, d))) addedge(x, newn); if ((r != c) && isprime(newn = cnum(a, b, r, d))) addedge(x, newn); if ((r != d) && isprime(newn = cnum(a, b, c, r))) addedge(x, newn); } } bfs(n); if (dis[m] == dis[0]) puts("-1"); else printf("%d\n", dis[m]); return 0; }

Day4 T1 装牛奶 (Dif 1)

题面

给定 $a,b$，求 $\max\{\{c=ax+by\mid x\in \mathbb N, y\in \mathbb N\}\cap[0, m]\}$ .

$1\le m\le 1000$ .

题解

~~这题好啊~~ .

但是 $m\le 1000$，所以我们只能被迫暴力喽（

代码是 $O(m^2)$ 的，暴力可以被优化到 $O(m)$ .

代码

x,y 的枚举上界可以紧到 x/a，x/b .

int a, b, m, ans; inline int smart(int x){return x > m ? 0 : x;} int main() { scanf("%d%d%d", &a, &b, &m); for (int x=0; x<=m; x++) for (int y=0; y<=m; y++) chkmax(ans, smart(unsigned(a*x + b*y))); printf("%d\n", ans); return 0; }

Day4 T2 圆形牛棚 (Dif 1)

题面

一个序列 $\{a_n\}$，找到一个循环移位 $\{b_n\}$，使得

\[w(\{b\})=\sum_{i=1}^n(i-1)b_i

\]

最小，输出这个 $w(\{b\})$ .

$3\le n\le 1000$，$a_i\le 100$ .

题解

暴力枚举每个 $\{b\}$ 然后把它的 $w$ 取 min .

Bonus：存在 $O(n)$ 做法（考虑一次移位产生的贡献）.

代码

const int N = 114514; int n, a[N], minn = 1919810; int main() { scanf("%d", &n); for (int i=0; i int ans = 114514u*1919810u, now = 0; for (int pos=0; pos { for (int i=0; i chkmin(ans, now); now = 0; } printf("%d\n", ans); return 0; }

Day4 T3 奶牛拍照 (Dif 2)

题面

一个序列 $\{a_n\}$，找最长子串使得和是 $7$ 的倍数 .

$n\le 50000$，$a_i\le 10^6$ .

题解

前缀和，找模 $7$ 同余的点 .

是不是扫两遍就完了，$O(n)$ .

代码

using namespace std; const int N = 114514; int n, a[N], lst[N], fst[N], ans; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%d", a+i), a[i] = (a[i] + a[i-1]) % 7; for (int i=n; i>=1; i--) fst[a[i]] = i; for (int i=1; i<=n; i++) lst[a[i]] = i; for (int i=0; i<=7; i++) chkmax(ans, lst[i] - fst[i]); printf("%d\n", ans); return 0; }

Day4 T4 愤怒的奶牛 (Dif 3)

题面

$n$ 个数轴上的点 $\{x_i\}$，有一个 $R$，有 $k$ 个炸弹，丢到 $x$ 会炸 $[x-R,x+R]$ .

给定 $n,k$，问 $R$ 至少是多少才能炸掉所有点 .

$n\le 50000$，$k\le 10$，$x_i\le 10^9$ .

题解

$k\le 10$ 是诈骗的 .

二分答案，贪心 check 即可，$O(d\log n)$，$d=\max\{x_i\}-\min\{x_i\}$ .

代码

using namespace std; const int N = 114514; int n, k, a[N]; inline bool check(int r) { int cut = 1; r *= 2; for (int i = 1, pos = 1; i <= n; i++) if (a[i] - a[pos] > r){++cut; pos = i;} return cut <= k; } int main() { scanf("%d%d", &n, &k); for (int i=1; i<=n; i++) scanf("%d", a+i); sort(a+1, a+1+n); int l = 0, r = 1e9, ans = -114514; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)){r = mid - 1; ans = mid;} else l = mid + 1; } printf("%d\n", ans); return 0; }

Day5 T1 排序 (Dif 2)

题面

给一个序列 $\{a_n\}$，问是否能通过一次区间翻转让序列有序（不降） .

$n\le 10^7$ .

题解

扫两遍，找到第一个破坏点，然后翻转过来判断即可 .

代码

using namespace std; const int N = 1e7+114514; int n, l, r, a[N]; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%d", a+i); for (int i=1; i<=n; i++) if (a[i] for (int i=n; i>=1; i--) if (a[i] reverse(a+l, a+1+r); if (is_sorted(a+1, a+1+n)) puts("YES"); else puts("NO"); return 0; }

Day5 T2 方差 (Dif 2)

题面

区间方差，答案乘 $(r-l+1)^2$，$n,q\le 10^6$，$a_i\le 10^3$ .

题解

方差的一种经典转换就是平方的均值减均值的平方，直接前缀和即可 .

代码

using namespace std; typedef long long ll; const int N = 114514; int n, q, a[N]; ll s[N], sqr[N]; int main() { scanf("%d%d", &n, &q); for (int i=1; i<=n; i++){scanf("%d", a+i); s[i] = s[i-1] + a[i]; sqr[i] = sqr[i-1] + a[i] * a[i];} int l, r; while (q--) { scanf("%d%d", &l, &r); --l; // 此处如果脑抽地把 l 减一区间长度就是 r-l 了！！！！！！！ printf("%lld\n", (sqr[r] - sqr[l]) * (r - l) - (s[r] - s[l]) * (s[r] - s[l])); } return 0; }

Day5 T3 车票 (Dif 6)

题面

$k$ 天，每天都有车，车的规则见 Day2 T3 中第二种 .

问每天需要多少票 .

$k\le 50$ .

题解

Day2 T3 $\times k$ ver.

代码

using namespace std; const int N = 1145141; int n, m, k, s[55][N], ans1; int main() { scanf("%d%d%d", &m, &n, &k); for (int i=1, p, q, r; i<=n; i++) { scanf("%d%d%d", &p, &q, &r); ++s[p][q]; --s[p][r]; } for (int i=1, ans; i<=k; i++) { for (int j=1; j<=m; j++) chkmax(ans, s[i][j] += s[i][j-1]); printf("%d\n", ans); ans = 0; } return 0; }

Day5 T4 回家 (Dif 3)

题面

无权图 $s$ 到 $t$ 最短路个数，答案 mod $p$ .

$n,m\le 10^6$，$p\le 10^8$ .

题解

无权图感觉可能有漂亮做法？？？

最后一个 SPFA 糊上就过了，naive .

代码

using namespace std; const int N = 1145141; vector g[N]; inline void addedge(int u, int v){g[u].emplace_back(v);} int n, m, s, t, p; int dis[N], cnt[N]; bool vis[N]; inline void spfa(int s) { memset(dis, 0x3f, sizeof dis); queue q; q.push(s); vis[s] = true; dis[s] = 0; cnt[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dis[v] == dis[u] + 1) cnt[v] = (cnt[v] + cnt[u]) % p; if (dis[v] > dis[u] + 1){dis[v] = dis[u] + 1; cnt[v] = cnt[u]; if (!vis[v]) q.push(v), vis[v] = true;} } vis[u] = false; } } int main() { scanf("%d%d%d%d%d", &n, &m, &p, &s, &t); for (int i=1, u, v; i<=m; i++) scanf("%d%d", &u, &v), addedge(u, v); spfa(s); printf("%d\n", cnt[t]); return 0; }

Day6 T1 【19普转提2】除草机(Dif 1)

题面

多组数据，每次问一个 $n\times m$ 的方阵，设计一条曲线经过所有点，至少需要多少次转弯 .

最多 $50000$ 组数据，$n,m\le 10^6$ .

题解

答案很显然，就是 $2\cdot\min\{n-1,m-1\}$ .

代码

using namespace std; const int N = 1145141; vector g[N]; inline void addedge(int u, int v){g[u].emplace_back(v);} int n, m; int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); printf("%d\n", 2 * min(n-1, m-1)); } return 0; }

Day6 T2 【19普转提2】收集隔膜 (Dif 6, $\color{red}{*}$)

题面

一个序列 $\{a_n\}$ 和一个序列 $\{w_n\}$，找 $1,2,3,\dots,n$ 的上升子序列使得：

其 $a$ 值上升

其 $w$ 值和不小于 $k$（$k$ 给定）

问方案数 .

$n\le 40$，$a_i,w_i\le 10^9$，$k\le 10^{11}$ .

题解

想了一年没想出来，最后看题解发现他妈的是折半搜索 .

震撼 . 这就是 $n\le 40$ 吗 .

考虑把一个状态 $\{s\}$ 分为两半，这样分别只有 $20$ 的量，直接 $O(2^n)$ 爆搜即可 .

假设左边的和是 $s_L$ 最大值是 $m_L$，右边的和是 $s_R$ 最小值是 $m_R$ .

于是状态合法即他俩能合并当且仅当 $s_L+s_R\ge k$ 且 $m_L\le m_R$，这非常显然吧 .

分别爆搜，把 $m_R$ 相同的合到一起，组内排序，只有 $O(n)$ 种不同的 $m_R$ .

显然每次右边合法的是一个后缀，因为排过序了，所以直接 lower_bound 就完了 .

时间复杂度 $O(\text{能过})$ .

代码

Day6 T3 【19普转提2】翻转序列 (Dif 3)

题面

一个长度为 $n$ 的排列 $\{a\}$，翻转一个区间 $[l,r]$，使得这个排列的不动点最多 .

不动点指的是 $a_i=i$ 的点 .

$n\le 5\times 10^5$ .

题解

找翻转中心，相同的并到一起统计即可 .

细节较多，反正我调了挺长时间的 .

我的做法多个 $\log$，于是荣获最慢解/cy

代码

using namespace std; const int N = 1e6+500, INF = 0x3f3f3f3f; typedef long long ll; int n, a[N], fp[N], cc; vector pc[N]; struct magic { __gnu_pbds ::tree, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> s; inline void insert(int x){s.insert(x);} inline int query(int l, int r){return s.order_of_key(r+1) - s.order_of_key(l);} }pcv[N]; int main() { scanf("%d", &n); for (int i=1, _; i<=n; i++) { scanf("%d", a+i); _ = a[i] + i; if (a[i] ^ i) pc[_].emplace_back(max(a[i], i)), pcv[_].insert(i); fp[i] = fp[i-1] + (a[i] == i); } int ans, cc; ans = cc = fp[n]; for (int i=1, l, r; i<=n*2; i++) { int s = pc[i].size(), x = (i & 1) ? 0 : i / 2; for (int _ : pc[i]) { l = i - _; r = _; chkmax(ans, pcv[i].query(l, r) + cc - (fp[r] - fp[l-1] - fp[x] + fp[x-1])); } } printf("%d\n", ans); return 0; }

Day6 T4 【19普转提2】树 (Dif 5, $\color{blue}{*}$)

题面

$n$ 个节点的树 .

给两个序列 $\{a\},\{b\}$，给树的每条边定向，使得 $\forall i\in[1,m]\cap\mathbb Z$，有要么从 $a_i$ 能到 $b_i$，要么从 $b_i$ 能到 $a_i$ .

输出方案数，对 $10^9+7$ 取模 .

$n\le 3\times 10^5$ .

题解

显然等价于树上一堆链然后找连通块个数吧 .

开始考虑的树上差分，但是会有两条链端点重合但是不相交的情况，难以判断，随机化做正确率又太低 .

题解的做法非常的牛逼啊牛逼 .

[马上补，绝对不鸽]

代码

Day7 T1 【PY题】异或 (Dif 3)

题面

给定 $l,r$ 求

\[\sum_{i=l}^r\sum_{i=l}^r(i\oplus j)

\]

其中 $\oplus$ 是异或 .

$0\le l,r\le 10^9$

题解

按位考虑贡献

代码

using namespace std; const int P = 1e9+7; int l, r; inline int calc(int n, int k) { if (n <0) return 0; int ans = 0; for (int i = 1<<30; i>k; i>>=1) if (n & i) ans += (i >> 1); if (n & k) ans += (n & (k - 1)) + 1; return ans; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &l, &r); int ans = 0; for (int i=1; i<=r; i<<=1) ans = (ans + 1ll * (calc(r, i) - calc(l-1, i)) % P *((r - l + 1 - calc(r, i) + calc(l-1, i)) % P) % P * i % P + P) % P; printf("%d\n", 2ll * ans % P); } return 0; }

Day7 T2 【PY题】取石子 (Dif 5, $\color{blue}*$)

题面

有三堆石子，个数分别为 $x,y,z$ .

Alice 和 Bob 博弈，Alice 先手，轮流操作 .

每次操作选择若干堆石子，从中各取出相同数量的石子（不能一个都不取）. 不能操作的人失败 .

判定先手是否必胜 .

$1\le x,y,z\le 300$，最多 $500$ 组数据 .

题解

代码

Day7 T3 【PY题】优化 (Dif 5)

题面

时空限制：2s / 512 MB .

有一个整数序列 $\{a_n\}$，选 $k$ 个不相交的连续子区间，从左到右记它们的和为 $s_{1\dots k}$ .

最大化

\[S=\sum_{i=1}^{k-1}|s_i-s_{i+1}|

\]

输出最大的 $S$ 即可 .

$n\le 3\times 10^4$，$k\le \min(n,200)$，$|a_i|\le 10^4$ .

题解

代码

Day8 T1 【19普转提 4】和 (Dif 1)

题面

题解

代码

Day8 T2 【19普转提4】串串 (Dif 1)

题面

题解

代码

Day8 T3 【19普转提 4】简单函数 (Dif 1)

题面

题解

代码

Day8 T4 【19普转提 4】简单MST (Dif 2)

题面

题解

代码

Day29 T1 「良心普及组」鸡兔同笼 (Dif 1)

题面

多头蛇有三个头与两个腿，而小精灵只有一个头，没有腿 . 现在给定所有头的数量与所有腿的数量，请你输出多头蛇的数量与小精灵的数量 .

无解输出 -1 .

题解

小学数学题

代码

using namespace std; int a, b; int main() { scanf("%d%d", &a, &b); if ((b <0) || (b & 1) || (a - b / 2 * 3 <0)){puts("-1"); return 0;} printf("%d %d\n", b / 2, a - b / 2 * 3); return 0; }

Day29 T2 「良心普及组」凉心出题人黄队 (Dif 2)

题面

题解

模拟

代码

using namespace std; const int N = 1e6+500; int n, v[N]; template class pool { unordered_map pol; unsigned cc; public: pool(){cc = 0;} ~pool() = default; unsigned get(T x) { auto ptr = pol.find(x); if (ptr == pol.end()){pol[x] = ++cc; return cc;} else return ptr -> second; } unsigned size()const{return cc;} void clear(){cc = 0; pol.clear();} }; pool P; int main() { scanf("%d", &n); for (int i=1, a, b; i<=n; i++){scanf("%d%d", &a, &b); v[P.get(a)] += b;} int s = P.size(); sort(v+1, v+1+s); if (s & 1) printf("%d\n", v[(s+1)/2] * 2); else printf("%d\n", v[s/2] + v[s/2+1]); return 0; }