前言

        势必要拿下的一场比赛，最后结果也算如愿。

        Standings：300

        重新回到蓝名了，也完成了之前 “ 早日在比赛切掉 6 题 ” 的期望。

        题目链接：Dashboard - Codeforces Round 962 (Div. 3) - Codeforces

A. Legs

        第一次在第一分钟就切题 ~~

        题意：

        Farmer John 的农场只有鸡和牛，他数出动物一共有 n 条腿，问最少有多少只动物。

        思路：

        因为牛有四条腿，尽可能多地让牛的腿去填满 n 。

#include<cstdio>
#include<cstring>
using namespace std;int T,n;int main()
{scanf("%d",&T);while (T --){scanf("%d",&n);printf("%d\n",(n + 2) / 4);}return 0;
}

B. Scale

        题意：

        给一个 01 矩阵，你需要把这个矩阵分成若干个 k * k 的子矩阵，每一个子矩阵都缩成一个单个的块，其值等于原来子矩阵内每个格的值（题目保证每个子矩阵的所有格的数字都一样）。

        例如：

        0 0 0 1 1 1

        0 0 0 1 1 1

        0 0 0 1 1 1

        1 1 1 0 0 0

        1 1 1 0 0 0

        1 1 1 0 0 0

        k = 3 时  ->

        0 1

        1 0

        思路：

        题目说得很清楚了，好像不知道该怎么讲。。。

#include<cstdio>
#include<cstring>
using namespace std;#define N 1005int T,n,k,a[N][N];
char s[N];int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&k);for (int i = 1;i <= n;++ i){scanf(" %s",s + 1);for (int j = 1;j <= n;++ j) a[i][j] = s[j] - '0';}for (int i = 1;i <= n / k;++ i){for (int j = 1;j <= n / k;++ j) printf("%d",a[(i - 1) * k + 1][(j - 1) * k + 1]);printf("\n");}}return 0;
}

C. Sort

        题意：

        给两个长度为 n 的字符串 a 和 b （由小写拉丁字母组成），你需要回答 q 个询问。

        询问之间是独立的，每个询问给你一个区间范围 [l,r] ，每次操作你可以任意选择一个 i ，令 ，x 可以是任意字符，求最少进行多少次操作可以让 sorted( a[l..r] ) = sorted( b[l..r] ) 。

        思路：

        因为对于 b 在 a 中每个缺失的字符都需要 1 次操作来填补，而我们并不关心到底是通过变化哪个 a 中的字符来满足条件。这样问题就转化为了在区间 [l,r] 内，每种字符 a 比 b 少多少个 （a 比 b 多的话记为 0），然后算总和。

        由于字符种类只有 26 种，给每种字符记录出现次数的前缀和即可算区间出现数目。

        比赛的时候没想那么多直接开敲，打了树状数组，虽然麻烦了点且多耗了点时间，但好在还是一遍过了。

#include<cstdio>
#include<cstring>
using namespace std;#define N 200005int T,n,q,t[30],now[30],tra[30][N],trb[30][N],ans;
char a[N],b[N];int lowbit(int x) { return x & (-x) ; }void adda(int x,int y)
{for (int i = y;i <= n;i += lowbit(i))++ tra[x][i];return;
}void addb(int x,int y)
{for (int i = y;i <= n;i += lowbit(i))++ trb[x][i];return;
}int aska(int x,int y)
{int tmp = 0;for (int i = y; i ;i -= lowbit(i))tmp += tra[x][i];return tmp;
}int askb(int x,int y)
{int tmp = 0;for (int i = y; i ;i -= lowbit(i))tmp += trb[x][i];return tmp;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&q);scanf("%s%s",a + 1,b + 1);for (int i = 1;i <= 26;++ i)for (int j = 1;j <= n;++ j) tra[i][j] = trb[i][j] = 0;for (int i = 1;i <= n;++ i){int na = a[i] - 'a' + 1;int nb = b[i] - 'a' + 1;adda(na,i),addb(nb,i);}while (q --){int l,r;scanf("%d%d",&l,&r),ans = 0;for (int i = 1;i <= 26;++ i){int ta = aska(i,r) - aska(i,l - 1);int tb = askb(i,r) - askb(i,l - 1);ans += (ta < tb) ? (tb - ta) : 0;}printf("%d\n",ans);}}return 0;
}

D. Fun

        题意：

        给两个正整数 n 和 x （ 1 <= n,x <= 10^6 ），计算满足条件的三元组的数目。

        1. ab + ac + bc <= n

        2. a + b + c <= x

        3. a,b,c 为正整数

        注意（1,1,2）和（1,2,1）是不同的三元组。

        思路：

        注意到 n 比较大，直接枚举 a,b,c 肯定会超时。

        条件 1 是乘法再相加，从这里入手：假设我们枚举 a ，那么根据 ab < ab + ac + bc <= n ，b的取值就是  的量级，这时候我们枚举 b <  ，根据调和级数复杂度就是 O（n log n）的。枚举完 a 和 b 之后，根据条件 2 可以确定 c 的取值范围：0 < c <= x - a - b 。我们在做的时候设定 a <= b <= c ，最后根据情况乘上对应的组合数即可。

        最终的时间复杂度：O（n log n）

#include<cstdio>
#include<cstring>
using namespace std;int T,n,x;
long long ans;int min(int x,int y) { return x < y ? x : y ; }int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&x),ans = 0ll;for (int a = 1;a <= x;++ a)for (int b = a;b <= (n / a);++ b){int r = min(x - (a + b),(n - a * b) / (a + b));int l = b;if(l > r) break;if(a == b) ans += 1ll + 3ll * (r - l);else ans += 3ll + 6ll * (r - l);}printf("%lld\n",ans);}return 0;
}

E. Decode

        题意：

        给一个长度为 n 的 01 串 s ，对每一对（l,r），统计 0 和 1 个数相等的子区间 [x,y] 数目。

        思路：

        显然不能直接做，我们考虑计算每一个 0 和 1 个数相等的子区间的贡献。

        记一个 0 为 +1 ，一个 1 为 -1 ，满足条件的区间 [x,y] 即为区间和为 0 的区间，即第 y 位和第 x - 1 位的前缀和相等，那么这段区间的贡献就是 x * (n - y + 1) 。但是这么做还是太慢，我们发现可以统计不同前缀和的值对应的区间左端点 x 的和，这样每加入一个新的 y 作为右端点时，y 的贡献就变成了 ，这样就把时间优化到线性了。

        记得取模 ！！！

#include<cstdio>
#include<cstring>
using namespace std;#define N 200005
#define mod 1000000007int T,n,now[N * 5],pre[N * 5],cnt[N * 5];
long long ans;
char s[N];int main()
{scanf("%d",&T);while (T --){scanf("%s",s + 1),n = strlen(s + 1),pre[0] = N;for (int i = -n;i <= n;++ i) now[i + N] = -1,cnt[i + N] = 0;now[N] = 0,ans = 0ll,cnt[N] = 1;for (int i = 1,x,y,tmp;i <= n;++ i){x = (s[i] == '0') ? 1 : -1 ;pre[i] = pre[i - 1] + x;if(now[pre[i]] != -1) ans = (ans + 1ll * cnt[pre[i]] * (n - i + 1)) % mod;now[pre[i]] = i;cnt[pre[i]] = (cnt[pre[i]] + i + 1) % mod;}printf("%lld\n",ans);}return 0;
}

F. Bomb

        题意：

        给两个序列 a 和 b ，你的初始得分为 0 ，每一轮你可以选择一个 i 并得到  的收益，然后令  。你只有 k 轮操作机会，求最大得分。

        思路：

        首先贪心地想，我们每轮都需要选择当前场上最大的那个数，但暴力做显然会超时。我们可以二分最后选择的那个数（即选择的最小的数）的大小，计算把这个数选上要花多少轮，不断地靠近 k 即可。注意二分值可能对应多个相同的数，不一定会全部选完，写得时候注意细节。

#include<cstdio>
#include<cstring>
using namespace std;#define N 200005int T,n,a[N],b[N];
long long k,ans;long long max(long long x,long long y) { return x > y ? x : y ; }long long check(int x)
{long long tmp = 0ll;for (int i = 1;i <= n;++ i)if(a[i] >= x)tmp += 1ll + (a[i] - x) / b[i];return tmp;
}long long count(int x)
{long long tmp = 0ll;for (int i = 1;i <= n;++ i){if(a[i] < x) continue;if(a[i] < b[i]){tmp += 1ll * a[i];continue;}int m = 1 + (a[i] - x) / b[i];int fst = a[i] - (m - 1) * b[i];int lst = a[i];tmp += 1ll * (fst + lst) * m / 2ll;}return tmp;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&k),ans = 0ll;long long l = 0ll;long long r = 0ll;for (int i = 1;i <= n;++ i) scanf("%d",&a[i]),r = max(r,1ll * a[i]);for (int i = 1;i <= n;++ i) scanf("%d",&b[i]);while (l <= r){int mid = (l + r) >> 1;if(check(mid) <= k) r = mid - 1,ans = max(ans,count(mid));else if(check(mid + 1) < k && check(mid) > k) r = mid - 1,ans = max(ans,count(mid + 1) + 1ll * mid * (k - check(mid + 1)));else l = mid + 1;}printf("%lld\n",ans);}return 0;
}

G. Penacony

        题意：

        n 个房子 n 条道路连成一个环，所有道路都是双向的但开始时都没有维修，维修之后道路才可以通行。给出 m 对关系 a,b（a < b），表示 a,b 之间一定要有一条通路，求最少维修的道路数量。

        思路：

        对于每一对关系，只有两种方式可以连通，一种是 a - > b ，另一种是 b - > n - > 1 - > a 。因此假设某条道路是不维修的，那么所有关系的连通方式都是确定唯一的。

        我们先假设初始状态：每对关系都是 a - > b 连通，用线段树标记路径。之后枚举不维修的道路，把曾经覆盖了这条路的记录去掉，再标记这条路相对的那条路径，查询 n 条道路中有多少条是被覆盖了的即可。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;#define N 200005int T,n,m,a[N],b[N],vis[N],ans;
vector<int> c[N];struct Tree
{int val,tag;
}tr[N << 2];void build(int k,int l,int r)
{tr[k].tag = tr[k].val = 0;if(l == r) return;int mid = (l + r) >> 1;build(k << 1,l,mid),build((k << 1) | 1,mid + 1,r);return;
}void update(int k,int l,int r,int x,int y,int w)
{if(x > y) return;if(l >= x && r <= y){tr[k].tag += w;if(tr[k].tag) tr[k].val = r - l + 1;else tr[k].val = tr[k << 1].val + tr[(k << 1) | 1].val;if(l == r && !tr[k].tag) tr[k].val = 0;return;}int mid = (l + r) >> 1;if(x <= mid) update(k << 1,l,mid,x,y,w);if(y > mid) update((k << 1) | 1,mid + 1,r,x,y,w);if(tr[k].tag) tr[k].val = r - l + 1;else tr[k].val = tr[k << 1].val + tr[(k << 1) | 1].val;return;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&m),ans = n;for (int i = 0;i <= n;++ i) c[i].clear();build(1,1,n);for (int i = 1;i <= m;++ i)scanf("%d%d",&a[i],&b[i]),vis[i] = 0,c[a[i]].push_back(i),c[b[i] - 1].push_back(i);for (int i = 1;i <= m;++ i) update(1,1,n,a[i],b[i] - 1,1);for (int i = 1;i <= n;++ i){for (auto j : c[i]){if(!vis[j]){update(1,1,n,a[j],b[j] - 1,-1);update(1,1,n,b[j],n,1);update(1,1,n,1,a[j] - 1,1);vis[j] = 1;}else{update(1,1,n,a[j],b[j] - 1,1);update(1,1,n,b[j],n,-1);update(1,1,n,1,a[j] - 1,-1);}}ans = min(ans,tr[1].val);}printf("%d\n",ans);}return 0;
}

总结

        这场比赛算是目前来说打得最满意的一场了，美中不足的是 C 题做复杂了浪费了点时间，E 题因为没看到取模也罚时了挺久，在解题速度上还有很大的提升空间，现在的愿景是早日 AK 一场比赛，任重而道远hhh 。打了一两个月 cf ，思维题上有了提升，但想想也只是填补了一些基础不牢的问题，还有很多算法和数据结构太久没碰了十分生疏，有待接着填坑。