广东工业大学第十四届程序设计竞赛 题解

发表于 | 分类于 |
字数统计: 2,642 字

菜鸡是怎样炼成的

A

题目大意：有2个人，每一个人会随机得到0和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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
void init(){

}
void solve(){
    printf("1.00\n1.00\n1.00\n1.00\n");
}
int main(){
    init();
    solve();
    return 0;
}

B

题目链接

实际上就是求区间$[4a+b+1, 4c+d+1]$范围上的斐波那契平方和。注意可能会$4a+b+1>4c+d+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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int f[50005], sum[50005], M = 192600817;
void init(){
    f[0] = 0, f[1] = 1, sum[1] = 1;
    for(int i = 2; i <= 50000; ++i)
        f[i] = (f[i - 2] + f[i - 1]) % M, sum[i] = (sum[i - 1] + 1ll * f[i] * f[i]) % M;
}
void solve(){
    int Q;
    while(scanf("%d", &Q) == 1){
        while(Q--){
            int a = read(), b = read(), c = read(), d = read();
            if(4 * a + b > 4 * c + d) swap(a, c), swap(b, d);
            printf("%d\n", (sum[4 * c + d + 1] - sum[4 * a + b] + M) % M);
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}

C

题目大意：定义一个鸽子数为这样的一个数：将其每一位上的数的平方相加，得到一个新的数，再对新的数如此操作，循环往复，最终能得到1。求从小到大第$k$个鸽子数。多次询问。

由于每一个数位的平方和不会很大，因此可以认为鸽子数的分布不会很宽泛，因此直接暴力。

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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
bool vis[5000005] = {0};
int num[150005] = {0}, cnt = 0;
inline int sqr(int x){
    return x * x;
}
bool judge(int x){
    if(vis[x]) return false;
    if(x == 1) return true;
    int t = x, res = 0;
    vis[x] = true;
    while(t > 0)
        res += sqr(t % 10), t /= 10;
    bool rres = judge(res);
    vis[x] = false;
    return rres;
}
void init(){
    for(int i = 1; cnt < 150000; ++i){
        if(judge(i)) num[++cnt] = i;
    }
}
int main(){
    init();
    int Q = read();
    while(Q--){
        int k = read();
        printf("%d\n", num[k]);
    }
    return 0;
}

D

题目大意：有$Q$个操作，操作1会向序列中添加$a$个$b$，操作2给出$a$和$b$，求将序列排序后下标位于$[a, b]$间的数的和。

离线应该可以做，就是倒着做，把插入改成删除，然后用树状数组维护最终的序列。
然后WA了，还WA了6发，比赛结束都没有调试出来。（我也不知道为什么）
所以还是乖乖地用权值线段树，操作1直接更新，操作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
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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int Q, a[100005], tot = 0, M = 1000000007;
ll seg1[2000005] = {0}, q[100005][3];
int seg2[2000005] = {0}, cnt = 0, siz;
void update(int id, int v){
    int k = id + siz - 1;
    seg1[k] += 1ll * v;
    int res = 1ll * v * a[id - 1] % M;
    seg2[k] = (seg2[k] + res) % M;
    while(k > 1){
        k >>= 1;
        seg1[k] += 1ll * v;
        seg2[k] = (seg2[k] + res) % M;
    }
}
int query(int id, int l, int r, ll k){
    if(l == r) return k * a[id - siz] % M;
    int lc = (id << 1), rc = (id << 1 | 1), mid = (l + r) >> 1;
    if(k >= seg1[lc]) return (query(rc, mid + 1, r, k - seg1[lc]) + seg2[lc]) % M;
    else return query(lc, l, mid, k);
}
void init(){
    Q = read();
    for(int i = 0; i < Q; ++i){
        scanf("%lld%lld%lld", &q[i][0], &q[i][1], &q[i][2]);
        if(q[i][0] == 1ll) a[tot++] = q[i][2];
    }
    sort(a, a + tot);
    tot = unique(a, a + tot) - a;
    for(siz = 1; siz < tot; siz <<= 1);
}
void solve(){
    for(int i = 0; i < Q; ++i){
        if(q[i][0] == 1){
            int id = lower_bound(a, a + tot, q[i][2]) - a;
            update(id + 1, q[i][1]);
        }else{
            int res1 = query(1, 1, siz, q[i][2]), res2 = query(1, 1, siz, q[i][1] - 1);
            printf("%d\n", (res1 - res2 + M) % M);
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}

E

题目链接

整个变换可以拆分成2个部分：平移和旋转放缩。后者是一个线性变换，因此可以用矩阵表示。
设原来三角形的后两个顶点和第一个点构成的两个向量构成的矩阵为$A$，变换后三角形的后两个顶点和第一个点构成的两个向量构成的矩阵为$B$。那么我们希望能求出变换矩阵$T$。因为有$TA=B$，因此$T=BA^{-1}$。
然后每次给定一个点，就先求出它相对于三角形第一个点的向量，设为$x$，那么变换后的向量就是$Tx$，之后把平移补上即可。

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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
pair<int, int> p1[3], p2[3];
int mat[2][2];
double det;
void init(){
    for(int i = 0; i < 3; ++i) p1[i].first = read(), p1[i].second = read();
    for(int i = 0; i < 3; ++i) p2[i].first = read(), p2[i].second = read();
    mat[0][0] = (p2[1].first - p2[0].first) * (p1[2].second - p1[0].second) + 
        (p2[2].first - p2[0].first) * (p1[0].second - p1[1].second);
    mat[0][1] = (p2[1].first - p2[0].first) * (p1[0].first - p1[2].first) + 
        (p2[2].first - p2[0].first) * (p1[1].first - p1[0].first);
    mat[1][0] = (p2[1].second - p2[0].second) * (p1[2].second - p1[0].second) + 
        (p2[2].second - p2[0].second) * (p1[0].second - p1[1].second);
    mat[1][1] = (p2[1].second - p2[0].second) * (p1[0].first - p1[2].first) + 
        (p2[2].second - p2[0].second) * (p1[1].first - p1[0].first);
    det = 1.0 / ((p1[1].first - p1[0].first) * (p1[2].second - p1[0].second) - 
        (p1[2].first - p1[0].first) * (p1[1].second - p1[0].second));
}
void solve(){
    int Q = read();
    while(Q--){
        int x = read(), y = read();
        int ax = x - p1[0].first, ay = y - p1[0].second;
        int aax = ax * mat[0][0] + ay * mat[0][1], aay = ax * mat[1][0] + ay * mat[1][1];
        double bx = aax * det, by = aay * det;
        printf("%.2lf %.2lf\n", bx + p2[0].first, by + p2[0].second);
    }
}
int main(){
    int T = read();
    while(T--){
        init();
        solve();
    }
    return 0;
}

F

题目链接

1
2


G

题目大意：求

和式变换，原式化为，对里面那个式子有：
由求导规则，，因此把$x=1$带进去，可以把里面的式子化成$i\times 2^{i-1}$。这样就变成了一个数列求和。然后这个和是可以错位相减算出来的，化简出答案是$(i-1)2^i + 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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int M = 1000000007;
ll n;
int poww(int a, int b, int c){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % M;
        a = 1ll * a * a % M, b >>= 1;
    }
    return res;
}
void init(){

}
void solve(){
    int res = 1;
    res = 1ll * (n + 1ll) * res % M;
    res = 1ll * res * poww(2, n % 1000000006ll, M) % M;
    res = (res + 1) % M;
    res = (res - (poww(2, (n + 1ll) % 1000000006ll, M)) + M) % M;
    printf("%d\n", res);
}
int main(){
    while(scanf("%lld", &n) == 1){
        init();
        solve();
    }
    return 0;
}

J

题目大意：给定公式，求。

基本的矩阵乘法，列向量里面保留$1, n, n^2, n^3$四项用于凑出$(n+1)^3$即可。

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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int M = 123456789;
ll n;
struct Mat{
    int mt[7][7], r, c;  
    Mat(){
        memset(mt, 0, sizeof(mt));
    }
    Mat(int _r, int o){
        memset(mt, 0, sizeof(mt));
        this->r = this->c = _r;
        if(o){
            for(int i = 0; i < _r; ++i)
                this->mt[i][i] = 1;
        }
    }
};
void mul(Mat &a, Mat &b, Mat &res){
    res.r = a.r, res.c = b.c;
    for(int i = 0; i < a.r; ++i)
        for(int j = 0; j < b.c; ++j){
            int sum = 0;
            for(int k = 0; k < a.c; ++k){
                sum += (1ll * a.mt[i][k] * b.mt[k][j] % M);
                if(sum >= M) sum -= M;
            }
            res.mt[i][j] = sum;
        }
}
Mat poww(Mat a, ll p){
    Mat I(a.r, 1), tmp(a.r, 0);
    while(p){
        if(p & 1ll) 
            mul(I, a, tmp), I = tmp, memset(tmp.mt, 0, sizeof(tmp.mt));
        mul(a, a, tmp), a = tmp, memset(tmp.mt, 0, sizeof(tmp.mt));
        p >>= 1;
    }
    return I;
}
Mat m1, ini;
void init(){ 
    m1.r = m1.c = 6;
    m1.mt[0][0] = 1, m1.mt[0][1] = 2, m1.mt[0][2] = 1, m1.mt[0][3] = 3, m1.mt[0][4] = 3, m1.mt[0][5] = 1;
    m1.mt[1][0] = 1, m1.mt[1][1] = 0, m1.mt[1][2] = 0, m1.mt[1][3] = 0, m1.mt[1][4] = 0, m1.mt[1][5] = 0;
    m1.mt[2][0] = 0, m1.mt[2][1] = 0, m1.mt[2][2] = 1, m1.mt[2][3] = 3, m1.mt[2][4] = 3, m1.mt[2][5] = 1;
    m1.mt[3][0] = 0, m1.mt[3][1] = 0, m1.mt[3][2] = 0, m1.mt[3][3] = 1, m1.mt[3][4] = 2, m1.mt[3][5] = 1;
    m1.mt[4][0] = 0, m1.mt[4][1] = 0, m1.mt[4][2] = 0, m1.mt[4][3] = 0, m1.mt[4][4] = 1, m1.mt[4][5] = 1;
    m1.mt[5][0] = 0, m1.mt[5][1] = 0, m1.mt[5][2] = 0, m1.mt[5][3] = 0, m1.mt[5][4] = 0, m1.mt[5][5] = 1;
    ini.r = 6, ini.c = 1;
    ini.mt[0][0] = 2, ini.mt[1][0] = 1, ini.mt[2][0] = 8, ini.mt[3][0] = 4, ini.mt[4][0] = 2, ini.mt[5][0] = 1;
}
void solve(){
    Mat m2 = poww(m1, n - 2);
    Mat res;
    mul(m2, ini, res);
    printf("%d\n", res.mt[0][0]);
}
int main(){
    int T = read();
    init();
    while(T--){
        scanf("%lld", &n);
        solve();
    }
    return 0;
}

总结

codeforces到了黄名之后有点飘