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;
    }
    
    

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

    信息

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