2012 MUTC 8 总结

题解链接：http://page.renren.com/601081183/note/866168965

题号：hdu 4370~4379

　　这次组队赛还是没有什么进步，我依然是我们队的代码主力，不过整场下来才过了两题。

　　这次比赛开始又是延迟了，因为开门的师兄到点了还没到机房。

　　最近比赛都是由我的队友看题，而我就只是在一旁等他们讲解题意，顺便吃个午饭。在我吃饭的过程中想了一下1001，当时没有什么思路，然后yy着突然想到什么东西了，就尝试着把它分解成几种情况来讨论。当时的几种情况其中一种还用到二分匹配最优解....- - 不过，当我仔细看清题目之后就推翻了自己写的那几种情况了，然后迫于无奈，还是放弃这题了....... 在比赛结束后，师兄跟我说我才意识到原来这是最短路啊！！！！！T^T 当时那个师兄还跟我说要优化，不然就会超时的。回到宿舍很快就打出了一个dij+heap(priority_queue)的代码，想起师兄的话，搞到我在交的时候还有点害怕超时了，加上了个快速读入数字来提速，不过令我意想不到的是交上去不仅是一个1y，还是时间只有109ms，那真是异常的快啊！！！

下面是1001(hdu 4370)的代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <queue>
  5 
  6 using namespace std;
  7 
  8 const int maxn = 301;
  9 const int inf = 1000000000;
 10 
 11 int mp[maxn][maxn];
 12 
 13 void qscan(int &n){
 14     char ch;
 15 
 16     while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
 17     if (ch != '-'){
 18         n = ch - '0';
 19         while ('0' <= (ch = getchar()) && ch <= '9')
 20             n = n * 10 + ch - '0';
 21     }
 22     else{
 23         n = 0;
 24         while ('0' <= (ch = getchar()) && ch <= '9')
 25             n = n * 10 - ch + '0';
 26     }
 27 }
 28 
 29 struct point{
 30     int n;
 31     int w;
 32     bool operator > (const point &x) const{
 33         return w > x.w;
 34     }
 35 };
 36 priority_queue<point, vector<point>, greater<point> > q;
 37 int dis[maxn];
 38 bool vis[maxn];
 39 
 40 int dij(int n){
 41     int cur;
 42     point tmp;
 43 
 44     for (int i = 1; i <= n; i++){
 45         vis[i] = false;
 46     }
 47     while (q.size()) q.pop();
 48     dis[1] = 0;
 49     vis[1] = true;
 50     for (int i = 2; i <= n; i++){
 51         tmp.w = dis[i] = mp[1][i];
 52         tmp.n = i;
 53         q.push(tmp);
 54     }
 55 
 56 #ifndef ONLINE_JUDGE
 57     printf("pass reset!");
 58 #endif
 59     while (true){
 60         while (vis[q.top().n]) q.pop();
 61         cur = q.top().n;
 62 #ifndef ONLINE_JUDGE
 63         printf("cur %d\n", cur);
 64 #endif
 65         q.pop();
 66         if (cur == n) return dis[n];
 67         for (int i = 2; i <= n; i++){
 68             if (!vis[i]){
 69                 if (dis[i] > dis[cur] + mp[cur][i]){
 70                     dis[i] = dis[cur] + mp[cur][i];
 71                     tmp.n = i;
 72                     tmp.w = dis[i];
 73                     q.push(tmp);
 74                 }
 75             }
 76         }
 77     }
 78 }
 79 
 80 int deal(int n){
 81     int i, j;
 82 
 83     for (i = 1; i <= n; i++){
 84         for (j = 1; j <= n; j++){
 85             qscan(mp[i][j]);
 86             if (i == j) mp[i][j] = inf;
 87         }
 88     }
 89 #ifndef ONLINE_JUDGE
 90     puts("scan success!");
 91 #endif
 92 
 93     return dij(n);
 94 }
 95 
 96 int main(){
 97 #ifndef ONLINE_JUDGE
 98     freopen("in", "r", stdin);
 99 #endif
100 
101     int n;
102 
103     while (~scanf("%d", &n)){
104         printf("%d\n", deal(n));
105     }
106 
107     return 0;
108 }

　　比赛中，我们开始了整整三个钟才过了一题1008。这题还过了挺惊险的，差点就因为看不出规律，又要放弃这题了。做这题的过程，刚开始我的一个队友想到一个规律，挺简单的，于是就打上去试一下，结果那是不用说的......- -

　　然后，我就花了一个多钟来打一个暴力方法找前几项的规律。时间这么长是因为没想到全排列的函数居然没有按照字典序来生成排列，然后还发现最大上升子序列居然打错了。于是这两个问题就搞了我好些时间，最后才打出个标准的答案来。还没这么简单，打出的答案观察了一下，发现H(n)这个函数值是ceil(sqrt(n))。然后，我们从这个发现开始入手，我慢慢发现了一个规律，最后几段的递减长度都是H(n)，然后划分的总段数都是H(n)（这句话好像挺废，其实后面所需的操作都是根据这句话来进行的）。其实，除非n是完全平方数，不然都会有残留段。不过，我的算法把n是完全平方数的情况都看作有残留段了。假设，靠前的那小于H(n)的需要特别处理的一大段可以分成k段，那么就把k-1个最小的元素按照升序放上来开头。其余的数都倒序排列。具体处理请看代码：

1008(hdu 4377)的代码：

View Code

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 int rest, part, tmp, rec;
 7 
 8 void work(){
 9     int n, r;
10 
11     scanf("%d", &n);
12     r = (int) ceil(sqrt((double)n));
13 
14     n--;
15     rest = n % r + 1;
16     part = n / r;
17     tmp = r;
18     rec = false;
19 
20     r = r - n / r - 1;
21     for (int i = 1; i <= r; i++){
22         if (!rec){printf("%d", i); rec = true;}
23         else printf(" %d", i);
24     }
25     for (int i = rest; i > r; i--){
26         if (!rec){printf("%d", i); rec = true;}
27         else printf(" %d", i);
28     }
29     for (int i = 0; i < part; i++){
30         for (int j = tmp; j > 0; j--)
31             if (!rec){printf("%d", j + rest); rec = true;}
32             else printf(" %d", j + rest);
33         rest += tmp;
34     }
35     puts("");
36     //printf("\nrest %d  r %d \n", rest, r);
37 }
38 
39 int main(){
40     int T;
41 
42     scanf("%d", &T);
43     while (T--)
44         work();
45 
46     return 0;
47 }

　　剩下两个钟，我们就主攻一道比较多人过的1005，一道dp题。队友给我说了一下题意，他就说这题不能暴力dp。看懂题以后，第一感觉就是要加上单调队列来做。我带着题目，上了趟厕所，仔细的想了想，结果回来的时候还是没想到怎么用到单调队列...囧，不过当时已经是有点感觉了。回到机房来，我拿起笔写了一下数组，发现如果要让dp值尽可能大，那么上一层dp[ j ]更新dp[ i ](i < j 且从左到右dp)的充分条件是dp[ i ]加上sum[i, j-1]比dp[ j ]小，那么这是dp[ i ]的存在也就没意义了。这个刚好单调队列的性质啊！！！分析出这个以后，就赶紧打出单调队列优化dp的代码来。不过比较久都没打过单调队列了，所以在十分不熟悉的情况下再三确认了insert操作的正确性。只剩一个钟了，代码终于出炉了，试了一下sample，错了。debug良久，发现原来是i 和j 打反了，郁闷啊！改了一下就对了，不过交上去wa了。我又debug了一下，发现还是因为i 和j 打错了 - - 所以初始化没成功！再交，还是wa.....T^T 不过幸亏这次队友的一组神数据，立马把我的忘记限制初始化长度的条件给测出来了！再改，再交！就是因为这个啊！ AC了！~

　　一个速度本来已经是挺快的代码，被我加上了快速读数后又更快了~

1005(hdu 4374)的代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <string>
  5 #include <cstdlib>
  6 
  7 using namespace std;
  8 
  9 const int maxn = 10005;
 10 const int inf = 1000000000;
 11 
 12 int q[maxn], qh, qt;
 13 int dp[maxn], ldp[maxn];
 14 int sum[maxn];
 15 
 16 void scan(int &a){
 17     char ch;
 18 
 19     while (((ch = getchar()) < '0' || ch > '9')&& ch != '-');
 20     if (ch == '-'){
 21         a = 0;
 22         while ((ch = getchar()) >= '0' && ch <= '9'){
 23             a = a * 10 + '0' - ch;
 24         }
 25     }
 26     else{
 27         a = ch - '0';
 28         while ((ch = getchar()) >= '0' && ch <= '9'){
 29            a = a * 10 + ch - '0';
 30         }
 31     }
 32 }
 33 
 34 int dis(int x, int y){
 35     if (x > y) return sum[x] - sum[y - 1];
 36     return sum[y] - sum[x - 1];
 37 }
 38 
 39 void up(int n){
 40     while (qh < qt && ldp[n] >= ldp[q[qt - 1]] + dis(q[qt - 1], n - 1)) qt--;
 41     q[qt++] = n;
 42 }
 43 
 44 void down(int n){
 45     while (qh < qt && ldp[n] >= ldp[q[qt - 1]] + dis(q[qt - 1], n + 1)) qt--;
 46     q[qt++] = n;
 47 }
 48 
 49 int ABS(int x){
 50     if (x < 0) return -x;
 51     return x;
 52 }
 53 
 54 int main(){
 55     int n, m, x, t;
 56     int sc, tmp;
 57 
 58     while (~scanf("%d%d%d%d", &n, &m, &x, &t)){
 59         sum[0] = 0;
 60         for (int i = 1; i <= m; i++){
 61             scan(sc);
 62             sum[i] = sum[i - 1] + sc;
 63         }
 64         for (int i = 1; i <= m; i++){
 65             if (ABS(i - x) <= t) ldp[i] = dis(i, x);
 66             else ldp[i] = -inf;
 67         }
 68         for (int i = 2; i <= n; i++){
 69 #ifndef ONLINE_JUDGE
 70             printf("dp: ");
 71             for (int j = 1; j <= m; j++){
 72                 printf("%d ", ldp[j]);
 73             }
 74             puts("");
 75 #endif
 76             for (int j = 1; j <= m; j++){
 77                 scan(sc);
 78                 sum[j] = sum[j - 1] + sc;
 79                 dp[j] = -inf;
 80             }
 81             qh = qt = 0;
 82             for (int j = 1; j <= m; j++){
 83                 up(j);
 84 #ifndef ONLINE_JUDGE
 85                 for (int k = qh; k < qt; k++)
 86                     printf("%d ", q[k]);
 87                 puts("");
 88 #endif
 89                 while (j - q[qh] > t) qh++;
 90                 tmp = ldp[q[qh]] + dis(q[qh], j);
 91                 if (dp[j] < tmp) dp[j] = tmp;
 92             }
 93             qh = qt = 0;
 94             for (int j = m; j >= 1; j--){
 95                 down(j);
 96 #ifndef ONLINE_JUDGE
 97                 for (int k = qh; k < qt; k++)
 98                     printf("%d ", q[k]);
 99                 puts("");
100 #endif
101                 while (q[qh] - j > t) qh++;
102                 tmp = ldp[q[qh]] + dis(q[qh], j);
103                 if (dp[j] < tmp) dp[j] = tmp;
104             }
105             for (int j = 1; j <= m; j++)
106                 ldp[j] = dp[j];
107         }
108 #ifndef ONLINE_JUDGE
109             printf("dp: ");
110             for (int j = 1; j <= m; j++){
111                 printf("%d ", ldp[j]);
112             }
113             puts("");
114 #endif
115         int maxdp = -inf;
116 
117         for (int i = 1; i <= m; i++)
118             if (maxdp < ldp[i]) maxdp = ldp[i];
119         printf("%d\n", maxdp);
120     }
121 
122     return 0;
123 }

　　剩下时间都不多了，其他题又没有思路，所以比赛就这样了！

　　赛后我和我队友才想懂1010原来是水题啊！！！不过题在想到方法前都不能算是水题吧.....

附上我的1010(hdu 4379)的代码：

View Code

 1 #include <cstdio>
 2 
 3 const int inf = 2100000000;
 4 
 5 int main(){
 6     int n, l, a, b, m;
 7     int mx, mn;
 8 
 9     while (~scanf("%d%d%d%d%d", &n, &l, &a, &b, &m)){
10         int cur = b;
11         int tl = l >> 1;
12         int cnt = 0;
13 
14         mx = -inf;
15         mn = inf;
16         if (n == 1){
17             cur += a;
18             cur %= m;
19             if (cur <= l)printf("1\n");
20             else printf("0\n");
21             continue;
22         }
23         for (int i = 1; i <= n; i++){
24             cur += a;
25             cur %= m;
26             if (cur <= tl){
27                 cnt++;
28                 if (mx < cur) mx = cur;
29             }
30             else{
31                 if (mn > cur) mn = cur;
32             }
33         }
34         if (mx != -inf && mn != inf && mn <= l - mx) cnt++;
35         else if (mx == -inf && mn <= l) cnt++;
36         printf("%d\n", cnt);
37     }
38 
39     return 0;
40 }

　　赛后感觉自己对算法的根本并不熟悉，以致于1001不能意识到是最短路，不知道这块能否依靠多做题来填补空缺，不过现在也就只好依靠多切题来学习更多算法的模型了！真心觉得1001出的十分妙！

　　另外，现在觉得，在自己强大起来前，和别人比较都是没有意义的，所以还是乖乖的学好算法切好题吧！-.-

　　求RP不实际，学算法最重要~

——written by Lyon