点按此处下载题面
PROBLEM A
很明显，双方最优策略是一直往前走，对手一直往前就能赢了，所以bx hao sui啊！
PROBLEM B
做这个题需要知道二项式定理，乘法逆元和等比数列求和，组合数取模。
![\[\sum_{i=1}^{n}(a^{i}+b^{i})^{k} = \sum_{i=1}^{n}\sum_{j=0}^{k} \binom{k}{j} a^{ij}b^{i(k-j)}=\sum_{j=0}^{k}\binom{k}{j} \sum_{i=1}^{n}q^{i}\]](https://haha.school/wp-content/ql-cache/quicklatex.com-0b71a6ace7071d5a6982f8d299db72ba_l3.png "Rendered by QuickLaTeX.com")
![\[q = a ^ {j} b ^ {k-j}\]](https://haha.school/wp-content/ql-cache/quicklatex.com-77f01bb8dde5ae28ff9d1a14c2991767_l3.png "Rendered by QuickLaTeX.com")
后面就是等比数列的求和。
需要注意的是q＝1的时候。
二项式系数可以用阶乘和逆元预处理，等比数列求和也可以用逆元求出来。复杂度O(Klog(N))。
PROBLEM C
这题求的是一个有向无环图的最小树形图。可以对每个点，选一个权值最小的入边加起来就是答案。
PROBLEM D
直接模拟统计出到最后时刻情怀值会受损多少。对于每个时间点，如果不能ak，则损害值增加tn-ti。最后总的损害值如果比原始情怀值小则just enjoy coding，否则fail to graduate。
PROBLEM E
PROBLEM F
PROBLEM G
|
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 |
//模拟易知，画出来的图形是Sierpinski三角形，一种分形图像 //所以可以直接模拟，也可以用递归绘制（just for fun） //如果你看到的注释没对齐，请在CodeBlocks中打开本代码 #include <iostream> #include <cstring> using namespace std; const int MAXN = 100; int n; char canvas[MAXN][MAXN * 2 - 1]; //画布 #define _USE_FRACTAL_METHOD_ //注释本行，将使用普通画法；否则，使用递归绘制分形 #ifndef _USE_FRACTAL_METHOD_ void draw() { //普通画法 canvas[0][n - 1] = '*'; //将第一行中间那个人设为* for (int i = 1; i < n; ++i) { //对于接下来每一行 for (int j = 0; j < 2 * n - 1; ++j) { //从左到右查看 bool flag[3]; //用来记录前方的人的状态 if (j == 0) //如果是最左边的人，就不用查看左前方 flag[0] = false; else flag[0] = canvas[i - 1][j - 1] == '*'; flag[1] = canvas[i - 1][j] == '*'; //记录正前方 if (j == 2 * n - 2) //如果是最右边的人，就不用查看右前方 flag[2] = false; else flag[2] = canvas[i - 1][j + 1] == '*'; if (!flag[0] && !flag[1] && flag[2]) //四种需要设为*的情况 canvas[i][j] = '*'; else if (!flag[0] && flag[1] && flag[2]) canvas[i][j] = '*'; else if (flag[0] && !flag[1] && !flag[2]) canvas[i][j] = '*'; else if (flag[0] && flag[1] && !flag[2]) canvas[i][j] = '*'; } } } #else void draw(int row, int col, int size) { //分形画法，以(row, col)为顶角，绘制大小为size的分形三角形 if (row >= n || col < 0 || col >= 2 * n - 1) //如果超出画布范围，就不画了 return; if (size == 1) //若已经是最小的三角形，直接绘制 canvas[row][col] = '*'; else { //否则递归 draw(row, col, size / 2); //三个小三角形的顶角坐标如参数所示 draw(row + size / 2, col - size / 2, size / 2); draw(row + size / 2, col + size / 2, size / 2); } } #endif // _USE_FRACTAL_METHOD_ int main() { while (cin >> n) { memset(canvas, '.', sizeof(canvas)); //初始化，将画布充填为. #ifndef _USE_FRACTAL_METHOD_ draw(); //普通画法 #else int size; //分形画法需要计算最大三角形的size，size为2^k for (size = 1; size < n; size *= 2); //寻找大于等于n的最小的size draw(0, n - 1, size); //分形画法 #endif // _USE_FRACTAL_METHOD_ for (int i = 0; i < n; ++i) { //输出 for (int j = 0; j < 2 * n - 1; ++j) cout << canvas[i][j]; cout << endl; } cout << endl; //输出额外的空行 } return 0; } |
PROBLEM H
对于每个数，我们需要满足的条件有两个：一个是各数位数字单调递减，第二个是这个数字满足被6整除。首先，如果直接枚举满足第二个条件的数，那么要枚举的数太多，复杂度太高。那么我们首先考虑满足第一个条件。各个数位的数字单调递减说明了各个数字不同（即每个数只能选一次），而数字只能在0-9这10个数选取（说明最多取10个数），且满足单调递减（说明对每组取的数，只有一个方案是符合的）。于是所有满足条件“各数位数字单调递减”的数字只有C(10, 1) + C(10, 2) + C(10, 3) + … + C(10, 9) + C(10, 10) = 2^10-1 = 1023。于是我们可以通过搜索的方法找到所有满足第一个条件的数，然后判断是否满足第二个条件。搜索的方法是先枚举高位，再枚举低位，每次枚举的数都得比高位的数小，直到没有数可以枚举（最小是0）结束。用递归可以解决。最后我们求出所有满足第一和第二个条件的数只有两百多个。注意最大的数会超出int的范围，所以我们可以用一个long long数组存下满足条件的数。接下来我们由于我们最多只有20组数据，所以我们可以判断每个合法的数是否小于或等于输入数据。
主要部分代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 |
ong long sum = 0, a[300]; int cnt = 0; void dfs(int n) { for(int i = n-1; i >= 0; --i) { sum = sum * 10 + i; if(sum % 6 == 0) a[cnt++] = sum; dfs(i); sum /= 10; } } |
PROBLEM I
|
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 |
//题意为，在输入矩阵中，数出 //横着或竖着 //连续三个或以上同颜色珠 //的次数 //如果你看到的注释没对齐，请在CodeBlocks中打开本代码 #include <iostream> using namespace std; int n, m; char board[128][128]; int main() { int t; cin >> t; //输入数据的组数 while (t--) { cin >> n >> m; //输入矩阵尺寸 for (int i = 0; i < n; ++i) //读取矩阵 for (int j = 0; j < m; ++j) cin >> board[i][j]; int ans = 0; //答案 char pre_type; //储存遇到的上一个珠子的种类 int cnt; //计数器，记录当前这种珠子遇到连续几个了 for (int i = 0; i < n; ++i) { //对于每一行进行检查 for (int j = 0; j < m; ++j) if (j == 0) { //如果是第一颗珠子 pre_type = board[i][j]; //设定 cnt = 1; } else { if (pre_type == board[i][j]) //如果与上一颗珠子的种类一样 ++cnt; //累加计数器 else { //如果与上一颗珠子的种类不一样 if (cnt >= 3) //如果上一种珠子出现的颗数大于等于3 ++ans; //累加答案 pre_type = board[i][j]; //更新 cnt = 1; //重置计数器 } } if (cnt >= 3) //不要忘了对最后出现的那种珠子判断 ++ans; } for (int i = 0; i < m; ++i) { //对于每一列进行检查，下同对行的检查 for (int j = 0; j < n; ++j) if (j == 0) { pre_type = board[j][i]; cnt = 1; } else { if (pre_type == board[j][i]) ++cnt; else { if (cnt >= 3) ++ans; pre_type = board[j][i]; cnt = 1; } } if (cnt >= 3) ++ans; } cout << ans << endl; //输出答案 } return 0; } |
PROBLEM J
把下标乘上1000得到一个递推式子，
BX(n) = BX(n – 1000) + BX(n – 1234)。
答案就是BX(n*1000)
Author Information
ABCJ : doubility(czk)
DH : ConquererV587(kbx)
GI: Xdynix(rxy)
