山东省第四届ACM大学生程序设计竞赛解题报告【6/10】

发表于 | 更新于 | 分类于
－－－－－－－－－－－山东省第四届ACM大学生程序设计竞赛解题报告－－－－－－－－－－ －

A.Rescue The Princess【计算几何】

题意：给出A、B坐标，要你找出一个点C，使得△ABC是正三角形，且点C在AB点的逆时针方向上。

思路：根据角的关系进行计算，“广义化”的思想省去了很多判断的麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5+5;
const double PI = acos(-1.0);
const double six = PI/3;

int main()
{
    int T;
    double x1, y1, x2, y2;
    cin >> T;
    while(T--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        double d = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
        double si = (y2-y1) / d;
        double co = (x2-x1) / d;
        double y = (sin(six)*co + cos(six)*si)*d;
        double x = (cos(six)*co - sin(six)*si)*d;
        printf("(%.2lf,%.2lf)\n", x1+x, y1+y);
    }
    return 0;
}

B.Thrall’s Dream

C.A^X mod P

D.Mountain Subsequences【思维】

队友AC

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 30;
const int mod = 2012;
long long sum1[maxn],sum2[maxn],sum3[maxn];
int m[100010];
int main()
{
    int n;
    ios::sync_with_stdio(0);
    while(cin>>n){
        memset(sum1,0,sizeof sum1);
        memset(sum2,0,sizeof sum2);
        memset(sum3,0,sizeof sum3);
        for(int i=0;i<n;i++){
            char a;cin>>a;
            m[i]=a-'a'+1;
        }
        long long ans=0;
        for(int i=0;i<n;i++){
            long long s1=0,s2=0,s3=0;
            int now=m[i];
            for(int i=0;i<now;i++){
                s1+=sum1[i];
                s2+=sum2[i];
            }
            for(int i=maxn-1;i>now;i--){
                s3+=sum3[i]+sum2[i];
            }
            ans+=s3;
            sum3[now]+=s3;
            sum2[now]+=s1+s2;
            sum1[now]+=1;
            ans%=mod;sum3[now]%=mod;
            sum2[now]%=mod;sum1[now]%=mod;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

E.Alice and Bob【规律】【二进制】

题意：给出一个多项式，求出指数为P的x的系数。

思路：写出几项就会发现，对应指数为P的x的系数就是二进制下的P为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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 55;

ll p, res;
int t, n, q, a[N];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        memset(a, 0, sizeof(a));
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        scanf("%d", &q);
        while(q--)
        {
            res = 1;
            scanf("%lld", &p);
            int idx = 0;
            while(p)
            {
                if(p & 1)
                    res = res * a[idx] % 2012;
                ++idx;
                p /= 2;
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}

F.Boring Counting【主席树】

题意：给出包含$n$个数的序列$a$，问区间$l_i$到$r_i$里面的数大小在$x_i$到$y_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
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 50050;
int a[maxn], t[maxn];
int n, q, tot, m;
int lson[maxn * 20], rson[maxn * 20], T[maxn], c[maxn * 20];
void initHash() {
	for (int i = 1; i <= n; i++)
		t[i] = a[i];
	sort(t + 1, t + 1 + n);
	m = unique(t + 1, t + 1 + n) - t - 1;
}
int build(int l, int r) {
	int root = tot++;
	c[root] = 0;
	if (l != r) {
		int mid = (l + r) >> 1;
		lson[root] = build(l, mid);
		rson[root] = build(mid + 1, r);
	}
	return root;
}
int Hash(int x) {
	return lower_bound(t + 1, t + 1 + m, x) - t;
}
int update(int root, int pos, int val) {
	int newroot = tot++; int tmp = newroot;
	c[newroot] = c[root] + val;
	int l = 0, r = m + 1;
	while (l<r) {
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			lson[newroot] = tot++; rson[newroot] = rson[root];
			newroot = lson[newroot]; root = lson[root];
			r = mid;
		}
		else {
			rson[newroot] = tot++; lson[newroot] = lson[root];
			newroot = rson[newroot]; root = rson[root];
			l = mid + 1;
		}
		c[newroot] = c[root] + 1;
	}
	return tmp;
}
int query(int L, int R, int l, int r, int rt) {
	if (L <= l&&r <= R) {
		return c[rt];
	}
	int ans = 0, mid = (l + r) >> 1;
	if (L <= mid) {
		ans += query(L, R, l, mid, lson[rt]);
	}
	if (R > mid) {
		ans += query(L, R, mid + 1, r, rson[rt]);
	}
	return ans;
}
int main()
{
	int te, cas = 1;
	scanf("%d", &te);
	while (te--) {
		tot = 0;
		printf("Case #%d:\n", cas++);
		scanf("%d%d", &n, &q);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		initHash();
		T[0] = build(0, m + 1);
		for (int i = 1; i <= n; i++) {
			int pos = Hash(a[i]);
			T[i] = update(T[i - 1], pos, 1);
		}
		while (q--) {
			int l, r, a, b;
			scanf("%d%d%d%d", &a, &b, &l, &r);
			l = Hash(l); int pos = Hash(r);
			if (pos == m + 1)r = pos;
			else if (t[pos] != r)r = pos - 1;
			else r = pos;
			int ans1 = query(l, r, 0, m+1, T[b]);
			int ans2 = query(l, r, 0, m+1, T[a - 1]);
			printf("%d\n", ans1 - ans2);
		}
	}
	return 0;
}

G.Rubik’s cube

H.A-Number and B-Number

数位DP？

I.The number of steps【期望】

题意：现在你在房间的最顶端，每次可以往左下右下或者左边走，给出走向各方向的概率，问走到最左下角的步数期望是多少。只能往左走时往左走的概率是1；只能往左下和右下走时概率分别是a和b；能往三个方向走时各方向概率分别是c、d和e。

思路：从前往后推就可以了。

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

int n;
double a, b, c, d, e;
double dp[50][50];

int main()
{
    while (scanf("%d", &n) != EOF && n) {
        scanf("%lf %lf %lf %lf %lf", &a, &b, &c, &d, &e);
        dp[n][1] = 0;
        for (int i = 2; i <= n; ++i) {
            dp[n][i] = dp[n][i-1]+1;
        }
        for (int i = n-1; i >= 1; --i) {
            dp[i][1] = a*(dp[i+1][1]+1)+b*(dp[i+1][2]+1);
            for (int j = 2; j <= i; ++j) {
                dp[i][j] = c*(1+dp[i+1][j])+d*(1+dp[i+1][j+1])+e*(1+dp[i][j-1]);
            }
        }
        printf("%.2f\n", dp[1][1]);
    }
    return 0;
}

J.Contest Print Server【模拟】

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 <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;

int t, n, s, x, y, m;
struct node
{
    char name[22];
    int req;
} a[N];
int main()
{
    int cas = 0;
    scanf("%d", &t);
    while(t--)
    {
        if(cas++)   puts("");
        scanf("%d%d%d%d%d", &n,&s,&x,&y,&m);
        for(int i = 1; i <= n; ++i)
            scanf("%s %*s %d %*s", a[i].name, &a[i].req);

        int now = 0;
        for(int i = 1; i <= n; )
        {
            if(now + a[i].req <= s)
            {
                ++i;
                now += a[i].req;
                printf("%d pages for %s\n", a[i].req, a[i].name);
            }
            else
            {
                printf("%d pages for %s\n", s - now, a[i].name);
                now = 0;
                s = s * x + y;
                s %= m;
            }
        }
    }
    return 0;
}
Donate comment here
0%