过了四题。。。

###A. Where do I Turn?

给三个点A，B, C，人在B点，背向A点，若走向C点求是直走，向左走，还是向右走。

求两个向量，AB， AC，用叉乘做，a x b = |a| |b| sin，得解。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

typedef struct record
{
    __int64 x;
    __int64 y;
} record;

record a, b, c;
__int64 tmp1, tmp2;

int main()
{
    cin >> a.x >> a.y;
    cin >> b.x >> b.y;
    cin >> c.x >> c.y;
    tmp1 = (c.x - a.x) * (b.y - a.y);
    tmp2 = (c.y - a.y) * (b.x - a.x);
    if(tmp1 == tmp2) printf("TOWARDS\n");
    if(tmp1 > tmp2) printf("RIGHT\n");
    if(tmp1 < tmp2) printf("LEFT\n");
    return 0;
}

###B. Effective Approach

求线性搜索正着搜和逆着搜的花费，直接用数组来记录数字的位置就可以。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

__int64 n, m, a[100010], p1, p2, b;

int main()
{
    __int64 tmp;
    scanf("%I64d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%I64d", &tmp);
        a[tmp] = i;
    }
    scanf("%I64d", &m);
    p1 = p2 = 0;
    for(int i = 1; i <= m; i++)
    {
        scanf("%I64d", &b);
        p1 += a[b];
        p2 += n - a[b] + 1;
    }
    printf("%I64d %I64d\n", p1, p2);
    return 0;
}

###C. Flying Saucer Segments

类似汉诺塔的一个题，可以直接用结论。

Fn = (3 * Fn - 1) + 2 => Fn = 3^n - 1

这种题直接让我想到ls同学…

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

__int64 quickpow(__int64 m, __int64 n, __int64 k)
{
    __int64 b = 1;
    while (n > 0)
    {
          if (n & 1)
             b = (b * m) % k;
          n = n >> 1 ;
          m = (m * m) % k;
    }
    return b;
}

int main()
{
    __int64 n, m;
    __int64 ans, tmp;
    cin >> n >> m;
    tmp = quickpow(3, n, m);
    ans = (( tmp - 1) % m + m) % m;
    cout << ans << endl;
    return 0;
}

###D. Naughty Stone Piles

= =来回想错了好几次。。。

给你n堆石头，每次可以移动一堆石头到另一堆，费用为移动堆的石头的个数。

现在又给了一个叠加限制k。

具体采取的策略就是先把石头数量排序，除了最重的，其他k个最重的叠加到最重的上面，除了 k + 1 个位置， 前面可以有 k 个位置来叠加， 那么再向前累计 k * k 个堆。

比较坑爹的是第十组数据总超时…最后看别人代码把 k = 1 预处理一下，就不超了。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define LL __int64
using namespace std;

LL rec[200010], sum[200010];

int main()
{
    LL n, q, k, ans, aans;
    scanf("%I64d", &n);
    for(LL i = 1; i <= n; i++)
        scanf("%I64d", &rec[i]);
    sort(rec + 1, rec + n + 1);
    sum[0] = 0;
    aans = 0;
    for(LL i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + rec[i];
        aans += rec[i] * (n - i);
    }
    scanf("%I64d", &q);
    for(LL i = 1; i <= q; i++)
    {
        scanf("%I64d", &k);
        if(k == 1)
        {
            printf("%I64d", aans);
        }
        else
        {
            ans = 0;
            LL j = n, x = 1, t = 0;
            while(j > 0)
            {
                if(x > j) x = j;
                ans += (sum[j] - sum[j - x]) * t;
                j -= x;
                t++;
                x *= k;
            }
            printf("%I64d", ans);
        }
        if(i != q)
            printf(" ");
    }
    cout << endl;
    return 0;
}