hihocoder24

Posted by Cww97 on 2017-08-28

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77625045
比赛https://hihocoder.com/contest/offers24/problems

应该能拿到个鼠标垫

舒服了

这个oj体验好差,每次都要先因为选错语言CE一发,而且刷新之后还是默认GCC

A ⼩Hi的钟表

算秒数,算角度,注意180以内,所以大于180之后拿360减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int h, m, s, t;

int main(){
//freopen("in.txt", "r", stdin);
int _;
scanf("%d", &_);
for (; _--;){
scanf("%d%d%d%d", &h, &m, &s, &t);
t += h * 3600 + m * 60 + s;
t %= 3600 * 12;
m = t % 3600;
double ans = fabs(1.0 * t / 120 - 1.0 * m / 10);
if (ans > 180) ans = 360 - ans;
//printf("t = %d\n", t);
//double ans = 1.0 * t / 120;
printf("%.4lf\n", ans);
}

return 0;
}

B 影院座位

没想到这题居然是最难的一题,卡了一万年

hint: 中位数,前缀和

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
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN];
int Getc[MAXN];
int Sum[MAXN];
int main(){
//freopen("in.txt", "r", stdin);
int N, M;
cin >> N >> M;
for(int i = 1; i <= N; i++) {
scanf("%d", Getc + i);
}
int cnt = 0;
for(int i = 1; i <= N; i++) {
if(Getc[i] == 0) {
a[cnt++] = i;
}
}
for(int i = 0; i < cnt; i++) {
a[cnt + i] = a[i] + N;
}
Sum[0] = a[0];
for(int i = 1; i < cnt * 2; i++) {
Sum[i] = Sum[i - 1] + a[i];
}
if(cnt < M) {
printf("-1\n");
return 0;
}
int ans = a[M / 2] * (M / 2) - Sum[M / 2 - 1] + Sum[M - 1] - Sum[M / 2] - (M - 1 - M / 2) * a[M / 2];
for(int i = 1; i < cnt; i++) {
ans = min(ans, a[(i + i + M) / 2] * (M / 2) - Sum[(i + i + M) / 2 - 1] + Sum[i - 1] + Sum[M + i - 1] - Sum[(i + i + M) / 2] - (M - 1 - M / 2) * a[(i + i + M) / 2]);
}
printf("%d\n", ans);
return 0;
}

C 同步H公司的终端

树形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
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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
LL a[N], ans;
int n;
bool NotRoot[N];
int FindRoot(){
for (int i = 1; i <= n; i++)
if (!NotRoot[i]) return i;
return -1;
}

struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):from(u), to(v), nxt(n){}
} edges[N * 2];
int E, head[N];
LL dist[N];
inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(){
E = -1;
for (int i = 0; i <= n; i++) head[i] = -1;
for (int i = 0; i <= n; i++) dist[i] = 0;
}

int dfs(int u, int pre){
//printf("dfs(%d, %d)\n", u, pre);
LL Max = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt){
Edge &e = edges[i];
dfs(e.to, u);
Max = max(Max, dist[e.to]);
}
dist[u] = Max + a[u];
for (int i = head[u]; i != -1; i = edges[i].nxt){
Edge &e = edges[i];
ans += Max - dist[e.to];
}
}

int main(){
//freopen("in.txt", "r", stdin);
int u, v;
for (; ~scanf("%d", &n);){
a[0] = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
Init();
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
AddEdge(u, v);
NotRoot[v] = 1;
}
int root = FindRoot();
ans = 0;
dfs(root, -1);
printf("%lld\n", ans);
}
return 0;
}

D 大富翁

本以为是个压轴题,以为要线段树什么各种数据结构来维护

然后一看过的人多的不正常,想,先拿30分再说,然后就莫名其妙过了

标算应该不是这么粗暴的,加强数据应该还是过不了

这里就是根据题意模拟

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
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN];
int N;
int Find(int x) {
if(x > N) return 0;
return 1 + Find(x + a[x]);
}
int main(){
cin >> N;
for(int i = 1; i <= N; i++) {
scanf("%d", a + i);
}
int Q;
cin >> Q;
while(Q--) {
int x;
scanf("%d", &x);
if(x == 1) {
int y;
scanf("%d", &y);
printf("%d\n", Find(y));
} else {
int u, v;
scanf("%d%d", &u, &v);
a[u] = v;
}
}
return 0;
}

hiho一下 第165周

分隔相同字符

复杂度1e52626

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
char st[N];
int Hash[222], n;

int getMax(char ch){
int ans = 0;
for (char i = 'a'; i <= 'z'; i++){
if (i == ch) ans = max(ans, Hash[i]-1);
else ans = max(ans, Hash[i]);
}
return ans;
}

char FindChar(char last){
n--;
for (char i = 'a'; i <= 'z'; i++){
if (!Hash[i]) continue;
if (i == last) continue;
int Max = getMax(i);
if (Max * 2 > n + 1) continue;
Hash[i]--;
return i;
}
return '0';
}

int main(){
//freopen("in.txt", "r", stdin);
scanf("%s", st);
int len = strlen(st);
n = len;
memset(Hash, 0, sizeof(Hash));
for (int i = 0; i < len; i++) Hash[st[i]]++;
int Max = getMax('0');
if (Max * 2 > len + 1) puts("INVALID");
else {
char last = ' ';
for (int i = 0; i < len; i++){
last = FindChar(last);
printf("%c", last);
}
puts("");
}
return 0;
}