标签: 补题 - CheaSim Blog

[nowcoder2] 补题向

A.run

题意

白云可以跑$k$米或者走$1$米,但不能连续跑,问到达终点有多少种方案。

题解

1步2步上楼梯的加强版。典型的dp题。

  • $dp[i][0/1]$表示第$i$米最终是走还是跑的方案数

转移方程

  • $dp[i][0] = dp[i-1][1]+dp[i-1][0]$
  • $dp[i][1] = dp[i-1][0]$

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
ll dp[maxn][2];
ll pre[maxn];
int q;
ll k;
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
scanf("%d%lld",&q,&k);
dp[0][0] = 1;
rep(i,1,maxn){
if(i>=k){
dp[i][1] = dp[i-k][0] % mod;
}
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % mod;
pre[i] = pre[i-1] + (dp[i][0] + dp[i][1]) % mod;
pre[i] %= mod;
}
rep(i,0,q){
int l,r;scanf("%d%d",&l,&r);
printf("%lld\n",(pre[r]-pre[l-1]+mod)%mod);
}
return 0;
}

D.Money

题意

白云可以在一个商店里卖或者买商品,但白云只能带一个商品。问最多能赚多少钱在最少的交易下。

题解

dp

$dp[i][0]$表示在$i$最后一次交易是买入的最优值,$dp[i][1]$表示在$i$最后一次交易是卖出的最优值。转移方程。

  • 在$[1,i-1]$中卖出的最优值后在$i$买入或者不买入中取最好值。$dp[i][0]=max(dp[i-1][0],dp[i-1][1]-a[i])$
  • 在$[1,i-1]$买入的最优值后在$i$卖出或者不卖中取最大值。$dp[i][1] = max(dp[i-1][1],dp[i-1][1]+a[i])$

只有由于要求最小交易次数,用pair<ll,int>来表示,第一个是金钱,第二个是交易次数,求最小次数,所以用min,并且把金钱变成负值,就可以相当于反向取最大了。

AC代码copydls的

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
ll a[maxn];
int T,n;
pair<ll,int> dp[maxn][2];
ll inf = 1ll<<60;
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(i,1,n+1) scanf("%lld",a+i);
dp[0][0] = make_pair(0,0);
dp[0][1] = make_pair(inf,0);
rep(i,1,n+1){
dp[i][0] = min(dp[i-1][0],make_pair(dp[i-1][1].fi-a[i],dp[i-1][1].se+1));
dp[i][1] = min(dp[i-1][1],make_pair(dp[i-1][0].fi+a[i],dp[i-1][0].se+1));
}
printf("%lld %d\n",-dp[n][0].fi,dp[n][0].se);
}
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
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
vector<ll> a;
ll inf = 1ll<<50;
int n;
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
int T;
scanf("%d",&T);
while(T--){
a.clear();
scanf("%d",&n);
a.push_back(inf);
rep(i,1,n+1){
ll x; scanf("%lld",&x);
a.push_back(x);
}
a.push_back(-1);
a.erase(unique(a.begin(),a.end()),a.end());
int len = a.size();
int down = -1;int cnt = 0;ll ans = 0;
rep(i,1,len-1){
if(a[i] <a[i-1] && a[i]<a[i+1]){
down = i;
}
if(a[i]>a[i+1]&&a[i]>a[i-1]){
cnt+=2;
ans += a[i]-a[down];
}
}
printf("%lld %d\n",ans,cnt);
}
return 0;
}

G transform

题意

白云要把一个数轴上的箱子中的产品搬到一个箱子点上,每个箱子都有一个价值,每次搬一个产品从箱子$a$到$b$上都要花费$2*abs(x[a]-x[b])$的力气,问在$T$总力气下,可以获得多少价值。

题解

二分+前缀数组

首先我们可以确定放箱子肯定是选择一定的区间内,因为每搬一个产品,肯定是越近消耗得越好,区间中只有左端点和右端点可能没搬完。

区间中,把所有产品集中到产品中位数,即改点左边的产品和右边的产品数量接近一致。便体力消耗最小。

难点

对于前缀数组的处理,我们用$suma$表示前缀产品和,$sumt$表示前缀对于假设运送产品到0点的和。$sumt[r]-sumt[l-1]$表示$[l,r]$移动到0点所需要的力气。

  • 那么如果我们将产品$[l,r]$运送到点$l$的消耗相当于把$[l,r]$中的元素都先运送到$l$中之后再把$l$中的元素送到0,进行减一哈,就是答案。$ans = sumt[r]-sumt[l-1]-(suma[r]-suma[l-1])*x[l]$
  • 将产品$[l,r]$运送到$r$点,相当于我们先把$[l,r]$转移到$r$上面之后再统一移动到0点。$ans+sumt[r]-sumr[l-1]=(suma[r]-suma[l-1])*x[r]$。

之后枚举每个$l$的每个$r$和每个$r$的每个$l$,枚举的时候固定$l$或者$r$是消耗完全的。

二分又一个小套路。

1
2
3
4
5
6
7
8
9
10
11
int l,r,mid,ans;
l = 1,r = maxn;
while(l<=r){
mid = (l+r)>>1;
if(check()){
ans = mid;l=mid+1; //避免了重复枚举Mid嘞。
}else{
r = mid-1;
}
}
printf("%d\n",ans);

AC代码

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<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e5 + 10;
ll n,T;
ll x[maxn],a[maxn],suma[maxn],sumt[maxn];
ll getl(ll l,ll r){
return (sumt[r]-sumt[l-1]) - (suma[r]-suma[l-1])*x[l];
}
ll getr(ll l,ll r){
return (suma[r]-suma[l-1])*x[r] - (sumt[r]-sumt[l-1]);
}
bool check(ll ans){
ll l,r,mid,mida;
mida = ans/2+1;
l = r = mid = 1;
while(1){
while(r<=n && suma[r]-suma[l-1]<ans) r++;
while(mid<r && suma[mid]-suma[l-1]<mida) mid++;
if(r>n || mid>r) break;
ll temp = suma[r]-suma[l-1]-ans;
if(getr(l,mid)+getl(mid,r)-temp*(x[r]-x[mid]) <= T) return true;
l++;
}
l = r = mid = n;
while(1){
while(l>=1 && suma[r]-suma[l-1]<ans) l--;
while(mid>l && suma[r]-suma[mid-1]<mida) mid--;
if(l<1 || mid<l) break;
ll temp = suma[r] - suma[l-1] - ans;
if(getr(l,mid)+getl(mid,r)-temp*(x[mid]-x[l])<=T) return true;
r--;
}
return false;
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%lld%lld",&n,&T); T>>=1;
rep(i,1,n+1) scanf("%lld",x+i);
rep(i,1,n+1){
scanf("%lld",a+i);
suma[i] = suma[i-1] + a[i];
sumt[i] = sumt[i-1]+a[i]*x[i];
}
ll l,r,mid,ans;
l = 1;r = suma[n];
while(l<=r){
mid = (l+r)>>1;
if(check(mid)){
ans = mid;l = mid+1;
}else {
r = mid-1;
}
}
printf("%lld\n",ans);
return 0;
}

https://www.nowcoder.com/discuss/88268?type=101&order=1&pos=4&page=1

https://www.cnblogs.com/Flower-Z/p/9528057.html

H.travel

题意

给定一棵树,树上每个点有一个$val$,从树上走三次,不能走重复的点,问能获得的最大价值是多少。

题解

树形dp

$f[i][j]$表示以$i$为根的子树选了$j$条路径的最大权值和。(也是包含$i$点)

$g[i][j]$表示以$i$为根的子树选了$j$条路径加上一条包含$i$到根节点链的最大权值。

根据题意可以知道,如果我们$i$是竖直链,那么加入一个没有竖直链的。

  • $g[u][i] = max(g[u][i],f[v][x]+g[u][i-x])$
  • $g[u][i] = max(g[u][i],g[v][x]+f[v][i-x])$

如果$i$不是竖直链

  • $f[u][i]=max(f[u][i],f[v][x]+f[u][i-x])$

对不起,我编不下去了。就是瞎几把转移转移。能转移的状态就都转移了就行了。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e5 + 10;
struct node{
int to,next;
}G[maxn<<1];
int head[maxn];
ll f[maxn][4],g[maxn][4];
int n,cnt;
ll val[maxn];
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int u,int fa){
ll best[4][3] = {0}; ll temp[4][3] = {0}; ll last[4][3] = {0};
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==fa) continue;
dfs(v,u);
memset(temp,0,sizeof(temp));
memset(best,0,sizeof(best));
rep(x,0,4){
temp[x][0] = f[v][x];
temp[x][1] = g[v][x];
}
rep(x,0,4) rep(y,0,4-x) rep(p,0,3) rep(q,0,3-p)
best[x+y][q+p] = max(best[x+y][p+q],last[x][p]+temp[y][q]);
memcpy(last,best,sizeof(best));
}
rep(x,0,4) f[u][x] = max(f[u][x],best[x][0]);
rep(x,1,4) rep(y,0,3) f[u][x] = max(f[u][x],val[u]+best[x-1][y]);
rep(x,0,4) rep(y,0,2) g[u][x] = max(g[u][x],val[u]+best[x][y]);
}
int main(){
#ifdef LOCAL
freopen("h.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d",&n);
rep(i,1,n+1) scanf("%lld",val+i);
rep(i,0,n-1){
int u,v;scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,-1);
printf("%lld\n",f[1][3]);
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//dls队伍代码,感觉比标程的容易懂一点。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N=410000;
vector<int> go[N<<1];
int n,w[N];
long long dp[N][4][2];
void treedp(int k1,int k2){
long long f[4][3];
long long pre[4][3];
memset(f,0x00,sizeof f);
for (int i=0;i<go[k1].size();i++){
int j=go[k1][i];
if (j!=k2){
treedp(j,k1);
memcpy(pre,f,sizeof f);
for (int a=0;a<4;a++)
for (int b=0;b<4;b++)
for (int c=0;c<3;c++)
for (int d=0;d<2;d++){
if (a+b>3||c+d>2) continue;
f[a+b][c+d]=max(f[a+b][c+d],pre[a][c]+dp[j][b][d]);
}
}
}
for (int i=0;i<4;i++){
dp[k1][i][0]=max(dp[k1][i][0],f[i][0]);
dp[k1][i][1]=max(dp[k1][i][1],f[i][1]+w[k1]);
if (i<3){
for (int a=0;a<2;a++)
for (int b=a+1;b<3;b++)
dp[k1][i+1][a]=max(dp[k1][i+1][a],f[i][b]+w[k1]);
}
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
for (int i=1;i<n;i++){
int k1,k2; scanf("%d%d",&k1,&k2);
go[k1].push_back(k2);
go[k2].push_back(k1);
}
treedp(1,0);
long long ans=0;
for (int i=0;i<=3;i++) ans=max(ans,dp[1][i][0]);
printf("%lld\n",ans);
}

I.Car

题意

给定一个长度为$n$的正方形,在上面放车。车有如下性质

  • 速度一样
  • 不能改变方向
  • 起点都在矩阵的边缘

题解

3

奇数点特判一下,免得减了两次。题解也是经验所得,莫得证明。

AC代码

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;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 1e5 + 10;
int col[maxn],row[maxn];
int main(){
#ifdef LOCAL
freopen("i.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
int ans = 2*n;
if(n%2) ans--;
rep(i,0,m){
int x,y;scanf("%d%d",&x,&y);
row[x] = 1;col[y]=1;
}
rep(i,1,n+1){
if(row[i]) ans--;
if(col[i]) ans--;
}
if(n%2 && row[(n+1)/2]==1 && col[(n+1)/2]) ans++;
printf("%d\n",ans);
return 0;
}

J.Farm

题意

有一块$nm$的田,里面每一个土地都种$a[i][j]$的植物,每一种植物都有专属化肥,如果用错化肥就挂了。问在进行$T$次区间浇化肥后,挂了过多少个植物。

题解

我一开始想的是能不能统计一下前缀和,如果加入的肥料和是植物种类的倍数就是对的。但是需要随机算法,避免出题人卡。毕竟是假算法。还是乖乖按照标答思路来。。


将化肥按照二进制分为肯定对植物不好和可能对植物好。如

$a$植物代号是101010,那么检查每一位的时候,101011肯定对它不好,101110在检查前几位的时候可能对它好。

分辨植物是否死亡就看。

  • 他加入对它好的次数是不是总的施在他身上的次数。如果不等,说明有其他不好的施肥了,那他就挂了。
  • 他加入对它不好的次数存不存在,如果有,那他也挂了。

还有一个细节,定义数组更加环保和不可能爆空间。之后可以定义

1
2
3
int f[maxn];
#define id(x,y) (x-1)*m+y
// f[x][y] = f[id(x,y)]

还有一个细节就是前缀和你如果想要改变一个区间的前缀和,那就

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void add(int x1,int x2,int y1,int y2){
f[id(x1,y1)]++;
if(x2<n) f[id(x2+1,y1)]--;
if(y2<m) f[id(x1,y2+1)]--;
if(x2<n && y2<m) f[id(x2+1,y2+1)]++;
}
void gen(int *s){
for(int i = 1;<=n;i++){
for(int j=1;j<=m;j++){
if(i>1) s[id(x,y)]+=t[id(x-1,y)];
if(j>1) s[id(x,y)]+=s[id(x,y-1)];
if(i>1&&j>1) s[id(x,y)]-=s[id(x-1,y-1)];
}
}
}

AC代码

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
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int read() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
#define id(x,y) (x-1)*m+y
const int maxn = 1e6 + 1000;
int n,m,T;
int ans[maxn];
int s[maxn],x1[maxn],x2[maxn],y1[maxn],y2[maxn],kind[maxn],a[maxn];
void add(int k,int *f){
int a,b,c,d;
a=x1[k]; b=x2[k]; c=y1[k]; d=y2[k];
f[id(a,c)]++;
if(b<n) f[id(b+1,c)]--;
if(d<m) f[id(a,d+1)]--;
if(b<n&&d<m) f[id(b+1,d+1)]++;
}
void gen(int *f){
rep(i,1,n+1) rep(j,1,m+1){
if(i>1) f[id(i,j)] += f[id(i-1,j)];
if(j>1) f[id(i,j)] += f[id(i,j-1)];
if(i>1&&j>1) f[id(i,j)] -= f[id(i-1,j-1)];
}
}
int main(){
#ifdef LOCAL
freopen("j.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&T);
rep(i,1,n+1) rep(j,1,m+1) a[id(i,j)] = read();
rep(i,0,T){
x1[i]=read();y1[i]=read();x2[i]=read();y2[i]=read();kind[i]=read();
add(i,s);
}
gen(s);
rep(bit,0,21){
int f[maxn] ={0};
rep(i,0,T){
if(kind[i]>>bit & 1){
add(i,f);
}
}
gen(f);
rep(i,1,n+1) rep(j,1,m+1){
if(a[id(i,j)]>>bit & 1){
if(f[id(i,j)]!=s[id(i,j)])
ans[id(i,j)] = 1;
}else if(f[id(i,j)]){
ans[id(i,j)] = 1;
}
}
}
int res = 0;
rep(i,1,n+1) rep(j,1,m+1){
if(ans[id(i,j)]) res++;
}
printf("%d\n",res);
return 0;
}

偷窥到大佬还有用树状数组做的。先copy一下代码。

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
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)1e6+5;
const int MOD=(int)1e9+7;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
vector<int>p[MAXN];
vector<pii>ve[MAXN];
int n,m;
void add(int x,int y,int z){
for(int i=x;i<=n;i+=i&-i){
for(int j=y;j<=m;j+=j&-j){
p[i][j]+=z;
}
}
}
int query(int x,int y){
int re=0;
for(int i=x;i;i-=i&-i){
for(int j=y;j;j-=j&-j){
re+=p[i][j];
}
}
return re;
}
void add(int a,int b,int x,int y,int f){
add(a,b,f);
add(x+1,y+1,f);
add(a,y+1,-f);
add(x+1,b,-f);
}
void init(){
for(int i=1;i<=n;i++)p[i].resize(m+1);
}
struct node{
int a,b,x,y,k;
void scan(){
a=read();b=read();x=read();y=read();k=read();
}
};
vector<node>op[MAXN];

int main()
{
int q;
n=read();m=read();q=read();
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;x=read();
ve[x].push_back(mp(i,j));
}
}
for(int i=1;i<=q;i++){
node now;
now.scan();
op[now.k].push_back(now);
add(now.a,now.b,now.x,now.y,1);
}
int ans=0;
for(int i=1;i<=n*m;i++){
// debug(i);
if(!ve[i].empty()){
for(auto opi:op[i])add(opi.a,opi.b,opi.x,opi.y,-1);
for(auto x:ve[i])if(query(x.fi,x.se))ans++;
for(auto opi:op[i])add(opi.a,opi.b,opi.x,opi.y,1);
//debug(ans);
}
}
printf("%d\n",ans);
return 0;
}