时间：2023-06-23 21:18:01 | 来源：网站运营
时间：2023-06-23 21:18:01 来源：网站运营
第46届ICPC澳门站 AEFK：A
在线咨询
// Problem: So I'll Max Out My Constructive Algor...// Contest: NowCoder// URL: https://ac.nowcoder.com/acm/contest/31454/A// Memory Limit: 1048576 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>#define endl '/n'#define pb push_backusing namespace std;using ll = long long;using db = double;using pii = pair<int , int>;const int mod = 1e9 + 7;const int maxn = 2e5 + 10;int a[100][110];void solve(){ int n, i, j; cin >> n; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) cin >> a[i][j]; a[n + 1][1] = a[n + 1][n] = mod; int sum = 0; vector <int> ans; a[n + 1][0] = a[n + 1][n] = 0; for (i = 1; i <= n; i++) { if (i & 1) { for (j = 2; j <= n; j++) sum += (a[i][j] < a[i][j - 1]); sum += (a[i][n] > a[i + 1][n]); } else { for (j = n - 1; j; j--) sum += (a[i][j] < a[i][j + 1]); sum += (a[i][1] > a[i + 1][1]); } } for (i = 1; i <= n; i++) { if (i & 1) for (j = 1; j <= n; j++) ans.pb(a[i][j]); else for (j = n; j; j--) ans.pb(a[i][j]); } if (sum >= (n * n + 1) / 2) { for (auto i : ans) cout << i << ' '; } else { reverse(ans.begin(), ans.end()); for (auto i : ans) cout << i << ' '; } cout << endl;}int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) solve(); return 0;}K// Problem: Link-Cut Tree// Contest: NowCoder// URL: https://ac.nowcoder.com/acm/contest/31454/K// Memory Limit: 1048576 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>#define endl '/n'#define pb push_backusing namespace std;using ll = long long;using db = double;using pii = pair<int , int>;const int mod = 1e9 + 7;const int maxn = 2e5 + 10;pii e[maxn];int bj[maxn];int val[maxn];bool vis[maxn];int find(int num){ if (num != bj[num]) bj[num] = find(bj[num]); return bj[num];}vector <pii> ed[maxn];vector <int> ans;bool dfs(int num, int d, int en){ if (en == num) return true; for (auto [u, v] : ed[num]) { if (vis[u] || v >= d) continue; vis[u] = 1; if (dfs(u, d, en)) { ans.pb(v); return 1; } } return 0;}void solve(){ int n, m, i, j, u, v; cin >> n >> m; for (i = 1; i <= n; i++) ed[i].clear(); for (i = 1; i <= m; i++) { cin >> u >> v; val[i] = i; e[i] = {u, v}; ed[u].pb({v, i}); ed[v].pb({u, i}); } for (i = 1; i <= n; i++) bj[i] = i, vis[i] = 0; for (i = 1; i <= m; i++) { int u = e[i].first, v = e[i].second; int x = find(u), y = find(v); if (x != y) bj[x] = y; else { ans.clear(); vis[e[i].first] = 1; dfs(e[i].first, i, e[i].second); ans.pb(i); sort(ans.begin(), ans.end()); for (auto t : ans) cout << t << ' '; cout << endl; return; } } cout << -1 << endl;}int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) solve(); return 0;}F// Problem: Sandpile on Clique// Contest: NowCoder// URL: https://ac.nowcoder.com/acm/contest/31454/F// Memory Limit: 1048576 MB// Time Limit: 4000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>#define endl '/n'#define pb push_backusing namespace std;using ll = long long;using db = double;using pii = pair<int , int>;const int mod = 1e9 + 7;const int maxn = 5e5 + 10;ll a[maxn];struct node{ ll id; ll val; bool operator < (const node & p) const { return val < p.val; }};void solve(){ ll n, i, j, m; cin >> n; priority_queue<node> p; ll sum = 0; for (i = 1; i <= n; i++) { cin >> a[i]; p.push({i, a[i]}); sum += a[i]; } if (sum > (n - 2) * n) { cout << "Recurrent" << endl; return; } if (n == 2) { cout << 0 << ' ' << 0 << endl; return; } ll tot = 0, cnt = 0; while (p.top().val + tot >= n - 1) { node t = p.top(); p.pop(); ll v = t.val + tot; ll k = v / (n - 1); t.val -= k * (n - 1); tot += k; t.val -= k; p.push(t); cnt++; if (cnt >= 10000000) { cout << "Recurrent" << endl; return; } } while (!p.empty()) { a[p.top().id] = p.top().val + tot; p.pop(); } for (i = 1; i <= n; i++) cout << a[i] << ' ';}int main(){ // ios::sync_with_stdio(false); // cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0;}E// Problem: Pass the Ball!// Contest: NowCoder// URL: https://ac.nowcoder.com/acm/contest/31454/E// Memory Limit: 1048576 MB// Time Limit: 6000 ms//// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>#define endl '/n'#define pb push_backusing namespace std;using ll = __int128;using db = double;using pii = pair<int, int>;const ll mod = 1231453023109121;const int maxn = 1e6 + 10;int to[maxn], vis[maxn];ll a[maxn], b[maxn];vector<ll> ans[maxn];namespace ntt{ const ll G = 3; ll n, m, L, R[maxn]; ll A[maxn], B[maxn]; ll qpow(__int128 a, ll b) { __int128 ans = 1; while (b > 0) { if (b & 1) ans = ans * a % mod; b >>= 1; a = a * a % mod; } return ans % mod; } void NTT(ll *a, int f) { for (int i = 0; i < n; i++) { if (i < R[i]) swap(a[i], a[R[i]]); } for (int i = 1; i < n; i <<= 1) { ll gn = qpow(G, (mod - 1) / (i << 1)); for (int j = 0; j < n; j += (i << 1)) { ll g = 1; for (int k = 0; k < i; k++, g = g * gn % mod) { ll x = a[j + k], y = g * a[j + k + i] % mod; a[j + k] = (x + y) % mod; a[j + k + i] = (x - y + mod) % mod; } } } if (f == 1) return; ll inv = qpow(n, mod - 2); reverse(a + 1, a + n); for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * inv % mod; } void solve(ll *A, ll *B) { m = n + m; L = 0; for (n = 1; n <= m; n <<= 1) L++; for (int i = 0; i < n; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1)); NTT(A, 1); NTT(B, 1); for (int i = 0; i < n; i++) A[i] = 1ll * A[i] * B[i] % mod; NTT(A, -1); } void clear(ll *A, ll *B) { for (int i = 0; i <= n; i++) R[i] = A[i] = B[i] = 0; L = 0; }} // namespace NTTvoid solve(){ int n, m, i, j, k; cin >> n >> m; for (i = 1; i <= n; i++) cin >> to[i]; for (i = 1; i <= n; i++) { if (!vis[i]) { int t = i, cnt = 0; b[cnt++] = i; vis[i] = 1; while (to[t] != i) { t = to[t]; vis[t] = 1; b[cnt++] = t; } for (j = 0; j < cnt; j++) a[j] = b[cnt - j - 1]; ntt::n = ntt::m = cnt; ntt::solve(a, b); if (ans[cnt].empty()) { ans[cnt].pb(a[cnt - 1]); for (j = cnt - 2; j >= 0; j--) ans[cnt].pb(a[j] + a[j + cnt]); } else { ans[cnt][0] += a[cnt - 1]; for (j = 1, k = cnt - 2; j < cnt; j++, k--) ans[cnt][j] += (a[k] + a[k + cnt]); } ntt::clear(a, b); } } vector <int> tr; for (i = 2; i <= n; i++) if (!ans[i].empty()) tr.pb(i); while (m--) { long long x, sum = 0; cin >> x; for (auto i : tr) sum += ans[i][x % i]; cout << sum << endl; }}int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0;}有什么不理解可以评论区留言关键词：澳门
