洛谷P4769 冒泡排序

佚名 6年前 (2019-04-08) 随笔 785人围观抢沙发百度已收录

首先有个全排列 + 树状数组的暴力。

然后有个没有任何规律的状压...首先我想的是按照大小顺序来放数，可以分为确定绝对位置和相对位置两种，但是都不好处理字典序。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

然后换个思路一位一位的考虑放哪个数。用一维来记录|i - p_i| - 逆序对数 * 2，还有一维记录是否紧贴下限，一个二进制数记录之前填了哪些数。

当前填到哪一位可以通过二进制中1的个数统计出来。这样就是一个n³2ⁿ的做法，可以过n <= 14的点，得到24分。

 1 /**
 2  * There is no end though there is a start in space. ---Infinity.
 3  * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 4  * Only the person who was wisdom can read the most foolish one from the history.
 5  * The fish that lives in the sea doesn't know the world in the land.
 6  * It also ruins and goes if they have wisdom.
 7  * It is funnier that man exceeds the speed of light than fish start living in the land.
 8  * It can be said that this is an final ultimatum from the god to the people who can fight.
 9  *
10  * Steins;Gate
11  */
12 
13 #include <bits/stdc++.h>
14 
15 const int N = 600010, MO = 998244353;
16 
17 int p[N], n;
18 
19 inline void Add(int &a, const int &b) {
20     a += b;
21     while(a >= MO) a -= MO;
22     while(a < 0) a += MO;
23     return;
24 }
25 
26 inline void out(int x) {
27     for(int i = 0; i < n; i++) {
28         printf("%d", (x >> i) & 1);
29     }
30     return;
31 }
32 
33 namespace Sta {
34     const int DT = 500, M = 33000;
35     int f[DT * 2][M][2], cnt[M], pw[M];
36     inline void prework() {
37         for(int i = 1; i < M; i++) {
38             cnt[i] = 1 + cnt[i - (i & (-i))];
39         }
40         for(int i = 2; i < M; i++) {
41             pw[i] = pw[i >> 1] + 1;
42         }
43         return;
44     }
45     inline void solve() {
46         memset(f, 0, sizeof(f));
47         f[DT][0][0] = 1;
48         /// DP
49         int lm = (1 << n) - 1, lm2 = n * (n - 1) / 2; /// lm : 11111111111
50         for(int s = 0; s < lm; s++) {
51             for(int i = -lm2; i <= lm2; i++) {
52                 /// f[i + DT][s][0/1]
53                 if(!f[i + DT][s][0] && !f[i + DT][s][1]) continue;
54                 //printf("f %d ", i); out(s); printf(" 0 = %d  1 = %d \n", f[i + DT][s][0], f[i + DT][s][1]);
55                 int t = lm ^ s;
56                 while(t) {
57                     int j = pw[t & (-t)] + 1, temp = i + std::abs(cnt[s] + 1 - j) - cnt[s >> (j - 1)] * 2 + DT, t2 = s | (1 << (j - 1));
58                     /// f[i + DT][s][1] -> f[std::abs(cnt[s] + 1 - j) - cnt[s >> (j - 1)] + DT][s | (1 << (j - 1))][1]
59                     Add(f[temp][t2][1], f[i + DT][s][1]);
60                     //printf("1 > %d ", temp - DT); out(t2); printf(" 1 = %d\n", f[temp][t2][1]);
61                     if(j > p[cnt[s] + 1]) {
62                         Add(f[temp][t2][1], f[i + DT][s][0]);
63                         //printf("0 > %d ", temp - DT); out(t2); printf(" 1 = %d\n", f[temp][t2][1]);
64                     }
65                     else if(j == p[cnt[s] + 1]) {
66                         Add(f[temp][t2][0], f[i + DT][s][0]);
67                         //printf("0 > %d ", temp - DT); out(t2); printf(" 0 = %d\n", f[temp][t2][0]);
68                     }
69                     t ^= 1 << (j - 1);
70                 }
71             }
72         }
73 
74         printf("%d\n", f[DT][lm][1]);
75         return;
76     }
77 }
78 
79 int main() {
80     //printf("%d \n", (sizeof(Sta::f)) / 1048576);
81     int T;
82     scanf("%d", &T);
83     Sta::prework();
84     while(T--) {
85         scanf("%d", &n);
86         for(int i = 1; i <= n; i++) {
87             scanf("%d", &p[i]);
88         }
89         Sta::solve();
90     }
91     return 0;
92 }