• 字符串思维题练习 DAY5(CF1137 B , CF 733D , CF 1360 F)


    字符串思维题练习 DAY5(CF1137 B , CF 733D , CF 1360 F)

    CF 1137 B. Camp Schedule(border)

    Problem - B - Codeforces

    大意:给出一个字符串 S 和一个字符串 T , 要求重排 S 使得在 S中和 T 相等的子串出现次数最多。

    不妨先考虑最暴力的重排方式 , 即把 S 排列成 T + T + T + … + T 的形式 ,不过这样重排显然不是最优的 。考虑如何能让结果变得更优 , 即让子串 T 出现的次数变多 。在总长固定的情况下 ,考虑让相邻的 T 尽可能的重合 ,即变成了找 T 的非平凡最大子 border , 求出 next 数组后利用最大border构造即可。

    #include
    using namespace std;
    #define fi first
    #define se second
    #define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #define int long long
    const int INF = 9e18;
    const int N = 2e6 + 10;
    const int mod = 1e9 + 7;
    typedef pair<int,int>PII;
    
    string s , t , ans;
    int n , m;
    int cnts_1 , cntt_1 , cnts_0 , cntt_0 ;
    
    int nex[N];
    
    void init(string s){
    	int len = s.size();
    	nex[1] = 0;
    	for(int i = 2 ; i <= len ; i ++){
    		nex[i] = nex[i-1];
    		while(nex[i] && s[nex[i]] != s[i-1]) nex[i] = nex[nex[i]];
    		nex[i] += (s[i-1] == s[nex[i]]);
    	}
    }
    
    /*
    1010101100
    10101
    */
    
    signed main(){
    
    	cin >> s >> t;
    	n = s.size();
    	m = t.size();
    	init(t);
    	int pos = nex[m];	
    	string now = t.substr(pos);
    
    	for(int i = 0 ; i < n ; i ++) {
    		cnts_0 += 1 * (s[i] == '0');
    		cnts_1 += 1 * (s[i] == '1');
    	}
    	
    	for(int i = 0 ; i < m ; i ++) {
    		cntt_0 += 1 * (t[i] == '0');
    		cntt_1 += 1 * (t[i] == '1');
    	}
    	
    	if(cnts_0 < cntt_0 || cnts_1 < cntt_1) {
    		cout << s << "\n";
    	} else {
    		cnts_0 -= cntt_0;
    		cnts_1 -= cntt_1;
    		ans += t;
    		m = now.size();
    		cntt_0 = cntt_1 = 0;
    		
    		for(int i = 0 ; i < m ; i ++) {
    			cntt_0 += 1 * (now[i] == '0');
    			cntt_1 += 1 * (now[i] == '1');
    		}
    		int need = INF;
    			
    		if(cntt_0) need = min(need , cnts_0 / cntt_0);
    		if(cntt_1) need = min(need , cnts_1 / cntt_1);
    		for(int i = 1 ; i <= need ; i ++) {
    			ans += now;
    		}
    		cnts_1 -= need * cntt_1;
    		cnts_0 -= need * cntt_0;
    		for(int i = 1 ; i <= cnts_1 ; i ++) ans += '1';
    		for(int i = 1 ; i <= cnts_0 ; i ++) ans += '0';
    		cout << ans << "\n";
    	}
    	
    	return 0;
    }
    //freopen("文件名.in","r",stdin);
    //freopen("文件名.out","w",stdout);
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82

    CF 733 D. Kostya the Sculptor(哈希)

    Problem - D - Codeforces

    大意:给出 n 个长方体 , 要求找出能切割出最大球体的长方体编号 。 可以选择不拼接或者选择两个某一个面相同的长方体进行拼接 , 仅能拼接一次。

    思路:对于不拼接的情况 , 遍历即可 。 对于可以拼接的情况 , 有两种思路:第一种离线做法 , 对于每一种面维护最大次大值 , 然后遍历所有存在次大值的面 , 更新答案和编号 , 但是这样写不是很好写。考虑第二种在线做法 , 对于每一种面维护一个前缀最大值 , 然后边遍历边用当前的长方体和面相同的最大的长方体进行合并 , 更新答案。

    对于面的表示 , 因为给出的边是无序的 , 所以一个面有两种表示方式 , 可以考虑用六种面的表示方式维护 或者 对边排序后用三种面的表示方式维护

    能表示出面的全集即可

    #include
    using namespace std;
    #define fi first
    #define se second
    #define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #define int long long
    const int INF = 9e18;
    const int N = 2e6 + 10;
    const int mod = 1e9 + 7;
    typedef pair<int,int>PII;
    
    map<PII,PII>mp;
    //[面 , id , val]
    int n , a[N] , b[N] , c[N] , res , id;
    
    PII ans , now;
    
    signed main(){
    
    	IOS
    	cin >> n;
    	res = -INF;
    	for(int i = 1 ; i <= n ; i ++) {
    		cin >> a[i] >> b[i] >> c[i];
    		if(min({a[i] , b[i] , c[i]}) > res) {
    			res = min({a[i] , b[i] , c[i]});
    			id = i;
    		}
    	}
    	
    	
    	bool tag = 0 ;
    	
    	for(int i = 1 ; i <= n ; i ++) {
    		now = {a[i] , b[i]};
    		if(mp.find(now) != mp.end()) {
    			if(min({c[i] + mp[now].se , a[i] , b[i]}) > res) {
    				tag = 1;
    				res = min({c[i] + mp[now].se , a[i] , b[i]});
    				ans = {i , mp[now].fi};
    			}
    		}
    		now = {b[i] , a[i]};
    		if(mp.find(now) != mp.end()) {
    			if(min({c[i] + mp[now].se , a[i] , b[i]}) > res) {
    				tag = 1;
    				res = min({c[i] + mp[now].se , a[i] , b[i]});
    				ans = {i , mp[now].fi};
    			}
    		}
    		now = {a[i] , c[i]};
    		if(mp.find(now) != mp.end()) {
    			if(min({b[i] + mp[now].se , a[i] , c[i]}) > res) {
    				tag = 1;
    				res = min({b[i] + mp[now].se , a[i] , c[i]});
    				ans = {i , mp[now].fi};
    			}
    		}
    		now = {c[i] , a[i]};
    		if(mp.find(now) != mp.end()) {
    			if(min({b[i] + mp[now].se , a[i] , c[i]}) > res) {
    				tag = 1;
    				res = min({b[i] + mp[now].se , a[i] , c[i]});
    				ans = {i , mp[now].fi};
    			}
    		}
    		now = {b[i] , c[i]};
    		if(mp.find(now) != mp.end()) {
    			if(min({a[i] + mp[now].se , b[i] , c[i]}) > res) {
    				tag = 1;
    				res = min({a[i] + mp[now].se , b[i] , c[i]});
    				ans = {i , mp[now].fi};
    			}
    		}
    		now = {c[i] , b[i]};
    		if(mp.find(now) != mp.end()) {
    			if(min({a[i] + mp[now].se , b[i] , c[i]}) > res) {
    				tag = 1;
    				res = min({a[i] + mp[now].se , b[i] , c[i]});
    				ans = {i , mp[now].fi};
    			}
    		}		
    		if(c[i] > mp[{a[i] , b[i]}].se) {
    			mp[{a[i] , b[i]}] = {i , c[i]};
    		}
    		if(c[i] > mp[{b[i] , a[i]}].se) {
    			mp[{b[i] , a[i]}] = {i , c[i]};
    		}
    		if(b[i] > mp[{a[i] , c[i]}].se) {
    			mp[{a[i] , c[i]}] = {i , b[i]};
    		}
    		if(b[i] > mp[{c[i] , a[i]}].se) {
    			mp[{c[i] , a[i]}] = {i , b[i]};
    		}
    		if(a[i] > mp[{b[i] , c[i]}].se) {
    			mp[{b[i] , c[i]}] = {i , a[i]};
    		}
    		if(a[i] > mp[{c[i] , b[i]}].se) {
    			mp[{c[i] , b[i]}] = {i , a[i]};
    		}		
    		
    	}
    	
    	if(!tag){
    		cout << "1\n";
    		cout << id << "\n";
    	}else{
    		cout << "2\n";
    		cout << ans.fi << " " << ans.se << "\n";
    	}
    	
    	return 0;
    }
    //freopen("文件名.in","r",stdin);
    //freopen("文件名.out","w",stdout);
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115

    CF 1360 F. Spy-string

    Problem - F - Codeforces

    大意:给出 n 个长 m 的字符串 , 要求构造一个字符串和给出的每一个字符串最多有一个位置不同。或说明这种字符串不存在。

    思路:考虑到 n , m 很小 , 考虑暴力。考虑答案字符串和给出的第一个字符串有可能相同 , 也有可能存在一个位置不同 , 暴力枚举每一个位置然后枚举改变成什么 , 然后暴力检查是否合法即可。

    时间复杂度 O ( 26 n m 2 T ) 时间复杂度O(26nm^2T) 时间复杂度O(26nm2T)

    #include
    using namespace std;
    #define fi first
    #define se second
    #define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #define int long long
    const int INF = 9e18;
    const int N = 2e6 + 10;
    const int mod = 1e9 + 7;
    typedef pair<int,int>PII;
    
    int t , n , m;
    string s[20] , x , y , ans;
    
    bool judge(string now){
    	for(int i = 1 ; i <= n ; i ++) {
    		int res = 0;
    		for(int j = 0 ; j < m ; j ++) {
    			if(now[j] != s[i][j]) res += 1;
    		}
    		if(res > 1) return 0;
    	}
    	return 1;
    }
    
    signed main(){
    
    	IOS
    	cin >> t;
    	
    	while(t --) {
    		cin >> n >> m;
    		for(int i = 1 ; i <= n ; i ++) cin >> s[i];
    		x = s[1];
    		bool tag = 0;
    		
    		for(int i = 0 ; i < m ; i ++) {
    			y = x;
    			for(char j = 'a' ; j <= 'z' ; j ++) {
    				y[i] = j;
    				if(judge(y)) {
    					tag = 1;
    					ans = y;
    				}
    			}
    		}
    		if(tag) {
    			cout << ans << "\n"; 
    		} else {
    			cout << "-1\n";
    		}
    	}
    
    	return 0;
    }
    //freopen("文件名.in","r",stdin);
    //freopen("文件名.out","w",stdout);x`x`
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
  • 相关阅读:
    Explain详解与索引最佳实践
    【区块链 | Openzeppelin】探索Openzeppelin 新增的跨链功能
    MySQL数据类型
    音视频同步
    中电金信:The Financial-Grade Digital Infrastructure
    html表格标签的学习,什么是html的表格标签
    【中国平安社招校招】【内推】【当天内推】
    【Vue】使用插槽和具名插槽解决组件内容传递问题(2)
    基于图卷积神经网络的微博疫情情感分析
    logback--进阶--04--配置
  • 原文地址:https://blog.csdn.net/woshilichunyang/article/details/133662415