CYJian的水题大赛2 解题报告 T1 JerryC Loves Driving（数学） T2 Jerry Loves Lines（排序，模拟） T3 Samcompu Loves Water（并查集） T4 Zrz_orz Loves Secondary Element
这场比赛是前几天洛谷上 暮雪﹃紛紛dalao的个人公开赛，当时基本上都在水暴力分......也没有好好写正解（可能除了T1）
过了几天颓废的日子之后，本蒟蒻觉得应该卓越一下了qwq，所以就打算写一个解题报告qwq（其实就是详细注释啦~~~）
首先T1已经给我们简化了,（我才不会告诉你前面的题目我都没看呢）
题目要求：给出A，B，求出下面式子的值——
(sum_{i=A}^B sum_{j=1}^i lfloorfrac{i}{j} floor{}*(-1)^j)
虽然有的dalao说这个就是普及-的签到题，（我真的好弱啊，我怎么普及-的题都不会做啊）但是我还是借鉴(qwq)了 大佬 BLUESKY007的思路才过了这个题qwq。
当然上来我们可以纯模拟，比如说这样：
for(int i=a;i<=b;i++)
{
int curans=0;
for(int j=1;j<=i;j++)
{
int cur=i/j;
if(j&1) cur=-cur;
curans+=cur;
}
ans+=curans;
}
这代码垃圾的一匹啊，（我怎么还有脸把它放上来献丑啊qwq）......稳稳地T飞。之后我们就要想优化——
这时，考虑到有关于我们可以打个表输出每次增加的值来看一看.......然后......就发现了规律。
比如我们分别以a=1,b=10和a=3,b=10来打表，输出如下（第一行是输入，最后一行是答案）
论我们发现了什么：
- 有没有发现后面那个是总的三角形减去上面的那个小三角形？qwq
- 有没有发现每一列都是等差数列？qwq
所以说......我们可以使用等差数列来进行O(n)时间复杂度的加和计算。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long a,b,ans1,ans2,yu,end;
int main(){
scanf("%lld%lld",&a,&b);
a--;//根据查分的思想:sum[i~j]=ans[j]-ans[i-1]
for(int i=1;i<=b;i++){
end=((b+1)/i)-1;
//这个计算的是完整的到了数字几(比如说在第三列上，每个数字出现三次才能算是完整的）
//至于为什么要b+1，是因为观察上表可以发现，每一列如果空行的上面再在上面加上一列空行（就是补成一个长方形），空行数正好等于数字需要出现的次数
//因为我们在上面补了空行，所以注意之后要减去一
yu=(b+1)%i;
//求不完整的数的个数
ans1+=(i&1?-1:1)*(i*((end+1)*end/2)+yu*(end+1));}
//等差数列求和公式
//注意"-"的处理，这里使用三元运算符
for(int i=1;i<=a;i++){
end=((a+1)/i)-1;
yu=(a+1)%i;
ans2+=(i&1?-1:1)*(i*((end+1)*end/2)+yu*(end+1));}
printf("%lld
",ans1-ans2);
return 0;
}
T2 Jerry Loves Lines（排序，模拟）
这个题在比赛的时候调了好久还是调炸了qwq......最后......最后还是交了一个暴力上去qwq。（暴力好像是有一半的分）
做这个题应该是有一个直观的感受，就是两条直线相交之后他们的rank一定会互相交换，因为两个直线如果相交则rank一定相邻，所以将低的那个rank++,高的rank--即可。（如果有多条直线的话同理，可以尝试手动模拟一下，（懒得画图解释了）因为节点记录的时候都是两条两条记录的，所以同上操作即可）
之后就是对询问的处理，为了方便我们以O（n）的复杂度进行x坐标从左到右扫描交换处理，我们可以先将询问存下来，按照x进行从小到大的排序，然后方便后来的一并处理。
具体细节见代码及注释。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
//因为int*int会爆int 所以我们要记得开long long
//感觉无论何时开long long 都是一个良好的习惯（才不是因为出题人提醒了呢）
#define N 2010
#define M 500500
using namespace std;
inline ll read() {
ll s = 0, t = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') t = -1; ch = getchar(); }
while(ch <= '9' && ch >= '0') { s = s * 10 + ch - '0'; ch = getchar(); }
return s * t;
}
//快速读入
struct Line {ll k,b,js; int id;}L[N];
inline ll cal_x(Line a, Line b) {return (b.b-a.b)/(a.k-b.k);} //求x值
inline ll cal_y(Line a, ll x) {return a.k*x+a.b;} //求y值
struct Ask {int id;ll x;}Q[M]; //储存询问
struct Swap {int x,y; ll p;};
bool operator < (Ask a, Ask b) {return a.x < b.x;}
//重载运算符
bool cmp(Swap a, Swap b) {
if(a.p != b.p) return a.p < b.p;
return a.x < b.x;
}
bool cmp1(Line a, Line b) {return a.js < b.js;}
int n,m,k,cnt,rank[N],num[N];
ll res[M];
Line L[N];
Swap S[N * N];
int main() {
n=read(); m=read(); k=read();
for(int i = 1; i <= n; i++)
{
L[i].k=read();
L[i].b=read();
}
for(int i = 1; i <= m; i++) {
Q[i].x=read();
Q[i].id = i;
}
sort(Q + 1, Q + 1 + m);
for(int i = 1; i <= n; i++) L[i].js = cal_y(L[i], Q[1].x);
sort(L + 1, L + 1 + n, cmp1);
//按照y值计算在第一个询问x时候的排名
//接下来开始处理节点信息
for(int i = 1; i <= n; i++) {
L[i].id = num[i] = rank[i] = i;
//初始化直线的id,排名所对应的直线编号,该线段所对应的排名（因为刚初始化，所以都一样）
for(int j = i + 1; j <= n; j++)
if(L[i].k != L[j].k && cal_y(L[i], Q[m].x) >= cal_y(L[j], Q[m].x)) {
//注意平行线情况需要跳过
ll d = cal_x(L[i], L[j]);
if(d >= Q[1].x) {
//因为刚才已经处理过第一个询问时候的直线排名了，
//所以现在第一个询问之前就算交换了也没有意义，就不需要处理了
cnt++;
S[cnt].x = i;
S[cnt].y = j;
//记录节点的相交线信息
S[cnt].p = d;
//记录x值+1
}
}
}
sort(S + 1, S + 1 + cnt, cmp);
//将节点进行排序
for(int i = 1, id = 1; i <= m; i++) {
while(id <= cnt && S[id].p < Q[i].x) {
//如果节点的信息在当前询问之前，就要处理
rank[S[id].x]++;
rank[S[id].y]--;
num[rank[S[id].x]] = S[id].x;
num[rank[S[id].y]] = S[id].y;
id++;
//rank记录的是当前直线在x=i时刻的排名
//num记录的是当前x=i时哪个排名对应的是哪个直线
}
res[Q[i].id] = cal_y(L[num[k]], Q[i].x);
//处理完当前询问之前的节点交换信息之后，将答案计入res数组中
//这时候注意因为我们将询问排序过了，但是输出的时候还是要按照初始询问次序输出
//所以要以Q[i].id为关键字输入
}
for(int i = 1; i <= m; i++) printf("%lld
", res[i]);
return 0;
}
T3 Samcompu Loves Water（并查集）
比赛的时候看错题了qwq，结果打了一个树剖上去......（我的语文阅读能力啊qwq)。最后一看发现貌似是统计不同的两点之间任意边权不大于某个值的方案数.......如果没有失效边的话肯定比较简单，直接对边进行排序一点一点加上去，并查集合并的时候size相乘即可。但是这道题需要处理失效边.......
打比赛的时候因为没有时间了所以就直接放了个很暴力的并查集上去，只拿了一半的分数（代码见下）
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 10010
using namespace std;
int t,n,ti[MAXN],ki[MAXN],cnt,ans;
int u[MAXN],v[MAXN],w[MAXN],fa[MAXN],size[MAXN];
int find(int x)
{
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d",&t,&n);
for(int i=1;i<=n-1;i++)
scanf("%d%d%d",&u[i],&v[i],&w[i]);
for(int i=1;i<=t;i++)
scanf("%d%d",&ti[i],&ki[i]);
for(int p=1;p<=t;p++)
{
ans=0;
memset(fa,0,sizeof(fa));
memset(size,0,sizeof(size));
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n-1;i++)
{
if(i==ki[p]||w[i]>=ti[p])
continue;
int a=find(u[i]),b=find(v[i]);
if(a!=b)
fa[a]=b;
}
for(int i=1;i<=n;i++)
{
size[find(i)]++;
// printf("i=%d fa=%d
",i,find(i));
}
for(int i=1;i<=n;i++)
{
if(size[i]==0) continue;
ans+=size[i]*(size[i]-1);
// printf("i=%d size=%d
",i,size[i]);
}
printf("%d
",ans);
}
return 0;
}
但是这样肯定不行啊......1e4的平方肯定跑不过，所以......我们注意到出题人提示了ki最多只有1e3个，所以我们可以将这些无效的边加到一个数组中储存下来，失效的时候就不用，恢复之后暴力加边。
代码和注释如下；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10001
#define ll long long
using namespace std;
struct Ask {int tim,pos,id;}S[N];
struct Edge {int u,v,w,id;}E[N],a[1001];
bool operator < (Ask a, Ask b) {return a.tim < b.tim;}
bool operator < (Edge a, Edge b) {return a.w < b.w;}
//重载运算符
struct bcj {int f,id; ll si;}s[N],tmp[N];
int T,n,L=1,cnt=0;
bool flag[N],done[N];
//flag标记是否可能会失效
long long ans[N],sum=0;
inline int find(bcj &x) { return x.f = x.id == x.f ? x.f : find(s[x.f]); }
//并查集的find操作
//注意这里要对x进行取地址，要不然x.f的赋值操作无法生效
void Add(bcj a, bcj b, ll &ans) {
//取地址进行修改
bcj fu = s[find(a)];
bcj fv = s[find(b)];
if(fu.id == fv.id) return ;
ans += fu.si * fv.si;
//根据乘法原理
fu.f = fv.id;
fv.si += fu.si;
s[find(a)]=fu;
s[find(b)]=fv;
//因为我们是将可能无效的边和一直有效的边分开处理的，
//在同一个循环中还要继续使用size
//所以修改了之后记得重新放回来
//当然这里也可以在前面使用 bcj& fu,bcj& fv
}
int main() {
scanf("%d%d",&T,&n);
for(register int i = 1; i < n; i++) {
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
E[i].id = i;
}
for(register int i = 1; i <= T; i++) {
scanf("%d%d",&S[i].tim,&S[i].pos);
S[i].id = i;
flag[S[i].pos] = 1;
//将可能无效的边进行标记
}
for(register int i = 1; i <= n; i++) {
if(flag[E[i].id])
a[++cnt] = E[i];
//这里就是上述所说将可能无效的边放在一起（a数组其实只用开1001大就可以）
s[i].f = i;
s[i].si = 1;
s[i].id = i;
//并查集初始化
}
sort(a + 1, a + 1 + cnt);
sort(E + 1, E + n);
sort(S + 1, S + 1 + T);
for(register int i = 1; i < n; i++)
{
//添加储存的无效边
while(L <= T && E[i].w >= S[L].tim)
{
ans[S[L].id] = sum;
memcpy(tmp, s, sizeof(s));
for(register int j = 1; j <= cnt; j++)
{
if(a[j].w >= S[L].tim) break;
//如果无效边大于当前所需要的，因为排序过了，所以直接break
if(S[L].pos == a[j].id || !done[a[j].id]) continue;
//如果当前添加边在此次无效，跳过
Add(s[a[j].u], s[a[j].v], ans[S[L].id]);
}
memcpy(s, tmp, sizeof(tmp));
//添加之后可能s数组的size值会改变
//因为每次的无效边都不一样
//为了防止算重，只能先储存s值到tmp中，之后再复制回来
//以避免中间的更改
L++;
}
if(L>T) break;
done[E[i].id] = 1;
if(flag[E[i].id]) continue;
//如果是会失效的边，跳过不进行添加
Add(s[E[i].u], s[E[i].v], sum);
//添加正常边
}
for(register int i = 1; i <= T; i++) printf("%lld
", ans[i]*2);
//因为题目中有说x-y和y-x不一样，所以要*2
return 0;
}
T4 Zrz_orz Loves Secondary Element
此题留坑，这几天就补上
P.S 吐槽一下， 对于此场比赛的难度， 暮雪﹃紛紛dalao是这样说的：
然后洛谷的标签是这样的qwq: