Burnling's Blog
0%

220410总结

发表于 更新于

总体分析

  • 开题顺序：T1 - T3 - T2

  • T1和T3各花了半小时，T2花了两小时（还没做出来

  • T1最开始没考虑到先往左走再瞬移的情况，测样例的时候发现和结果差的太多，又重新想了想，发现了问题然后解决，再测发现两个样例都过了（觉得应该是正解）于是就开下一题了

  • T3最开始想用差分数组存英雄身高（大概是脑子短路了想用差分但没想在哪用差分），但是发现每次查询都是 $O(R)$ 的复杂度，在极端数据下应该是过不了的

    于是就用差分数组存修改的信息（其实一开始就应该想到的），修改的复杂度是$O(1)$，查询的复杂度是 $O(R-L)$，大概能过？

    测大样例发现 $N=10^6,Q=1000$ 的时候就超时了。。。甚至吸氧都过不去

    （大样例应该是格式不太对，我最后被迫用 char 型字符串读入的操作符，不然要么读到空格要么读到换行符

    但是因为我也不会更优的算法（简而言之：太菜了），所以就扔了个快读上去

    好家伙快读一上直接快了将近一秒（

    我单方面宣布快读是神！

    upd. 看了队友博客我甚至怀疑我们做的是不是一套题（

    upd. 在洛谷测了一下T1，发现调试时候的一个 printf 忘删了，，，

    upd. 在洛谷测了一下T3 发现不开O2会WA一个点TLE两个点，开了O2会TLE一个WA一个，，

    upd. 最终是 $0+20+100$

  • T2想了各种奇怪的思路但是都很容易举出反例（想了一个半小时），最后想碰碰运气（还没写完，先求最长上升子序列，再把不在这个序列里面的高度要么加要么减使它能放到序列里面

    T2能得多少分只能看数据了

  • 时间分配还行，T2做得稍微有点急躁了，要是心静一点可能能想出来更好的方法

  • 尽可能地一遍写对，debug太痛苦了

T1 catchcow

当动态规划做的

由于到达 $i(1\leq i \leq N)$ 的最短时间一定是 $N-i$ ，预处理出 $f(i)=N-i(1\leq i \leq N)$

然后对于点 $i(N\leq i \leq K)$ ，它可以由 $i-1$ 或 $i+1$ 或 $\dfrac{i}{2}(i=2n,n\in Z)$ 转移得到

然后T飞了。。。写的时候忘了可以瞬移 - 左移 - 瞬移这么走

所以对于这种最短步数之类的问题，应该优先考虑广搜

从一个点出发，第一次到达终点的步数一定是最少的

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;

struct S{
	int d,s;
};
int vis[2000005];

int N,K;

int main(){
	freopen("catchcow.in","r",stdin);
	freopen("catchcow.out","w",stdout);
	scanf("%d%d",&N,&K);
	queue<S>q;
	q.push((S){N,0});
	while(true){
		S t = q.front();
		q.pop();
		if(vis[t.d]) continue;
		vis[t.d] = 1;
		if(t.d == K){
			return 0 & printf("%d\n",t.s);
		}
		if(t.d-1 >= 0) q.push((S){t.d-1,t.s+1});
		if(t.d <= K){
			q.push((S){t.d+1,t.s+1});
			q.push((S){t.d*2,t.s+1});
		}
	}
	return 0;
}

T2 grading

考试没做出来，考完看了一些题解

是个线性dp

显然修改高度是修改为原数组中的高度是最优的

设 $f(i,j)$ 表示前 $i$ 个数，末尾改成第 $j$ 小的数的最小代价

可得状态转移方程 $f(i,j)=\min(f(i,j-1),f(i-1,j)+\operatorname{abs}(A_i-B_i))$

​ $A_i$ 指原数组， $B_i$ 指排序过的数组

这是改成单调不降所需的最小代价，单调不升同理

T3 magic

我的做法是用差分数组记录区间修改情况，查询的时候扫一遍 $[L,R]$ 整个区间

整体复杂度略高，不过堪堪通过评测（洛谷上的还过不去）

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
#include<bits/stdc++.h>
using namespace std;

int P[1000020];
int mA[1000020];

int N,Q;

inline int read() {//快读就是神！
    register int x=0,f=1;
    register char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

int main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	N = read();Q = read();
	for(int i = 1;i<=N;i++) P[i] = read();
	char S[2];
	while(Q--){
		char md;
		int l,r,d;
		scanf("%s",S);
		md = S[0];
		l = read();r = read();d = read();
		if(md == 'M'){
			mA[l]+=d;
			mA[r+1]-=d;
		}else{
			int ad = 0;
			int cnt = 0;
			for(int i = l;i<=r;i++){
				ad += mA[i];
				if(P[i] + ad >= d) cnt++;
			}
			printf("%d\n",cnt);
		}
	}
	return 0;
}