—— Summon, Light!
0%

弱校联盟 2016 四川省赛

发表于 更新于 Valine：

。。。反正都不会。。。反正都是抄的。。。

水题。。。刚开始我还写了个判断在不在长方体之内的函数。。。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
struct point {
    int x,y,z;
} p[4];

inline long long sqr(long long x)
{
    return x*x;
}

int main()
{
    for (int i=0; i<3; i++)
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    int x,y,z;
    if (p[0].x<p[1].x) x=p[1].x;
    else if (p[0].x>p[2].x) x=p[2].x;
    else x=p[0].x;
    if (p[0].y<p[1].y) y=p[1].y;
    else if (p[0].y>p[2].y) y=p[2].y;
    else y=p[0].y;
    if (p[0].z<p[1].z) z=p[1].z;
    else if (p[0].z>p[2].z) z=p[2].z;
    else z=p[0].z;
    printf("%lld\n",sqr(x-p[0].x)+sqr(y-p[0].y)+sqr(z-p[0].z));
}

Coins

神题。。。根本没想到要分类讨论。。。
就说一下比较难的 $a=0$ $and$ $b\geq 2$ $and$ $c>0$ 的情况：

  • 首先可以放入 $k$ 个 3，那就有 $c$ 种不同的价钱。
  • 考虑到 $b\geq 2$ ，我们可以拿出 $1$ 个 3，放入 $1$ 个 2，价钱会减 1，或者放入 $2$ 个 2，价钱会加 1，这样多了 $2c$ 种价钱。
  • 下面可以先放入 $c$ 个 3（所有 3），再放入 $k$ 个 2，这样多了 $b$ 种价钱。
  • 而当 $k\gt 2$ 时，我们发现【不，并没有 ˊ_>ˋ】还可以拿出 $1$ 个 3，并且不会重复。
    放入所有 3，放入了 $k$ 个 2：$3c+2,3c+4,3c+6,3c+8,…$
    除了前 2 个（$3c\pm 1$ 已经出现过了）都可以拿出 1 个 3：$3c+3,3c+5,…$
    所以又多了 $b-2$ 种价钱。

总数为 $3c+2b-2$
其余看代码：

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll solve(ll a,ll b,ll c)
{
    if (a>=2) {
        return 3*c+2*b+a;
    }
    if (a==1) {
        if (b>=1) return 3*c+2*b+a;
        if (b==0) return 2*c+a;
    }
    if (a==0) {
        if (b>=2)
            if (c==0) return b;
            else return 3*c+2*b-2;
        if (b==1) return 2*c+b;
        if (b==0) return c;
    }
}

int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    printf("%lld\n",solve(a,b,c));
}

Matrix Transformation

直接看别人代码。。。发现就是类似于十字链表的东西，然后就自己写了
$Mnode$ 里面的 $r$ 就是记录该点右边的点，$d$ 就是记录该点下面的点
因为只记录两个方向，更新行的时候只需要更新 $l$ 的上面一行和 $r$ 这一行
所以说不必要的时候就不要四个方向都存了。。。其余看代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=201;
struct Mnode {
    int r,d;
    Mnode() {}
    Mnode(int _r,int _d):r(_r),d(_d) {}
} m[N*N];
int n,q,root;

inline int get(int x,int y)
{
    return x*n+y;
}

void rollr(int l,int r,int d)
{
    if (d==0) return;
    int rt=root;
    for (int i=0;i<(l-1+n)%n;i++)
        rt=m[rt].d;
    int pl=m[rt].d;
    for (int i=0;i<d;i++)
        pl=m[pl].r;
    for (int i=0;i<n;i++) {
        m[rt].d=pl;
        rt=m[rt].r;
        pl=m[pl].r;
    }
    for (int i=l-1;i<r;i++)
        rt=m[rt].d;
    int pr=m[rt].d;
    for (int i=0;i<n-d;i++)
        pr=m[pr].r;
    for (int i=0;i<n;i++) {
        m[rt].d=pr;
        rt=m[rt].r;
        pr=m[pr].r;
    }
    if (l<=0&&0<=r)
        for (int i=0;i<d;i++)
             root=m[root].r;
}

void rollc(int l,int r,int d)
{
    if (d==0) return;
    int rt=root;
    for (int i=0;i<(l-1+n)%n;i++)
        rt=m[rt].r;
    int pl=m[rt].r;
    for (int i=0;i<d;i++)
        pl=m[pl].d;
    for (int i=0;i<n;i++) {
        m[rt].r=pl;
        rt=m[rt].d;
        pl=m[pl].d;
    }
    for (int i=l-1;i<r;i++)
        rt=m[rt].r;
    int pr=m[rt].r;
    for (int i=0;i<n-d;i++)
        pr=m[pr].d;
    for (int i=0;i<n;i++) {
        m[rt].r=pr;
        rt=m[rt].d;
        pr=m[pr].d;
    }
    if (l<=0&&0<=r)
        for (int i=0;i<d;i++)
             root=m[root].d;
}

inline void print()
{
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (j<n-1) printf("%d ",root);
            else printf("%d\n",root);
            root=m[root].r;
        }
        root=m[root].d;
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    int tot=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++) {
            m[tot++]=Mnode(get(i,(j+1)%n),get((i+1)%n,j));
        }
    root=0;
    while (q--) {
        int k,l,r,d;
        scanf("%d%d%d%d",&k,&l,&r,&d);
        if (k==1) rollr(l,r,d);
        else rollc(l,r,d);
//        printf("ROOT: %d\n",root);
//        print();
    }
    print();
    return 0;
}
咖啡，亦我所需也