洛谷18年7月月赛比赛总结

洛谷18年9月月赛比赛总结
题目

比赛经历

哇这次是oi赛制耶
感觉心理压力会小很多……

第一题一开始很自信,觉得可以暴力,因为位数可能不会太大……
当时电脑上没有g++,于是就应验了师兄们对在线ide的推测,没来得及装的时候比赛就开始了……
主要是没检查到(原电脑在竞赛室不想拿回来)
随便出组数据就tle了
但仔细看看题目,就是没有说无解的情况,我也不会证明有解
后来认真想想,推推柿子,发现原来是bsgs,时间复杂度nlogn
然后如果无解,我会输出-1
打了个对拍,暴力会出负数,也就是无解情况
为了方便对拍,统一输出-1
拍了30min的rand数据,范围不会太大(感觉rand的最大值是刚好的),避免暴力太慢,感觉应该没问题了……(30min伏笔)

然后是t2,感觉是约束一下,但没有太明确的思路,先跳
t3是一棵树,除以2以后,化一下柿子,发现就是 $min \sum C->A_i$
然后感觉可以参考一下“中位数的应用”,就是考虑移动的贡献
那么不难发现,从根向下移动,相当于非该子树的A要多走w,子树内则少走w
这样就是每条边走过去的贡献
那么我们不妨先把初始的C设在根节点,然后往下重新计算dis,如果最小的dis小于0,那么移动到那里会更优
仔细检查一下变量类型,感觉没问题,然后思考一下也应该是正解,时间复杂度n

此时只剩一个半小时,稍微有点慢了
看看t4,标题写着分块是什么鬼
感觉能拿30分
后来忽然发现,统计1的数量需要乘以15,凉凉

看t2,发现只需要转移成第二行的情况,然后维护一下确定的区间
具体而言,就是把每个约束条件转化为a~b的形式,而且满足 $2 \leq num \leq 2m$
如果宽度小于m多解,大于m无解,否则定位一下就好了
一直coding到最后3min,虚的一匹
还好最后成功写完,交了上去
到比赛首页,居然发现比赛延迟30min!
赶快回去细细检查,发现细节稍微有点多,挖掘了一下样例后真发现几个bug,应该问题也不大了

检查一波,然后看t4,发现我制杖了,预处理一下1的数量就好了,值域很小
那么又骗了30分
目前最高分330
时间刚好结束

好像比赛首页因为太多人刷新炸了?
出去陪弟弟玩了波大富翁,好颓废啊
回来发现145是什么鬼?怎么可能还有rk23,这么sb的分数……
woc,80+60+0+5
太困了先睡了……

T1_Analysis

请先思考后再展开

因为 $n \leq MOD$
所以答案是超过int的,没发现这点
交上去还是80
再仔细想想,因为刚刚发现的这一点,两个MOD相乘会爆ll,所以要快速乘
tle!因为现在复杂度变成了log方,真是连锁反应……
主要是因为我之前的写法一直都是 $A^b=ed \times inv(A^{at})$ ,n=at+b
那么改改就好了,避免以后吃亏
$A^b=A^{at} \times inv(ed)$ , n=at-b

所以说,还是考虑不够周全,造成连锁反应
感觉这种事情很危险啊,特别是noip之前
不久前还跟别人说自己很少fail题,因为大部分题都不会做……
立刻就来教训了

T1_Code_std

请先思考后再展开
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=110000;
typedef long long ll;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
ll MOD;
ll qmul(ll x,ll e)
{
ll ans=0;
while(e>0)
{
if(e&1) ans=(ans+x)%MOD;
x=(x+x)%MOD;e>>=1;
}
return ans;
}
ll qpower(ll x,ll e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=qmul(ans,x);
x=qmul(x,x);e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}//MOD is prime
ll ed;
map<ll,int> mp;
ll bsgs()
{
int t=ceil(sqrt((double)MOD));
ll now=1;
for(int i=0;i<=t;i++)
{
mp[now]=i;
now=now*10%MOD;
}
ed=inv(ed);
ll dec=qpower(10,t);
now=1;
for(int a=1;a<=t;a++)
{
now=qmul(now,dec);
ll wt=qmul(now,ed);
if(mp.count(wt)) return (ll)a*t-mp[wt];
}
return -1;
}
void main()
{
scanf("%lld%lld",&ed,&MOD);
if(ed==0) {puts("0");return;}
ed=ed*9+1;ed%=MOD;
printf("%lld",bsgs());
}
};
int main()
{
mine::main();
}

T2_Analysis

请先思考后再展开

发现这种做法是错误的
因为我不能确定它实际在第二行还是第三行……
所以换个思路,考虑直接约束1的位置
然而我完全不会怎么解带模的不等式:$(A+k-2) \% m \leq m+(A-B-1) \% m$
总之,如果能解出来,可能是同时多个区间,需要找到被覆盖s次的区间
这个的话,可以补集转化一下,维护其补集的交,这样无论解有多少个区间都能解决,非常巧妙

T3_Analysis

请先思考后再展开

哇哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈……woc看错题了
使得他送货所需的最长距离最小
而不是
使得他送货所需的距离总长最小
我就说怎么会爆零
大概是第一次彻头彻尾看错题?可能真的没细看那时候
如果要找个理由的话,哪有人会关心最长那个啊
还有就是样例恰好只有一个商品……

不过然后就不会做了……好像二分也没有什么卵用

膜出题人
嗯决策和刚才一样,都是具有单调性的,而且最优方向一定是由局部最优组成的
然后我自己也能猜到一个性质:题目中的距离,一定是 $2 \times c到ab路径的距离+ab路径长度$
那么关键是最小化左边的部分
考虑从任意一个点开始,用刚才的思路,考虑跳过去的贡献
每一次,暴力计算出所有总答案最大的点对
考虑每条边,如果有任何点对跨越该边(可以用dfs序和siz判断),意味着当前是最优位置
如果那边有点对,另一边也有点对,跳过去没有意义,当前也是最优位置
否则,单纯地往那边跳即可

当前的时间复杂度是 $O(深度 \times n)$
套一个点分治即可

T4_Analysis

请先思考后再展开

原来是空间挂了……
正解是神仙的莫队改版
以后做……

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/b37c.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%