|
|
显然昨天是没更新，被各种催qwq。
A. The Ultimate Square 找规律
题意：
给定整数 n ，表示存在长度为 \lfloor i \rfloor (i \in [1, n]) 宽度为 1 的木板，求这些木板能够拼接成的变长最大的正方形。
分析：
找规律以及和样例发现答案是 \lceil x \rceil 。
代码：
void solve()
{
cin >> n;
cout << (n + 1) / 2 << endl;
}
B. Diverse Substrings 思维
题意：
定义一种特殊的数字串当且仅当该串出现的数字种类大于等于出现次数最多的数。给定一个初始串，求存在多少子串是特殊的。
分析:
刚开始往双指针想了，结果发现不满足双指针的性质。于是发现数的种类只有 10 个，那么长度超过 100 的串一定是不特殊的。因此从每一个下标出发，枚举接下来长度为 100 以内的子串暴力判断即可。
代码：
void solve()
{
cin >> n;
string s;
cin >> s;
s = &#34;?&#34; + s;
int mx = 0, cc = 0, ans = 0;
for(int i = 0 ; i < 10 ; i ++ ) cnt = 0;
for(int i = 1; i <= n ; i ++ ) {
for(int j = 0 ; j < 10 ; j ++ ) cnt[j] = 0;
mx = 0, cc = 0;
for(int j = i; j <= min(i + 99, n); j ++ ) {
cnt[s[j] - &#39;0&#39;] ++ ;
if(cnt[s[j] - &#39;0&#39;] == 1) cc ++ ;
mx = max(cnt[s[j] - &#39;0&#39;], mx);
if(cc >= mx) ans ++ ;
}
}
cout << ans << endl;
}
C. Zero-Sum Prefixes
题意：
给定一个长度为 n 的数组，对于某一位置 i 满足 a_i = 0 ，可以将 a_i 修改为任意整数。求最终前缀和数组中 0 出现的最多次数。
分析:
考虑从后往前构造。如果一个 0 出现，最优操作一定是让这个 0 后面出现次数最多的某一个值变成 0。虽然在这个 0 前面可能仍然存在 0，但是我们一定可以让这个位置的 0 自适应成某一个值使得出现次数最多的值的前缀和变为 0 。
通解： 考虑两个 0 之间出现次数最多的数，也就是对答案真正的贡献。最少的贡献是 1 。
坑点： 第一个 0 出现前的位置如果前缀和为 0 记得要加到答案上。
代码：
void add(int x) {
mp[x] ++ ;
mx = max(mp[x], mx);
}
void clear(int x) {
mx = cnt = 0;
for(int i = x; i <= n ; i ++ )
if(st) return ;
else mp[s] -- , st = true;
}
void solve()
{
cin >> n;
mp.clear();
mx = cnt = 0;
for(int i = 1; i <= n ; i ++ ) {
cin >> a;
s = s[i - 1] + a;
st = 0;
}
int ans = 0, last = n + 1;
for(int i = n; i >= 1 ; i -- ) {
add(s);
if(a == 0) {
ans += max(1ll, mx);
last = i;
clear(i);
}
}
for(int i = 1; i <= n ; i ++ ) {
if(a == 0) break;
else if(s == 0) ans ++ ;
}
cout << ans << endl;
}
D. ConstructOR 构造 or exgcd
题意：
给定三个整数 a, b, d ，求一个整数 x 使得其满足 a|x 和 b|x 可以被 d 整除。
1 \leq a, b, c < 2^{30}, 0 \leq x < 2 ^ {60}
分析:
解法1:
我们构造 x ，每次都让 x 加上 d 的整数倍。因为 x 的范围 2^{60} ，因此在值上是不会溢出的。现在我们的目的是让 x 与 a , b or 后值相同。如果 a 或 b 在某一位 i 上出现了 1 ，那么我们让 d 直接与这一位对齐，也就是让 x 加上 d*2^{i - t} ，其中 t 表示 x 的前导 0 的数量。接下来一旦出现答案和 a | b 在某一位不一致的情况，直接加上位移后的 d 对齐即可。( | 表示按位或 )
如果 d 的前导 0 的数量大于 a|b 显然一定无解。
明天更 exgcd 的思路qwq。
解法2:
对于 a 和 b ，我们直接让 nw = a | b ，我们的目的是构造一个 d 的倍数 x 使得 x | nw = x 。假如我们直接拿 nw 当最终的答案的话，最终会剩下 nw \space \text{mod} \space d 的余数。我们构造的 x 在范围上是 a|b 的平方倍，因此可以考虑用多出来的 30 位去构造出一个对 d 的余数为 (d - nw \space mod \space d) 的值，这就需要解一个线性同余方程。
x * 2^{30} \equiv t \space mod \space d
我们根据这个同余方程构造出： x * 2^{30} + y * d =t ，解方程找到一个正整数解即可。 x 化为 x * t / gcd ，最终的答案是： x * 2^{30} + nw 。
关于证明为什么一定存在或者不会爆精度的问题暂时也没想明白qwq。
代码1：
void solve(){
int a, b, d;
cin >> a >> b >> d;
int t1 = __builtin_ctzll(d);
int t2 = min(__builtin_ctzll(b), __builtin_ctzll(a));
if(t1 > t2){
cout << -1 << endl;
return ;
} else {
int c = a | b;
int x = 0;
for(int i = 0; i < 30 ; i ++)
if((x >> i & 1) == 0 && (c >> i & 1) == 1)
x += d << (i - t1);
cout << x << endl;
}
}
代码2:
int exgcd(int a, int b, int &x, int &y) {
if(!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve() {
cin >> a >> b >> d;
int t1 = __builtin_ctzll(d);
int t2 = min(__builtin_ctzll(b), __builtin_ctzll(a));
if(t1 > t2){
cout << -1 << endl;
return ;
}
int nw = a | b;
int t = (d - nw % d) % d;
int x, y;
int gcd = exgcd(1 << 30, d, x, y);
x = (x * t / gcd) % d;
if(x < 0) x += d;
cout << (1 << 30) * x + nw << endl;
} |
|
喧嚣卡
千斤顶
照妖镜
