2 条题解

  • 4
    @ 2026-11-11 14:25:02

    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
      @ 2026-11-7 7:30:51
      #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

      [2026济南登峰营] D3 P1 不同位置(string) - 文件读写

      信息

      ID
      970
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      (无)
      递交数
      25
      已通过
      7
      上传者