字符串思维题练习 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<bits/stdc++.h>
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);

CF 733 D. Kostya the Sculptor(哈希)

Problem - D - Codeforces

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

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

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

能表示出面的全集即可

#include<bits/stdc++.h>
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(){IOScin >> 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);

CF 1360 F. Spy-string

Problem - F - Codeforces

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

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

$时间复杂度O(26nm^2T)$

#include<bits/stdc++.h>
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(){IOScin >> 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`