11.15赛氪补题

11.15赛氪补题(A,H还没补好)

小结

出了5题，排名124（大佬们都没参加，参加的都是弱校（或者是我们学校这样的中强校）叭）

//我们学校强队也几乎没参加，这是7~14队的选拔赛（为icpc准备的）

队友出了D题模拟（繁），F题和H题（图），我发现我连图都不会了，我是个铁fw。

我出了B题水题，还WA了一发，你敢信？（有个小细节码错了，呜呜

还有I题，这题大概就是想到是甚么个简化，就可以做出来

我们队伍由于数论不会，A题就没做出来。

一直在卡J题，一直在贪心，结果是网络流，不说网络流学的怎么样了，就根本没有想到用网络流做。

A题

题意

给出n,k， 输出$G_k(n)\%1e^9+7$

题解

B题 数位dp-dp

模拟，签到题

D题 兰德索尔杯-cup

题意

参加比赛的成员四人一组，在不同的赛道上进行跑步。下图 就是
跑步的一个场景： 可以看到，跑道上充满了一些特殊物件：加速阵、障碍物、魔物等等。这使得比
赛充满了乐趣（
在这道题目中，为了简化起见，我们可以认为每个人的跑步速度相同（其实本来就如此），且将跑道看
作是一个长度为 n的字符串。字符串上的每个位置代表了 1m的距离。不同的字符分别代表不同的地
形：
‘.’ ：代表平地，正常情况下，在平地上跑步速度1m/s
‘w’ ：代表水坑。正常情况下，在水坑上跑步速度为 0.5m/s。
‘>’ ：代表加速阵。所有人触碰到加速阵的瞬间，接下来5s 内跑步速度翻倍，之后这个格子变为
平地。注意，加速倍数和加速时间不能叠加。举例来说，如果当前加速时间剩余3s，此时又碰到
一个加速阵，加速时间重新变为5s。
‘s’ ：代表石块。所有人触碰到石块的瞬间都会被绊倒，在原地停留1s，之后这个格子变为平
地。
‘m’ ：代表魔物。所有人触碰到魔物的瞬间需要在原地停留 打败魔物，之后这个格子变为平
地。
现在，给出跑道的长度和每个跑道的地形，请输出每个人完成比赛的用时。

题解

模拟

技巧 时间都*2

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;
#define ll long long
const int MAX = 55;
const int MOD = 1e9 + 7;
double ans[5];int main() {int n;scanf("%d", &n);for(int kk = 1; kk <= 4; kk++) {string str;cin >> str;int len = str.length();int tmp = 0;int res = 0;for(int i = 0; i < len; i++) {if(str[i] == '.') {if(res >= 1) {res -= 1; tmp += 1;}else tmp += 2;}else if(str[i] == 'w') {if(res >= 2) {res -= 2; tmp += 2;}else if(res >= 1) {res -= 1; tmp += 3;} else tmp += 4;}else if(str[i] == '>') {res = 10;res -= 1; tmp += 1;}else if(str[i] == 's') {res = max(0, res - 2);tmp += 2;if(res >= 1) {res -= 1; tmp += 1;}else tmp += 2;}else {res = max(0, res - 4);tmp += 4;if(res >= 1) {res -= 1; tmp += 1;}else tmp += 2;}}ans[kk] = tmp;}for(int i = 1; i <= 4; i++) {printf("%.1f ", ans[i] / 2);}
}

F题 大数据分析-data

模拟，签到题

H题 最大化-max

题意

题解

I题 小x的好路-road

题意

有一个完全图，要求走任意次，每次路不能重复，把所有的边走完。

每次经过一个点时，这个点的权重是来路和去路两个路的权值最大

题解

其实对于每个点来说，（总共有奇数给点）。

找分成（n - 1） / 2个两条路，找最小的最大值之和。

即排序找第1，3，5，，，个点，相加权值。

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int maxn = 1e3 + 10;
vector<int> ans[maxn];int main() {int n;scanf("%d", &n);for(int i = 0; i < n * (n - 1) / 2; i++) {int a, b, w;scanf("%d%d%d", &a, &b, &w);a--, b--;ans[a].push_back(w);ans[b].push_back(w);}for(int i = 0; i < n; i++) {sort(ans[i].begin(), ans[i].end());}ll res = 0;for(int i = 0; i < n; i++) {for(int j = n - 2; j >= 0; j-=2) {res += ans[i][j];}}printf("%lld\n", res);
}

J题 染方块-color

题意

现在有一个 n x n 的方格，每一个格子是 X，O，或者 . ，而你 可以把 . 染成 X。

在你对你想染色的 . 进行染色之后，方格会有这样的变化：如果 一个 O 块上下左右都是 X，这个 O 就会变成 .

给定方格的初始状态，你现在可以对其进行符合条件的染色，求 空格最大能达到多少个。

题解

//为什么要用网络流？视频里说是题感，好叭

//我感觉他题解ppt有误，反正按照我的理解，码下来，可以过

• 最大流

• S -> O f = 1

• O -> . f = 1

• . -> T f = 1

• 答案：cnt(.) + cnt(O) - Maxflow

//答案为cnt(green)+cnt(绿色周围的白点)-maxflow。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;
#define SZ(v) (int)v.size()
const int MAX = 55;
const int INF = 1e9;
const int MAXN = 2e4 + 10;
const int MAXM = 2e5 + 10;namespace MaxFlow {struct Edge {int v, rev, f;Edge(int v, int rev, int f):v(v),rev(rev),f(f){}};int n, s, t;int cur[MAXM], dep[MAXN], gap[MAXN];int flow;std::vector<Edge> G[MAXN];void add_edge(int u, int v, int f) {G[u].push_back(Edge(v, SZ(G[v]), f));G[v].push_back(Edge(u, SZ(G[u]) - 1, 0));}int dfs(int u, int lim) {if (u == t) return lim;int num = 0, f;for (int &i = cur[u], v; i < SZ(G[u]); ++i) {if (dep[v = G[u][i].v] == dep[u] - 1 && (f = G[u][i].f))if (G[u][i].f -= (f = dfs(v, std::min(lim - num, f))),G[v][G[u][i].rev].f += f, (num += f) == lim)return num;}if (!--gap[dep[u]++]) dep[s] = n + 1;return ++gap[dep[u]], cur[u] = 0, num;}void init(int _n) {n = _n;for (int i = 0; i < n; ++i) G[i].clear();}void solve(int _s, int _t) {s = _s, t = _t, flow = 0;for (int i = 0; i <= n; ++i) cur[i] = dep[i] = gap[i] = 0;for (gap[0] = n; dep[s] <= n; flow += dfs(s, INF));}
}using MaxFlow::add_edge;int main() {int N;char mp[MAX][MAX];int cnt = 0;while(scanf("%s", mp[cnt]) != EOF) {cnt++;}N = strlen(mp[0]);int ans = 0;for(int i = 0; i < N; i++) {for(int j = 0; j < N; j++) {if(mp[i][j] == '.' || mp[i][j] == 'O') ans++;}} int s = N * N + 1, t = s + 1;MaxFlow::init(t + 1);for(int i = 0; i < N; i++) {for(int j = 0; j < N; j++) {if(mp[i][j] == 'O') {add_edge(s, i * N + j, 1);if(i - 1 >= 0 && mp[i - 1][j] == '.') add_edge(i * N + j, (i - 1) * N + j, 1);if(i + 1 <  N && mp[i + 1][j] == '.') add_edge(i * N + j, (i + 1) * N + j, 1);if(j - 1 >= 0 && mp[i][j - 1] == '.') add_edge(i * N + j, i * N + j - 1, 1);if(j + 1 <  N && mp[i][j + 1] == '.') add_edge(i * N + j, i * N + j + 1, 1);}if(mp[i][j] == '.') {add_edge(i * N + j, t, 1);}}} MaxFlow::solve(s, t);printf("%d\n", ans - MaxFlow::flow);
}

热身赛 B题

热身赛 B题

给几个链接，怕不小心关掉了
https://blog.csdn.net/bok_choy_/article/details/109698401
https://blog.csdn.net/qq_46672746/article/details/109736981
https://www.cnblogs.com/war1111/p/13993120.html
https://edu.saikr.com/course/557/task/3185/show