好老的题了，但是还是很有做头的。
总结
- 不吸氧看来确实是没法用
stl的啊（set常数太大了，开O2也没过） SPFA没认真学，觉得有堆优化Dijkstra就天下无敌了，今天负边权教我做人- 于是苦逼的只有180分
- 第一题我看错了，想了10分钟，本来打算打暴力50分，然后又看对了。 /(ㄒoㄒ)/~~
- 后来发现其实打Bellman-Ford可以拿下40分，但是我没有认真想（何况Floyd算法也可以）
小奇挖矿
题目分析
我们发现这道题每个操作只对其后面又影响，然后我们想到DP要求的无后效性，于是我们直接倒着DP一下就好了。
（最重要的是这道题有取东西的顺序）
代码
#include#include using namespace std;#define forn(i) for(int i=1;i<=n;++i)const int maxn = 1e5 + 10;int opt[maxn], a[maxn];int main() { freopen("explo.in","r",stdin); freopen("explo.out","w",stdout); double n, k, c, w; cin >> n >> k >> c >> w; forn(i) cin >> opt[i] >> a[i]; double p_1 = 1-0.01*k; double p_2 = 1+0.01*c; double ans = 0; for (int i = n; i; -- i) if (opt[i] & 1) ans = max(ans, ans * p_1 + a[i]); else ans = max(ans, ans * p_2 - a[i]); printf("%.2lf", ans*w); return 0;}
小奇的数列
题目分析
emmm，这道题暴力都可以70分。我怕不吸氧set过不了，于是写了个70的部分分，然后写了个stl版正解
70pts： 首先根据抽屉原理，如果询问长度 \(\ge q\) 那就必有前缀和模\(q\)相等，或者这个数本身被\(q\)整除，然后因为\(q \le 200\)直接\(n ^ 2\)暴力
100pts： 考虑已经定下来一端，我们只需要寻找另外一段，是的他们的差值最小就行了，于是自然的写出二分。维护的话，考虑平衡树，或者set都可以。
代码
set版
#include#include #include using namespace std;typedef long long qword;#define pb push_back#define forn(i) for(int i=1;i<=n;++i)#define rep(i,s,t) for(int i=(int)(s);i<=(int)(t);++i)int n, m;const int maxn = 5e5 + 10;int a[maxn];qword sum[maxn];inline void Init() { cin >> n >> m; forn(i) cin >> a[i]; forn(i) sum[i] = sum[i - 1] + a[i];}qword mod(qword x, int p) { x %= p; while (x < 0) x += p; return x % p;}inline void work() { int L, R, Q; qword ans; while (m--) { cin >> L >> R >> Q; ans = Q; if (R - L >= Q) {cout << 0 << endl; continue;} rep(i,L,R) rep(j,i,R) ans = min(ans, mod(sum[j] - sum[i - 1],Q)); cout << ans << endl; }}inline void solve() { int L, R, Q; qword ans; while (m--) { cin >> L >> R >> Q; ans = Q; if (R - L + 1 >= Q) {cout << 0 << endl; continue;} set s; s.insert(0); rep(i,L,R) { qword w = mod(sum[i] - sum[L - 1], Q); set ::iterator it = s.upper_bound(w); if (it != s.begin()) --it; ans = min(ans, mod(w - *it, Q)); s.insert(w); } cout << ans << endl; }}#define OKint main() {#ifdef OK freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); ios::sync_with_stdio(0);#endif // OK Init(); if(n <= 100000 && m<=10000) work(); else solve();}
小奇会地球
题意
给一个有负边的n个点的图，如果能给全图边权同时加上（或减去）一个值t，问图中1到n的最短路距离非负时的最小距离。
题目解析
首先跑有负边图的最短路只能SPFA。
由于t和答案同增同减，具有单调性。我们可以二分t来取符合条件的最小距离。
如果通过负环不能到达n号点，这个负环实际上可以忽略。
所以开头建反边，从n跑dfs看能到达哪些点，只对这些点跑最短路即可。
复杂度\(O(Tn^2logt)\)
代码
#include#include #include #include #include #include #define rep(i,s,t) for(int i = (int)(s); i <= (int)(t); ++ i)#define seta(a,x) memset (a, x, sizeof (a))#define tral(i) for(int i=h[u];i+1;i=e[i].nxt)typedef long long qword;using namespace std;const int mod=1e9+7,N=305;struct Edge{int to,nxt,w;}e[N*N];struct dat{int u,v,w;}a[N*N];int h[N],n,m,cnt,dis[N],mn,mx,num[N];bool vis[N],viss[N];queue Q;inline void add( int u, int v, int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}inline int SPFA(int x) { rep(i,1,n) dis[i] = 1e9, num[i] = 0, vis[i] = 0; while(!Q.empty()) Q.pop(); Q.push(1); vis[1] = 1; dis[1] = 0; while(!Q.empty()) { int u=Q.front();Q.pop(); tral(i) { int v = e[i].to; if(!viss[v]) continue; if(dis[v] > dis[u]+e[i].w+x) { if((++num[v]) > n) return -1e9; dis[v] = dis[u]+e[i].w+x; if(!vis[v]) vis[v] = 1, Q.push(v); } } vis[u] = 0; } return dis[n];}inline void dfs(int u) { viss[u] = 1; tral(i) { int v = e[i].to; if(viss[v]) continue; dfs(v); }}int main() { int T; cin >> T; while(T--) { seta(h, -1); cnt = 0; mn = 1e9; mx = -1e9; cin >> n >> m; rep(i,1,m) { cin >> a[i].u >> a[i].v >>a[i].w; add(a[i].v, a[i].u, a[i].w); mn = min(mn, a[i].w); mx = max(mx, a[i].w); } dfs(n); seta(h, -1); cnt = 0; rep(i,1,m) add(a[i].u, a[i].v, a[i].w); if(SPFA(-mn + 100) == 1e9) {cout << "-1" << endl;continue;} int l = -mx, r = -mn, ans = 0; while(l <= r) { int mid = l+r >> 1, check = SPFA(mid); if(check >= 0) ans = check,r = mid-1; else l = mid+1; } cout << ans << endl; } return 0;}