2019牛客第十场F题详解_算法日常[13/100]

2019牛客第十场F题详解

题目

2019牛客第十场F题详解


题解

我的分析请看代码

本来以为发现了更快更简单的做法,结果想写成思路给大家看,然后不断想怎么表述这个算法,想着想着发现这是一个假的超快AC算法,然后大家有兴趣的话可以看我的AC代码二的分析(果然写blog做搬运工也是有收获的)

AC代码

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
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=6e5+5;
const int N=6e5+3;
int a[maxn],b[maxn],cnt[maxn],ans,n,r;
vector <int> h[maxn];
multiset <int> s;
void add(int x){
auto p=s.find(cnt[x]);
s.erase(p); cnt[x]++;
s.insert(cnt[x]);
}
void del(int x){
auto p=s.find(cnt[x]);
s.erase(p); cnt[x]--;
s.insert(cnt[x]);
}
int main(){
cin >> n >> r;
for (int i=0;i<n;i++){
cin >> a[i] >> b[i];
/* 统一右移2*r */
a[i]+=r*2; b[i]+=r*2;
}
for (int i=0;i<n;i++){
/*打a[i]的时候,把a[i]-r,a[i]+r也叠加上a[i]上面的值,
这样就能使得a[i]表示打a[i]能获得的总值*/
h[a[i]-r].pb(b[i]);
h[a[i]].pb(b[i]);
h[aa[i]+r].pb(b[i]);
cnt[b[i]]++; cnt[b[i]-r]++; cnt[b[i]+r]++;
}
for (int i=r;i<=N-r;i++) s.insert(cnt[i]);
for (int i=r;i<=N-r;i++){
/*得到中间打这里能够得到的个数*/
int ret=(int)h[i].size();
/*暂时删除相关的所有列值*/
for (auto x:h[i]) del(x),del(x-r),del(x+r);
/*然后得到当下最大的3列值*/
auto p=s.rbegin();
ans=max(ans,ret+(*p));
/*再把列值插回去*/
for (auto x:h[i]) add(x),add(x-r),add(x+r);
}
cout << ans << endl;
}

能更快AC的假算法

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
/*直接行列序列化排序的做法,真滴是好想法!*/

/*2019年8月18日20:26:30 发现这是一个假做法!靠着数据水才过的!因为这里只比较了最大的3个
行值,就去比较列值了!

因为可能有一种情况就是选第4大行,但是取到的列值更多,这应该是有可能出现的,
总之这种做法虽然能过 但是是有可能遗漏情况的假算法!

必须要枚举到所有的行
*/
#include<bits/stdc++.h>
using namespace std;
const int M =1e5 + 10;
int num[M *3];
int n , r , ans;
int cnt[M * 3];
struct node{
int x , y;
int id;
bool operator<(node d)const{
return x > d.x;
}
}a[M] , b[M];

int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >>r;
for(int i =1;i <= n;i++){
cin >> a[i].x >> a[i].y;
a[i].x++;
a[i].y++;
num[a[i].x]++;
}
/*枚举每个行坐标,相加从上到下3行的值-->二维降到一维*/
for(int i = 1;i <= 100000;i++){
/*之所以放在最左边是因为i是从最左边开始,免去判断*/
b[i].x = num[i] + num[i +r] + num[i +r +r];
b[i].id = i;
}
/*行值获利大到小排序*/
sort(b + 1 ,b + 100001);
for(int i = 1;i <= 3;i++){
memset(cnt , 0 ,sizeof(cnt));
for(int j = 1;j <= n;j++){
/*除去原来的行(3次行值取max)以外的其他列的值的统计*/
if(a[j].x != b[i].id && a[j].x != b[i].id +r && a[j].x != b[i].id +r * 2) cnt[a[j].y]++;
}
int sum = 0;
for(int j = 1; j < M;j++) sum = max( sum , cnt[j] + cnt[j +r] +cnt[j + r + r]);
ans = max(ans , sum + b[i].x);
}
cout << ans <<endl;
}

每天叨叨一句

天将降大任于斯人也,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,行拂乱其所为,所以动心忍性,曾益其所不能

点击查看

本文标题:2019牛客第十场F题详解_算法日常[13/100]

文章作者:单林敏

发布时间:2019年08月18日 - 18:15:16

最后更新:2019年10月17日 - 21:44:06

原始链接:https://www.wolfdan.cn/算法日常-13-100/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%