2016弱校联盟十一专场10.2部分题解

2/10

传送门

H. Around the World

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef long long LL;
11 typedef unsigned long long ULL;
12 typedef pair<int,int> pii;
13 
14 const int N = 2e6 + 10, mod = 1e9 + 7;
15 LL F[N];
16 
17 void init() {
18   F[0] = 1;
19   for (int i = 1; i < N; i++) F[i] = F[i - 1] * i % mod;
20 }
21 
22 LL pow_mod(LL a, LL b, LL c) {
23   LL ret = 1;
24   while (b) {
25     if (b & 1) ret = ret * a % c;
26     a = a * a % c;
27     b = b >> 1;
28   }
29   return ret;
30 }
31 
32 LL C(int n, int m) {
33   if (n < m) return 0;
34   else return F[n] * pow_mod(F[m], mod - 2, mod) % mod * pow_mod(F[n - m], mod - 2, mod) % mod;
35 }
36 
37 const int M = 1e5 + 10;
38 int deg[M];
39 
40 int main() {
41 #ifdef JUDGE
42   freopen("case.in", "r", stdin);
43 #endif
44   init();
45   int n;
46   while (~scanf("%d", &n)) {
47     LL res = 1;
48     memset(deg, 0, sizeof(int) * (n + 1));
49     for (int i = 1; i < n; i++) {
50       int u, v, c;
51       scanf("%d%d%d", &u, &v, &c);
52       deg[u] += c;
53       deg[v] += c;
54       res = res * C(2 * c, c) % mod * c % mod;
55     }
56     res = res * F[deg[1]] % mod;
57     for (int i = 2; i <= n; i++) res = res * F[deg[i] - 1] % mod;
58     cout << res << endl;
59   }
60   return 0;
61 }
62 /*
63 题意：
64 给你一棵树，告诉每条边有2 * c条路径，问有多少条欧拉回路
65 题解：
66 这道题用的是best定理：以i为结点的欧拉回路等于以i为根的外向树 * deg（s）！ * pro（（deg（v） - 1）！v属于V不等于s）
67 以i为根的外向树显然是pro（c），即所有的输入的c乘起来即可。
68 最后还要注意的是每条边都有编号，所以要C（2c，c）从2c条边里面选择c条作为出边，剩下的作为入边。
69 */

I. Longest Increasing Subsequence 

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 #define lson l, m, rt*2
 5 #define rson m + 1, r, rt*2+1
 6 #define xx first
 7 #define yy second
 8 typedef long long LL;
 9 typedef unsigned long long ULL;
10 typedef pair<int,int> pii;
11 const int N = 6, M = 1100;
12 int a[N], L[N], R[N], n, lis[N];
13 LL dp[N][M], sum[M], ans[N];
14 
15 int LIS() {
16   for (int i = 0; i < n; i++) {
17     lis[i] = 1;
18     for (int j = 0; j < i; j++)
19       if (a[i] > a[j])
20         lis[i] = max(lis[i], lis[j] + 1);
21   }
22   return *max_element(lis, lis + n);
23 }
24 
25 int main() {
26 #ifdef JUDGE
27   freopen("case.in", "r", stdin);
28 #endif
29   while (~scanf("%d", &n)) {
30     int m = 0;
31     for (int i = 0; i < n; i++) {
32       scanf("%d%d", L + i, R + i);
33       m = max(m, R[i]);
34     }
35     for (int i = 0; i < n; i++) a[i] = i, ans[i + 1] = 0;
36 
37     do {
38       memset(dp, 0, sizeof dp);
39       for (int i = L[a[0]]; i <= R[a[0]]; i++) dp[0][i] = 1;
40       for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + dp[0][i];
41       for (int i = 1; i < n; i++) {
42         for (int j = L[a[i]]; j <= R[a[i]]; j++) {
43           dp[i][j] += sum[j - 1];
44           if (a[i] < a[i - 1]) dp[i][j] += dp[i - 1][j];
45         }
46         for (int j = 1; j <= m; j++) sum[j] = sum[j - 1] + dp[i][j];
47       }
48       int x = LIS();
49       ans[LIS()] += sum[R[a[n - 1]]] - sum[L[a[n - 1] - 1]];
50     } while (next_permutation(a, a + n));
51 
52     for (int i = 1; i <= n; i++) {
53       printf("%lld", ans[i]);
54       if (i != n) putchar(' '); else putchar('\n');
55     }
56 
57   }
58   return 0;
59 }
60 /*
61 题意：
62 给你n（n <= 5）个区间，从中选择一个数vi,最后{v1，……vn}的LIS为1~n的个数。
63 题解：
64 首先五个数字的大小关系就只有5！种，所以先枚举n的排列表示这n个序列的大小关系
65 然后，我们令a[i]表示排名为i的数组是什么，如果相同那么就让下标大的排在前面，为什么？
66 因为这样方便其LIS，如果相同的下标小的排在前面的话，求LIS就有错。
67 然后就是求这种序列有多少种？
68 dp（i，j）表示考虑到第i小的序列，最后一个数为j的方案数，最后为了转移是O（n）我们预处理一个sum（j）
69 表示后面的数小于等于j的方案数和，最后累加一下所有情况的答案即好了。
70 */

J. Matrix Transformation

  1 /*zhen hao*/
  2 #include 
  3 using namespace std;
  4 
  5 #define lson l, m, rt*2
  6 #define rson m + 1, r, rt*2+1
  7 #define xx first
  8 #define yy second
  9 
 10 typedef long long LL;
 11 typedef unsigned long long ULL;
 12 typedef pair<int,int> pii;
 13 
 14 const int N = 210;
 15 
 16 struct Node {
 17   int right, down, val;
 18 } nodes[N * N];
 19 
 20 int n, Q, tmp[N], tmp2[N];
 21 
 22 int get_id(int x, int y) {
 23   return x * (n + 1) + y;
 24 }
 25 
 26 inline int walk(int p, int x, int y) {
 27   while (x--) p = nodes[p].right;
 28   while (y--) p = nodes[p].down;
 29   return p;
 30 }
 31 
 32 int main() {
 33 #ifdef JUDGE
 34   freopen("case.in", "r", stdin);
 35 //  freopen("case.out", "w", stdout);
 36 #endif
 37   while (~scanf("%d%d", &n, &Q)) {
 38     int cnt = 0;
 39     for (int i = 0; i <= n; i++)
 40       for (int j = 0; j <= n; j++) {
 41         if (i != n) nodes[get_id(i, j)].down = get_id(i + 1, j);
 42         if (j != n) nodes[get_id(i, j)].right = get_id(i, j + 1);
 43         if (i && j) nodes[get_id(i, j)].val = cnt++;
 44       }
 45     while (Q--) {
 46       int t, l, r, d, p, q, o, tp, tq;
 47       scanf("%d%d%d%d", &t, &l, &r, &d);
 48       if (d == 0) continue;
 49       l++; r++;
 50       if (t == 1) {
 51         tp = p = walk(0, 0, l - 1);
 52         q = walk(p, d, 0), o = walk(q, n - d, 0);
 53         for (int i = l; i <= r; i++) {
 54           p = walk(p, 0, 1);
 55           q = walk(q, 0, 1);
 56           o = walk(o, 0, 1);
 57           nodes[o].right = nodes[p].right;
 58           nodes[p].right = nodes[q].right;
 59         }
 60         p = tp;
 61         tq = q = walk(p, 0, r - l + 1);
 62         for (int i = 1; i <= n; i++) {
 63           p = walk(p, 1, 0);
 64           q = walk(q, 1, 0);
 65           tmp[i] = nodes[p].down;
 66           tmp2[i] = nodes[q].down;
 67         }
 68         p = tp;
 69         q = tq;
 70         for (int i = 1; i <= n; i++) {
 71           p = walk(p, 1, 0);
 72           q = walk(q, 1, 0);
 73           nodes[p].down = tmp[i + d <= n ? i + d : i + d - n];
 74           nodes[q].down = tmp2[i - d >= 1 ? i - d : i - d + n];
 75         }
 76       }
 77       else {
 78         tp = p = walk(0, l - 1, 0);
 79         q = walk(p, 0, d), o = walk(q, 0, n - d);
 80         for (int i = l; i <= r; i++) {
 81           p = walk(p, 1, 0);
 82           q = walk(q, 1, 0);
 83           o = walk(o, 1, 0);
 84           nodes[o].down = nodes[p].down;
 85           nodes[p].down = nodes[q].down;
 86         }
 87         p = tp;
 88         tq = q = walk(p, r - l + 1, 0);
 89         for (int i = 1; i <= n; i++) {
 90           p = walk(p, 0, 1);
 91           q = walk(q, 0, 1);
 92           tmp[i] = nodes[p].right;
 93           tmp2[i] = nodes[q].right;
 94         }
 95         p = tp;
 96         q = tq;
 97         for (int i = 1; i <= n; i++) {
 98           p = walk(p, 0, 1);
 99           q = walk(q, 0, 1);
100           nodes[p].right = tmp[i + d <= n ? i + d : i + d - n];
101           nodes[q].right = tmp2[i - d >= 1 ? i - d : i - d + n];
102         }
103       }
104     }
105     int p = 0, q;
106     for (int i = 1; i <= n; i++) {
107       q = p = nodes[p].down;
108       bool first = 0;
109       for (int j = 1; j <= n; j++) {
110         q = nodes[q].right;
111         printf("%d", nodes[q].val);
112         if (j != n) putchar(' ');
113       }
114       puts("");
115     }
116   }
117   return 0;
118 }
119 /*
120 题意：给你一个n * n的矩阵，有两种操作：
121 1、1 l r d 表示将l到r行顺时针转d距离
122 2、2 l r d 表示将l到r列顺时针转d距离
123 让你输出最后的矩阵
124 题解：
125 用十字链表
126 具体是建立一个结构体作为一个结点，维护下，右和值
127 然后记得每次只是将原来指向某元素的指针赋给新的指向该元素的指针即可
128 最后输出矩阵
129 */