工大杯题解

发表于 分类于 本文字数： 852 阅读时长 ≈ 3 分钟

"工大杯"程序设计竞赛 罚时之旅

大家好, 我就是L·罚时一年·同学.

A题

DFS会WA.
题目有点问题, 没说明一定是一颗树, 但是数据太水, 导致直接求直径就能A. 正解是先判环在DFS, 可是我并没有写出来.

B题

乍一看还以为是表达式求值, 仔细看发现不考虑符号优先级. 注意从右往左结合, 因此读入所有数字到数字栈, 符号到符号栈, 每次取栈顶运算输出结果即可.
正解是直接倒序遍历字符串, 可是STL大法好

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
#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <stack>
using namespace std;

#define DEBUG 1

void solve(){
    string tmp;
    cin>>tmp;
    stack<int> nums;
    stack<char> ops;
    istringstream sin(tmp);
    int temp = 0;
    sin>>temp;
    char op;
    nums.push(temp);
    while((op = sin.get()) != EOF){
        ops.push(op);
        sin>>temp;
        nums.push(temp);
    }
    int ans = nums.top();
    nums.pop();
    int b;
    while(!ops.empty()){
        op = ops.top();
        b = nums.top();
        ops.pop();
        nums.pop();
        if(op == '+'){
            ans += b;
        }
        else if(op == '-'){
            ans -= b;
        }
        else if(op == '*'){
            ans *= b;
        }
        else if(op == '/'){
            ans /= b;
        }
    }
    cout<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C题

网络流, 可是我并不会

D题

最开始还以为是数论, 用gcd推了半天, 没推出来. 然后发现是裸的初中数学.

a*b = a+b = i, 消元, 列二次方程, 得到a^2 - a*i + i = 0. 判别式大于等于0只需 i*i - 4*i>=0.

当然也可以简单地判断 n 是否在(0,4)内

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    long long n;
    cin>>n;
    cout<<((n*n-4*n>=0)?"YES":"NO")<<endl;
    return 0;
}

E题

板子里有, 可是我不会高静模, 于是 GG.

正解并不需要高静. 每次读入 n 的一位, 分别模 p 和 p-1, 算2^(n-1%(p-1))*n%p即可.

F题

不会

G题

水题, 暴力即可. 看错题了导致WA一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int ans = 0;
    while(n != 1){
        if(n%2){
            n = 3 * n + 1;
        }else{
            n = n / 2;
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

H题

并不会, 正解是摩尔投票算法.

I题

DP, 用 count[x][i] 表示第 x 位涂色为 i 所花费的最少钱数.
转移方程: count[x][i] = min(count[x-1][j] + cost[x][j], j!=i) cost[x][j] 表示将 x 涂为颜色 j 所花费的钱.
是线性递推, 可以压缩至一维 dp, 但没必要.

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
#include <iostream>
using namespace std;
#define MAXN 1010
#define min(a,b) ((a)<(b)?(a):(b))
int n;
int R[MAXN] = {0};
int B[MAXN] = {0};
int G[MAXN] = {0};
int coust[MAXN][4] = {0};
int main(){
    cin>>n;
    for(int i = 0; i < n; ++ i){
        cin>>R[i]>>G[i]>>B[i];
    }
    //R 1 G 2 B 3
    coust[0][1] = R[0];
    coust[0][2] = G[0];
    coust[0][3] = B[0];
    for(int i = 1; i < n; ++ i){
        coust[i][1] = min(R[i] + coust[i-1][2],R[i]+coust[i-1][3]);
        coust[i][2] = min(G[i] + coust[i-1][1],G[i]+coust[i-1][3]);
        coust[i][3] = min(B[i] + coust[i-1][1],B[i]+coust[i-1][2]);
    }
    int minn = 0x7fffffff;
    minn = min(minn,coust[n-1][1]);
    minn = min(minn,coust[n-1][2]);
    minn = min(minn,coust[n-1][3]);
    cout<<minn<<endl;
    return 0;
}

J题

大水题, 详情请见本公众号推送的"每日一题-每位数字问题".
记得特判0.
如果使用数字解法, 则不需要处理前导0. 如果使用字符串需要处理前导0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n == 0){
        cout<<0<<endl;
        return 0;
    }
    while(n){
        cout<<n%10;
        n/=10;
    }
    cout<<endl; 
    return 0;
}

部分题解和官方正解雷同, 并不是我抄袭, 正解就是我写的.