虽然很多是水题，不过还是记录一下。。。。然后还有好多得做的题目都还没补TAT

1209. 1, 10, 100, 1000…

一个这样的串110100100010000……问第n位是什么。

很明显第n*(n+1)/2位才会是1，其中n为正整数，所以判断一下就行了。

1224. Spiral

给定一个N＊M的矩阵，开始面向左侧，由右上角开始顺时针方向走，每个格子走过一次，为走完整个矩阵需要改变方向多少次。

答案是这个：min(2(n-1), 2(m-1)+1)。至于为什么，仔细想想的话应该就明白了，不过这题虽然简单，我好像还是被坑了好几次。比如说什么 N, M (1 ≤ N, M ≤ 2^31 − 1)，但是乘一下就爆int，得用long long之类的。。。

1225. Flags

用红、白、蓝三种颜色去染一排连续的格子，染色规则是

  • 相邻两个格子颜色不能一样
  • 蓝色必须夹在红色和白色的格子中间

求给定格子数的染色方案
显然，最后一个格子不能染蓝色，就是说，最后一个格子只能是红or白。那个我们就可以得到如下关系

F[N] = F[N-1] + F[N-2]

第N－1个，最后是红或者白，那么第N个只能选白或者红。第N－1个是蓝色，即N－2个为红或者白，就是F[N－2]，那么第N个只能是白或者红。然后就是F[1] = F[2] = 2。

1226. esreveR redrO

给定一个文本，把每一段连续的字母翻转，其它字符保持不变。
直接做咯，每次看到涉及字符串的题总是会有恐惧感。贴一下代码，安慰一下自己的心灵，有时候字符串的题没有想像中那么多坑。

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
#include <iostream>
#include <cstdio>

using namespace std;

char a[300];

int main() {
    char c;
    int t = -1;
    while (1) {
        c = getchar();
        if (c == EOF) break;
        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            a[++t] = c;
        } else {
            for (int i = t; i >= 0; i--)
                printf("%c", a[i]);
            printf("%c", c);
            t = -1;
        }
    }
    for (int i = t; i >= 0; i--)
        printf("%c", a[i]);
    return 0;
}

1227. Rally Championship

详情请戳

1228. Array

这个读懂题就会做了。。。。

1229. Strong Brickwork

详情请戳

1258. Pool

题目可以理解为，给一个矩形，上下左右四条边分别用F、B、L、R表示，给定起始点还有终点的坐标，求一束光由起点到终点的移动距离，给出反射的边的序列。

我们可以把四条边都想像成镜子，然后就是我们学物理时的那点小花招，把求两点间的折线的长度转化成了求两点间的直线距离。我想了好久才理清楚怎么变换坐标。。。。，感觉这还是一道很有趣的题目，一开始以为是变态的计算机何，所以不敢做TAT

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
#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
    double w, d, x1, y1, x2, y2, x, y;
    string s;
    cin >> w >> d;
    cin >> x1 >> y1;
    cin >> x2 >> y2;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        switch (s[i]) {
            case 'F':
                y1 = -y1;
                break;
            case 'B':
                y1 = 2 * d - y1;
                break;
            case 'L':
                x1 = -x1;
                break;
            case 'R':
                x1 = 2 * w - x1;
                break;
        }
        cout << x1 << ' ' << y1 << endl;
    }
    double ans;
    ans = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    printf("%.4f\n", ans);
    return 0;
}

1259. How to Become Star?

根据给定的定义，求N角星的个数。

Definition. A star is the closed broken line built by the final amount of steps of the following algorithm:

  1. Fix and arbitrary angle α (0 < α < π).
  1. The first link is (0, 0) — (1, 0).
  1. The second link is the resultant of the turn by the angle α counter-clockwise with respect to the point (1, 0) of the first one.
  1. The (i + 2)-nd link is the resultant of the turn by the angle α counter-clockwise of the (i + 1)-st one with respect to the free end (the opposite to the one that is connected to the i-th link) of the (i + 1)-st link.
  1. The algorithm stops immediately when the broken line is closed.

Problem illustrationProblem illustration

该怎么证明呢( ´ ▽ ` )ﾉ，自行参见题目的discuss吧或者自行证明，可以用复数。最后答案是Φ(n)/2

好吧，来补个证明，希望没讲错，外加能讲清楚：

  • 设 β＝π－α ，则 0 < β < π ; //N, α为题目描述中的
  • 有 Nβ mod 2π ＝ 0，则对于该β，N为对应的最小的整数。 //为什么mod 2π等于0，我们可以想像把N角星的各个顶点移动到(1, 0)这点，则每次画一条新边就是上一条边顺时针旋转β，第n条边要刚好跟第一条边重合，且是第一次跟第一条边重合。
  • ∴β = p * π / N, p为整数, 又为满足上式p要为偶数
  • ∴β = 2 i π / N ，0 < i < N/2
  • 上面说到，N为β对应的最小的整数，即不存在整数 k，k < N, 且 kβ mod 2π ＝ 0, 即
  • 对任意k < N，k 2 i * π / N mod 2π ≠ 0.
  • ∴k * i / N 不能为整数，即 i 必须与 N 互质，可得最后的答案为Φ(n)/2

1260. Nudnik Photographer

1～n进行排列，第一位为1，相邻两个数字的差不能超过2。求方案数。

F[N]表示N个数的方案数，那么F[N]可由如下方法得到：

  • 2放在第二位，则是F[N-1]
  • 3放在第二位，第三位放2（那么再小一位一定是4），就是F[N-3]
  • 3放在第二位，第三位不放2，且n >=4,那么就只有一种方案，形如：1、3、5、7、8、6、4、2

所以最后可的方程：F[N] = F[N-1] + F[N-3] + 1

1261. Tips

某岛使用的货币的面值是3的幂，3，9，27…..，你要付一笔N元的账单，并且需要给小费，小费需要由不同面值的纸币组成。输出你需要付的最少的钱数sum，以及小费数tips。

显然3进制下，sum以及tips只由1和0组成。然后就是构造出这个最小的tips了，我们可以把N表示成3进制，由最低位开始，如果N在该位为2，tips和N就加上3在该位的幂。好像大概就是这么回事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

int a[100];

int main() {
    int n, m = 1, x = 0, y = 0;
    cin >> n;
    x = n;
    do {
        if (n % 3 == 2) {
            y += m;
            n++;
        }
        n /= 3;
        m *= 3;
    } while (n);
    if (!y) y = m;
    cout << x + y << ' ' << y << endl;
    return 0;
}

1262. Pseudo-Roman Number

这题的难度同样在于读题，理解题意后就会发现，对于1～9每个数字都有一个最短的表示方式，然后逐位处理就行了。

1263. Elections

直接做，统计每个数字出现的百分比，不解释

1264. Workdays

这是签到题吧=_=

后记：终于写完了的说，发现写题解还是很累，很多自己想得明白但还是说不清楚，再也不写这种一点都不过简要的什么一周记录了，以后就挑一些有趣的来写就好了，可是我觉得很多题都很有趣怎么办(°_°)