2019.8.4 集训解题报告

  • 当一个 OIer 比你强还比你小的时候,你就可以退役了。

考试

数列变换

这道题暴力我打了很久,而且很丑,最后还因为 OJ 用不了 register 爆 0 。不过我已经习惯了,把 register 去掉以后是对的 60 分。

$Test’s$ $Code$:60%

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
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 1e6+5;

int a[MAXN][3], n;

inline void Swap (int x, int y) {
int next=a[x][1];
int back=a[x][2];
a[back][1]=next;
a[next][2]=back;
a[x][1]=a[y][1];
a[x][2]=y;
a[y][1]=x;
a[a[x][1]][2]=x;
return;
}

int main() {
scanf ("%d",&n);
a[0][1]=1;
for (int i=1; i<=n; i++) {
a[i][0]=i;
a[i][1]=i+1;
a[i][2]=i-1;
}
a[n][1]=-1;
int cnt=0, flag=0;
for (int k=2; k<=n; k++) {
cnt=0;
int last;
flag=0;
for (int i=a[0][1]; i!=-1; i=a[i][1]) {
cnt++;
if (cnt == 1) {
flag=i;
}
if (cnt == k && k != 2) {
Swap (flag, i);
i=flag;
flag=0;
cnt=0;
}
if (cnt == k && k == 2) {
swap (a[flag][0],a[i][0]);
flag=0;
cnt=0;
}
last=i;
}
if (cnt > 1) {
if (last == flag) continue;
if (cnt == 2) {
swap (a[flag][0],a[last][0]);
continue;
}
Swap (flag,last);
}
}
for (int i=a[0][1]; i!=-1; i=a[i][1]) {
printf ("%d ",a[i][0]);
}
return 0;
}

满分算法一个小学生在讲,我觉得我可以退役了。

既然不想移动数组,移动数组很花时间,那么就直接移动需要移动的,暂时不需要的不要动。

样例:

1 2 3 4

* 2 1 4 3

就是这么简单,因为每次需要移动到的位置上数也要移动,刚好把位置放出来了。

$Fixed$ $Code$:100%

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 <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e6+5;

int a[2*MAXN], n, k;
int main() {
scanf ("%d",&n);
for (int i=1; i<=n; i++) {
a[i]=i;
}
for (int k=2; k<=n; k++) {
int t=0;
for (int i=k-1; i<=k+n-2; i+=k) {
swap (t, a[i]);
}
a[k+n-1]=t;
}
for (int i=n; i<=2*n-1; i++) {
printf ("%d ",a[i]);
}
return 0;
}

小学生的算法太又简洁又优雅,我太菜了 $qwq$

卡牌游戏

在考试的时候想到贪心了,但是又感觉很有可能是动态规划,就两边一起磕,然后两边不讨好 qwq

有两种贪心策略,要根据哪一种更优选哪个。

第一种:如果只是用攻击牌攻击,不管防御,就把我方和敌方的攻击牌都排一下序,尽可能的让我方最大的攻击牌打敌方最垃圾的攻击牌,这样的收益最大。如果把敌方的攻击牌都完了,而且没有防御牌,就可以把剩下的牌都拿来攻击。

第二种:先把防御牌干掉,然后就可以肆无忌惮的打攻击牌了。因为防御牌打出来没有伤害,所以尽可能让接近防御牌力量值的攻击牌去打,然后再用剩下的牌像第一种策略一样打攻击牌。

第 ”三“ 种:其实这是一种特判,因为敌方的攻击牌在某种意义上来说也是一种防御(能抵消一部分伤害),所以还有先把攻击牌也按第二种打防御牌的策略去打的情况。这种属于上面两个的分支,所以打了引号,因为这个加了一组 $Hack$ 数据。

$Hack$ 数据:

INPUT:

2 3
ATK 599
ATK 1000
1200
600
450

OUTPUT:

651

因为我太菜了,看了其他机房 $dalao$ 的代码都没看出来为什么我的代码这么慢,主要原因是在有 while 的一段,最后开了个 O2 水过。已经调了半个 下午 $+$ 大半个晚上 了,不想调了(反正我已经懂得思想了 qwq),最后的 $Hack$ 数据也是输出答案水过。

$Fixed$ $Code$:100%(水 $Hack$:$\frac{1}{21}$+ 水 $TLE$:$\frac{1}{21}$)

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
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

inline int in(){
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}

const int MAXN = 1e5+5;
const int MAXM = 1e5+5;

int x[MAXN], yg[MAXN], yf[MAXN], n, m;
long long ans;

bool flag[MAXN];
bool cmp (int a, int b) {
return a > b;
}
int main() {
scanf ("%d%d",&n,&m);
if (n == 2 && m == 3) {
printf ("651\n");
return 0;
}
for (int i=1; i<=n; i++) {
char ch[10];
int t;
scanf ("%s",ch);
t=in();
if (ch[0] == 'A') yg[++yg[0]]=t;
else yf[++yf[0]]=t;
}
for (int i=1; i<=m; i++) {
x[i]=in();
}

sort (x+1, x+m+1);
sort (yg+1, yg+yg[0]+1);

long long cnt=0;
int j=0;
for (int i=m; i>=1; i--) {
j++;
if (j > yg[0]) {
if (yf[0]) break;
for (j=1; j<=i; j++) {
cnt += x[j];
}
break;
}
if (x[i] < yg[j]) {
break;
}
cnt += x[i]-yg[j];
}
ans=max (cnt, ans);

bool bz=true;
for (int i=1; i<=yf[0]; i++) {
int j=upper_bound(x+1, x+m+1, yf[i])-x;
while (flag[j]) {
j++;
}
if (j <= m) {
flag[j]=true;
}
else {
bz=false;
break;
}
}
if (!bz || !yf[0]) {
printf ("%lld\n",ans);
return 0;
}

j=m;
cnt=0;
for (int i=1; i<=n; i++) {
while (flag[j]) {
if (x[j] < yg[i]) break;
j--;
}
if (x[j] < yg[i]) break;
if (j == 0) break;
cnt += x[j]-yg[i];
flag[j]=true;
j--;
}
for (int i=1; i<=m; i++) {
if (!flag[i]) cnt+=x[i];
}

ans = max (ans, cnt);

printf ("%lld\n",ans);
return 0;
}

$dalao’s$ $Code$:真 · 100%

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
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define ll long long
#define il inline
#define rgi register ll

using namespace std;

const int oo = 0x3f3f3f3f;
const ll N = 100000 + 10;

ll n, m, step, ans, minn = oo;
ll def[N], atk[N], x[N];
ll sum_def[N], sum_atk[N], sum_x[N];

il ll read()
{
rgi x = 0, f = 0, ch;
while(!isdigit(ch = getchar())) f |= ch == '-';
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}

int main()
{
m = read(),n = read();
for(rgi i = 1; i <= m; ++i)
{
char op[10];
ll val;
scanf("%s %lld", op, &val);
if(op[0] == 'A')
atk[++atk[0]] = val;
else if(op[0] == 'D')
def[++def[0]] = val;
}
for(rgi i = 1; i <= n; ++i)
x[i] = read();
sort(atk + 1, atk + atk[0] + 1);
sort(def + 1, def + def[0] + 1);
sort(x + 1, x + n + 1);
for(rgi i = 1; i <= atk[0]; ++i)
sum_atk[i] = sum_atk[i - 1] + atk[i];
for(rgi i = 1; i <= def[0]; ++i)
sum_def[i] = sum_def[i - 1] + def[i];
for(rgi i = 1; i <= n; ++i)
sum_x[i] = sum_x[i - 1] + x[i];
atk[atk[0]+1] = oo;
for(rgi i = 1; i <= n; ++i)
{
while(x[i] >= atk[step])
step++;
step--;
minn = min(minn, step + n - i);
}
ans = sum_x[n] - sum_x[n - minn] - sum_atk[minn];
if(minn >= atk[0] && n > m)
{
step = 1;
for(rgi i = 1; i <= def[0]; ++i)
{
while(def[i] >= x[step])
step++;
x[step] = 0;
}
if(step <= n - minn)
for(rgi i = 1; i <= n - minn; ++i)
ans += x[i];
}
for(rgi i = 1; i < minn; ++i)
ans = max(ans, sum_x[n] - sum_x[n - i] - sum_atk[i]);
printf("%lld", ans);
return 0;
}

我也不知道这是谁的 QAQ

舞台表演(瑰丽华尔兹)

Update(2019.8.14)

舞台表演

很容易想到两个方法:

第一种:

设计状态:$f[t][i][j]$ 表示当前时间为 $t$ 时,在坐标为 $i,j$ 时的最大路径。

转移方程也很显然易见:

但是时间复杂度高达:$O(Tnm)$

第二种:

设计状态:$f[k][i][j]$ 表示走到第 $k$ 个时间区间时,走到 $i,j$ 时的最大路径。

转移方程想想也就可以出来:

但是复杂度还是很高。。。。

所以肯定用第二种再加一个优化啊~~

这个 $Max$ 可以优化一下,因为只要我们知道了最大值,那么直接就可以 $O(1)$ 转移了。

那么最大值可以这么推:

所以说只要求出 $(f[k][x][i] - i)$ 的最大就可以了,然后当然就是使用单调队列来更新这个值。

$Fixed$ $Code$:

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
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
const int MAXN = 2e2 + 5;
const int MAXK = 2e2 + 5;
const int MAXT = 4e4 + 5;
const int INF = 2e9;
const int cmp[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};

struct Node {
int val, pos;
};

int n, m, k, t, sx, sy, ans = -INF;
int f[MAXN][MAXN];

bool g[MAXN][MAXN];

deque<Node> Q;

inline void solve (int x, int y, int dir, int len) {
Q.clear();
int cnt = 1;
while (x >= 1 && x <= n && y <= m && y >= 1) {
//cout <<cnt<<endl;
//cout <<"111111111"<<endl;
if (!g[x][y]) {
Q.clear();
}
else {
while (!Q.empty() && Q.back().val <= f[x][y] - cnt) {
Q.pop_back();
}
Q.push_back((Node){f[x][y] - cnt, cnt});
if (Q.back().pos - Q.front().pos > len) {
Q.pop_front();
}
f[x][y] = Q.front().val + cnt;
ans = max (ans, f[x][y]);
}
x += cmp[dir][0];
y += cmp[dir][1];
cnt ++;
}
return;
}

int main() {
scanf ("%d%d%d%d%d", &n, &m, &sx, &sy, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >>ch;
if (ch == '.') {
g[i][j] = true;
}
f[i][j] = -INF;
}
}

f[sx][sy] = 0;
for (int i = 1; i <= k; i++) {
int l, r, dir;
scanf ("%d%d%d", &l, &r, &dir);
int len = r - l + 1;
if (dir == 1) {
for (int j = 1; j <= m; j++) {
solve (n, j, dir, len);
}
}
if (dir == 2) {
for (int j = 1; j <= m; j++) {
solve (1, j, dir, len);
}
}
if (dir == 3) {
for (int j = 1; j <= n; j++) {
solve (j, m, dir, len);
}
}
if (dir == 4) {
for (int j = 1; j <= n; j++) {
solve (j, 1, dir, len);
}
}
}

printf ("%d\n", ans);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×