Preface
不想上学。
Content
[CF827C]DNA Evolution
给定一个字符串 \(s\)。
\(Q\) 次询问，每次有两种操作：
1 x c，表示把 \(s\) 的第 \(x\) 个字符换成 \(c\)。
2 l r e，表示把字符串 \(e\) 在 \(s_{l\sim r}\) 下方重复写无数次，求相同位置字符相同的个数。\(1\le |s|,Q \le 10^5,1\le |e| \le 10\)。
看到 \(|e| \le 10\) 的范围，直接从这点下手。
因为 \(e\) 写无数次具有周期性，我们可以一次性统计 $\bmod |e| $ 值相同的位置。
直接树状数组维护一下就好了。时间复杂度 \(O(|s|\log |s|\times |e|^2)\)，可以更快，但我懒。
Code
// Problem: CF827C DNA Evolution
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF827C
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
char s[maxn],t[15],A[] = {'A' , 'T' , 'G' , 'C'};
int n,m,Q,pos[100];
struct BIT {
int c[maxn];
int lowbit(int x) {
return x & -x;
}
void add(int x,int y) {
for(;x <= n;x += lowbit(x))c[x] += y;
return ;
}
int query(int x) {
int ans = 0;
for(;x;x -= lowbit(x))ans += c[x];
return ans;
}
}tr[11][10][4];
int main() {
scanf("%s",s + 1);
n = strlen(s + 1);
for(int i = 0;i < 4;++ i)pos[A[i]] = i;
for(int i = 1;i <= n;++ i) {
for(int j = 1;j <= 10;++ j) {
tr[j][i % j][pos[s[i]]].add(i , 1);
}
}
scanf("%d",&Q);
while(Q --) {
int op;
scanf("%d",&op);
if(op & 1) {
int x;
char c;
scanf("%d %c",&x,&c);
for(int j = 1;j <= 10;++ j) {
tr[j][x % j][pos[s[x]]].add(x , -1);
tr[j][x % j][pos[c]].add(x , 1);
}
s[x] = c;
}
else {
int l,r,ans = 0;
scanf("%d %d %s",&l,&r,t + 1);
m = strlen(t + 1);
for(int i = 1;i <= m;++ i) {
if(l + i - 1 > r)break ;
int k = l + i - 1 + ((r - l - i + 1) / m * m);
ans += tr[m][(l + i - 1) % m][pos[t[i]]].query(k) - tr[m][(l + i - 1) % m][pos[t[i]]].query(l + i - 2);
}
printf("%d\n",ans);
}
}
return 0;
}
[CF903D]Almost Difference
给定序列 \(a_{1\sim n}\)，定义 \(d(x,y)\)：
if abs(x - y) > 1 then return y - x; else return 0;求 \(\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^n d(a_i,a_j)\)。
\(1\le n\le 2\times 10^5,1\le a_i\le 10^9\)，答案可能爆
long long。
因为这题爆 long long，所以存储要用 long double。
其它没啥好说的，整个 std::map 存一下就行。
时间复杂度 \(O(n\log n)\)。
Code
// Problem: CF903D Almost Difference
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF903D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef long double ld;
int n;
std::map<int,int> s;
ld sum,ans;
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i) {
int x;
scanf("%d",&x);
ans += 1ll * (i - 1) * x - sum + s[x + 1] - s[x - 1];
++ s[x];
sum += x;
}
printf("%.0Lf",ans);
return 0;
}
[CF837D]Round Subset
给定 \(a_{1\sim n}\)，选出其中 \(k\) 个数，使它们乘积末尾 \(0\) 的数量最大化。
\(1\le k\le n\le 200,1\le a_i\le 10^{18}\)。
根据小学数学的知识，我们知道，\(0\) 的数量等于 \(2\) 和 \(5\) 出现次数的较小值。
考虑 DP，因为 \(5\) 数量较少，所以考虑将 \(5\) 的数量设入状态。
令 \(f(i,j,p)\) 表示前 \(i\) 个数选了 \(j\) 个，其中含 \(p\) 个 \(5\) 时 \(2\) 数量的最大值。
显然有 \(f(i,j,p)=\max\{f(i-1,j,p),f(i-1,j-1,p-sum_5(a_i))+sum_2(a_i)\}\)。
这个式子还能用滚动数组优化下空间。时间复杂度 \(O(n^2k\log_5 a)\)。
Code
// Problem: CF837D Round Subset
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF837D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 6005;
int n,k,f[maxn][maxm],b[maxn],c[maxn];
int main() {
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;++ i) {
long long p;
scanf("%lld",&p);
for(long long x = p;!(x & 1);x >>= 1)++ b[i];
for(long long x = p;!(x % 5);x /= 5)++ c[i];
}
memset(f , 0xcf , sizeof(f));
f[0][0] = 0;
for(int i = 1;i <= n;++ i) {
for(int j = std::min(i , k);j;-- j) {
for(int p = 30 * i;p >= c[i];-- p) {
f[j][p] = std::max(f[j][p] , f[j - 1][p - c[i]] + b[i]);
}
}
}
int ans = 0;
for(int i = 1;i <= 30 * n;++ i)ans = std::max(ans , std::min(i , f[k][i]));
printf("%d",ans);
return 0;
}
[CF1271E]Common Number
题面太长，懒得写。
我的思路和题解里其他大佬的思路不太一样。
定义 calc(x) 为 \(x\) 在 \(path_j\) 中出现的次数。
打个表发现 \(calc(x)\) 没有规律，但 std::max(calc(x),calc(x + 1)) 是单调递减的。
根据这个规律，二分答案即可。
至于 calc(x) 的计算我实在想不出来，可以看 这位大佬的题解。
Code
// Problem: CF1271E Common Number
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1271E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll calc(ll x) {
if(x > n)return 0;
int lg = floor(log2(n / x));
ll ans = (1ll << lg) - 1 + std::min(n - x * (1ll << lg) + 1 , (1ll << lg));
if(x & 1)return ans;
return ans + calc(x + 1);
}
int main() {
scanf("%lld %lld",&n,&k);
ll l = 1,r = n;
while(l <= r) {
ll mid = l + r >> 1;
if(std::max(calc(mid) , calc(mid + 1)) >= k)l = mid + 1;
else r = mid - 1;
}
if(calc(r + 1) >= k)printf("%lld",r + 1);
else printf("%lld",r);
return 0;
}
[lugu P5851][USACO19DEC]Greedy Pie Eaters P
题意不想写了。
摆了，不写题解了，直接放代码。
Code
// Problem: P5851 [USACO19DEC]Greedy Pie Eaters P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5851
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
typedef long long ll;
int n,m,g[maxn][maxn][maxn];
ll f[maxn][maxn];
int main() {
scanf("%d %d",&n,&m);
for(int i = 1;i <= m;++ i) {
int l,r,x;
scanf("%d %d %d",&x,&l,&r);
for(int j = l;j <= r;++ j) {
g[l][r][j] = std::max(g[l][r][j] , x);
}
}
for(int len = 2;len <= n;++ len) {
for(int i = 1;i + len - 1 <= n;++ i) {
int j = i + len - 1;
for(int k = i;k <= j;++ k) {
g[i][j][k] = std::max(g[i][j][k] , std::max(g[i + 1][j][k] , g[i][j - 1][k]));
}
}
}
for(int len = 1;len <= n;++ len) {
for(int i = 1;i + len - 1 <= n;++ i) {
int j = i + len - 1;
for(int k = i;k <= j;++ k) {
f[i][j] = std::max(f[i][j] , f[i][k - 1] + f[k + 1][j] + g[i][j][k]);
}
}
}
printf("%lld",f[1][n]);
return 0;
}
明天要去学校了，希望上午能学会 Pollard-Rho，让我的 AC 300 是 [Ynoi2015] 此时此刻的光辉