AtCoder Beginner Contest 415

AtCoder Beginner Contest 415

A题

枚举$x$是否在序列$A$中即可。

B题

模拟题，将$s[i]={=}^{\prime }{\#}^{\prime }$的位置保存在ans中，之后每次输出两个即可。

C题

状压dp

定义$dp[i]$表示状态$i$可达，初始化$dp[0]=1$。

转移方程：假设当前状态为$i$，且$dp[i]==1$，那么枚举$i$的每一位，如果为0，那么我们判断是否能够转移。假设第$j$位为0，那么新的状态$state=i+1<<j$，如果$s[state]={=}^{\prime }{0}^{\prime }$，那么可以转移过去$dp[state]=1$，最后跑完了之后只需要检查$dp[(1<<n)-1]==1?Yes:No$。

void solve(){int n;string s;cin >> n >> s;s=" "+s;if(s.back()=='1'){cout << "No" << endl;return;}vector<int> ok(1LL<<n,0);
//	for(int i=1;i<=n;i++){
//		if(s[1LL<<(i-1)]=='0') ok[1LL<<(i-1)]=1;
//	}ok[0]=1;for(int i=0;i<(1LL<<n);i++){//i就是状态if(ok[i]){//枚举到达这个状态没有使用过的药品for(int j=0;j<n;j++){if(i>>j &1) continue;//如果没有使用，那么可以用来转移int nxt=i+(1<<j);if(s[nxt]=='0') ok[nxt]=1;}}}if(ok[(1LL<<n) -1]) cout << "Yes" << endl;else cout << "No" << endl;
}

D题

贪心

我们每次选能够选择中的亏损最少的那个，因为可以多次选。假设当前有$N$瓶，选第$i$个，能够选$x$次，那么在第$x-1$次选完之后，肯定有$N-(x-1)\times (A_i-B_i)\ge A_i$，那么化简$N+A_i-B_i-A_i>=x\times (A_i-B_i)$，得到$x\le \frac{N-B_i}{A_i-B_i}$，$x$向下取整。

之后就是先按照差值从小到大排序，依次枚举，统计答案。

struct node{int a,b;bool operator <(node other){if(a-b!=other.a-other.b) return a-b<other.a-other.b;else return a<b;}
};void solve(){int n,m;cin >> n >> m;vector<int> A(m+1),B(m+1);for(int i=1;i<=m;i++){cin >> A[i] >> B[i];}vector<node> vt(m+1);for(int i=1;i<=m;i++){vt[i]={A[i],B[i]};}sort(vt.begin()+1,vt.end());int ans=0;//可以多次和i交换，那么计算出可以交换的次数for(int i=1;i<=m;i++){if(n<vt[i].a) continue;int x=(n-vt[i].b)/(vt[i].a-vt[i].b);ans+=x;n-=x*(vt[i].a-vt[i].b);}cout << ans << endl;
}

E题

二分+dp

定义$dp[i][j]$表示在第$i+j-1$个监狱买完饭之后能够剩余最多的金币数。

const int maxn=2e5+9,mod=1e9+7;
int p[maxn];
bool check(int mid,vector<vector<int>>&a,int n,int m){vector<vector<int>> dp(n+1,vector<int>(m+1,-inf));//inf特判dp[1][1]=mid+a[1][1]-p[1+1-1];if(dp[1][1]<0) return false;//先转移第一行for(int j=2;j<=m;j++){if(dp[1][j-1]>=0){dp[1][j]=dp[1][j-1]+a[1][j]-p[1+j-1];}}for(int i=2;i<=n;i++){if(dp[i-1][1]>=0){dp[i][1]=dp[i-1][1]+a[i][1]-p[1+i-1];}}for(int i=2;i<=n;i++){for(int j=2;j<=m;j++){if(!(dp[i-1][j]<0&&dp[i][j-1]<0)){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]-p[i+j-1];}}}return dp[n][m]>=0;
}void solve(){int n,m;cin >> n >> m;vector<vector<int>> a(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin >> a[i][j];}}for(int i=1;i<=n+m-1;i++) cin>>p[i];p[n+m]=0;
//	a[n][m]=0;int l=0,r=inf,mid,ans;while(l<=r){mid=(l+r)/2;if(check(mid,a,n,m)){ans=mid;r=mid-1;}else l=mid+1;}cout << ans << endl;
}

F题

线段树区间合并

对于每一个节点，我们要维护这些信息：左端点$l$，右端点$r$，包含左端点的前缀最大连续相同字符长度$pre$，包含右端点的最大连续相同字符长度$suf$，节点的最长连续相同字符长度$mx$。

在$pushup$和$query$的时候，要手动合并信息即可。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
#define lc u<<1
#define rc u<<1|1
typedef  long long ll;
typedef pair<int,int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int maxn=5e5+9,mod=1e9+7;
char s[maxn];
struct segment{int l,r;int pre,suf,mx;
}tr[maxn<<2];
void pushup(int u){tr[u].pre=tr[lc].pre;if(tr[lc].r-tr[lc].l+1==tr[lc].pre&&s[tr[lc].r]==s[tr[rc].l]){tr[u].pre=max(tr[u].pre,tr[lc].r-tr[lc].l+1+tr[rc].pre);}tr[u].suf=tr[rc].suf;if(tr[rc].r-tr[rc].l+1==tr[rc].suf&&s[tr[lc].r]==s[tr[rc].l]){tr[u].suf=max(tr[u].suf,tr[rc].r-tr[rc].l+1+tr[lc].suf);}tr[u].mx=max(tr[lc].mx,tr[rc].mx);if(s[tr[lc].r]==s[tr[rc].l]){tr[u].mx=max(tr[u].mx,tr[lc].suf+tr[rc].pre);}
}void build(int u,int l,int r){tr[u]={l,r,1,1,1};if(l==r) return;int mid=(l+r)/2;build(lc,l,mid);build(rc,mid+1,r);pushup(u);
}
void update(int u,int l,int r,char c){if(tr[u].l==tr[u].r){s[l]=c;//前缀最大长度，后缀最大长度不会改变，因为是单点tr[u].suf=tr[u].pre=tr[u].mx=1;return;}int mid=(tr[u].l+tr[u].r)/2;if(l<=mid) update(lc,l,r,c);if(r>mid) update(rc,l,r,c);pushup(u);
}
segment query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r){return tr[u];}//babaacczccint mid=(tr[u].l+tr[u].r)/2;if(r<=mid) return query(lc,l,r);if(l>mid) return query(rc,l,r);segment left,right,res;left=query(lc,l,r);right=query(rc,l,r);res.l=left.l;res.r=right.r;//区间合并res.pre=left.pre;if(left.pre==left.r-left.l+1&&s[left.r]==s[right.l]){res.pre=max(res.pre,left.r-left.l+1+right.pre);}res.suf=right.suf;if(right.suf==right.r-right.l+1&&s[left.r]==s[right.l]){res.suf=max(res.suf,right.r-right.l+1+left.suf);}res.mx=max(left.mx,right.mx);if(s[left.r]==s[right.l]){res.mx=max(res.mx,left.suf+right.pre);}return res;
}
void solve(){int n,q;cin >> n >> q;for(int i=1;i<=n;i++){cin >> s[i];}build(1,1,n);while(q--){int op,l,r,pos;char c;cin >> op;if(op==1){cin >> pos >> c;update(1,pos,pos,c);}else{cin >> l >> r;segment res=query(1,l,r);cout << res.mx << endl;}}
}
/*
找到区间最长相同字符长度，那么要维护信息区间左右端点以及每个区间以第一个字符开头的最长连续相同字符长度
和最后一个字符向前的最长长度
用于区间合并，其他不用
也就是向上合并信息时，最长长度为左边最长长度，右边最长长度，以及可能中间的
*/
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t=1;
//	cin >> t;while(t--){solve();}return 0;
}