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

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

比赛经历

先把第一题做了
然后第二题wa了几次,蹲坑的时候忽然灵光一现想到了漏洞……
然后就挂机了……和以前没什么区别

T1_Analysis

请先思考后再展开

先离散化一下,统计每个数出现个数
如果剩下一个的时候,判断素数即可

看了题解发现原来我的代码是有漏洞的
没有考虑,最后没有数字的情况(没有把t初始化为1),然后居然ac了

T1_Code_原

请先思考后再展开
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
82
83
84
85
86
87
88
89
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
bool isprime(ll x)
{
if(x<=1) return 0;
if(x==2) return 1;
for(ll i=2;i*i<=x;i++) if(x%i==0) return 0;
return 1;
}
struct Nod
{
ll d;
int p;
}a[MAXN*2],b[MAXN*2];
bool cmp(Nod x,Nod y) {return x.d<y.d;}
ll yz[MAXN*2];//old
int mx;
int n,m;
void lsh()
{
memcpy(b,a,sizeof a);
sort(b+1,b+n+m+1,cmp);
mx=1;yz[mx]=b[1].d;a[b[1].p].d=mx;
for(int i=2;i<=n+m;i++)
{
if(b[i-1].d!=b[i].d) mx++;
yz[mx]=b[i].d;a[b[i].p].d=mx;
}
}
int c[MAXN*2];
bool check()
{
bool bk=0;
ll t;//这里应该改成1
for(int i=1;i<=mx;i++)
{
if(c[i]>0)
{
if(bk==0)
{
if(c[i]>1) return 0;
bk=1,t=yz[i];
}
else if(bk) return 0;
}
}
//printf("mx=%d\n",mx);
return isprime(t);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i].d),a[i].p=i;
for(int i=1;i<=m;i++) scanf("%lld",&a[n+i].d),a[n+i].p=n+i;
lsh();
memset(c,0,sizeof c);
for(int i=1;i<=n;i++) if(yz[a[i].d]>1) c[a[i].d]++;
for(int i=n+1;i<=n+m;i++) if(yz[a[i].d]>1) c[a[i].d]--;
if(check()) puts("YES");
else puts("NO");
}
}

T2_Analysis

请先思考后再展开

一眼贪心模拟
显然碰到连续两个跳过的点,就失败
但是一开始写成了【连续两个小段失败】,其实可能只是跳过中间那个点就行
还有一个细节漏了,就是不能跳过m-1

T2_Code_原

请先思考后再展开
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int n,m,s;
int w[MAXN];
bool v[MAXN];
int ans[MAXN],tot=0;
bool check()
{
int now=0;
bool fail=0;
int nx=1;
while(now<m+1)
{
int dis=w[nx]-w[now];
if(dis<s)
{
if(nx==m+1 or fail) return 0;
fail=1;
nx++;
}
else
{
now=nx;
nx++;
v[now]=1;
ans[++tot]=now;
fail=0;
}
}
while(now>0)
{
int nx=now-1;while(nx>0 and v[nx]) nx--;
int dis=w[now]-w[nx];
if(dis<s) return 0;
v[nx]=1;
now=nx;
ans[++tot]=now;
}
for(int i=0;i<=m+1;i++) if(!v[i]) return 0;
puts("YES");
for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
return 1;
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++) scanf("%d",&w[i]);
w[0]=0;w[m+1]=n;
if(!check()) puts("NO");
}

T3_Analysis

请先思考后再展开

当时想了1h都没有思路
只是想到通过差分和贪心,面对一个局面时可以线性地判断
然后就在想方设法【线性扫时间,通过利用残留信息logn判断】
然后就实在想不到什么残留信息可以用……

强行伏笔:一直奇怪那个r给出来有什么用(可能是用来迷惑人的?)
然后题目下面一大堆限制条件,以为只是用来手算范围的
其实有一个隐藏的特性:$R_i>=i$
所以说一次成功后,后面的都能成功,也就是满足二分性
(不一定是一个完美的函数,但最后一定都是成功)
(让我联想到化学反应的结束图像)

实话说我经常会这样害怕毒瘤题面

T3_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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=510000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n,m,k,mx;
int a[MAXN],c[MAXN];
struct Nod
{
int w,x,v;
}b[MAXN];
int check(int mid)
{
memcpy(c,a,sizeof a);
for(int i=1;i<=mid;i++) c[b[i].x]-=b[i].v,c[b[i].x+1]+=b[i].v;
int ans=0,tot=0;
for(int i=1;i<=n;i++)
{
tot+=c[i];
if(tot<1)
{
ans+=(1-tot);
c[i]+=(1-tot);
if(i+k<=n) c[i+k]-=(1-tot);//debug 2分的小细节!
tot+=(1-tot);
}
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&mx);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--) a[i]-=a[i-1];//差分
for(int i=1;i<=mx;i++) {int t;scanf("%d",&t);}
for(int i=1;i<=m;i++) scanf("%d%d%d",&b[i].w,&b[i].x,&b[i].v);
b[m+1].w=INF;
int ans;
int l=0,r=m;
while(l<=r)
{
int mid=(l+r)/2;
int tot=check(mid);
if(tot>=b[mid+1].w) l=mid+1;
else ans=tot,r=mid-1;
}
printf("%d",ans);
}

T4_Analysis

请先思考后再展开

有关区间最小值,有这样一个套路:
先用一个递减的单调栈,分别从前往后和从后往前,
求出l[i]和r[i]表示第一个比a[i]大的位置,
则l[i]+1~r[i]-1中间,用到的最大值都是a[i]

考虑枚举这个最大值位置,然后枚举左右中数量少的那一边的端点
这样另一个端点的取值范围就确定了,静态主席树即可,当然树状数组+离散化+二分查找也行。
这样做的话读者可能认为复杂度是$O(n^2 log_2 n)$的,
无异于【预处理st表+暴力枚举端点】的复杂度

然鹅,这种做法的复杂度其实是$O(n log_2^2 n)$的
证明:
对于每个i,它能够把l[i]~r[i]分成两半,分出来后,下一层级的j不能跨越出去
所以说每次选取少的那一边,$枚举量 \leq log_2 n$
换句话说,这些查询区间的总量是nlogn个,可以用set查重

至于空间,如果用树状数组或者线段树,不离散化的话,复杂度是m
至于主席树,因为是静态的,前缀和形式,动态开点则变成nlogm,大大降低

debug:
有一个漏洞,就是相同的数会多次作为最大值
我的想法灰常暴力:set判重,不影响复杂度,由于区间不多,空间也不大
而优秀的rose就有更劲的方法:全覆盖时强行保证只用最左边的
具体而言,左边延伸到比x大或相等的,右边延伸到比x大的
这样它们右端点相通,但左端点不会重复覆盖

T4_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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int dd[MAXN],top;//存储位置
int n;
int a[MAXN],l[MAXN],r[MAXN];//debug l和r定义不同,确保最大值中只用最左边那个!
void pre_lr()
{
//debug l[i]-1是>=a[i]的
top=1;dd[top]=1;l[1]=1;
for(int i=2;i<=n;i++)
{
while(top>0 and a[dd[top]]<a[i]) top--;
l[i]=(top>0)?dd[top]+1:1;//debug 可能空
dd[++top]=i;
}
//debug r[i]+1是>a[i]的
top=1;dd[top]=n;r[n]=n;
for(int i=n-1;i>=1;i--)
{
while(top>0 and a[dd[top]]<=a[i]) top--;
r[i]=(top>0)?dd[top]-1:n;//debug 可能空
dd[++top]=i;
}
}
struct Nod
{
int lc,rc;
int c;
Nod()
{
lc=rc=0;
c=0;
}
}p[MAXN*40];
int rt[MAXN];
int id=0;
void add(int &x,int l,int r,int d,int o)
{
if(l>r) return;
if(!x) x=++id;
p[x].c+=o;
if(l==r) return;
int mid=(l+r)/2;
if(d<=mid) add(p[x].lc,l,mid,d,o);
else add(p[x].rc,mid+1,r,d,o);
}
void merg(int x,int &y)
{
if(x==0) return;
if(y==0) {y=x;return;}
p[y].c+=p[x].c;
merg(p[x].lc,p[y].lc);
merg(p[x].rc,p[y].rc);
}
int calc(int x,int l,int r,int d)//<=d
{
if(l>r or x==0) return 0;
if(l==r and l==d) return p[x].c;
int lc=p[x].lc,rc=p[x].rc,mid=(l+r)/2;
if(d<=mid) return calc(lc,l,mid,d);
else return p[lc].c+calc(rc,mid+1,r,d);
}
const int MAXNUM=1000000000;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
add(rt[i],1,MAXNUM,a[i],1);
merg(rt[i-1],rt[i]);
}
pre_lr();
ll ans=0;
for(int mid=1;mid<=n;mid++)
{
int fl=l[mid],fr=r[mid];
if(mid-fl<fr-mid)//left
{
for(int i=fl;i<=mid;i++)
{
int d=a[mid]/a[i];
ans+=calc(rt[fr],1,MAXNUM,d)-calc(rt[mid-1],1,MAXNUM,d);
}
}
else//right
{
for(int j=mid;j<=fr;j++)
{
int d=a[mid]/a[j];
ans+=calc(rt[mid],1,MAXNUM,d)-calc(rt[fl-1],1,MAXNUM,d);
}
}
}
printf("%lld",ans);
}

T5_Analysis

请先思考后再展开

看到“凸包”两个字就想跑……

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

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