Luogu 7月月赛 解题报告

T1:
题意:给出一个序列,可以减少某个数的值,求使得相邻的两个数之和小于$x$的最小减少量
题解:由于是两个数比较,那么我们之间两两和$x$比较,比较简单,直接水一发,注意开long long

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<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
int n, x;
void clean() {}
void init() {
clean();
int a, b; long long ans = 0;
scanf("%d", &a);
for (int i=1;i<n;i++) {
scanf("%d", &b);
if (a + b > x) ans += a + b - x, b = max(0, b - (a + b - x));
a = b;
}
printf("%lld\n", ans);
}
void solve() {}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &x)==2) init(), solve();
return 0;
}

T2:
题意:在一个$h * w$矩阵中,可以上下左右移动,并且有一次可以瞬移到相对自己位置的$(D,R)$向量,费用都为1,求$(1,1)$到$(h,w)$的最小费用
题解:直接BFS,只不过要多开一个数组来判瞬移

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 1000 + 5;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
struct node {
int x, y, step, cd;
};
int h, w, d, r, vi[MAXN][MAXN][2];
char s[MAXN][MAXN];
void clean() {
ms(vi, 0);
}
void init() {
clean();
for (int i=1;i<=h;i++) scanf("%s", s[i]+1);
}
void solve() {
queue<node> q;
vi[1][1][0] = 1, q.push((node){1,1,0,false});
while (!q.empty()) {
node p = q.front(); q.pop();
if (p.x==h&&p.y==w) {
printf("%d\n", p.step);
return ;
}
for (int i=0;i<4;i++) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx>0&&ty>0&&tx<=h&&ty<=w&&!vi[tx][ty][p.cd]&&s[tx][ty]!='#') {
vi[tx][ty][p.cd] = 1;
q.push((node){tx,ty,p.step+1,p.cd});
}
}
if (p.x+d>0&&p.x+d<=h&&p.y+r>0&&p.y+r<=w&&!vi[p.x+d][p.y+r][1]&&s[p.x+d][p.y+r]!='#'&&!p.cd) {
vi[p.x+d][p.y+r][1] = 1;
q.push((node){p.x+d,p.y+r,p.step+1,true});
}
}
printf("-1\n");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d%d%d", &h, &w, &d, &r)==4) init(), solve();
return 0;
}

T3:
题意:在一个$[0,L]$的区间上有$n$个点,每个点的距离$x[i]$,每个点$i$上有一个权值$r[i]$,在$[0,L]$中找一个点$a$,使得$\sum_{i=1}^{n}|x[i] - a| * b[i]$最小。
题解:可以发现$a$在这些点上的中位数答案最优,那直接找这些点的中位数,然后统计一下答案。
这里提供了中位数做法、暴力、数据生成器
中位数:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5;
struct data {
LL x, r;
bool operator < (const data &b) const {
return x < b.x;
}
}a[MAXN];
LL l, tr = 0;
int n;
LL abss(LL x) {return x>=0 ? x : -x;}
void clean() {}
void init() {
clean();
for (int i=1;i<=n;i++) {
scanf("%lld%lld", &a[i].x, &a[i].r);
tr += a[i].r;
}
}
void solve() {
sort(a+1, a+1+n);
LL ans = 0, zws, zws1, zws2, gl, tot = 0;
if (tr%2) gl = (tr+1)/2; else gl = tr/2;
for (int i=1;i<=n;i++) {
tot += a[i].r;
if (tot>=gl) {
zws1 = a[i].x;
if (tr%2==0) {
if (tot==gl) zws2 = a[i+1].x; else zws2 = a[i].x;
} else zws2 = zws1;
break;
}
}
zws = (zws1+zws2)/2;
for (int i=1;i<=n;i++) {
ans += abss(a[i].x-zws)*a[i].r;
}
printf("%lld\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%lld%d", &l, &n)==2) init(), solve();
return 0;
}

暴力:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5, INF = 1000000000;
int n, l, x[MAXN], r[MAXN];
int abss(int x) {return x>=0 ? x : -x;}
void clean() {}
void init() {
clean();
for (int i=1;i<=n;i++) {
scanf("%d%d", &x[i], &r[i]);
}
}
void solve() {
int ans = INF;
for (int i=0;i<=l;i++) {
int tem = 0;
for (int j=1;j<=n;j++) {
tem += abss(x[j]-i)*r[j];
}
ans = min(ans ,tem);
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("2.out", "w", stdout);
#endif
while (scanf("%lld%d", &l, &n)==2) init(), solve();
return 0;
}

数据生成器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<algorithm>
#include<windows.h>
#include<winbase.h>
#include<set>
using namespace std;
int n = 10, L = 1000, r = 50;
int main() {
freopen("1.in", "w", stdout);
srand(GetTickCount());
printf("%d %d\n", L, n);
for (int i=1;i<=n;i++) {
printf("%d %d\n", rand()%(L+1), rand()%r+1);
}
return 0;
}

T4:
坑,待补充

------ 本文结束 ------