2017锐捷网络杯，总共9道题，1-2名解决了8道，本人仅仅解决了4道，拿了18名的名次，恰好是三等奖最后一名，奖金800元，开心。
题目复现：http://acm.whu.edu.cn/olive/problems/8
题号：703-711

707. Matrix

输入一个数N(12<=N<=100)，一个九宫格，从1-N选取9个不同的数填充，使得横竖斜和都为N。

思路：暴力枚举，如果枚举全部则100^9复杂度，但是和已告诉，即可以只枚举4个数就行，时间复杂度100^4，可能稍微超过1s，可以离线计算然后存储提交。

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 <iostream>
using namespace std;

int ans;

void dfs(int arr[], int dex, bool flag[], int N) {
    if(dex == 3 && arr[1] + arr[2] >= N) return;
    if(dex == 4 && arr[1] + arr[3] >= N) return;
    if(dex == 5) {
        arr[5] = N - arr[1] - arr[3];
        arr[6] = N - arr[2] - arr[4];
        arr[7] = N - arr[1] - arr[2];
        arr[8] = N - arr[3] - arr[4];
        arr[9] = N - arr[7] - arr[8];
        for(int i = 1; i <= 9; i++) if(arr[i] < 1) return;
        for(int i = 5; i <= 9; i++) if(flag[arr[i]]) return;
        if((arr[5]+arr[6]+arr[9] == N)&&(arr[1]+arr[4]+arr[9] == N)&&(arr[5]+arr[4]+arr[7] == N)) {
           ans++;
        }
        return;
    }
    if(dex > 5) return;
    for(int i = 1; i <= N; i++) {
        if(!flag[i]) {
            flag[i] = true;
            arr[dex] = i;
            dfs(arr, dex+1, flag, N);
            flag[i] = false;
        }
    }
    return;
}

int main()
{
    int N;
//    for(N = 12; N <= 100; N++){
//        ans = 0;
//        int arr[10];
//        bool flag[105];
//        for(int i = 0; i < 105; i++) flag[i] = false;
//        dfs(arr, 1, flag, N);
//        cout << ans << ',';
//    }
    int num[105] = {0,0,0,8,0,0,24,0,0,32,0,0,56,0,0,80,0,0,104,0,0,136,0,0,176,0,0,208,0,0,256,0,0,304,0,0,352,0,0,408,0,0,472,0,0,528,0,0,600,0,0,672,0,0,744,0,0,824,0,0,912,0,0,992,0,0,1088,0,0,1184,0,0,1280,0,0,1384,0,0,1496,0,0,1600,0,0,1720,0,0,1840,0};
    while(cin >> N) {
        cout << num[N - 12] << endl;
    }
    return 0;
}

709. Circle

题目：计算两个圆上面部分的面积。

思路：纯数学几何问题。

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

#define pi acos(-1.0)

using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	int n, x1, x2, r;
	cin >> n;
	while (n--)
	{
		cin >> x1 >> x2 >> r;
		if (x2 - x1 > 2 * r)
		{
		    double shadow = 0;
			printf("%.2f\n", shadow);
		}
		else
		{
			double d = double(x2 - x1) / 2;
			double h = sqrt(r*r - d*d);
			double ang = asin(d / r);
			double aver1 = ang / 2 * r*r;
			double aver2 = h*d / 2;
			double aver = aver1 - aver2;
			double shadow = 2 * ((r - h)*d - aver);
			printf("%.2f\n", shadow);
		}
	}
	return 0;
}

711. To be or not

题目：计算字符串中有多少个”AC”的字符串。
思路：直接数呗。

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

int main()
{
    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        int ans = 0;
        for(int i = 0; i < s.length() - 1; i++){
            if(s[i] == 'A' && s[i + 1] == 'C') {
                ans++;
                i++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

710. Filling

题目：给定两种规格瓷砖，输入一个N，问有多少种方案能铺满2*N地板。
思路：动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T, n;
    constexpr int mod = 1e9 + 7;
    cin >> T;
    int res[100005] = {1, 1, 2, 5};
    for (int i = 4; i < 100005; i++) {
        res[i] = res[i - 1] * 2 + res[i - 3];
        res[i] %= mod;
    }
    while (T--) {
        cin >> n;
        cout << res[n] << endl;
    }
    return 0;
}

705. Line Up

题目：只能移动相邻的两个数使数组有序，升序或者降序。
思路：求逆序对即可，普通方法时间复杂度高，可借用归并排序。

704. Super Brain

题目：给两个数使用二进制表示，求四种与或运算的最大值。
思路：模拟计算出结果比较即可。