您的位置: 首页  >  IT文章  >  牛客国庆集训派对Day6 Solution

牛客国庆集训派对Day6 Solution

分类: IT文章 • 2025-01-09 08:24:50

A    Birthday

思路：设置一个源点，一个汇点，每次对$源点对a_i, b_i , a_i 对 b_i 连一条流为1，费用为0的边$

每个点都再连一条 1, 3, 5, 7, ....的边到汇点之间，因为每多加一个流的费用，然后就是最小费用最大流

  1 #include<bits/stdc++.h>
  2  
  3 using namespace std;
  4  
  5 const int INF = 0x3f3f3f3f;
  6  
  7 const int maxn = 1010;
  8 const int maxm = 10010;
  9  
 10 struct Edge{
 11     int to, nxt, cap, flow, cost;
 12 }edge[maxm];
 13  
 14 int head[maxn], tot;
 15 int pre[maxn], dis[maxn];
 16 bool vis[maxn];
 17 int N;
 18  
 19 void Init(int n)
 20 {
 21     N = n;
 22     tot = 0;
 23     memset(head, -1, sizeof head);
 24 }
 25  
 26 void addedge(int u, int v, int cap, int cost)
 27 {
 28     edge[tot].to = v;
 29     edge[tot].cap = cap;
 30     edge[tot].cost = cost;
 31     edge[tot].flow = 0;
 32     edge[tot].nxt = head[u];
 33     head[u] = tot++;
 34  
 35     edge[tot].to = u;
 36     edge[tot].cap = 0;
 37     edge[tot].cost = -cost;
 38     edge[tot].flow = 0;
 39     edge[tot].nxt = head[v];
 40     head[v] = tot++;
 41 }
 42  
 43 bool SPFA(int s, int t)
 44 {
 45     queue<int>q;
 46     for(int i = 0; i < N; ++i)
 47     {
 48         dis[i] = INF;
 49         vis[i] = false;
 50         pre[i] = -1;
 51     }
 52     dis[s] = 0;
 53     vis[s] = true;
 54     q.push(s);
 55     while(!q.empty())
 56     {
 57         int u = q.front();
 58         q.pop();
 59         vis[u] = false;
 60         for(int i = head[u]; ~i; i = edge[i].nxt)
 61         {
 62             int v = edge[i].to;
 63             if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
 64             {
 65                 dis[v] = dis[u] + edge[i].cost;
 66                 pre[v] = i;
 67                 if(!vis[v])
 68                 {
 69                     vis[v] = true;
 70                     q.push(v);
 71                 }
 72             }
 73         }
 74     }
 75     if(pre[t] == -1) return false;
 76     else return true;
 77 }
 78  
 79 int solve(int s,int t)
 80 {
 81     int flow = 0 ;
 82     int cost = 0;
 83     while(SPFA(s, t))
 84     {
 85         int Min = INF;
 86         for(int i = pre[t]; ~i; i = pre[edge[i ^ 1].to])
 87         {
 88             Min = min(Min, edge[i].cap - edge[i].flow);
 89         }
 90         for(int i = pre[t]; ~i; i = pre[edge[i ^ 1].to])
 91         {
 92             edge[i].flow += Min;
 93             edge[i ^ 1].flow -= Min;
 94             cost += edge[i].cost * Min;
 95         }
 96         flow += Min;
 97     }
 98     return cost;
 99 }
100  
101 int n, m;
102  
103 int main()
104 {
105     while(~scanf("%d %d", &n, &m))
106     {
107         Init(n + m + 2);
108         int s = 0, t = n + m + 1;
109         for(int i = 1; i <= n; ++i)
110         {
111             int u, v;
112             scanf("%d %d", &u, &v);
113             addedge(0, i, 1, 0);
114             addedge(i, u + n, 1, 0);
115             addedge(i, v + n, 1, 0);
116         }
117         for(int i = n + 1; i <= n + m; ++i)
118         {
119             for(int j = 1; j < 100; j += 2)
120             {
121                 addedge(i, t, 1, j);
122             }
123         }
124         int cost = solve(0, n + m + 1);
125         printf("%d
", cost);
126     }
127     return 0;
128 }
View Code

B    Board

思路一：考虑 $a[x], b[x]$ 分别表示第x行加了多少， 第x列加了多少 那么 $arr[x][y]$ 就可以表示成 $a[x] + b[y]$ 那么 就可以通过找一个点来解，比如说找一个点$x_1, y_1$ 那么 $a[x] + b[y] = a[x] + b[y_1] + a[x_1] + b[y] - a[x_1] - b[x_1] = arr[x][y_1] + arr[x_1][y] - arr[x_1][y_1]$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define N 1010
 5  
 6 int n;
 7 int arr[N][N];
 8  
 9 int Move[4][2] =
10 {
11     -1, -1,
12      1,  1,
13     -1,  1,
14      1, -1,
15 };
16  
17 bool ok(int x, int y)
18 {
19     if (x < 1 || x > n || y < 1 || y > n) return false;
20     return true;
21 }
22  
23 int main()
24 {
25     while (scanf("%d", &n) != EOF)
26     {
27         int x, y;
28         for (int i = 1; i <= n; ++i)
29             for (int j = 1; j <= n; ++j)
30             {
31                 scanf("%d", &arr[i][j]);
32                 if (arr[i][j] == -1)
33                     x = i, y = j;
34             }
35         if (n == 1)
36             printf("%d
", arr[1][1] == -1 ? 0 : arr[1][1]);
37         else
38         {
39             for (int i = 0; i < 4; ++i)
40             {
41                 int nx = x + Move[i][0];
42                 int ny = y + Move[i][1];
43                 if (ok(nx, ny))
44                 {
45                     printf("%d
", arr[x][ny] + arr[nx][y] - arr[nx][ny]);
46                     break;
47                 }
48             }
49         }
50     }
51     return 0;
52 }
View Code

思路二：考虑分成n块，包含n行n列，那么每次对每一列加上一个数或者对每一行加上一个数，相当于对n块都加上了，也就是说，这n个块最后相加的数是相同的，然后就可以求解

 1 #include<bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 #define N 1010
 6  
 7 int n;
 8 int arr[N][N];
 9 int sum[N];
10 int x, y;
11  
12 int main()
13 {
14     while(~scanf("%d", &n))
15     {
16         memset(sum, 0, sizeof sum);
17         for(int i = 1; i <= n; ++i)
18         {
19             for(int j = 1; j <= n; ++j)
20             {
21                 scanf("%d", &arr[i][j]);
22                 if(arr[i][j] != -1) sum[(i + j) % n] += arr[i][j];
23                 else x = i, y = j;
24             }
25         }
26         int tmp = (x + y) % n;
27         int ans = 0;
28         if(tmp != 0)
29         {
30             ans = sum[0] - sum[tmp];
31         }
32         else
33         {
34             ans = sum[1] - sum[tmp];
35         }
36         printf("%d
", ans);
37     }
38     return 0;
39 }
View Code

C    Circle

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 
 6 int main()
 7 {
 8     while (scanf("%d", &n) != EOF)
 9         printf("%d
", n);
10     return 0;
11 }
View Code

D    土龙弟弟

留坑。

E    Growth

思路：考虑将$x, y 分别离散  dp[x][y]$ 表示 $a_i, b_i 到达 x, y $的状态 的时候可以拿到多少奖励了

$value[x][y] 表示的是 到达x并且到达y 的奖励一共有多少$

$dp[i][j] = max(dp[i][j - 1] + value[i][j - 1] *(yy[j] -  yy[j - 1]), dp[i - 1][j] + value[i - 1][j] * (xx[i] - xx[i - 1]));$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define N 1010
 5 #define ll long long
 6  
 7 int n, mx, my;
 8 ll m;
 9 int xx[N], yy[N], zz[N];
10 ll dp[N][N], value[N][N];
11  
12 struct node
13 {
14     int x, y, z;
15     void scan(int i)
16     {
17         scanf("%d%d%d", &x, &y, &z);
18         xx[i] = x; yy[i] = y;
19     }
20 }arr[N];
21  
22 void Init()
23 {
24     sort(xx + 1, xx + 1 + n);
25     sort(yy + 1, yy + 1 + n);
26     mx = unique(xx + 1, xx + 1 + n) - xx - 1;
27     my = unique(yy + 1, yy + 1 + n) - yy - 1;
28     memset(dp, 0, sizeof dp);
29     memset(value, 0, sizeof value);
30     for (int i = 1; i <= n; ++i)
31     {
32         arr[i].x = lower_bound(xx + 1, xx + 1 + mx, arr[i].x) - xx;
33         arr[i].y = lower_bound(yy + 1, yy + 1 + my, arr[i].y) - yy;
34         value[arr[i].x][arr[i].y] += arr[i].z;
35     }
36 }
37  
38 int main()
39 {
40     while (scanf("%d%lld", &n, &m) != EOF)
41     {
42         for (int i = 1; i <= n; ++i) arr[i].scan(i); Init();
43         for (int i = 1; i <= mx; ++i)
44         {
45             for (int j = 1; j <= my; ++j)
46             {
47                 value[i][j] += value[i - 1][j] + value[i][j - 1] - value[i - 1][j - 1];
48             }
49         }
50         for (int i = 1; i <= mx; ++i)
51         {
52             for (int j = 1; j <= my; ++j)
53             {
54                 dp[i][j] = max(dp[i][j], dp[i - 1][j] + value[i - 1][j] * (xx[i] - xx[i - 1]));
55                 dp[i][j] = max(dp[i][j], dp[i][j - 1] + value[i][j - 1] * (yy[j] - yy[j - 1]));
56             }
57         }
58         ll ans = 0;
59         for (int i = 1; i <= mx; ++i)
60         {
61             for (int j = 1; j <= my; ++j)
62             {
63                 if(xx[i] + yy[j] <= m) ans = max(ans, dp[i][j] + value[i][j] * (m - xx[i] - yy[j] + 1));
64             }
65         }
66         printf("%lld
", ans);
67     }
68     return 0;
69 }
View Code

F    kingdom

留坑。

G    Matrix

留坑。

H    Mountain

水。

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 #define N 1010
 6  
 7 int n;
 8 int arr[N];
 9  
10 int main()
11 {
12     while(~scanf("%d", &n))
13     {
14         for(int i = 1; i <= n; ++i)  scanf("%d", arr + i);
15         int ans = 0;
16         for(int i = 1; i <= n; ++i)
17         {
18             ans = max(ans, arr[i]);
19         }
20         ans = ans * 2;
21         printf("%d
", ans);
22     }
23     return 0;
24 }
View Code

I    清明梦超能力者黄YY

思路：树链剖分维护u->v 路径上染色次数，倒着操作，每次找有没有第k次染色的点，有的话拿出来更新的答案，并且把那个点的然后次数置位-INF, 每个点最多拿出来一次

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3  
  4 #define N 100010
  5 #define INF 0x3f3f3f3f
  6  
  7 int n, m, k;
  8 vector <int> G[N];
  9 int ans[N];
 10  
 11 struct QUE
 12 {
 13     int u, v, c;
 14     void scan()
 15     {
 16         scanf("%d%d%d", &u, &v, &c);
 17     }
 18 }que[N];
 19  
 20 int top[N], fa[N], deep[N], num[N], p[N], fp[N],son[N], pos;
 21  
 22 void Init()
 23 {
 24     memset(son, -1, sizeof son);
 25     pos = 0;
 26     fa[1] = 1, deep[1] = 0;
 27 }
 28  
 29 void DFS(int u)
 30 {
 31     num[u] = 1;
 32     for (auto v : G[u]) if (v != fa[u])
 33     {
 34         fa[v] = u; deep[v] = deep[u] + 1;
 35         DFS(v); num[u] += num[v];
 36         if (son[u] == -1 || num[v] > num[son[u]])
 37             son[u] = v;
 38     }
 39 }
 40  
 41 void getpos(int u, int sp)
 42 {
 43     top[u] = sp;
 44     p[u] = ++pos;
 45     fp[pos] = u;
 46     if (son[u] == -1) return;
 47     getpos(son[u], sp);
 48     for (auto v : G[u]) if (v != son[u] && v != fa[u])
 49         getpos(v, v);
 50 }
 51  
 52 struct SEG
 53 {
 54     struct node
 55     {
 56         int l, r;
 57         int lazy, Max, pos;
 58         node () {}
 59         node (int _l, int _r)
 60         {
 61             l = _l, r = _r;
 62             Max = 0;
 63             pos = _l;
 64             lazy = 0;
 65         }
 66     }a[N << 2];
 67  
 68     void pushup(int id)
 69     {
 70         if (a[id << 1].Max > a[id << 1 | 1].Max)
 71         {
 72             a[id].Max = a[id << 1].Max;
 73             a[id].pos = a[id << 1].pos;
 74         }  
 75         else
 76         {
 77             a[id].Max = a[id << 1 | 1].Max;
 78             a[id].pos = a[id << 1 | 1].pos;
 79         }
 80     }
 81  
 82     void pushdown(int id)
 83     {
 84         if (a[id].l >= a[id].r) return;
 85         if (a[id].lazy)
 86         {
 87             int lazy = a[id].lazy; a[id].lazy = 0;
 88             a[id << 1].lazy += lazy;
 89             a[id << 1 | 1].lazy += lazy;
 90             a[id << 1].Max += lazy;
 91             a[id << 1 | 1].Max += lazy;
 92         }
 93     }
 94  
 95     void build(int id, int l, int r)
 96     {
 97         a[id] = node(l, r);
 98         if (l == r) return;
 99         int mid = (l + r) >> 1;
100         build(id << 1, l, mid);
101         build(id << 1 | 1, mid + 1, r);
102         pushup(id);
103     }
104  
105     void update(int id, int l, int r, int val)
106     {
107         if (a[id].l >= l && a[id].r <= r)
108         {
109             a[id].Max += val;
110             a[id].lazy += val;
111             return;
112         }
113         pushdown(id);
114         int mid = (a[id].l + a[id].r) >> 1;
115         if (l <= mid) update(id << 1, l, r, val);
116         if (r > mid) update(id << 1 | 1, l, r, val);
117         pushup(id);
118     }
119 }segtree;
120  
121 void change(int u, int v, int val)
122 {
123     int fu = top[u], fv = top[v];
124     while (fu != fv)
125     {
126         if (deep[fu] < deep[fv])
127         {
128             swap(fu, fv);
129             swap(u, v);
130         }
131         int l = p[fu], r = p[u];
132         segtree.update(1, l, r, 1);
133         while (1)
134         {
135 //          puts("bug");
136             if (segtree.a[1].Max < k) break;
137             int pos = segtree.a[1].pos;
138 //          cout << pos << " " << segtree.a[1].Max << endl;
139             ans[fp[pos]] = val;
140             segtree.update(1, pos, pos, -INF);
141 //          cout << pos << " " << segtree.a[1].Max << endl;
142         }
143         u = fa[fu], fu = top[u];
144     }
145     if (deep[u] > deep[v]) swap(u, v);
146     int l = p[u], r = p[v];
147 //  printf("%d %d
", l, r);
148     segtree.update(1, l, r, 1);
149     while (1)
150     {
151         if (segtree.a[1].Max < k) break;
152         int pos = segtree.a[1].pos;
153 //      cout << pos << endl;
154         ans[fp[pos]] = val;
155 //      cout << segtree.a[1].pos << " " << segtree.a[1].Max << endl;
156         segtree.update(1, pos, pos, -INF);
157 //      cout << segtree.a[1].pos << " " << segtree.a[1].Max << endl;
158 //      puts("...................");
159     }
160 }
161  
162 int main()
163 {
164     while (scanf("%d%d%d", &n, &m, &k) != EOF)
165     {
166         Init();
167         for (int i = 1, u, v; i < n; ++i)
168         {
169             scanf("%d%d", &u, &v);
170             G[u].push_back(v);
171             G[v].push_back(u);
172         } DFS(1), getpos(1, 1);
173 //      for (int i = 1; i <= n; ++i) printf("%d %d %d
", i, p[i], fp[i]);
174         for (int i = 1; i <= m; ++i) que[i].scan();
175         memset(ans, 0, sizeof ans);
176         segtree.build(1, 1, n);
177         for (int i = m; i >= 1; --i) change(que[i].u, que[i].v, que[i].c);
178         for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], " 
"[i == n]);
179     }
180     return 0;
181 }
View Code

J    最短路

思路一（应该不是正解）：对于环内的点，拿出来，分别跑Dijkstra, 这样的点数应该在100左右，然后每次询问的时候更新答案。但是有一点奇怪的是，用并查集找出环内的点，就不会T，标记访问直接DFS找就会T。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 using pii = pair <int, int>;
  4  
  5 #define N 101010
  6  
  7 const int INF = 0x3f3f3f3f;
  8  
  9 template <class T>
 10 inline bool scan_d(T &ret)
 11 {
 12     char c; int sgn;
 13     if (c = getchar(), c == EOF) return 0;
 14     while (c != '-' && (c < '0' || c > '9')) c = getchar();
 15     sgn = (c == '-') ? -1 : 1;
 16     ret = (c == '-') ? 0 : (c - '0');
 17     while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
 18     ret *= sgn;
 19     return 1;
 20 }
 21  
 22 inline void out(int x)
 23 {
 24     if (x / 10) out(x / 10);
 25     putchar(x % 10 + '0');
 26 }
 27  
 28 vector <int> G[N];
 29 int vis[N], deep[N], stk[N], top;
 30  
 31 struct ST
 32 {
 33     int mm[N << 1];
 34     int dp[N << 1][20];
 35     int rmq[N << 1];
 36     int F[N << 1], P[N], cnt;
 37  
 38     void Init(int n)
 39     {
 40         mm[0] = -1;
 41         for (int i = 1; i <= n; ++i)
 42         {
 43             mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
 44             dp[i][0] = i;
 45         }
 46         for (int j = 1; j <= mm[n]; ++j)
 47             for (int i = 1; i + (1 << j) - 1 <= n; ++i)
 48                 dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];
 49     }
 50  
 51     int query(int a, int b)
 52     {
 53         if (a > b) swap(a, b);
 54         int k = mm[b - a + 1];
 55         return rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k];
 56     }
 57  
 58     void DFS(int u, int fa)
 59     {
 60         F[++cnt] = u;
 61         rmq[cnt] = deep[u];
 62         P[u] = cnt;
 63         vis[u] = 1;
 64         for (auto v : G[u]) if (v != fa)
 65         {
 66             if (vis[v])
 67             {
 68                 stk[++top] = v;
 69                 continue;
 70             }
 71             deep[v] = deep[u] + 1;
 72             DFS(v, u);
 73             F[++cnt] = u;
 74             rmq[cnt] = deep[u];
 75         }
 76     }
 77  
 78     void init(int root, int node_num)
 79     {
 80         cnt = 0;
 81         deep[1] = 0;
 82         DFS(root, root);
 83         Init(2 * node_num - 1);
 84     }
 85  
 86     int query_lca(int u, int v)
 87     {
 88         return F[query(P[u], P[v])];
 89     }
 90 }st;
 91  
 92 int n, m;
 93 int dis[210][N];
 94 queue <int> q;
 95  
 96 void Dijkstra(int it, int st)
 97 {
 98     for (int i = 1; i <= n; ++i)
 99     {
100         vis[i] = 0;
101         dis[it][i] = INF;
102     }
103     dis[it][st] = 0;
104     q.push(st);
105     while (!q.empty())
106     {
107         int u = q.front(); q.pop();
108         if (vis[u]) continue;
109         vis[u] = 1;
110         for (auto v : G[u])
111         {
112             if (dis[it][v] > dis[it][u] + 1)
113             {
114                 dis[it][v] = dis[it][u] + 1;
115                 q.push(v);
116             }
117         }
118     }
119 }
120  
121 vector <pii> tmp;
122  
123 int pre[N];
124  
125 int find(int x)
126 {
127     if (x != pre[x])
128         pre[x] = find(pre[x]);
129     return pre[x];
130 }
131  
132 void Run()
133 {
134     while (scan_d(n), scan_d(m))
135     {
136         for (int i = 1; i <= n; ++i) pre[i] = i; top = 0;
137         for (int i = 1, u, v; i <= m; ++i)
138         {
139             scan_d(u), scan_d(v);
140             int fu = find(u), fv = find(v);
141             if (fu == fv)
142             {
143                 tmp.emplace_back(u, v);
144                 stk[++top] = u;
145             }
146             else
147             {
148                 G[u].push_back(v);
149                 G[v].push_back(u);
150                 pre[fu] = fv;
151             }
152         }
153         st.init(1, n); 
154         sort(stk + 1, stk + 1 + top);
155         int nn = unique(stk + 1, stk + 1 + top) - stk - 1;
156         for (auto it : tmp)
157         {
158             G[it.first].push_back(it.second);
159             G[it.second].push_back(it.first);
160         }
161         for (int i = 1; i <= nn; ++i) Dijkstra(i, stk[i]);
162         int q;
163         scan_d(q);
164         while (q--)
165         {
166             int u, v;
167             scan_d(u), scan_d(v);
168             int root = st.query_lca(u, v);
169             int ans = deep[u] + deep[v] - 2 * deep[root];
170             for (int i = 1; i <= nn; ++i)
171                 ans = min(ans, dis[i][u] + dis[i][v]);
172             out(ans), putchar('
');
173         }
174     }
175 }
176 int main()
177 {
178     #ifdef LOCAL
179         freopen("Test.in", "r", stdin);
180     #endif
181  
182     Run();
183     return 0;
184 }
View Code

K    排序

留坑。

相关推荐