被稱作遺憾之物 爬滿了脊骨 又把控了痛楚 被稱作無用之物 修筑了唯一的通路
test30
前兩題都 0pts，nbm（？
2-A 飛船制造 (spaceship.cpp)
怎么有傻子沒開 c++11 寫了 rank 然后 re 惹 /fad
考慮依次枚舉 \(s=i+j+k\)，計算出 \(s\) 一定的方案數就能確定唯一的 \(s\)，方案數計算好像只能考慮背包。然后依次枚舉 \(i\)，計算出 \(s,i\) 一定時 \((j,k)\) 的方案數就能確定唯一的 \(i\)，方案數可以考慮 \(j\) 的上下界。然后依次枚舉 \(j\)，不斷增加排名直到符合題目要求即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=3000005;
int n, rk, f[3][N];
signed main() {
// freopen("1.txt","r",stdin);
freopen("spaceship.in","r",stdin);
freopen("spaceship.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> rk;
up(i,1,3*n) f[0][i]=f[0][i-1]+(i<=n);
up(i,1,3*n) f[1][i]=f[0][i-1]-(i-n-1>=0?f[0][i-n-1]:0);
up(i,1,3*n) f[1][i]+=f[1][i-1];
up(i,1,3*n) f[2][i]=f[1][i-1]-(i-n-1>=0?f[1][i-n-1]:0);
int counter=0;
up(s,3,3*n) {
int val=f[2][s];
if(counter+val>=rk) {
up(i,1,n) {
int l=max(1ll,s-i-n);
int r=min(n,s-i-1);
if(l<=r) {
if(counter+r-l+1>=rk) {
up(j,1,n) {
if(1<=s-i-j&&s-i-j<=n) {
if(++counter==rk) {
cout << i << ' ' << j << ' ' << s-i-j << '\n';
return 0;
}
}
}
}
counter+=r-l+1;
}
}
}
counter+=val;
}
return 0;
}
2-B 機器人 (robot.cpp)
怎么有人下發錯誤的 statement，謀害本可使爆零，以及這個原題“阻礙關系具有傳遞性”想何出什么樣的意味（？
發現 \(n\leq 1000\)，努力去想簡單暴力的辦法，考慮所有的可能的阻礙對 \((i,j,t)\) 表示 \(i\) 可能在 \(t\) 時刻阻礙 \(j\)，然后去順次考慮每一個點對生不生效。因為題目給了一些互不相等所以不用去糾邊角情況。發現只要動態維護 \(u\) 有沒有被阻礙、以及被阻礙到哪個地方就能判斷生效情況以及更新阻礙情況，不盡之處皆是一些簡單分討（？
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=1005, M=1000005;
int n, m, x[N], y[N], tag[N], in[N], Ans[N];
vector<int> to[N];
char opt[N];
struct node {
int i, j, t;
bool operator<(const node &rhs) const { return t<rhs.t; }
} p[M];
void dfs(int x) {
for(int y:to[x]) dfs(y), Ans[x]+=Ans[y]+1;
}
signed main() {
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,1,n) cin >> opt[i] >> x[i] >> y[i];
up(i,1,n) {
if(opt[i]!='N') continue;
up(j,1,n) if(opt[j]=='E') {
if(x[j]>x[i]||y[j]<y[i]) continue;
int ti=y[j]-y[i], tj=x[i]-x[j];
if(ti==tj) continue;
if(ti<tj) p[++m]=(node){i,j,tj};
if(tj<ti) p[++m]=(node){j,i,ti};
}
}
sort(p+1,p+1+m);
up(u,1,m) {
int i=p[u].i, j=p[u].j;
// cout << "breat " << i << ' ' << j << '\n';
if(!tag[j]&&(!tag[i]||opt[i]=='N'&&y[j]<=y[i]+tag[i]
||opt[i]=='E'&&x[j]<=x[i]+tag[i])) {
tag[j]=p[u].t, to[i].pb(j), ++in[j];
}
}
up(i,1,n) if(!in[i]) dfs(i);
up(i,1,n) cout << Ans[i] << '\n';
return 0;
}
2-C 總統大選 (election.cpp)
大樣例全過掛分的來了。上次見到你，你叫作《機械師》。
貪心，首先先拿 \(a\) 再拿 \(b\) 顯然是劣的，考慮操作拿 \(b_1,\dots,b_m,a_{m+1},\dots,a_{m_0}\)，答案就是 \(\sum_{i=1}^m \frac{b_i}{i}+\sum_{i=m+1}^{m}\frac{a_i}{m+1}\)。最終的操作序列一定是按照 \(b\uparrow\) 的順序獲得協作者，然后在剩下的州里面挑 \(a\) 最小的或者選票直到足夠。按照這個做是按照 \(b\uparrow\) 排序，枚舉協作者總人數 \(m\)，然后背包 \(f[i][j][k]\) 表示考慮前 \(i\) 個人選了 \(j\) 個協作者 \(k\) 個演講的最小時間，答案是 \(\min_{m=0}^{m_0}\{f[n][m][m_0-k]\}\)，還需要優化掉一個 \(O(n)\)。
直覺上我們希望拿最小的若干個 \(b\) 再拼湊上若干個后綴上最小的 \(a\)，但是這么做是錯誤的，感性理解就是有些點雖然 \(b\) 不大但 \(a\) 尤其小，其拿 \(a\) 的性價比太高了，具體而言假定 \((a_1,b_1),(a_2,b_2)\) 要協作一個選票一個，設 \(b_1>b_2\)，協作 1 比協作 2 優的條件形如 \(b_1+\frac{a_2}{2}<b_2+\frac{a_1}{2}\)，也就是 \(2(b_2-b_1)<(a_1-a_1)\) 是有可能被滿足的。
但是不影響扣掉這些被 \(a\) 的東西之后協作者堆成一個前綴，考慮處理前綴非 \(a\) 即 \(b\) 的答案之后往后合并即可，相當于額外加了一個枚舉前綴位置。
只做 \(\forall i\in[1,m_0],j+k=i\) 就足夠貢獻了，還是枚舉 \(m\)，那么新的狀態計算 \(f[i][j]\) 表示考慮了前 \(i\) 個州選了 \(j\) 個協作者的最小時間，計算后綴選 \(u\) 個 \(a\) 的最小時間和即可合并出答案。
#include<bits/stdc++.h>
#define int long long
#define db double
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define a first
#define b second
using namespace std;
const int N=505, inf=1e13;
int n, m, arr[N], sum[N][N];
pii p[N];
db Ans=inf, f[N][N];
inline void chk(db &a,db b) { a=min(a,b); }
signed main() {
freopen("election.in","r",stdin);
freopen("election.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
up(i,1,n) {
cin >> p[i].a >> p[i].b;
if(p[i].b==-1) p[i].b=inf;
}
sort(p+1,p+1+n,[](pii i,pii j){return i.b<j.b;});
dn(i,n,1) {
int tot=0;
up(j,i,n) arr[++tot]=p[j].a;
sort(arr+1,arr+1+tot);
up(j,1,n-i+1) sum[i][j]=sum[i][j-1]+arr[j];
}
up(k,0,m) {
up(i,0,m) up(j,0,k) f[i][j]=inf;
f[0][0]=0;
up(i,1,m) up(j,0,min(i,k)) {
chk(f[i][j],f[i-1][j]+(db)p[i].a/(k+1));
chk(f[i][j+1],f[i-1][j]+(db)p[i].b/(j+1));
}
up(i,0,m) chk(Ans,f[i][k]+(db)sum[i+1][m-i]/(k+1));
}
cout << fixed << setprecision(15) << Ans << '\n';
return 0;
}
2-D 風力發電機 (wind.cpp)
我是怎么做到不同 mst 最后才考慮重構樹的，題目有點像模板套模板套模板嗯對。
因為求解答案是加入權值為 \(0\) 的邊重新求 mst，所以實際上要使用的邊肯定是原 mst 的子集，復雜問題進一步的我們建立出重構樹，顯然這樣子可以體現 mst 更好的性質（權值遞增、集合合并、順序明確）。
現在考慮選定一些特殊點怎么在 mst 上考慮貢獻，假設只有 \(p,q\) 就是刪除 \(lca(p,q)\)，因為能刪除的是 \(p/q\to lca(p,q)\) 的邊，而越上面的越不劣。進一步考慮很多個點 \(p_1,\dots,p_m\) 的情況，有點像虛樹因為會剛好新建立 \(m-1\) 個虛點誒，更具體的可以考慮手摸 \(m\) 比較小的情況，發現可以歸納法看到貢獻是對的。
進一步考慮一個點什么時候會成為虛點，顯然是左右子樹皆不為空的情況，就是存在 \((p,q)\) 滿足 \(l\leq p<q\leq r\) 然后 \(p/q\) 分別在左右子樹里面吧，哦發現 dsu on tree 點對個數只有 \(O(n\log n)\)，可以處理出來。現在考慮怎么求解答案，就是對于 \(l,r\) 查詢 \((p,q,w)\) 滿足 \(l\leq p<q\leq r\) 的不同 \(w\) 的權值和，掃描線處理掉一維，然后要對 \(q\leq r\) 的每個 \(w\) 考慮 \(\max p\)，打在樹狀數組上即可快速查詢。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=200005, M=5000005;
int n, m, T, len, dsu[N], tot, val[N], ls[N], rs[N], Ans[N], lst[N], tr[N], pre;
struct edge { int u, v, w; } e[N], p[M], q[N];
vector<int> to[N];
set<int> point[N];
int get(int x) { return x==dsu[x]?x:dsu[x]=get(dsu[x]); }
void add(int x,int v) { for( ; x<=n; x+=x&-x) tr[x]+=v; }
int ask(int x) { int ret=0; for( ; x; x-=x&-x) ret+=tr[x]; return ret; }
int dfs(int x) {
if(x<=n) {
point[x].insert(x);
return x;
}
int l=dfs(ls[x]), r=dfs(rs[x]);
if(point[l].size()>point[r].size()) swap(l,r);
for(int val:point[l]) {
auto it=point[r].lower_bound(val);
if(it!=point[r].end()) p[++len]=(edge){val,*it,x};
if(it!=point[r].begin()) p[++len]=(edge){*--it,val,x};
}
for(int val:point[l]) point[r].insert(val);
point[l].clear();
return r;
}
signed main() {
freopen("wind.in","r",stdin);
freopen("wind.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> T, tot=n;
up(i,1,m) cin >> e[i].u >> e[i].v >> e[i].w, ++e[i].u, ++e[i].v;
sort(e+1,e+1+m,[](edge i,edge j){return i.w<j.w;});
up(i,1,n) dsu[i]=i;
up(i,1,m) {
int x=get(e[i].u), y=get(e[i].v);
if(x!=y) {
pre+=e[i].w, val[++tot]=e[i].w, dsu[tot]=tot;
ls[tot]=x, rs[tot]=y, dsu[x]=dsu[y]=tot;
// cout << " " << tot << "(" << e[i].w << ")"<< ' ' << ls[tot] << '\n';
// cout << " " << tot << "(" << e[i].w << ")"<< ' ' << rs[tot] << '\n';
}
}
dfs(tot);
sort(p+1,p+1+len,[](edge i,edge j){return i.v<j.v;});
// up(i,1,len) cout << "check " << p[i].u << ' ' << p[i].v << ' ' << p[i].w << '\n';
up(i,1,T) q[i].w=i, cin >> q[i].u >> q[i].v, ++q[i].u, ++q[i].v;
sort(q+1,q+1+T,[](edge i,edge j){return i.v<j.v;});
int j=1;
up(i,1,T) {
while(j<=len&&p[j].v<=q[i].v) {
// cout << "insert " << p[j].u << ' ' << p[j].v << ' ' << val[p[j].w] << '\n';
int id=p[j].w;
if(lst[id]) {
if(lst[id]<p[j].u) {
add(lst[id],-val[id]);
lst[id]=p[j].u;
add(p[j].u,val[id]);
}
}
else add(p[j].u,val[id]), lst[id]=p[j].u;
++j;
}
Ans[q[i].w]=ask(n)-ask(q[i].u-1);
}
up(i,1,T) cout << pre-Ans[i] << '\n';
return 0;
}
浙公網安備 33010602011771號