2018.3.10 省选模拟赛

从这里开始

  • 概况
  • Problem A 三元组
  • Problem B 攻略
  • Problem C 迂回

概况

  这是省选T1合集?还是欢乐AK赛?

  全班一半以上的人三道题都会做qwq。

  Doggu还剩一小时时以为自己AK了,然后玩了一小时。虽然最终被卡了20分的常数。

  ZJC 1个半小时AK?Excuse me?

  我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉。

  发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280。

  教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3小时。我觉得我做了假题。难道是noip模拟题?

Problem A 三元组

  (题意过于简洁,不需要大意)

  暴力做法是枚举$a, b, c$中的中的一个,然后计算剩下两个中合法的对数(这个可以预处理)。

  于是我到了一个分治FFT的做法,时间复杂度$O(Tn log^{2}n)$,会被卡掉。

  但是这么做不优秀,没有利用题目的性质。

  对于$a$,恰好是1 ~ n。所以可以考虑从小到大枚举$c$,每次会增加1个可用的$a$和$b$。然后会对凑出和为$b + 1, b + 2, b + 3, \cdots$的地方有1的贡献。

  这是一个区间加的操作,用线段树树状数组就好了。

Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #ifndef WIN32
 6 #define Auto "%lld"
 7 #else
 8 #define Auto "%I64d"
 9 #endif
10 using namespace std;
11 typedef bool boolean;
12
13 #define ll long long
14
15 typedef class IndexedTree {
16     public:
17         int k;
18         ll s[100005];
19
20         IndexedTree() {        }
21         IndexedTree(int k):k(k) {
22             memset(s, 0, sizeof(ll) * (k + 1));
23         }
24
25         void add(int idx, int x) {
26             idx++;
27             for ( ; idx <= k; idx += (idx & (-idx)))
28                 s[idx] += x;
29         }
30
31         ll query(int idx) {
32             idx++;
33             ll rt = 0;
34             for ( ; idx; idx -= (idx & (-idx)))
35                 rt += s[idx];
36             return rt;
37         }
38
39         void add(int l, int r, int x) {
40             add(l, x);
41             add(r + 1, -x);
42         }
43         void modify(int x, int p) {
44             if (p >= k) {
45                 add(0, p / k);
46                 p %= k;
47             }
48             if (p < k && p) {
49                 if (x + p < k)
50                     add(x + 1, x + p, 1);
51                 else {
52                     if (x < k - 1)
53                         add(x + 1, k - 1, 1);
54                     add(0, x + p - k, 1);
55                 }
56                 return;
57             }
58         }
59 }IndexedTree;
60
61 const int N = 1e5 + 5;
62
63 int n, k;
64
65 inline void init() {
66     scanf("%d%d", &n, &k);
67 }
68
69 ll ans = 0;
70 IndexedTree st;
71 inline void solve() {
72     ans = 0, st = IndexedTree(k);
73     for (int i = 1, b, c; i <= n; i++) {
74         b = i * 1ll * i % k, c = b * 1ll * i % k;
75         st.modify(b, i);
76         ans += st.query(c);
77     }
78     printf(Auto"\n", ans);
79 }
80
81 int T;
82 int main() {
83     freopen("exclaim.in", "r", stdin);
84     freopen("exclaim.out", "w", stdout);
85     scanf("%d", &T);
86     for (int kase = 1; kase <= T; kase++){
87         init();
88         printf("Case %d: ", kase);
89         solve();
90     }
91     return 0;
92 }

Problem A

Problem B 攻略

  (题意极其简洁,不需要大意)

  去年省选D1T1。直接长链剖分。

Code

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #ifndef WIN32
  6 #define Auto "%lld"
  7 #else
  8 #define Auto "%I64d"
  9 #endif
 10 using namespace std;
 11 typedef bool boolean;
 12
 13 #define ll long long
 14
 15 typedef class Edge {
 16     public:
 17         int ed, nx;
 18
 19         Edge(int ed = 0, int nx = 0):ed(ed), nx(nx) {    }
 20 }Edge;
 21
 22 typedef class MapManager {
 23     public:
 24         int ce;
 25         int* h;
 26         Edge* es;
 27
 28         MapManager() {    }
 29         MapManager(int n, int m):ce(0) {
 30             h = new int[(n + 1)];
 31             es = new Edge[(m + 1)];
 32             memset(h, 0, sizeof(int) * (n + 1));
 33         }
 34
 35         void addEdge(int u, int v) {
 36             es[++ce] = Edge(v, h[u]);
 37             h[u] = ce;
 38         }
 39
 40         Edge& operator [] (int pos) {
 41             return es[pos];
 42         }
 43 }MapManager;
 44
 45 int n, k;
 46 MapManager g;
 47 int* vs;
 48 int *lson;
 49 ll res = 0;
 50 int top = 0;
 51 ll* secs;
 52
 53 inline void init() {
 54     scanf("%d%d", &n, &k);
 55     vs = new int[(n + 1)];
 56     lson = new int[(n + 1)];
 57     secs = new ll[(n + 1)];
 58     g = MapManager(n, n << 1);
 59     for (int i = 1; i <= n; i++)
 60         scanf("%d", vs + i);
 61     for (int i = 1, u, v; i < n; i++) {
 62         scanf("%d%d", &u, &v);
 63         g.addEdge(u, v);
 64     }
 65 }
 66
 67 ll dfs1(int p) {
 68     ll mxl = 0, mxs = 0, cmp;
 69     for (int i = g.h[p]; i; i = g[i].nx) {
 70         int e = g[i].ed;
 71         cmp = dfs1(e);
 72         if (cmp > mxl)
 73             mxl = cmp, mxs = e;
 74     }
 75     lson[p] = mxs;
 76     return mxl + vs[p];
 77 }
 78
 79 void dfs2(int p, ll va) {
 80     boolean aflag = true;
 81     va += vs[p];
 82     if (lson[p])    aflag = false, dfs2(lson[p], va);
 83     for (int i = g.h[p]; i; i = g[i].nx, aflag = false) {
 84         int e = g[i].ed;
 85         if (e == lson[p])    continue;
 86         dfs2(e, 0);
 87     }
 88     if (aflag)
 89         secs[++top] = va;
 90 }
 91
 92 inline void solve() {
 93     dfs1(1);
 94     dfs2(1, 0);
 95     sort(secs + 1, secs + top + 1, greater<ll>());
 96     for (int i = 1; i <= top && i <= k; i++)
 97         res += secs[i];
 98     printf(Auto"\n", res);
 99 }
100
101 int main() {
102     freopen("game.in", "r", stdin);
103     freopen("game.out", "w", stdout);
104     init();
105     solve();
106     return 0;
107 }

Problem B

Problem C 迂回

  (题意极度简洁,不需要大意)

  设原图的邻接矩阵为$A$,那么相当于求$A^{1} + A^{2} + \cdots + A^{k - 1}$的对角线上的和。

  直接用poj 3233的分治做法。

  但是这样$O(n^{3}\log^{2}k)$会T掉。

  考虑到分治中的快速幂很重复,其实可以把快速幂的过程和分治过程合并。

  时间复杂度$O(n^{3}\log k)$

Code

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef bool boolean;
 5
 6 const int N = 105;
 7
 8 typedef class Matrix {
 9     public:
10         int a[N][N];
11
12         Matrix() {    }
13         Matrix(int n) {
14             for (int i = 0; i < n; i++)
15                 for (int j = 0; j < n; j++)
16                     a[i][j] = ((i == j) ? (1) : (0));
17         }
18
19         int* operator [] (int p) {
20             return a[p];
21         }
22 }Matrix;
23
24 int n, k, p;
25 char buf[233];
26 Matrix g;
27
28 Matrix operator * (Matrix a, Matrix b) {
29     Matrix rt;
30     for (int i = 0; i < n; i++) {
31         for (int j = 0; j < n; j++) {
32             rt[i][j] = 0;
33             for (int k = 0; k < n; k++)
34                 rt[i][j] = (rt[i][j] + a[i][k] * 1ll * b[k][j]) % p;
35         }
36     }
37     return rt;
38 }
39
40 Matrix operator + (Matrix a, Matrix b) {
41     Matrix rt;
42     for (int i = 0; i < n; i++) {
43         for (int j = 0; j < n; j++) {
44             rt[i][j] = (a[i][j] + b[i][j]) % p;
45         }
46     }
47     return rt;
48 }
49
50 Matrix qpow(Matrix a, int pos) {
51     Matrix pa = a, rt = Matrix(n);
52     for ( ; pos; pos >>= 1, pa = pa * pa)
53         if (pos & 1)
54             rt = rt * pa;
55     return rt;
56 }
57
58 inline void init() {
59     scanf("%d", &n);
60     for (int i = 0; i < n; i++) {
61         scanf("%s", buf);
62         for (int j = 0; j < n; j++)
63             g[i][j] = ((buf[j] == ‘Y‘) ? (1) : (0));
64     }
65     scanf("%d%d", &k, &p);
66 }
67
68 Matrix pa;
69 Matrix dividing(Matrix& a, int pos) {
70     if (pos == 1)
71         return (pa = a);
72     if (pos & 1) {
73         Matrix rt = dividing(a, pos - 1);
74         pa = pa * a;
75         return rt + pa;
76     }
77     Matrix tem = dividing(a, pos >> 1), bas = pa;
78     for (int i = 0; i < n; i++)
79         bas[i][i] += 1;
80     pa = pa * pa;
81     return bas * tem;
82 }
83
84 int res = 0;
85 inline void solve() {
86     Matrix a = dividing(g, k - 1);
87     for (int i = 0; i < n; i++)
88         res = (res + a[i][i]) % p;
89     printf("%d", res);
90 }
91
92 int main() {
93     freopen("tour.in", "r", stdin);
94     freopen("tour.out", "w", stdout);
95     init();
96     solve();
97     return 0;
98 }

Problem C

原文地址:https://www.cnblogs.com/yyf0309/p/8538903.html

时间: 03-09

2018.3.10 省选模拟赛的相关文章

2018.2.12 省选模拟赛

题目大意 (题目很简洁了,不需要大意) 其实显而易见地可以发现,当被卡一次后后面的路程都是固定了的. 可以用类似动态规划的思想来进行预处理.现在的问题就是怎么知道在某个位置刚等完红灯然后出发会在哪个路口再次被卡. 尝试画一画图: 其中横轴表示位置,纵轴表示时间,长方体表示红灯时段.有用的部分长度只有$r + g$,所以在模意义下弄一下就可以减少很多重复和无用状态: 但是这样仍然不好处理上面提到的问题,考虑让线段横着走,第一个撞着的长方形就是答案.为了实现这个目标,就每个长方形向下移动一段(移动的

2018/3/29 省选模拟赛 80

我真是太菜了... T1 10分纯暴力没写,20分容斥也没写(人就是懒死的).还有30分矩乘不会 正解 <IOI2018 中国国家集训队第一阶段作业题解部分 - 杭州第二中学 吴瑾昭.pdf>最后一题 T2  以为自己能拿到50分,但是其实那个暴力算法只能过10分的点,n=2000的20分数据用n^3带剪枝过不了,所以拿了30分. 正解 <计数与期望问题选讲 CLJ.pdf>最后一题 我记得我以前好像看到过这个文档但是没读过..今天读一下 T3 依然是分情况50分,30分树归20分

2018/3/9 省选模拟赛 0分

第二题模拟扫一遍就可以过,不能更划算了.q=1的30分写的比100分还麻烦,有趣哦. 破暴力40分也没什么可写了,日常辣鸡吃枣药丸. 原文地址:https://www.cnblogs.com/137shoebills/p/8533870.html

2018/3/27 省选模拟赛 140分

T1 树归 100 T2 写的快速幂卷积 40,超时了,正解是矩阵乘法之类的. 正解 1 暴力(m<=5):将x的所有约数提出来矩阵乘法 2 3 定义乘法同构: 4 A=p[1]^a[1] * p[2]^a[2] * ... * p[n]^a[n] 5 B=q[1]^b[1] * q[2]^b[2] * ... * q[n]^b[n] 6 其中p[i]与q[i]皆为质数 7 将数组a与b降序排序后如果是完全相同的,那么称A与B是乘法同构的 8 如 2*2*2*2*3*3*5 与 7*11*11*

2018.6.29 省选模拟赛

*注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A 小D与电梯 Problem B 小D与田野 Problem C 小D与函数 Problem A 小D与电梯 题目大意 假设电梯在0层,容量无限大.给定$n$个人的到达时间和要去的楼层.电梯上下一层楼花费的时间为1,电梯开关门.乘客上下的耗时不计,电梯可以停留在某一层楼.问将所有人送达到目的地,并让电梯回到0层的最少耗时. 先按到达时间将所有人排序.显然,每次电梯运输的人是一段连续的区间中的人. 用$f[i]$表示将前$

2018.2.23 省选模拟赛

从这里开始 Problem A cycle Problem B meal Problem C naive Problem A cycle 判断是否有经过一个点的负环,我们可以跑最短路.判断这个点到自己的最短路是否是负数. 于是可以二分环大小跑dfs版spfa. 于是可以分层图做时间复杂度四方的dp. (YYR给的数据水得吓人,这两个做法居然都跑过了.然后都被我和jmr卡掉了) 注意到如果一个点走不超过$k$条边回到自己的最短路的长度是负数,那么走不超过$k + 1$条边也是. 因此我们可以二分答

10.30 NFLS-NOIP模拟赛 解题报告

总结:今天去了NOIP模拟赛,其实是几道USACO的经典的题目,第一题和最后一题都有思路,第二题是我一开始写了个spfa,写了一半中途发现应该是矩阵乘法,然后没做完,然后就没有然后了!第二题的暴力都没码QAQ 现在我来写解题报告了,有点饿了QAQ.. 第一题 题目 1: 架设电话线 [Jeffrey Wang, 2007] 最近,Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务,于 是,她们要求FJ把那些老旧的电话线换成性能更好的新电话线.新的电话线架设 在已有的N(2 <=

@省选模拟赛03/16 - T3@ 超级树

目录 @description@ @solution@ @accepted code@ @details@ @description@ 一棵 k-超级树(k-SuperTree) 可按如下方法得到:取一棵深度为 k 的满二叉树,对每个节点向它的所有祖先连边(如果这条边不存在的话). 例如,下面是一个 4-超级树: 请统计一棵 k-超级树 中有多少条不同的简单有向路径,对 mod 取模. input 一行两整数 k, mod. output 一行一整数表示答案. example input1: 2

xjoi省选模拟赛_14

T1 发现 对于当前 投出 奇数次向上的概率为 p 那么 若加入一个 pi=0.5 的骰子 发现  p奇 +1=p奇 * 0.5+p偶 * 0.5 = p偶+1  也就是说 只要方案中存在一个 p=0.5 的骰子 这个方案必然合法  : 1 #include <bits/stdc++.h> 2 #define N 100 3 #define eps 1e-7 4 using namespace std; 5 typedef long double ldb; 6 int t,n; 7 ldb A