【2024.10.03】NOIP2024 赛前集训-刷题训练（5）
NOIP2017 提高组 小凯的疑惑
形式化题面：求最大的正整数 \(w\)，满足 \(ax + by = w\) 不存在一对非负整数解。
第一眼想到 \(exgcd\)，拿来分析一下：
因为 \(gcd(a,b) = 1\)，所以 \(\forall w \in \mathbb{N^+}\) 肯定都有解，但不一定 \(x, y\) 都是非负整数。
接着容易发现，当其中一个未知数的解为 \(-1\) 时，\(w\) 可能就不满足条件。
但这个条件只是必要的。举个例子 :
\[3 \times 8 + 7 \times (-1) = 21 = 3 \times (8 - 7) + 7 \times(-1 + 3) = 3 \times 1 + 7 \times 2
\]
于是我们发现当 \(y = -1\) 时，\(w\) 满足题目条件当且仅当 $ x \lt b$。从 \(exgcd\) 的通解求法来讲，就是不能通过 \(x+kb, y -kb\) 来构造出一组非负整数解。
那么 \(w = a \times (b - 1) + b \times (-1) = a \times b - a - b\)， 令 \(x = -1\) 推出来时一样的。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long ;
ll a, b;
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> a >> b;cout << a * b - a - b << '\n';return 0;
}
NOIP2017 提高组 时间复杂度
小模拟。把细节列出来认真写就好，耐得住性子总能找到缺陷调出来。
注意一下对时间复杂度的统计是遇到 F 就+ 1并更新 mx，遇到 E 就- 1。
借助 \(STL\) 可以省很多事。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long ;
int T;
int len, num, cnte, cntf, mx;
stack<pair<char, int>> stk;
map<char, int> mp;
char omiga[10000], type[10000], name[10000], x[10000], y[10000];
int change(char *a){if(a[0] == 'n') return 100000000;int val = 0;for(int i = 0; a[i]; ++i) val = val * 10 + a[0] - 48;return val;
}
int solve(){int ans = 2;cin >> len >> omiga;bool flag = 0;int answer = 0;num = 0;cnte = 0;cntf = 0;mx = 0;char stop = ' ';mp.clear();while(stk.size()) stk.pop();for(auto x:omiga){if(x == 'n') flag = 1;if(isdigit(x)){if(!flag) answer = 0;else answer = answer * 10 + x - 48;}}F(i, 1, len){cin >> type;if(type[0] == 'E'){if(ans == -1) continue;++cnte;if(cnte > cntf) {ans = -1;continue;}char nw = stk.top().first;int delta = stk.top().second;stk.pop();if(stop == nw) stop = ' ';if(!isalpha(stop) && delta > 100) -- num;mp[nw] = 0;}else{++cntf;cin >> name >> x >> y;if(ans == -1) continue;if(mp[name[0]] != 0) ans = -1;int delta = change(y) - change(x) + 1;mp[name[0]] = 1;stk.emplace(name[0], delta);if(isalpha(stop)) continue;if(delta > 100) mx = max(mx, ++num);if(delta <= 0) stop = name[0];}}if(ans == -1 || cnte != cntf) return -1;if(answer == mx) return 1;return 0;
}
signed main(){
// freopen("ex_complexity2.in","r",stdin);
// freopen("complexity.out","w",stdout);ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> T;while(T -- ){int ans = solve();if(ans == 1) cout << "Yes\n";else if(ans == 0) cout << "No\n";else cout << "ERR\n";}return 0;
}
NOIP2017 提高组 逛公园
第一步，找零环（小trick：先只连权值为 0 的边跑 \(tarjan\)）。
第二步，跑 \(dijkstra\)。
第三步，建反图记忆化搜索方案数。
我们记 \(f[i][j]\) 表示 \(1\) 到 \(i\) 的路径长为 \(dis[i] + j\) 的最短路，对于边 \((v, u, w)\)， 因为 \(dis[v] + w + j[v] = dis[u] + j[u]\)， 即 \(j[v] = dis[u] + j[u] - w - dis[v]\)， 有如下转移：
\[f[u][j] += f[v][dis[u] + j - w - dis[v]]
\]
注意初始化写完整，两张图的相关数组不要混用！
！！！自己疏忽的地方：\(f[1][0] = 1\)， 但 \(f[1][k] = 0\) 不一定成立，因为可以从某个点绕回 \(1\)， 这样 \(f[1][k]\) 就是有贡献的了。
积累 dp 统计方案的这个方法。（类似分层图）
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define mk make_pair
#define fi first
#define se second
#define index iiiiidx
using namespace std;
using ll = long long ;
const int N = 2e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct cat{ int u, v, w; }edge[N << 1];
struct node{ int v, w, ne; }e[N << 2], g[N << 2];ll dis[N], f[N][105];
bool vis[N];
priority_queue<pair<ll, int> >q;int first[N], idx = 0;
int head[N], index = 0;int dfn[N], low[N], scc[N], cnt = 0, num = 0;
bool ins[N];
stack<int> stk;int T, n, m, k, mod;void add(int x, int y, int z){ e[++idx] = (node){y, z, first[x]}; first[x] = idx; }
void ADD(int x, int y, int z){ g[++index] = (node){y, z, head[x]}; head[x] = index; }
void tarjan(int u, int f){dfn[u] = low[u] = ++cnt, stk.emplace(u), ins[u] = 1;for(int i = first[u];i ;i = e[i].ne){int v = e[i].v;if(!dfn[v]) tarjan(v, u),low[u] = min(low[u], low[v]);else if(ins[v]) low[u] = min(low[u], dfn[v]);}if(low[u] == dfn[u]){++num; int x, siz = 0;do{ x = stk.top();ins[x] = 0;scc[x] = num;stk.pop();++siz;}while(x != u);if(siz == 1) scc[x] = 0, --num;}
}
void dijkstra(int st){while(q.size()) q.pop();q.emplace(mk(0, st));dis[st] = 0;while(q.size()){int u = q.top().se; q.pop();if(vis[u]) continue;vis[u] = 1;for(int i = first[u]; i; i = e[i].ne){int v = e[i].v, w = e[i].w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.emplace(mk(-dis[v], v));}}}
}
ll dfs(int u, int k){if(scc[u]) return -1;if(u == 1 && k == 0) return f[u][k] = 1;if(f[u][k] != -1) return f[u][k];ll ret = 0;for(int i = head[u]; i; i = g[i].ne){int v = g[i].v, w = g[i].w;ll tmp = dis[u] + k - w - dis[v];if(tmp >= 0 && tmp <= k) {int delta = dfs(v, tmp);if(delta == -1) return -1;(ret += delta) %= mod;}}return f[u][k] = ret;
}
void init(){memset(dis, 0x3f, sizeof(dis));memset(f, -1, sizeof(f));memset(vis, 0, sizeof(vis));memset(first, 0, sizeof(first)); idx = 0;memset(head, 0, sizeof(head)); index = 0;memset(dfn, 0, sizeof(dfn)); cnt = 0; num = 0;memset(low, 0, sizeof(low));memset(scc, 0, sizeof(scc));memset(ins, 0, sizeof(ins));if(stk.size()) stk.pop();cin >> n >> m >> k >> mod;F(i, 1, m){int u, v, w;cin >> u >> v >> w;edge[i] = (cat){u, v, w};if(w == 0) add(u, v, w), ADD(v, u, w);}F(i, 1, n) if(!dfn[i]) tarjan(i, 0);
}
int solve(){F(i, 1, m){int u = edge[i].u, v = edge[i].v, w = edge[i].w;if(w != 0) add(u, v, w), ADD(v, u, w);}dijkstra(1);ll ans = 0;F(i, 0, k) {ll delta = dfs(n, i);if(delta == -1) return -1;(ans += delta) %= mod;}return ans;
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> T;while(T--){init();cout << solve() << '\n';}return 0;
}
NOIP2017 提高组 奶酪
前置知识：球之间位置关系的判定依据：圆心距 与 半径和的关系。
下文用 “相切” 代指 “相切或相交”。
算法1：并查集维护球之间的关系，\(O(Tn^2)\)。
算法2：先按 \(z\) 从小到大对所有圆心 \(a[i]\) 排序。另开一个数组 \(b\)，若当前 \(a[i]\) 与 某个 \(b[j]\) 相切或者与下表面相切，就放进 \(b\) 里面。最后只需要判断是否存在 \(b[i]\) 与上表面相切就行。时间严格弱于 \(O(Tn^2)\)。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define int ll
using namespace std;
using ll = long long ;
const int N = 1005;
int T;
int n, h, r, btop = 0;
__int128 base;
__int128 pw(__int128 x){return x * x;
}
struct node{int x, y, z;bool operator < (const node &o)const{return z < o.z;}__int128 operator - (const node &o)const{return pw(x - o.x) + pw(y - o.y) + pw(z - o.z);}
}a[N], b[N];
inline bool check(int nw){if(a[nw].z <= r) return 1;F(i, 1, btop) if(a[nw] - b[i] <= base) return 1;return 0;
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> T;while(T --){btop = 0;cin >> n >> h >> r;base = 4 * r * r;F(i, 1, n) cin >> a[i].x >> a[i].y >> a[i].z;sort(a + 1, a + n + 1);F(i, 1, n) if(check(i)) b[++ btop] = a[i];bool tag = 0;G(i, btop, 1) if(b[i].z >= h - r) {tag = 1; break;}if(tag) cout << "Yes\n";else cout << "No\n";}return 0;
}
