2019.8.18 集训解题报告

又一次考试前一个小时开始写解题报告…. qwq


考试

能量获取

感觉是树形 $dp$ ,但是不会做。我的构思是:$f[i][j]$ 表示第 $i$ 个节点以下(包括自己)满足 $j$ 个节点需要的能量最小值。转移的时候注意每个边的能量限制,超了就不能转移,然后还要求最小值。

但是我不会打…..虽然似乎数据给的很松,$O(n^2)$ 都可以过….. QAQ


考试之后…..

第一题怎么又是贪心?!我看来我贪心真是菜到一种境界了。。。。。直接引用 $JZOJ$ 题解上的话:

贪心,每次选取能量需求最小的节点,扫描它到根节点的路径上的边的容量,看能否满足,如果能满足就把它到根节点的路径上的边的容量都减去它的需求即可。

本题如果把握不好贪心的正确性也可以写树状动规(多叉树,背包转移),但是显然编程复杂度就上升了一个层次。

emmmmmmm,自闭

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

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

struct Node {
int num, e;
};
Node a[MAXN];

int n, ans, fa[MAXN], w[MAXN];

bool cmp (Node a, Node b) {
return a.e < b.e;
}

int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d%d%d", &fa[i], &a[i].e, &w[i]);
a[i].num = i;
}

sort (a + 1, a + n + 1, cmp);

for (int i = 1; i <= n; i++) {
int j = a[i].num;
while (j != 0) {
if (w[j] - a[i].e < 0) break;
w[j] -= a[i].e;
j = fa[j];
}

if (j == 0) {
ans ++;
}
else {
int k = a[i].num;
while (k != j) {
w[k] += a[i].e;
k = fa[k];
}
}
}

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

封印一击

这题好像比较水,但是我的算法是 $O(n^2)$ 的,这题因为我怂,所以我数据分流来打,数据小就用暴力的 $O(nm)$ 来写,不然就用 $O(n^2)$ 来写。不过正解应该是 $O(n \log n)$ 。

很容易发现,最后的最优解一定在一个元素爆炸的临界值 $b$ ,否则一定可以让答案更优。所以,把每个元素按照 $b$ 排一个序(口胡了,不需要排序)(又口胡了,要排序),然后依次更新答案就可以了。

写到这里的时候,我发现了两个小优化,一个是卡常,计算时间,然后到 $990ms$ 的时候输出当前最优答案,然后看人品水一些分。还有一个就是使用前缀和优化,我现在发现,其实排序是有用的,排序之后枚举每一个数时,前面那些比当前 $b$ 小的就不用计和了,因为不会产生贡献。(这又口胡了,不存在这种东西 qwq)

$Test’s$ $Code$:50%

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

using namespace std;
const int MAXN = 1e5 + 5;
const int MANM = 1e9 + 5;

struct Node {
int a, b;
};
Node a[MAXN];

int n, ans, sum, Max;

bool cmp (Node x, Node y) {
return x.b < y.b;
}

inline void solve50 () {
int temp = 0;
for (int i = 1; i <= Max; i++) {
temp = 0;
for (int j = 1; j <= n; j++) {
if (i < a[j].a) {
temp += a[j].a;
}
if (a[j].a <= i && i <= a[j].b) {
temp += i;
}
}
if (sum < temp) {
sum = temp;
ans = i;
}
}
return;
}

inline void solve100 () {
sort (a + 1, a + n + 1, cmp);

int temp = 0;
int flag = 0;
for (int i = 1; i <= n; i++) {
temp = 0;
int t = a[i].b;
for (int j = i; j <= n; j++) {
if (t < a[j].a) {
temp += a[j].a;
}
if (a[j].a <= t && t <= a[j].b) {
temp += t;
}
if (a[j].b == t) {
flag = j;
}
}
if (t > sum) {
ans = t;
sum = temp;
}
i = flag;
}
return;
}

int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d%d", &a[i].a, &a[i].b);
Max = max (Max, a[i].b);
}

if (Max * n <= 1e7) {
cout <<"solve50()"<<endl;
solve50 ();
}
else solve100();

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

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

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

struct Node {
long long a, b;
};
Node a[MAXN];

struct Data {
long long p;
bool flag;
};
Data data[MAXN << 1];

long long n, point, ans;

bool cmp (Data a, Data b) {
return a.p < b.p;
}

int main() {
scanf ("%lld", &n);

long long sum = 0;
for (int i = 1; i <= n; i++) {
scanf ("%lld%lld", &a[i].a, &a[i].b);
data[i].p = a[i].a;
data[i].flag = true;
data[n + i].p = a[i].b;
data[n + i].flag = false;
sum += a[i].a;
}

sort (data + 1, data + 2 * n + 1, cmp);

int cnt = 0;
for (int i = 1; i <= 2 * n; i++) {
if (data[i].flag) {
cnt ++;
sum -= data[i].p;

if (ans < sum + cnt * data[i].p) {
ans = sum + cnt * data[i].p;
point = data[i].p;
}

}
else {
if (ans < sum + cnt * data[i].p) {
ans = sum + cnt * data[i].p;
point = data[i].p;
}
cnt --;
}
}

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

不开 long long 见祖宗 qwq

归途与征程

这什么鬼啊。。。。

感觉应该是用 $O(n \log n)$ 的做法吧。。。。这题我连暴力都不想打 qwq

样例都是输出 $B$ 的长度,那我也输出这个吧,如果数据像昨天第 1 题很水的话,还能拿几分。


考试后,我这样输出没有分,但是输出 0 竟然有 20 分?!

正解:$dp + hash$

先放一个官方题解:

$Solution’s$ $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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
unsigned long long c[110],p[110],g[110],temp;
char a[110],b[200010];
int f[200010][52],d[110],n,m,t,i,j,k,l,ans;
int main()
{
freopen("journey.in","r",stdin);
freopen("journey.out","w",stdout);
scanf("%s",a+1);
n=strlen(a+1);
for(p[0]=i=1;i<=n;i++) p[i]=p[i-1]*13331;
for(i=1;i<=n;i++)
if(a[i]=='*')
if(i>1&&a[i-1]!='*') c[++t]=temp,d[t]=j,temp=j=0; else;
else temp+=(a[i]-'a'+1)*p[j++];
if(a[n]!='*') c[++t]=temp,d[t]=j,temp=j=0;
scanf("%s",b+1);
m=strlen(b+1);
if(!t) {cout<<m<<endl; return 0;}
for(i=1;i<=m;i++) b[m+i]=b[i];
for(j=1;j<=t;j++) f[m*2+1][j]=f[m*2+2][j]=m*2+1;
for(i=m*2;i;i--)
{
memset(g,-1,sizeof(g));
g[0]=0;
for(j=0;j<n;j++)
if(i+j<=2*m) g[j+1]=g[j]+(b[i+j]-'a'+1)*p[j];
for(j=1;j<=t;j++)
{
f[i][j]=f[i+1][j];
if(g[d[j]]==c[j]) f[i][j]=i+d[j]-1;
}
}
for(i=1;i<=m;i++)
{
bool flag=true;
for(j=n;j&&a[j]!='*';j--)
if(a[j]!=b[i+m-1-(n-j)]) {flag=false; break;}
if(!flag||j==0&&n!=m) continue;
for(k=1,l=i;k<=t-(a[n]!='*');k++)
{
if(k==1&&a[1]!='*'&&f[i][k]+1!=i+d[1]) break;
l=f[l][k]+1;
}
if(k>t-(a[n]!='*')&&l<=i+m-(n-j)) ans++;
}
cout<<ans<<endl;
return 0;
}
Your browser is out-of-date!

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

×