工大杯题解

发表于 分类于 本文字数： 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;
}

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