codeforces 248 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

有点可惜啊,整场比赛,写的代码里面有很多小bug,所以提交AB两次的时候有些慢了,不过过了之后排名还好,好像是90多,然后看了C,想了可能有20分钟的样子,想了出来,但是写起来也是有很多小bug,想赶着在1小时前过掉的,但是调小bug浪费了时间,最后1小时02分钟过了,排名很满意了19,后来跌了一下也是25左右。提交前有想过测试一下 10 10 10 10 10 这种数据的,但是急了,没测试,最后就是输出答案的时候,ans = INF,对于那种数据ans不会被更新的,最后输出了INF,应该是输出0的,所以 system test的时候C题挂了,最后的排名是144,很可惜,但是这就是比赛的一部分,下去加油。另外比赛中想出了D题的做法,就是相对暴力地搞,不过水平太差,没能在比赛中写出来,赛后写完了,继续努力吧

A.B 略

C.
如果一个数字改变了,只会对它两边的两个数字产生影响,所以对于一个数字x,开一个vector,把每个x两边的数字都放入x中(如果两边的数字有x,那么不用放,只放非x的数字)
我们枚举x,即把x变为某个数字,看看结果会不会变小,对于每个x,应该变为什么呢?那就看x对应的那个vector了,取中间大的那个数字z,让x变为z就行了,原因很浅白,因为是求一堆数字和一个数字的绝对值之和,那么这个数字,在这堆数字的中间值的时候,和最小
这样做,整个算法的复杂度是O(n)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define LL long long
#define N 100010
#define MAX 100010
#define INF 1000000000000000LL
#define pb push_back

int a[N],m,n;
vector<int>pos[N];
LL cost[N];

inline int abs(int x){ return x >= 0 ? x : -x; }

int main(){
while(scanf("%d%d",&m,&n)!=EOF){
memset(cost,0,sizeof(cost));
for(int i = 1; i <= m; i++) pos[i].clear();
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= n; i++){
if(i-1 && a[i-1] != a[i]){
pos[a[i]].pb(a[i-1]); cost[a[i]] += abs(a[i-1]-a[i]);
}
if(i<n && a[i+1] != a[i]){
pos[a[i]].pb(a[i+1]); cost[a[i]] += abs(a[i+1]-a[i]);
}
}
for(int i = 1; i <= m; i++)
if(pos[i].size()) sort(pos[i].begin(),pos[i].end());
LL sum = 0LL;
for(int i = 1; i < n; i++) sum += abs(a[i+1]-a[i]);
LL res = INF;
for(int i = 1; i <= m; i++) if(pos[i].size()) {
LL temp = sum - cost[i];
int size = pos[i].size() , mid = size/2 , midVal = pos[i][mid];
for(int k = 0; k < size; k++)
temp += abs(midVal-pos[i][k]);
res = min(res,temp);
}
if(res == INF) res = 0LL;
cout << res << endl;
}
return 0;
}

D.
暴力地搞
对于一行,把1区间保存下来,1区间是值一段连续为1的区间
例如:
第1行:[2,5], [8,9], [11,12]表示2到5列是1,8到9列是1,11到12列是1
对于一列,也这样保存下来
对于修改一个点(r,c),改变的只有r行,c列,所有重新去保存那些1区间,复杂度是O(n) n是行长,列长
对于查询,就想上,下,左,右,四个方向去找一次
例如上,下方向找,那就是对于 c 这一列,在没一行找到一个1区间是包含c的,如果有1行不包含就退出了
向左,右方向找是一样的,我写了一个类,只实现上下方向找的方法,对于左右找,那就把矩阵转90度就行了,所以有两个矩阵,都是上下方向找
不过代码太长了,呵呵

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define N 1010
#define pii pair<int,int>
#define pb push_back
#define mp make_pair

class MyClass{
public:
int row,col,map[N][N];
int mostL,mostR,ans1,ans2;
vector<pii>sr[N];

void reset(int r,int c){ row = r , col = c; }

void getSegRow(int r){
sr[r].clear();
int flag = 0,st = 0,ed = 0;
for(int i = 1; i <= col; i++){
if(map[r][i]){
if(!flag) st = ed = i;
else ed = i;
flag = 1;
}
else{
if(flag){ sr[r].pb(mp(st,ed)); st = ed = 0; }
flag = 0;
}
}
if(flag) sr[r].pb(mp(st,ed));
}

void findUpAndDown(int r,int c){
ans1 = ans2 = 0;
mostL = 0 , mostR = col+1;
find(ans1,c,r,0,-1);
mostL = 0 , mostR = col+1;
find(ans2,c,r,row+1,1);
}

int find(int &ans,int c,int str,int edr,int delta){
int cnt = 0;
for(int r = str; r != edr; r += delta){
int index = binary(r,c);
if(index == -1) break;
mostL = max(mostL,sr[r][index].first);
mostR = min(mostR,sr[r][index].second);
cnt++;
ans = max(ans,cnt*(mostR-mostL+1));
}
return cnt;
}

int binary(int r,int c){
int low = 0 , high = sr[r].size()-1 , ans = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(sr[r][mid].second < c) low = mid + 1;
else if(sr[r][mid].first > c) high = mid - 1;
else return mid;
}
return ans;
}
};

int main(){
MyClass obj1,obj2;
int row,col,Q,t;
while(scanf("%d%d%d",&row,&col,&Q)!=EOF){

obj1.reset(row,col);
obj2.reset(col,row);

for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
scanf("%d",&obj1.map[i][j]);

for(int i = 1; i <= col; i++)
for(int j = 1; j <= row; j++)
obj2.map[i][j] = obj1.map[row-j+1][i];

for(int i = 1; i <= obj1.row; i++) obj1.getSegRow(i);
for(int i = 1; i <= obj2.row; i++) obj2.getSegRow(i);

while(Q--){
int op,r,c;
scanf("%d%d%d",&op,&r,&c);
if(op == 1){
obj1.map[r][c] = 1 - obj1.map[r][c];
obj1.getSegRow(r);
t = c , c = obj1.row-r+1 , r = t;
obj2.map[r][c] = 1 - obj2.map[r][c];
obj2.getSegRow(r);
}
else{
int ans = 0;
obj1.findUpAndDown(r,c);
ans = max(ans,max(obj1.ans1,obj1.ans2));
t = c , c = obj1.row-r+1 , r = t;
obj2.findUpAndDown(r,c);
ans = max(ans,max(obj2.ans1,obj2.ans2));
printf("%d\n",ans);
}
}
}
return 0;
}