当前位置：首页 > news >正文

noip9

news 2026/4/11 23:27:11

11.16

感觉大家这场挂分比较严重啊，我都到rk4了。

顺带一提，这场是原场，洛谷上都有原题（但数据太水了，不如原数据）

t1

模拟题。

赛时没算时间复杂度，用了个set以为对了，赛后才发现若卡满还不如暴力跳（多个log）。

发现列数很少但行数很多，而对于每次从头向下落，前面有大部分重复的路径。

于是我们记录路径，每次从底向上即可。

（其实说难听点就是直接模拟换种实现方式，但保证复杂度）

code

#include <bits/stdc++.h>
#define pir pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e4 + 10;
int n, m, k, tot[40];
char c[30010][40];
int path[40][N][2];inline void work(int pos)
{while (tot[pos] > 1 && c[path[pos][tot[pos]][0]][path[pos][tot[pos]][1]] != '.') // 每次回退path[pos][tot[pos]][0] = path[pos][tot[pos]][1] = 0, --tot[pos];int x = path[pos][tot[pos]][0], y = path[pos][tot[pos]][1];while (1){bool f = 0;while (c[x][y] == '.')++x;--x;++tot[pos];path[pos][tot[pos]][0] = x;path[pos][tot[pos]][1] = y;if (c[x + 1][y] == 'X'){c[x][y] = 'O';// cout << "x=" << x << " y=" << y << " c=" << c[x][y] << "\n";break;}if (c[x][y - 1] == '.' && c[x + 1][y - 1] == '.')--y;else if (c[x][y + 1] == '.' && c[x + 1][y + 1] == '.')++y;else{f = 1;c[x][y] = 'O';}if (f)break;}
}signed main()
{freopen("kamen.in", "r", stdin);freopen("kamen.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> m >> k;for (int i = 0; i <= m + 1; ++i)for (int j = 0; j <= k + 1; ++j)c[i][j] = 'X';for (int i = 1; i <= m; ++i)for (int j = 1; j <= k; ++j)cin >> c[i][j];for (int i = 1; i <= k; ++i){++tot[i];path[i][tot[i]][0] = 1;path[i][tot[i]][1] = i;}cin >> n;for (int i = 1, x; i <= n; ++i){cin >> x;work(x);}for (int i = 1; i <= m; ++i, cout << "\n")for (int j = 1; j <= k; ++j)cout << c[i][j];return 0;
}

t2

赛时50pts,原数据下只有28pts。

数据过水导致的。

容易发现，将图拓扑排序后不在图上的点均无解。

易证，不解释。

对于剩下部分，我们用贪心思想。

先将限制降序排序，然后此时就可能确定这条边的入点的答案（若此点出度为1）。

之后类似拓扑排序思想，将出度为0的点压入队列更新所有相连的点，同时按降序对每条边更新点。

只需对遍历过的边打标记即可保证复杂度。

即有点更新又有边根更新可能感觉很乱，看代码理解一下。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
struct edge
{int u, v, lim, val;
} a[N];
vector<int> e[N];
bool vis[N];
int cd[N], ans[N];
queue<int> q;inline bool cmp(edge a, edge b)
{return a.lim > b.lim;
}signed main()
{freopen("merchant.in", "r", stdin);freopen("merchant.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; ++i){cin >> a[i].u >> a[i].v >> a[i].lim >> a[i].val;++cd[a[i].u];}sort(a + 1, a + 1 + m, cmp);memset(ans, 0x3f, sizeof(ans));for (int i = 1; i <= m; ++i) // 入边的编号e[a[i].v].emplace_back(i);for (int i = 1; i <= n; ++i)if (!cd[i])q.push(i);for (int i = 1; i <= m; ++i){while (q.size()){int x = q.front();q.pop();for (auto k : e[x]) // 边的编号{if (vis[k])continue;vis[k] = 1;--cd[a[k].u];if (!cd[a[k].u])q.push(a[k].u);if (ans[x] != inf)ans[a[k].u] = min(ans[a[k].u], max(ans[a[k].v] - a[k].val, a[k].lim));}}if (!vis[i]){vis[i] = 1;--cd[a[i].u];if (!cd[a[i].u])q.push(a[i].u);ans[a[i].u] = min(ans[a[i].u], a[i].lim);}}for (int i = 1; i <= n; ++i)cout << (ans[i] == inf ? -1 : ans[i]) << ' ';return 0;
}

t3

神秘构造题。

赛时10:00左右开始犯困，大脑紊乱。

于是看题面看了0.5h。

只会15pts简单部分。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, w;
int c[N][N], b[N][N];inline void solve1()
{if (c[0][1] + b[0][1] < w){cout << "NO";exit(0);}int tot = (n - 1) * 2;cout << tot << "\n";int u = 0;for (int i = 1; i <= n - 1; ++i){cout << u << ' ' << u + 1 << ' ' << b[0][1] << "\n";++u;}u = 0;for (int i = 1; i <= n - 1; ++i){cout << u << ' ' << u + 1 << ' ' << w - c[0][1] << "\n";++u;}exit(0);
}signed main()
{freopen("bike.in", "r", stdin);freopen("bike.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> w;// cout << "n=" << n << " w=" << w << "\n";int c1 = 0, b1 = 0;bool bj1 = 0, bj2 = 0;for (int i = 1; i < n; ++i)for (int j = 0; j < i; ++j){cin >> c[j][i];c1 = c[0][1];if (c[j][i] != c1)bj1 = 1;// cout << "j=" << j << " i=" << i << " c=" << c[j][i] << "\n";}for (int i = 1; i < n; ++i)for (int j = 0; j < i; ++j){cin >> b[j][i];b1 = b[0][1];if (b[j][i] != b1)bj2 = 1;// cout << "j=" << j << " i=" << i << " b=" << b[j][i] << "\n";}// for (int i = 1; i < n; ++i, cout << "\n")//     for (int j = 0; j < i; ++j)//     {//         cout << c[j][i] << " ";//     }// for (int i = 1; i < n; ++i, cout << "\n")//     for (int j = 0; j < i; ++j)//     {//         cout << b[j][i] << " ";//     }if (!bj1 && !bj2)solve1();cout << "No\n";// cout << "bj1=" << bj1 << " bj2=" << bj2 << "\n";return 0;
}