2 条题解
-
4
Nd Ntcd I Ntcd Nd.
syh666!!!
这题其实很简单,思路就是先找到一个尽可能靠右的1,设其下标为j,需要满足n-j+1>=k,这样能够保证把后面这j位翻转能够满足题目要求,且字典序严格小于原串。
然后再考虑是否翻转第j位的1为0,如果n-j+1=k,则直接全部翻转输出。
否则,直接保留当前这个1,然后,从前到后尽可能翻转0为1,如果全翻过来还有剩余,那么从后到前开始翻1为0,刚好翻到k个,1个都不要多。
这样就可以保证既有k位不一样,又满足小于等于原串字典序,同时易证字典序最大。
时间复杂度线性。
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; string s; int k, n, lst[N], vis[N]; int main() { freopen("string.in", "r", stdin); freopen("string.out", "w", stdout); ios :: sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> s, cin >> k, n = s.size(), s = " " + s; int pos = 1e9; for(int i=n; i>=1; --i) { if(s[i] == '1') pos = i; lst[i] = pos; } pos = 1e9; if(k == 0) { for(int i=1; i<=n; ++i) cout << s[i]; return 0; } for(int i=n; i>=1; --i) { if(lst[i] <= n - k + 1 && s[i] == '1') { pos = i; break; } } if(pos == 1e9) { cout << -1; return 0; } for(int i=1; i<=n; ++i) vis[i] = 0; for(int i=1; i<pos; ++i) vis[i] = 1; vis[pos] = 1, s[pos] = '0'; int idx = 0; for(int i=pos+1; i<=n; ++i) if(s[i] == '0' && !vis[i]) s[i] = '1', ++idx, vis[i] = 1; if(idx < k - 1) { for(int i=n; i>=pos+1; --i) { if(s[i] == '1' && idx < k - 1 && !vis[i]) s[i] = '0', ++idx, vis[i] = 1; } } for(int i=1; i<=n; ++i) cout << s[i]; return 0; } -
3
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; string s; int k, n, lst[N], vis[N]; int main() { freopen("string.in", "r", stdin); freopen("string.out", "w", stdout); ios :: sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> s, cin >> k, n = s.size(), s = " " + s; int pos = 1e9; for(int i=n; i>=1; --i) { if(s[i] == '1') pos = i; lst[i] = pos; } pos = 1e9; if(k == 0) { for(int i=1; i<=n; ++i) cout << s[i]; return 0; } for(int i=n; i>=1; --i) { if(lst[i] <= n - k + 1 && s[i] == '1') { pos = i; break; } } if(pos == 1e9) { cout << -1; return 0; } for(int i=1; i<=n; ++i) vis[i] = 0; for(int i=1; i<pos; ++i) vis[i] = 1; vis[pos] = 1, s[pos] = '0'; int idx = 0; for(int i=pos+1; i<=n; ++i) if(s[i] == '0' && !vis[i]) s[i] = '1', ++idx, vis[i] = 1; if(idx < k - 1) { for(int i=n; i>=pos+1; --i) { if(s[i] == '1' && idx < k - 1 && !vis[i]) s[i] = '0', ++idx, vis[i] = 1; } } for(int i=1; i<=n; ++i) cout << s[i]; return 0; }
- 1
信息
- ID
- 970
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 25
- 已通过
- 7
- 上传者