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;
}