1.数星星(二分)
题意
天上有n颗星星，每颗星星从第秒（包含边界）开始闪烁，闪烁周期是秒，天上每颗星星每闪烁一次，小度便会记一次数。
假设小度今晚从第l秒开始数，第r秒天就亮了，当数到c颗星星的时候，小度便会睡着。
请问小度今晚是否能睡着？如果能，将在第几秒睡着，反之则输出“-1”。
数据范围
思路
答案具备单调性，且范围极大，正解显然是二分答案！设小度第x秒睡着，显然答案下界为l，上界为r，也就是从l秒开始数直到第x秒结束，判断计数值是否不小于c。
假设星星在第x秒开始闪烁并计数，第y秒结束，闪烁周期为w,则闪烁次数为;如若在第x秒开始闪烁，但从第l秒才开始计数，第y秒结束，则严格大于第l秒的第一次开始计数的时间t为，易知，当y-x能被w整除时，边界点l也需计数一次，同理，之后的计数为.
Code:
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
| #include<bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main(){
std::ios::sync_with_stdio(false);cin.tie(0);
int n;
i64 l, r, c;
cin >> n;
vector<i64> a(n + 1), b(n + 1);
for (int i = 1; i <= n;i++)cin >> a[i];
for (int i = 1; i <= n;i++)cin >> b[i];
cin >> l >> r >> c;
auto check = [&](i64 x) -> bool
{
i64 res = 0;
for (int i = 1; i <= n;i++){
if(b[i]>x)continue; //计数值显然为零
if(b[i]<l){
i64 ll = b[i] + ((l - b[i]) / a[i] + 1) * a[i]; //ll代表从l秒往后开始第一次闪烁的秒数
if ((l - b[i]) % a[i] == 0){ //特判边界值
res++;
if(res>=c)
return 1;
}
if(x>=ll){
res += (x - ll) / a[i] + 1;
if (res >= c)
return 1;
}
}else{
res += (x - b[i]) / a[i] + 1;
if (res >= c)
return 1;
}
}
return 0;
};
i64 L = l, R = r, ans = -1;
while (L <= R){
i64 mid = L + R >> 1;
if(check(mid))
R = mid - 1, ans = mid;
else
L = mid + 1;
}
cout << ans << endl;
return 0;
}
|
2.激光控制器（离散化+差分）
题意
坐标轴上每个整数点都配备了激光控制器，初始状态下所有控制器面朝北方，每拨动一次都会按照”北-东-南-西-北“的顺时针方向循环。
小度从坐标原点出发，进行N次操作，每次操作用一个整数和一个字符表示，其中表示从当前控制器开始连续拨动多少个控制器，表示拨动方向。数据保证小度不会偏离原点单位。
给定小度的操作序列，请求出最终朝向东方的激光器有多少台。
数据范围
思路
对于连续区间的修改，很明显的思路就是差分，但是题目中最大的坐标范围高达,在最终统计时复杂度必然无法满足。然而，我们发现的上限仅，可以对每次进行独立的考虑。
不难发现，每次操作的区间范围可以求得，也就是区间的端点是固定的且不超过个，我们可以对这些端点离散化排序，所以区间操作的变化本质上就是端点间的“跳跃”和区间赋值。
满足条件的区间条件就是操作数量模4等于1，为方便统计，将每个区间的端点以右端点为准，表示整个块，每个独立的块内部的操作数显然是相同的，起始的右端点为原点，每次区间变化使用差分技巧，并对右端点进行特判(原因详见代码注释)，在最终统计时只需遍历相邻区间端点，数量就是相邻坐标的差值。
Code:
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
| #include<bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main(){
std::ios::sync_with_stdio(false);cin.tie(0);
int n;
cin >> n;
vector<int> a(n + 2), b(n + 2), x(n + 1), diff(n + 2);
vector<char> op(n + 1);
map<int, bool> mp; //统计存在的右端点下标值
map<int, int> idx; //右端点对应的块号
mp[0] = 1;
int cur = 0; //右端点值
for (int i = 1; i <= n;i++){
cin >> x[i] >> op[i];
if(op[i]=='R')
cur += x[i] - 1, mp[cur] = 1;
else
cur -= x[i] - 1, mp[cur] = 1;
}
int cnt = 0;
for(auto it:mp){
idx[it.first] = ++cnt;
b[cnt] = it.first;
}
cur = 0;
int mn, mx;
for (int i = 1; i <= n;i++){
if(op[i]=='R'){
mn = idx[cur];
cur += x[i] - 1;
mx = idx[cur];
}else{
mx = idx[cur];
cur -= x[i] - 1;
mn = idx[cur];
}
a[mx]++;
diff[mn]++, diff[mx]--;
//对每个右端点当做差分的上界，所以单个右端点需要进行特判
}
int res = 0, ans = 0;
for (int i = 1; i < cnt;i++){
res += diff[i];
if(res%4==1) //除去右端点的块内操作数
ans += b[i + 1] - b[i] - 1;
if ((res + a[i]) % 4 == 1) //右端点的操作数
ans++;
}
res += diff[cnt] + a[cnt];
if(res%4==1)
ans++;
cout << ans << endl;
return 0;
}
|
3.好像相等（字符串哈希）
题意
给定一个长度为n的小写字母字符串s，q次询问其子串与是否完全相等，如果不相等，那么将他们修改成相等字符串则需要最少将多少种字符更改为“*”,并从小到大输出更改的字符种类.
数据范围
思路
由于q的询问次数高达次，很显然需要采用离线算法，又涉及到字符串的子串问题，不难想到字符串哈希。由于修改是针对某个字符进行修改，所以我们可以对每个字符单独计算其各个位置的前缀哈希值。
关键是如何判断对应子串位置的哈希值相同，例如字符串“[aba]ss[aba]”，对于子串[1,3]与[6,8]的a字符，只需判断与之间是否存在线性关系，其系数显然等于，x表示两个子区间的距离（或）。
所以接下来使用双哈希取模法，预处理pw数组（base的指数），维护出某个字符的前缀哈希值，遍历26个字母判断子区间哈希值，将不满足的字符存入vector中即可。
PS:题设条件不保证，所以输入区间端点的时候务必判断左右方位！！！
Code:
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
| #include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
char s[100010];
i64 Hash1[30][100010], Hash2[30][100010], pw1[100010], pw2[100010];
//Hash[i][j]表示字符i在前j个位置的前缀哈希值，pw[i]表示base^i
const i64 base1 = 1313131, base2 = 233333;
const i64 p1 = 1e9 + 7, p2 = 1e9 + 9;
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
int n, q;cin >> n >> q;
cin >> s + 1;
pw1[0] = pw2[0] = 1;
for (int i = 1; i <= 26;i++)
Hash1[i][0] = Hash2[i][0] = 0;
for (int i = 1; i <= n; i++){
pw1[i] = (pw1[i - 1] * base1) % p1;
pw2[i] = (pw2[i - 1] * base2) % p2;
for (int j = 1; j <= 26;j++){
Hash1[j][i] = Hash1[j][i - 1];
Hash2[j][i] = Hash2[j][i - 1];
if (s[i] - 'a' + 1 == j){
Hash1[j][i] = (Hash1[j][i] + (j * pw1[i]) % p1) % p1;
Hash2[j][i] = (Hash2[j][i] + (j * pw2[i]) % p2) % p2;
}
}
}
auto getHash1 = [&](int L, int R, int c) -> i64
{
return (Hash1[c][R] - Hash1[c][L - 1] % p1 + p1) % p1;
};
auto getHash2 = [&](int L, int R, int c) -> i64
{
return (Hash2[c][R] - Hash2[c][L - 1] % p2 + p2) % p2;
};
while(q--){
int lx, rx, ly, ry;
cin >> lx >> rx >> ly >> ry;
if(lx>ly) //保证区间[lx,rx]在左方位
swap(lx, ly), swap(rx, ry);
vector<int> v;
for (int i = 1; i <= 26;i++){
if ((getHash1(lx, rx, i) * pw1[ly - lx]) % p1 == getHash1(ly, ry, i) && (getHash2(lx, rx, i) * pw2[ly - lx]) % p2 == getHash2(ly, ry, i))
continue;
v.emplace_back(i);
}
cout << v.size() << endl;
for(auto it:v){
char ch = (it + 'a' - 1);
cout << ch;
}
cout << endl;
}
return 0;
}
|
微信
支付宝