abc 408 d~f
這次做了一次 abc，d 做出來了，但是比較麻煩，又用正確方法寫了一遍，整理一下 d,e,f，g 有一些超綱。
abc408d
考慮把區間 \(l,r\) 最后變成 1，然后嘗試去表示這個時候的答案。
\(sum[i]\) 表示 \(i\) 位置以及之前的 1 的總和。
可以很簡單列出來↓
\(sum[n]-(sum[r]-sum[l-1])+(r-l+1)-(sum[r]-sum[l-1])\)
我們嘗試移項可以得出↓
\(sum[n]+(r-2*sum[r])+(2*sum[l-1]-(l-1))\)
我們枚舉 r，維護 sum[l-1]-(l-1) 的前綴最小值就可以做了。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
int T, n, sum[MN], pre[MN];
char s[MN];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>T; while(T--){
cin>>n; for(int i=1; i<=n; ++i) cin>>s[i]; int ans=0x3f3f3f3f;
for(int i=0; i<=n+1; ++i) sum[i]=0, pre[i]=0x3f3f3f3f;
for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+(s[i]=='1');
for(int i=0; i<=n; ++i) pre[i]=2*sum[i]-i;
for(int i=1; i<=n; ++i) pre[i]=min(pre[i],pre[i-1]);
for(int i=1; i<=n; ++i) ans=min(ans,sum[n]+(i-2*sum[i])+pre[i]);
cout<<ans<<'\n';
}
return 0;
}
abc408e
明明自己今天剛說了說關于位運算的，結果一考沒想出來。
我們貪心考慮，從高位到低位嘗試放 0。
對于某一位，我們如果要嘗試填 0 的話，我們刪掉所有的邊權不含 0 的邊之后應該是可以從 1 走到 n 的。
如果填 0 不成我們邊需要填 1 了。
填 0 之后我們不能考慮這一位是 1 的了，全部刪掉。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
struct Node{
int u, v, w;
int tag=true;
}side[MN];
int n, m, father[MN], ans=0;
int find(int x){
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}
void merge(int x, int y){
x=find(x), y=find(y);
if(x==y) return;
father[x]=y; return;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1; i<=m; ++i){
cin>>side[i].u>>side[i].v>>side[i].w;
}
for(int t=30; t>=0; --t){
for(int i=1; i<=n; ++i) father[i]=i;
for(int i=1; i<=m; ++i){
if(side[i].w&(1<<t)||!side[i].tag) continue;
merge(side[i].u,side[i].v);
}
if(find(1)!=find(n)){
ans+=(1<<t);
}else{
for(int i=1; i<=m; ++i){
if(side[i].w&(1<<t)){
side[i].tag=false;
}
}
}
}
cout<<ans<<'\n';
return 0;
}
abc408f
數據結構優化dp，把 h 從小到大排序，線段樹維護 dp 值，實時更新可以轉移的位置。
這個沒啥好說的，就是沒有去寫。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int MN=2e6+216;
struct Segmentree{
int l, r, maxn;
}tr[MN];
void pushup(int k){
tr[k].maxn=max(tr[lc].maxn,tr[rc].maxn);
}
void build(int k, int l, int r){
tr[k].l=l, tr[k].r=r;
if(l==r){tr[k].maxn=0; return;}
int mid=(tr[k].l+tr[k].r)>>1;
build(lc,l,mid); build(rc,mid+1,r);
pushup(k); return;
}
void update(int k, int pos, int val){
if(tr[k].l==tr[k].r){tr[k].maxn=val; return;}
int mid=(tr[k].l+tr[k].r)>>1;
if(pos<=mid) update(lc,pos,val);
else update(rc,pos,val);
pushup(k); return;
}
int query(int k, int l, int r){
if(tr[k].l>=l&&tr[k].r<=r) return tr[k].maxn;
int mid=(tr[k].l+tr[k].r)>>1, res=0;
if(l<=mid) res=max(res,query(lc,l,r));
if(r>mid) res=max(res,query(rc,l,r));
pushup(k); return res;
}
struct Node{
int h, id;
bool operator <(const Node &o)const{
return h<o.h;
}
}node[MN];
int n, d, r, pos=0, dp[MN];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>d>>r; build(1,1,n);
for(int i=1; i<=n; ++i){
cin>>node[i].h; node[i].id=i;
}
sort(node+1,node+n+1);
for(int i=1; i<=n; ++i){
while(node[pos].h+d<=node[i].h){
update(1,node[pos].id,dp[pos]); ++pos;
}
dp[i]=query(1,max(1,node[i].id-r),min(n,node[i].id+r))+1;
}
int ans=0;
for(int i=1; i<=n; ++i) ans=max(ans,dp[i]);
cout<<ans-1<<'\n';
return 0;
}
浙公網安備 33010602011771號