https://ac.nowcoder.com/acm/contest/3006
题解 https://ac.nowcoder.com/discuss/366644?type=101&order=0&pos=1&page=2
这场是真的傻了，E题人名打错调了半个小时愣是没看见。最后一个半小时还差两题看一题是个大模拟直接跳了，还有一题看着像爆搜，但发现怎么过的人这么少，又想其它方法，结果最后还是写了个爆搜，处理僵尸的时候还特意优化了，结果数据水的不行，错的都能过90几，结束几分钟后发现少乘了个2，还真是爆搜，A完人傻了，早知道干嘛不早点搞。
B. 牛牛战队的比赛地
题意：平面上有几个点，要求在x轴上找一个点，到所有点的最大距离最小。
最大最小，又是二分。每个点到x轴上某点距离小于等于L，这些x轴上的点组成一个区间，如果所有点的区间有交集，那么就能找到一个答案。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const double eps = 1e-8;
typedef pair<double, double>pii;
int n;
vector<pii>vc;
double x[maxn], y[maxn];
bool check(double t) {
vc.clear();
for (int i = 1; i <= n; i++) {
double Y = abs(y[i]);
if (t < Y)return false;
double d = sqrt(t*t - Y * Y);
vc.push_back(pii(x[i] - d, x[i] + d));
}
double s = vc[0].first, T = vc[0].second;
for (int i = 1; i < n; i++) {
s = max(s, vc[i].first);
T = min(T, vc[i].second);
}
return T >= s;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];
double L = 0, R = 100000.0;
while (R - L > eps) {
double mid = (L + R) / 2;
if (check(mid))R = mid;
else L = mid;
}
printf("%.6lf\n", L);
return 0;
}
|
D. 牛牛与牛妹的约会
题意：x轴上两个点，从第一个点到第2个点的最小花费。可以花费1从k到 3k，或者直接走，花费等于走的距离。
根据0和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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll mod = 1000000007;
const double eps = 1e-8;
int T;
double a, b;
double sq(double x) {
double ans;
if (x == 0)return 0;
if (x < 0)ans = -1.0;
else ans = 1.0;
x = abs(x);
double L = 0, R = x;
while (R - L > eps) {
double mid = (L + R) / 2;
double tmp = mid * mid*mid;
if (tmp < x)L = mid;
else if (tmp > x)R = mid;
else return mid*ans;
}
return L * ans;
}
int main() {
cin >> T;
while (T--) {
scanf("%lf%lf", &a, &b);
double ans = 0;
while (1) {
double tmp = sq(a);
if (abs(tmp - b) + 1 - abs(a - b) < eps)ans += 1.0;
else break;
a = tmp;
}
ans += abs(a - b);
printf("%.9lf\n", ans);
}
return 0;
}
|
F. 碎碎念
题意：每次AC说1句话，RJ说x句话。问总共说了L到R句话，可能有几种情况。
很明显的前缀和。再对于总共说了n句话可以dp预处理。
dp[i][0/1] 表示说了 i 句话，且最后一句/x句，是AC/RJ时说的。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll mod = 1000000007;
const double eps = 1e-8;
int T;
int x;
ll dp[maxn][2];
ll sum[maxn];
int main() {
cin >> x;
dp[1][1] = 1ll;
dp[1][0] = 0ll;
dp[x][0] = 1;
for (int i = 2; i < maxn; i++) {
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
if (i > x)dp[i][0] = dp[max(i - x, 0)][1];
}
for (int i = 1; i < maxn; i++)sum[i] = (sum[i - 1] + dp[i][0] + dp[i][1]) % mod;
cin >> T;
while (T--) {
int L, R;
scanf("%d%d", &L, &R);
printf("%lld\n", (sum[R] - sum[L - 1] + mod) % mod);
}
return 0;
}
|
G. 街机争霸
题意：一张迷宫，有起点，终点，障碍，还有僵尸。每个僵尸只会上下或左右走k格，再折返，不断循环。
和普通迷宫一样，直接bfs，就是要处理一下僵尸。
由于僵尸很少，来回的距离也很短，所以可以把每个僵尸什么时间走到哪格先标上去，如果遇到僵尸，主角可以往回走，相当于距离增加 2*往回走的格子数。枚举格子数，第一次能过就直接过，大于k就没意义了，所以也很少。
由于是折返，所以周期是单项距离乘2，单个周期一个格子经过两次，都要标上。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll mod = 1000000007;
typedef pair<int, int> pii;
typedef pair<int, pii> ppii;
int n, m, p, k;
char mz[600][600], op[maxn];
int sx, sy, tx, ty;
vector<int>vc[600][600];
int d[600][600];
bool leg(int x, int y, int dis) {
if (x<1 || x>n || y<1 || y>m || mz[x][y] == '&')return false;
return true;
}
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };
int cal(int x, int y, int dis) {
int res = 0;
bool flg = 1;
for (; res <= k; res++) {
flg = 1;
for (int u : vc[x][y]) {
if (dis < u)continue;
if ((dis + 2 * res - u) % (2 * (k - 1)) == 0) {
flg = 0;
break;
}
}
if (flg)break;
}
if (!flg)return -1;
else return 2*res;
}
int bfs() {
priority_queue<ppii, vector<ppii>, greater<ppii> >que;
memset(d, 0x3f, sizeof(d));
d[sx][sy] = 0;
que.push(ppii(0, pii(sx, sy)));
while (!que.empty()) {
ppii tp = que.top(); que.pop();
int x = tp.second.first, y = tp.second.second, dis = tp.first;
if (x == tx && y == ty)return dis;
if (d[x][y] < dis)continue;
for (int i = 0; i < 4; i++) {
int nx = dx[i] + x, ny = dy[i] + y;
if (!leg(nx, ny, dis + 1))continue;
int tmp = cal(nx, ny, dis + 1);
if (tmp == -1)continue;
if (d[nx][ny] > dis + tmp + 1) {
d[nx][ny] = d[x][y] + tmp + 1;
que.push(ppii(d[nx][ny], pii(nx, ny)));
}
}
}
return -1;
}
int main() {
cin >> n >> m >> p >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf(" %c", &mz[i][j]);
if (mz[i][j] == 'L')sx = i, sy = j;
if (mz[i][j] == 'A')tx = i, ty = j;
}
}
for (int i = 0; i < p; i++) {
int x, y;
scanf("%d%d", &x, &y);
scanf("%s", op);
if (op[0] == 'U') {
for (int j = 0; j < k; j++) {
vc[x - j][y].push_back(j);
vc[x - j][y].push_back(2 * (k - 1) - j);
}
}
else if (op[0] == 'L') {
for (int j = 0; j < k; j++) {
vc[x][y - j].push_back(j);
vc[x][y - j].push_back(2 * (k - 1) - j);
}
}
else if (op[0] == 'D') {
for (int j = 0; j < k; j++) {
vc[x + j][y].push_back(j);
vc[x + j][y].push_back(2 * (k - 1) - j);
}
}
else {
for (int j = 0; j < k; j++) {
vc[x][y + j].push_back(j);
vc[x][y + j].push_back(2 * (k - 1) - j);
}
}
}
int ans = bfs();
if (ans == -1)puts("Oh no");
else cout << ans << endl;
return 0;
}
|
H. Hash
题意：给定一个6位字符串，和哈希函数，求出另一个与它哈希值相同的6位字符串，且字典序比原串大的第一个串。
这个函数就是26进制，mod下相同，还要比它大，就是加上一个mod，再转回字符串。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const double eps = 1e-8;
char s[maxn], t[maxn];
int mod;
int Hash(char str[])
{
int res = 0;
for (int i = 0; i < 6; i++)
{
res = (res * 26 + str[i] - 'a');
}
return res;
}
int main() {
while (cin >> s >> mod) {
int tmp = Hash(s);
if (tmp + mod >= 26 * 26 * 26 * 26 * 26 * 26)cout << -1 << endl;
else {
tmp += mod;
for (int i = 5; i >= 0; i--) {
t[i] = 'a' + tmp % 26;
tmp /= 26;
}
cout << t << endl;
}
}
return 0;
}
|
C. C语言IDE
题意：模拟IDE提取函数的功能，提取出给定程序里的所有函数。
不用说了，大模拟。
实在不想写，偷了个代码。。
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
const double eps=1e-6;
const ll mod=1e9+7;
char s[1000005];
char ans[1000005];
int main()
{
s[0]='\n';
int n=1;
while(scanf("%c",&s[n])!=EOF)n++;
int dan=0,shuang=0;
for(int i=0;i<n;i++)
{
if(s[i]=='\'')dan=1-dan,s[i]=0;
if(dan)s[i]=0;
}
for(int i=0;i<n;i++)
{
if(s[i]=='\"')shuang=1-shuang,s[i]=0;
if(shuang)s[i]=0;
}
int flag=0;
for(int i=0;i<n;i++)
{
if(s[i]=='/'&&s[i+1]=='*')flag=1;
if(flag&&s[i]=='*'&&s[i+1]=='/')
{
flag=0;
s[i]=s[i+1]=0;
}
if(flag)s[i]=0;
}
for(int i=0;i<n;i++)
{
if(s[i]=='/'&&s[i+1]=='/')
{
int pos=i;
while(s[pos]!='\n')
{
s[pos]=0;
pos++;
}
}
}
flag=0;
dan=0,shuang=0;
for(int i=0;i<n;i++)
{
if(s[i]=='\'')dan=1-dan;
if(s[i]=='\"')shuang=1-shuang;
if(dan==0&&shuang==0&&s[i]=='{')flag++;
if(dan==0&&shuang==0&&s[i]=='}'){s[i]=0;flag--;}
if(flag)s[i]=0;
}
s[n]='\n';
for(int i=0;i<n;i++)if(i==0||s[i]=='\n'||s[i]==0)
{
int l=i,r=i+1;
while(s[r]!='\n'&&s[r]!=0)r++;
int has=0;
dan=0,shuang=0;
for(int j=l;j<=r;j++)
{
if(s[j]=='\'')dan=1-dan;
if(s[j]=='\"')shuang=1-shuang;
if(dan==0&&shuang==0&&s[j]==')')
{
has=1;
int pos=j+1;
while(s[pos]!='\n')
{
if(s[pos]=='{'){has=1;break;}
if(s[pos]==';'){has=0;break;}
pos++;
}
}
}
if(!has)
{
for(int j=l;j<r;j++)s[j]=0;
}
i=r-1;
}
flag=0;
for(int i=0;i<n;i++)
{
if(s[i]=='#')flag=1;
if(s[i]=='>'){s[i]=0;flag=0;}
if(flag)s[i]=0;
}
for(int i=0;i<n;i++)
{
if(s[i]==','||s[i]==')')
{
int pos=i-1;
while(s[pos]==' ')pos--;
if(s[pos]=='d'&&s[pos-1]=='i'&&s[pos-2]=='o'&&s[pos-3]=='v'&&(s[pos-4]==','||s[pos-4]==' '||s[pos-4]=='('||s[pos-4]==0||s[pos]-4=='\n'))continue;
if(pos<0||s[pos]=='(')continue;
while(pos>=0&&s[pos]!=' ')
{
s[pos]=' ';
pos--;
}
}
}
for(int i=0;i<n;i++)if(s[i]=='\n')s[i]=0;
int tot=0;
int pos=0;
while(pos<n)
{
while(pos<n&&(s[pos]==' '||s[pos]==0||s[pos]=='\n'))pos++;
while(pos<n&&s[pos]!=0)
{
if(s[pos]!=' '&&pos!=0)ans[tot++]=s[pos];
else if(pos>0&&s[pos]==' '&&s[pos-1]!=' ')ans[tot++]=' ';
pos++;
}
ans[tot++]='\n';
}
for(int i=1;i<tot;i++)
{
if(ans[i]=='('||ans[i]==','||ans[i]==')')
{
int poss=i-1;
while(poss>=0&&ans[poss]==' ')
{
ans[poss]=0;
poss--;
}
poss=i+1;
while(poss<tot&&ans[poss]==' ')
{
ans[poss]=0;
poss++;
}
}
}
for(int i=0;i<tot;i++)if(ans[i]=='\n')ans[i]=0;
for(int i=0;i<tot;i++)
{
if(ans[i]!=0)putchar(ans[i]);
if(ans[i]==')')putchar('\n');
}
return 0;
}
|
