工大杯题解

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

大家好, 我就是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;
}

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