牛客寒假算法基础集训(白给)营5题解

如此屑的J题还有什么存在的必要吗(半恼),受某次noip的某个屑题的影响导致我现在对结论题的印象非常之差。

可能是看着前几场打的还可以,康哥一声令下本场记分。。我一开始寻思着吧,估计和前几场差不多呗,看牛客的考点感觉也不算太难。然后拿到题目一看,签到题怎么没了?做着做着我才懂得一个道理————永远不要太相信预告片啊(逃

这段掐了别播

(我上上场中的杯子年前发不过来了,时候不巧,快递停了。。。)

已更新补题。


A 炫酷双截棍

原题:https://ac.nowcoder.com/acm/contest/331/A

这题虽然是AC数最多的题,但是就难度而言不能算签到。考点就是个模拟,手边没有草稿纸的话单纯靠大脑里的GPU大概是计算不准这个情况的。。。(然后我本场还真的忘了拿草稿纸,这场没在家打,就随便找了张硬纸板当草纸了。。)

题意是说有一个形似双截棍的东西,一根棍的一个点固定在(0,0)上可以随意转,然后另一头连接着另一个棍,都能三百六十度随意转,既然能转那显然存在转的到的区域。然后给出一些询问,问这些点哪个可以在第二个棍的另一端部分能转到。简单画一下图可以发现l2另一个顶点可以到达的区域是一个圆环,在这个圆环里面任何一个点都能够到,根据询问,如果询问的点够不到的话要输出最小距离,显然两点之间线段最短,一个点是不在区域内的,另一个点是哪?连接这个点和(0,0),连线过圆环的内界和外界,这两个点分别对应了当点在圆环内和点在圆环外的“另一个点”,距离直接用大半径减去小半径就可以。圆环的两个边界到也要算出来,一个是l1+l2,一个是l1-l2。

然而做到这里,你并不能拿到AC。坑点:题目没有保证l1>l2,如果l1<l2,计算小边界的时候就会出现负数。所以真实的小边界应该是abs(l1-l2)。

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#define maxn 2333
using namespace std;
double l1,l2;

double dis(double x,double y) {
return sqrt((x*x) + (y*y));
}

int main() {
ios::sync_with_stdio(false);
cin >> l1 >> l2;
double reachDisMin = abs(l1 - l2);
double reachDisMax = l1 + l2;
int t;
cin >> t;
double xi,yi;
while (t--) {
cin >> xi >> yi;
double checkDis = dis(xi,yi);
if (checkDis >= reachDisMin && checkDis <= reachDisMax) {
printf("0.00000000\n");
}
else{
if (checkDis < reachDisMin) {
printf("%.8lf\n",reachDisMin - checkDis);
}
else if (checkDis > reachDisMax) {
printf("%.8lf\n",checkDis - reachDisMax);
}
}
}

return 0;
}

I 炫酷镜子

原题:https://ac.nowcoder.com/acm/contest/331/I

搜索也行,瞎搞也行,一开始读题以为题目挺难的,后来发现随便搞搞就能过。

这题我要感谢暑假里学游戏开发的自己,如果没有当时写飞机大战控制飞机移动代码的思路这题,我可能真的会傻傻的去搜索然后处理各种难受的边界(尽管用这个做法也调了好长时间),不过看到自己一遍过还是很开心的,特别刺激。

题目设定有一点物理学原理(和上一场考二力合成那个硬核物理没法比。。),就是光的反射定律。有两种和水平面成角45°的镜子,但是方向不一样。光源在二维数组的最上方,问从左到右依次射入一束光,光会从二维数组下部射出。

数据量比较小,当时我就考虑是不是可以去一个个的模拟光行走的过程。于是去分析镜子,发现一共是有八种情况,

每一种镜子都有四种可能射入的光线,射出光线应该怎样,嗯,大家都学过初中物理,这个不用多说。

简单来讲,我的做法的关键就在一个点:记录当前光线状态。为了方便我编写和调试,我使用了字符串作为状态标记。(想过用1234代表上下左右来着,但是debug起来实在是费事,不如直接用字符串标来的简单)

首先对整个空间做一个预处理:加上一个边框,这个边框方便我们判断光线是否出界。是否出界是结束循环的判断标准。当然实际上不加也行,不加就是空字符呗。。。加上的话稍微形象一些。

模拟光线运动。初始状态光线在最上面。这里的核心在于应该首先进行光线状态转变再进行移动。否则会出现转变状态失效的问题。模拟光线移动应该在光线出界时结束。

状态转变函数很简单,要注意参数必须传址而不是传值,因为牵扯到参数的修改。这里传入三个参数,一个是当前状态,另外的是当前的x坐标和y坐标。如果当前位置的字符是’.’,那说明光线还没有走到镜子,所以不用改状态,直接return。如果是镜子,则按照当前状态相应的去改变状态为反射后的状态。注意字符\不能写成’\’,应是’\\’。

题目保证光线一定能射出去,所以不用担心死循环问题。现在光线出界了,只需要看一下到底是在哪里出界的就可以。如果是在下方出界,也就是按照题目的要求从下方射出,则返回其y坐标,否则返回-1,该返回值可以直接作为答案输出。

题外话:这个程序调试的时间远大于编写的时间……

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 2333
#define debug cout << "ok" << endl;
using namespace std;
char c[maxn][maxn];
string status;
int n,m;

void change(string &status,int &x,int &y){
if (c[x][y] == '.')
return;
else if (c[x][y] == '/'){
if (status == "up"){
status = "right";
}
else if (status == "down"){
status = "left";
}
else if (status == "left"){
status = "down";
}
else if (status == "right"){
status = "up";
}
}
else if (c[x][y] == '\\'){
if (status == "up"){
status = "left";
}
else if (status == "down"){
status = "right";
}
else if (status == "left"){
status = "up";
}
else if (status == "right"){
status = "down";
}
}
}

int lightwork(int col){
status = "down";
int x = 1,y = col;
while (c[x][y] != '#') {
change(status,x,y);
if (status == "up"){
x--;
}
else if (status == "down"){
x++;
}
else if (status == "left"){
y--;
}
else if (status == "right"){
y++;
}
}

if (x == n+1)
return y;
else
return -1;
}


int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i=0;i<maxn;i++)
for (int j=0;j<maxn;j++)
c[i][j] = '#'; // edge
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin >> c[i][j];

int ans = -1;
for (int i=1;i<=m;i++){
ans = lightwork(i);
cout << ans << endl;
}
// cout << lightwork(1);
return 0;
}

J 炫酷数学

原题:https://ac.nowcoder.com/acm/contest/331/J

屑题。大屑题。看起来像是个数论题,实际呢,数论推个P,打表找规律。

这题根本没得讲,就推规律,推得出来就AC,推不出来就莫得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 <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#define maxn 2333
using namespace std;
long long int fast_pow(long long int a,long long int x,long long int p){
long long int ans = 1;
long long int sum = a % p;
for (;x;x>>=1,sum = sum*sum%p)
if (x&1)
ans = ans*sum%p;
return ans;
}
long long int m;
int main() {
ios::sync_with_stdio(false);
cin >> m;
cout << fast_pow(3,m,998244353);
return 0;
}

upd:以下为补题题解

G 炫酷数字

原题:https://ac.nowcoder.com/acm/contest/331/G

补题补的我好苦QAQ,先是打表看不懂,后来又卡我输入输出,超级难受

大体上明白这个表怎么打的了,这题应该就能算是补了。参考了zyd学长的博客和std后明白了这是咋做的了。

它是大循环套着小循环的结构,循环要一直走到maxn,里面的小循环控制的是某个数i的因子数的统计,就比如说j=1,所有的数都有1这个因数,就让所有的数因子数+1,然后j=2的话,所有2的倍数都有2这个因数,就让这些数因子数+1,3,4,5,都是如此。然后,每进行完一轮因数统计,就要更新最小答案,因为最后输出的要求是最小数,而拥有同样因子数的数可能有很多,必须求一轮因子数更新一次答案,最后询问啥输出啥就ok。

我终于可以睡觉了。。。。

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 <cstdio>
#include <cmath>
#define maxn 1000001
#define debug cout << "ok" << endl;
using namespace std;
int n, t;
int num[maxn];
int vis[maxn];

void init() {
for (int i = 1; i < maxn; i++) {
for (int j = i; j < maxn; j += i) {
num[j]++;
}
if (vis[num[i]] == 0)
vis[num[i]] = i;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int n, t;
cin >> t;
while (t--) {
cin >> n;
if (vis[n] == 0)
printf("-1\n");
else printf("%d\n", vis[n]);
}
return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:牛客寒假算法基础集训(白给)营5题解

文章作者:Shawn Zhou

发布时间:2019年01月31日 - 19:01

最后更新:2019年02月02日 - 21:02

原始链接:http://shawnzhou.xyz/2019/01/31/19-01-31-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%