CodeforcesRound1005(Div.2)(A-D)

题目链接：Dashboard - Codeforces Round 1005 (Div. 2) - Codeforces

A. Brogramming Contest 思路

每次把后缀1...10...0放到t里面再把0...0放回s，这样重复

代码 void solve(){ int n; cin>>n; string s; cin>>s; int cnt=0; bool f=false; for(int i=0;i<n;i++){ if(s[i]=='1'){ if(!f) cnt++; f=true; } if(s[i]=='0'){ if(f) cnt++; f=false; } } cout<<cnt<<"\n"; } signed main() { vcoistnt cout<<fixed<<setprecision(2); int _=1; cin>>_; while(_--) solve(); return 0; } B. Variety is Discouraged 思路

可以发现a的最大得分就是n-cnt，(n表示数组a的长度，cnt是只出现一次的数量），那么我们发现如果移除一个只出现一次的数是不会改变得分的，移除出现多次的数会使得得分变小，这么这题就可以转换成寻找只包含出现一次数的最大子数组

代码 #include<bits/stdc++.h> using namespace std; #define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define ull unsigned long long #define bit __builtin_popcount #define lowbit(x) ((x)&-(x)) #define vi vector<int> #define vb vector<bool> typedef pair<int,int> pll; const int N=2e5+10; const int inf=1e18; const int mod=998244353; void solve(){ int n; cin>>n; vi a(n+10); map<int,int> mp; for(int i=1;i<=n;i++){ cin>>a[i]; mp[a[i]]++; } int i=1; int l=-1,r=-1; int mx=0; while(i<=n){ if(mp[a[i]]==1){ int x=i; int st=i; while(mp[a[x]]==1) x++; int ed=x-1; if(x-i>mx){ mx=x-i; l=st; r=ed; } i=x; }else{ i++; } } if(l==-1){ cout<<"0\n"; }else{ cout<<l<<" "<<r<<"\n"; } } signed main() { vcoistnt cout<<fixed<<setprecision(2); int _=1; cin>>_; while(_--) solve(); return 0; } C. Remove the Ends 思路

我们发现选择一个负数会把后面的数全删掉，那么我们贪心地从后往前选负数，选择一个正数会把前面的数删掉，我们贪心地从前往后选正数。如果我们选择了一个负数，那么这个负数之后的正数是不可选的；

那么我们遍历一遍 正数的前缀和+负数的后缀和 取最大值即是答案

代码 #include<bits/stdc++.h> using namespace std; #define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define ull unsigned long long #define bit __builtin_popcount #define lowbit(x) ((x)&-(x)) #define vi vector<int> #define vb vector<bool> typedef pair<int,int> pll; const int N=2e5+10; const int inf=1e18; const int mod=998244353; void solve(){ int n; cin>>n; vi a(n+10); for(int i=1;i<=n;i++){ cin>>a[i]; } vi p(n+10,0); vi suf(n+10,0); for(int i=1;i<=n;i++){ if(a[i]>0) p[i]=p[i-1]+a[i]; else p[i]=p[i-1]; } for(int i=n;i>=1;i--){ if(a[i]<0) suf[i]=suf[i+1]-a[i]; else suf[i]=suf[i+1]; } int ans=0; for(int i=1;i<=n;i++){ ans=max(ans,p[i]+suf[i]); } cout<<ans<<"\n"; } signed main() { vcoistnt cout<<fixed<<setprecision(2); int _=1; cin>>_; while(_--) solve(); return 0; } D. Eating 思路

首先这题要x>=w[i]才能吃掉，我们转换一下，根据异或的性质我们可以用suf[i]表示后缀异或和，即只有那么我们才能够把w[i-1]给吃掉，从后往前找到第一个不满足的即可；

发现如果我们直接遍历的话会超时，那么我们接下来需要解决如何优化

如果x>=y，那么二进制下x的最高位1的位置>=y的最高位1，且只有x的最高位1=y的最高位1时之后x的最高位1的位置才会改变

那么我们便可把问题转化为每次从后往前找到第一个最高位1的位置>=当前x的最高位，如果能够吃掉就更新x的最高位，否则结束搜索；具体查找可以用线段树实现，细节看代码。

代码 #include<bits/stdc++.h> using namespace std; #define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define vi vector<int> #define vb vector<bool> typedef pair<int,int> pll; const int N=2e5+10; const int inf=1e18; const int mod=998244353; int get(int x){ //得到二进制下x最高位1的位置 if(x==0) return -1; return 31-__builtin_clz(x); } struct SegmentTree { int n; vector<int> mx; SegmentTree(const vector<int>& a) { n = a.size(); mx.resize(4 * n); build(0, 0, n - 1, a); } void build(int id, int l, int r, const vector<int>& a) { if (l == r) { mx[id] = a[l]; return; } int mid = (l + r) / 2; build(2*id+1, l, mid, a); build(2*id+2, mid+1, r, a); mx[id] = max(mx[2*id+1], mx[2*id+2]); } int query(int id, int l, int r, int start, int x) { if (r < start || mx[id] < x) return -1; if (l == r) return l; int mid = (l + r) / 2; int L = query(2*id+1, l, mid, start, x); if (L != -1) return L; return query(2*id+2, mid+1, r, start, x); } int find(int start, int x) { return query(0, 0, n-1, start, x); } }; void solve(){ int n,q; cin>>n>>q; vi w(n); for(int &x:w) cin>>x; vi rev(n); //将w倒转方便后续操作 vi h(n); //最高位1位置 int mxb=-1; //最大最高位 for(int i=0;i<n;i++){ rev[i]=w[n-1-i]; h[i]=get(rev[i]); mxb=max(mxb,h[i]); } vi pre(n+1,0); //异或前缀 for(int i=0;i<n;i++){ pre[i+1]=pre[i]^rev[i]; } SegmentTree st(h); while(q--){ int x;cin>>x; int curb=get(x); if(curb>mxb){ cout<<n<<" ";continue; } int cnt=0; int pos=0; while(pos<n){ int i=st.find(pos,curb); //找到第一个最高位1>=x的位置 if(i==-1){ cnt+=(n-pos); break; } cnt+=(i-pos); x^=(pre[i]^pre[pos]); curb=get(x); pos=i; if(h[pos]>curb){ break; } if(x>=rev[pos]){ cnt++; x^=rev[pos]; curb=get(x); pos++; }else{ break; } } cout<<cnt<<" "; }cout<<"\n"; } signed main() { vcoistnt cout<<fixed<<setprecision(2); int _=1; cin>>_; while(_--) solve(); return 0; }