这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 | |||
2020-2021:teams:wangzai_milk:20200718比赛记录 [2020/07/22 21:58] infinity37 [C - Operation Love] |
2020-2021:teams:wangzai_milk:20200718比赛记录 [2020/07/23 20:44] (当前版本) wzx27 |
||
---|---|---|---|
行 15: | 行 15: | ||
===== 题解 ===== | ===== 题解 ===== | ||
+ | ==== A - Clam and Fish ==== | ||
+ | |||
+ | 依次经过 $n$ 个格子,每个格子上可能有 $\text{fish}$ 或 $\text{clam}$。 | ||
+ | |||
+ | 每个格子上可以下面的选一个操作: | ||
+ | |||
+ | 如果有 $\text{clam}$,可以制作一个鱼饵 | ||
+ | |||
+ | 如果有 $\text{fish}$,可以得到一条鱼 | ||
+ | |||
+ | 消耗一个鱼饵获得一条鱼 | ||
+ | |||
+ | 什么事都不做 | ||
+ | |||
+ | 显然有鱼的位置选操作三。剩下的有能制作鱼饵就制作鱼饵,否则就用鱼饵捕鱼。最后加上剩下鱼饵的二分之一。 | ||
+ | |||
+ | <hidden code> <code cpp> | ||
+ | #include<bits/stdc++.h> | ||
+ | #define ALL(x) (x).begin(),(x).end() | ||
+ | #define ll long long | ||
+ | #define ull unsigned long long | ||
+ | #define pii_ pair<int,int> | ||
+ | #define mp_ make_pair | ||
+ | #define pb push_back | ||
+ | #define fi first | ||
+ | #define se second | ||
+ | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
+ | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
+ | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
+ | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
+ | using namespace std; | ||
+ | const ll INF = 1LL<<60; | ||
+ | const int inf = 1<<30; | ||
+ | const int maxn = 2e6+5; | ||
+ | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
+ | |||
+ | char s[maxn]; | ||
+ | int main() | ||
+ | { | ||
+ | fastio(); | ||
+ | int _; char x; | ||
+ | for(cin>>_;_;_--){ | ||
+ | int n; cin>>n; | ||
+ | cin>>s+1; | ||
+ | int ans = 0,cnt = 0; | ||
+ | rep(i,1,n){ | ||
+ | if(s[i]=='0'){ | ||
+ | if(cnt) ans++,cnt--; | ||
+ | }else if(s[i]=='1'){ | ||
+ | cnt++; | ||
+ | } | ||
+ | else ans++; | ||
+ | } | ||
+ | ans += cnt/2; | ||
+ | cout<<ans<<endl; | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | |||
+ | </code> </hidden> | ||
+ | \\ | ||
+ | |||
==== B - Classical String Problem ==== | ==== B - Classical String Problem ==== | ||