摘要:荣获铁人三项

10122020机房赛

T1

题目分析

因为不存在三线共点,所以不平行的三条直线就一定能形成三角形.

那么考虑三角形中的三条边,这三条边所在的直线可以按照斜率进行排序.

于是有个思路就是把直线的斜率全部算出来然后排序,枚举作为三角形三条线中中间的那一条线,然后处理出两边有多少斜率不等的直线组合成三角形即可.

代码

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
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=300010;
const double eps=1e-9;
lxl n,ans;
struct _Line
{
lxl a,b,c;
inline bool operator <(const _Line &another)const{return a*another.b<b*another.a;}
inline bool operator ==(const _Line &another)const{return b*another.a==a*another.b;}
}l[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
int main(void)
{
n=read();
for(R int i(0);i<n;++i)
l[i].a=read(),l[i].b=read(),l[i].c=read();
std::sort(l,l+n);
lxl e(0),r(0);
for(R int i(0);i<n;++i)
{
while(l[e]<l[i])++e;
while(!(l[i]<l[r])&&r<n)++r;
ans+=e*(n-r);
}
printf("%lld\n",ans);
return 0;
}

T2

题目分析

可以知道的是对于一个轨道,上面停的列车编号一定是递减的,也就是说一辆列车的前面不能有一辆编号比她大的车,因为前面的车一定先出队.

那么问题就转化为,求用多少个下降子序列可以覆盖原序列.

我们可以发现一个性质,这个数等于原序列的最长上升子序列长度.

证明貌似很麻烦,要考虑最长上升子序列的位置和大小关系,不过几组数据就看得到规律了.

代码

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
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=108620;
lxl n,top,ans,best=INF,times=1;
lxl a[big],vis[big],end[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline lxl random(lxl x){return rand()*rand()%x;}
int main(void)
{
srand(time(NULL));
n=read();
for(R int i(1);i<=n;++i)a[i]=read();
memset(vis,0,sizeof vis),memset(end,0,sizeof end);
ans=0;
end[++top]=a[1];
for(R int i(2);i<=n;++i)
{
lxl it=end[top];
if(a[i]>=it)end[++top]=a[i];
else
{
lxl l(1),r(top),mid,pos;
while(l<=r)
{
mid=(l+r)>>1;
lxl mit=end[mid];
if(mit>a[i])pos=mid,r=mid-1;
else l=mid+1;
}
end[pos]=a[i];
}
}
printf("%lld\n",top);
return 0;
}

T3

题目分析

先对所有边的$g$进行排序,这样就可以通过直接枚举边来获取$maxg$,对当前枚举到的边的$s$进行排序,求得最小生成树即为答案.

考虑优化,每次往集合里加入一条边,只用将它并入集合即可,具体来说就是维护一个$s$单增的临时数组,加入新边时进行插入.

可以发现当前的最小生成树只会由之前已经形成过最小生成树的边结合上新加入的边组成,这样每次做最小生成树时的边数量为$O(n)$,复杂度就可以做到$O(mn)$了.

代码

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
#define R register
#define INF 4557430888798830399
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl small=410,big=50010;
lxl n,m,have,s,g,ans=INF,cnt,maxg,maxs;
lxl fa[big];
struct _Edge
{
lxl u,v,s,g,used;
inline bool operator <(const _Edge &another)const{return g<another.g;}
}e[big],tmp[big],now[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void refresh(lxl x)
{
lxl l(1),r(have),mid,pos(-1);
while(l<=r)
{
mid=(l+r)>>1;
if(tmp[mid].s>e[x].s)pos=mid,r=mid-1;
else l=mid+1;
}
if(~pos)
{
++have;
for(R int i(have);i>=pos+1;--i)tmp[i]=tmp[i-1];
tmp[pos]=e[x];
}
else tmp[++have]=e[x];
}
inline void init()
{
cnt=maxs=maxg=0;
for(R int i(1);i<=n;++i)fa[i]=i;
for(R int i(1);i<=have;++i)now[i]=tmp[i],now[i].used=false;
}
lxl find(lxl x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(void)
{
n=read(),m=read(),s=read(),g=read();
for(R int i(1);i<=m;++i)e[i]=(_Edge){read(),read(),read()*s,read()*g};
std::sort(e+1,e+1+m);
for(R int i(1);i<=m;++i)
{
refresh(i),init();
for(R int j(1);j<=have;++j)
{
lxl x=find(now[j].u),y=find(now[j].v);
if(x!=y)
{
fa[x]=fa[y],now[j].used=true;
++cnt,maxs=std::max(maxs,now[j].s);
if(cnt==n-1)
{
lxl nhave(0);
for(R int k(1);k<=have;++k)
if(now[k].used)tmp[++nhave]=now[k];
have=nhave;
ans=std::min(ans,maxs+e[i].g);
break;
}
}
}
}
printf(ans==INF?"-1\n":"%lld\n",ans);
return 0;
}

总结

这次是有了签到题,然而按照原先的惯例乱序开题直接暴毙…

先开t2,然而没有去做转化,打了个二分优化转移的dp去做最小下降子序列覆盖了,最后十分钟才发现自己打挂了.

然后t3看$n$范围小感觉是个dp,三方复杂度预处理出路径信息然后合并子树那种,想了想不怎么会做于是打了个随机化,因为随机化打得不太熟导致各种re浪费大量时间.

最后t1没啥时间写了,打了个暴力,签到题没签成,大概有个正解的思路但那点时间实在实现不了了,虽说就算正解也不难写不过细节写法导致的精度卡得很恶心估计一时半会也搞不出来.

于是全部打铁荣获铁人三项.

以后是不要乱序开题了,后面要用到的写不熟的东西可能要调很久,而且发现自己只要代码打起来脑子就不想题了,还是得改改习惯.