专栏文章

10.15 下午总结

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlk0c2
此快照首次捕获于
2025/12/02 04:23
3 个月前
此快照最后确认于
2025/12/02 04:23
3 个月前
查看原文

P13867 [SWERC 2020] Unique Activities

好遗憾。。。map<ull, int> 写成了 map<ull, bool>，没改出来，写了个暴力。
因为长度为 lenlen 的子串满足， ≥len\ge len 的也满足，发现重复子串的长度具有单调性，考虑二分答案。
在 check⁡\operatorname{check} 函数中，对长度为 lenlen 的子串的哈希值进行统计，再检查是否有唯一的，若有，记录起始下标 st=ist = i，并缩小二分答案的区间。
CPP
#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int N = 3e5 + 10, P = 13331;

string s;
int n, st;
ull hs[N], pw[N];
map<ull, int> mp;

ull get_hs(int l, int r) {
	return hs[r] - hs[l - 1] * pw[r - l + 1];
}

bool check(int mid) {
	if (mid == 0 || mid > n)
		return 0;
	mp.clear();
	for (int i = 1; i + mid - 1 <= n; i++) {
		int j = i + mid - 1;
		mp[get_hs(i, j)]++;
	}
	for (int i = 1; i + mid - 1 <= n; i++) {
		int j = i + mid - 1;
		if (mp[get_hs(i, j)] == 1) {
			st = i;
			return 1;
		}
	}
	return 0;
}

signed main() {
	cin >> s;
	n = s.size();
	s = ' ' + s;
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * P;
		hs[i] = hs[i - 1] * P + s[i];
	}
	int l = 0, r = n + 1;
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	cout << s.substr(st, r);
	return 0;
}

P4656 CEOI 2017 Palindromic Partitions

嗯。这个思路一样，但是错了。
  1. 整个字符串若可以划分，一定是从中间位置堆成；
  2. 考虑贪心，从两端向中间枚举，若出现相同的串，直接截取，答案加二，到了对称轴的时候停止，答案加一。
CPP
#include<bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int N = 1e6 + 5, base = 13331;
ull hs[N], ht[N], pw[N];
int n;

signed main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		int n = s.size();
		int s1 = 0, s2 = 0, B = 1, ans = 0;
		for (int i = 0; i < n / 2; i++) {
			s1 = s1 * base + s[i];
			s2 = s2 + s[n - i - 1] * B;
			B = B * base;
			if (s1 == s2)
			{
				ans += 2;
				s1 = s2 = 0;
				B = 1;
			}
		}
		if (n % 2 == 1 || s1)
			ans++;
		cout << ans << "\n";
	}
	return 0;
}

P3105 [USACO14OPEN] Fair Photography S

设白色为 1，黑色为 -1，维护前缀和 sumisum_i。
枚举右端点 ii，若 sumi≥0sum_i \ge 0，判断其是否为偶数，若是，[1,i][1,i] 这段区间就是最大的，否则 [2,i][2,i] 这段区间就是最大的。
若 sumi<0sum_i < 0，若 sumisum_i 的下标之前已经被统计过了，则 [mpsumi+1,i][mp_{sum_i + 1},i] 这段区间就是最大的，否则记录下标。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;

int n, ans, sum[N];

struct node {
    int x, w;
} a[N];
map<int, int> mp;

bool cmp(node a, node b) {
    return a.x < b.x;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> a[i].x >> c;
        if (c == 'W') a[i].w = 1;
        else a[i].w = -1;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i].w;
        if (mp[sum[i]] == 0 && sum[i] < 0)
            mp[sum[i]] = i;
        else if (sum[i] < 0)
            ans = max(ans, a[i].x - a[mp[sum[i]] + 1].x);
        if (sum[i] % 2 == 0 && sum[i] >= 0)
            ans = max(ans, a[i].x - a[1].x);
        else if (sum[i] >= 0)
            ans = max(ans, a[i].x - a[2].x);
    }
    cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...