题目链接：
https://vjudge.net/contest/153814
A - An ant’s story(思维)
HDU - 3343
感觉特别坑的一道题目，只要蚂蚁爬的速度>0，它就能到终点，用到了极限思想？不明觉厉..GG..
AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int main()
{
int t;
int a, b, c;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&a,&b,&c);
if(b > 0)
cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
B - War Chess(BFS<用到优先队列>)
HDU - 3345
BFS好题，当时做的时候不是TLE就是MLE。赛后我重新写还是MLE（喵喵喵？ 后来问了一下陆历川大哥，他说得用优先队列，能用优先队列的就别用队列，然后给我发了个优先队列的讲解博客地址。又学到了新东西啊..
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
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
94
95
using namespace std;
const int MAX = 105;
int n, m, v;
int dir[][2] = {0,1,1,0,-1,0,0,-1};
char mapa[MAX][MAX], newa[MAX][MAX];
bool vis[MAX][MAX], eme[MAX][MAX];
struct node
{
int x, y, v;
bool operator < (const node &a) const
{
return v < a.v;//v大的优先
}
} q, p;
bool ok()
{
if(p.x < 0 || p.y < 0 || p.x >= n || p.y >= m) return false;
if(!p.v || vis[p.x][p.y] || mapa[p.x][p.y] == '#' || mapa[p.x][p.y] == 'E') return false;
if(mapa[p.x][p.y] == '.' || mapa[p.x][p.y] == 'P') p.v -= 1;
else if(mapa[p.x][p.y] == 'T') p.v -= 2;
else if(mapa[p.x][p.y] == 'R') p.v -= 3;
if(p.v < 0) return false;
if(eme[p.x][p.y]) p.v = 0;
return true;
}
void bfs()
{
priority_queue<node> Q;
Q.push(q);
while(!Q.empty())
{
q = Q.top();
Q.pop();
for(int i = 0; i < 4; ++i)
{
p.x = q.x + dir[i][0];
p.y = q.y + dir[i][1];
p.v = q.v;
if(ok())
{
vis[p.x][p.y] = 1;
if(mapa[p.x][p.y] != 'P') newa[p.x][p.y] = '*';
Q.push(p);
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(vis, 0, sizeof(vis));
memset(eme, 0, sizeof(eme));
scanf("%d%d%d",&n, &m, &v);
for(int i = 0; i < n; ++i)
{
scanf("%s",mapa[i]);
strcpy(newa[i], mapa[i]);
}
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(mapa[i][j] == 'Y')
{
vis[i][j] = 1;
q.x = i;
q.y = j;
q.v = v;
}
if(mapa[i][j] == 'E')
{
if(i - 1 >= 0) eme[i-1][j] = 1;
if(j - 1 >= 0) eme[i][j-1] = 1;
if(i + 1 < n) eme[i+1][j] = 1;
if(j + 1 < m) eme[i][j+1] = 1;
}
}
bfs();
for(int i = 0; i < n; ++i)
cout << newa[i] << endl;
cout << endl;
}
return 0;
}
C - Lucky Number(基础)
HDU - 3346
这个不多说了，又是抢的一血。额..当时有点激动漏了个条件（当然样例是不会让你看出来的，细心一点就好了。
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
using namespace std;
int main()
{
int t, n, ans, ans2;
while(~scanf("%d",&t))
{
while(t--)
{
ans = ans2 = 0;
scanf("%d",&n);
if(n % 8 == 0) cout << "Lucky number!" << endl;
else
{
int tem = n;
while(tem)
{
int qq = tem % 10;
ans += qq;
tem /= 10;
ans2 = ans2 + qq*qq;
}
if(ans % 8 == 0 || ans2 % 8 == 0)
cout << "Lucky number!" << endl;
else cout << "What a pity!" << endl;
}
}
}
return 0;
}
D - Calculate the expression(模拟)
HDU - 3347
模拟呀..今下午自己写了会，用了不少STL的东西，后来将表示数字的字符转换为数字时我想到了atoi函数，然而这个函数对string不适用，想着改为char数组后再用这个函数吧，改着改着把自己改迷糊了..去听完报告回来后全换为char数组，结果TLE了（如果用stringstream不就直接弄死我..问了问我兄弟，他说在打游戏让我去他博客找找看（→_→ 你很棒棒哦 对比后感觉自己写的略微“高级”，然后我把“高级”部分改为朴素的if – else if然后就过了，噫，看来能A题的代码才是好代码。
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
char s[105];
char k[25];
int main()
{
int t, n, flag, tem, ans;
scanf("%d",&t);
while(t--)
{
flag = 1;
ans = 0;
map<string, int> ss;
scanf("%d",&n);
//cout << "n= " << n << endl;
for(int i = 1; i < n; ++i)
{
scanf("%s = %d",s, &tem);
ss[s] = tem;
//cout << "s= " << s << " tem= " << tem << endl;
//cout << "???" << endl;
}
while(1)
{
scanf("%s",s);
tem = 0;
if(s[0] >= '0' && s[0] <= '9')//是正数 数字
{
for(int i = 0; i < strlen(s); ++i)
{
tem *= 10;
tem += (s[i] - '0');
}
if(flag == 0) ans = ans - tem;
else ans = ans + tem;
}
else if(s[0] == '-') //这里注意一下 表达式中出现-号一定是常数 （我之前还以为会有 1 + -aa的情况..
{
for(int i = 1; i < strlen(s); ++i)
{
tem *= 10;
tem += (s[i] - '0');
}
if(flag == 1) ans = ans - tem;
else ans = ans + tem;
}
else if(flag == 0)
ans = ans - ss[s];
else
ans = ans + ss[s];
scanf("%s",k);
if(k[0] == '=') break;
if(k[0] == '+') flag = 1;
else flag = 0;
}
scanf("%s",k);//处理最后剩下的"？"
//cout << "ans= " << ans << endl;
cout << ans << endl;
}
return 0;
}
写完这篇博客的第二天发现了个有趣的函数——c_str()，这个函数会生成一个const char*指针，指向以空字符终止的数组，有了它我们就可以对string使用atoi函数了。马上去写了一下，觉得爽的同时也觉得自己还是图样图森破。
（我发现的问题，那些前辈们肯定早就知道了，还有的早就在函数库里添加了相应的函数，只是我不知道而已(￣ε(#￣)☆╰╮(￣▽￣///) 最后再说一句——STL大法好
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
45
46
47
48
49
50
51
using namespace std;
int main()
{
int t, n, tem, flag, ans;
string s, stem;
scanf("%d",&t);
while(t--)
{
map<string, int> num;
scanf("%d",&n);
for(int i = 1; i < n; ++i)
{
cin >> s;
scanf(" = %d",&tem);
num[s] = tem;
//cout << s << " " << tem;
}
getchar();//接收一个换行符 这里要注意一下
getline(cin, stem);
stringstream ss(stem);
ans = 0;
flag = 1;
while(ss >> s)
{
if(s == "=") break;
if(s == "-") flag = -1;
else if(s == "+") flag = 1;
else
{
if(isalpha(s[0]))
{
tem = num[s];
}
else
{
tem = atoi(s.c_str());//666
}
ans += (tem*flag);
}
}
cout << ans << endl;
}
return 0;
}
E - coins(贪心)
HDU - 3348
贪一贪。（代码写的通俗易懂，至于别人的空间复杂度低的我也不去管了，反正能A题的代码都是好代码(⊙v⊙) 明明很好解决的问题，却只有我和我兄弟做出来了。啧啧啧，队友瑕还说这个和上次做的多重背包的很像，受背包毒害不浅啊..还有通过这次训练，我决定我来作主代码手，毕竟我刷的（基础）题多，见识的（无用）知识点多，还有单身19年+的手速。
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
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
using namespace std;
int a[5], b[5]; //面值为1 5 10 50 100的钞票个数
int main()
{
int t, p, ans1, ans2;;
scanf("%d",&t);
while(t--)
{
scanf("%d",&p);
ans1 = ans2 = 0;
for(int i = 0; i < 5; ++i)
scanf("%d",&a[i]);
for(int i = 0; i < 5; ++i)
b[i] = a[i];
int tem = p;
while(tem >= 100 && a[4])
{
tem -= 100;
a[4]--;
ans2++;
}
while(tem >= 50 && a[3])
{
tem -= 50;
a[3]--;
ans2++;
}
while(tem >= 10 && a[2])
{
tem -= 10;
a[2]--;
ans2++;
}
while(tem >= 5 && a[1])
{
tem -= 5;
a[1]--;
ans2++;
}
while(tem >= 1 && a[0])
{
tem -= 1;
a[0]--;
ans2++;
}
if(tem > 0)
{
ans2 = ans1 = -1;
cout << "-1 -1" << endl;
}
else
{
while(b[0] + b[1] * 5 + b[2] * 10 + b[3] * 50 < p)
{
p -= 100;
ans1++;
}
while(b[0] + b[1] * 5 + b[2] * 10 < p)
{
p -= 50;
ans1++;
}
while(b[0] + b[1] * 5 < p)
{
p -= 10;
ans1++;
}
while(b[0] < p)
{
p -= 5;
ans1++;
}
ans1 += p;
cout << ans2 << " " << ans1 << endl;
}
}
return 0;
}
F - lazy gege(数学)
HDU - 3349
平面几何，找长方形的重心—>看正方形的对角线长度和长方形中较短的边的关系，一共有三种情况，自己画个图就很好理解了。计算几何主要就是看思维了，代码实现并没有什么难度，注释的挺详细了，注意一下三个if的顺序。
AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int main()
{
int t;
double l, a, b, ans;
scanf("%d",&t);
while(t--)
{
scanf("%lf%lf%lf",&l,&a,&b);
if(a > b) swap(a, b); //保证a为长方形的较小边
double tem = sqrt(2.0) * l; //正方形的对角线长度
if(a < tem) ans = a*a/4.0; //放在正方形上的部分为等腰△
else if(a > tem && a < 2.0*tem) ans = l*l - (tem - a/2)*(tem - a/2); //正方形面积减去等腰三角形面积
else ans = l*l; //覆盖正方形
printf("%.4lf\n",ans);
}
return 0;
}
G - #define is unsafe(模拟)
HDU - 3350
用栈实现的模拟题，这里我用vector数组模拟了个栈。
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
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
using namespace std;
struct node
{
int val;//值
int add;//+的次数
};
//用vector实现模拟栈的FILO
vector<node> ans;//数值栈
vector<char> sig;//符号栈
int main()
{
int T;
string str;
node tem, tem2;
scanf("%d",&T);
while(T--)
{
cin >> str;
//不要忘记初始化
tem.val = tem.add = 0;
ans.clear();
sig.clear();
for(int i = 0; i < str.length(); ++i)
{
//逐字扫描，只有'('、'+'、','、')'和数字是有用的
//"MAX"不做处理
//优先级：'(' > '+' > ',' > ')'
switch(str[i])
{
case '(':
sig.push_back(str[i]);
tem.val = tem.add = 0;
break;
case '+':
ans.push_back(tem);
sig.push_back(str[i]);
tem.val = tem.add = 0; //每次push后都要初始化tem
break;
case ',':
while(!sig.empty() && sig.back() == '+')
{
tem2 = ans.back();
tem.val += tem2.val;
tem.add += tem2.add + 1;
ans.pop_back();
sig.pop_back();
}
ans.push_back(tem);
sig.push_back(str[i]);
tem.val = tem.add = 0; //初始化tem
break;
case ')':
while(!sig.empty() && sig.back() == '+')
{
tem2 = ans.back();
tem.val += tem2.val;
tem.add += tem2.add + 1;
ans.pop_back();
sig.pop_back();
}
tem2 = ans.back();
if(tem.val < tem2.val)
{
tem.val = tem2.val;
tem.add = tem2.add*2 + tem.add;
}
else
{
tem.add = tem.add*2 + tem2.add;
}
sig.pop_back();
sig.pop_back();
ans.pop_back();
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
tem.val = tem.val*10 + str[i] - '0';
break;
}
}
while(!sig.empty() && sig.back() == '+')
{
tem2 = ans.back();
tem.val += tem2.val;
tem.add += tem2.add + 1;
ans.pop_back();
sig.pop_back();
}
cout << tem.val << " " << tem.add << endl;
}
return 0;
}
