CheaSim Blog
发表更新acm5 分钟读完 (大约715个字)

[hdoj4661] Message Passing

HDOJ 4661: Message Passing

题意

每个人拥有一个信息，也可以传给另外一个人他拥有的所有信息。现在给定一个联络树，问至少多少次传递可以让所有人拥有所有信息。

题解

可以看出至少要$(n-1)*2$次传递，因为每个人都至少传出一次，传入一次。而怎么可以最少传递呢？我们可以假设根为中心，先将所有信息传递给他，之后再从他传递回来。这里有一点很巧妙，传入和传出的可能种类是一样的，所以我们只需要计算一次传入，平方后便是该点为中心的方案数。

因为子节点必须先传给父节点信息以免漏传，所以传入的方案数是满足一种拓扑排序的。那么可以看我之前的一篇博客，计算拓扑排序对一个点进行计算的。

那么怎么从已知的父节点的$f(root)$传递到子节点$f(v)$呢？

$s(i)$表示以$i$为根节点的子节点数目。

我们假设子节点$s(v)=q$，那么如果子节点变成根节点后，子节点的$s(v)=n$，而原来的父节点$f(u)$变成了$n-q$个子节点数目了。于是通过公式

$f(root)=(f(root)-1)!/s(1)/s(2)/…/s(n)$

我们可以推导出$f(v) = f(u) * s(q)/s(n-q)$

搞定!

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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 = 1e6 + 10;
const ll mod = 1e9 + 7;
struct node{
    int to,next;
}G[maxn<<1];
int head[maxn],pre[maxn],q[maxn],vis[maxn];
ll f[maxn],sz[maxn],fac[maxn];
int cnt,n,T;
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    rep(i,0,n+1){
        head[i] = -1;
        q[i] = 0;
        f[i] = 1;
        vis[i] = 0;
        sz[i] = 0;
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&T);
    fac[0] = 1;
    rep(i,1,maxn){
        fac[i] = fac[i-1]*i % mod;
    }
    while(T--){
        scanf("%d",&n);
        init();
        rep(i,0,n-1){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        int l = 0,r = 0;vis[1] = 1;q[0] = 1;
        while(l<=r){
            int u = q[l++];
            for(int i = head[u];~i;i=G[i].next){
                int v = G[i].to;
                if(vis[v]) continue;
                pre[v] = u;
                vis[v] = 1;
                q[++r] = v;
            }
        }
        per(i,1,n){
            sz[q[i]] ++;
            sz[pre[q[i]]] += sz[q[i]];
        }
        sz[1] ++;
        ll cnt = fac[n];
        rep(i,1,n+1) cnt = (cnt*pow3(sz[i],mod-2))%mod;
        ll ans = 0;
        ans = cnt*cnt %mod;f[1] = cnt;
        rep(i,1,n){
            ll cur = f[pre[q[i]]];
            cur = cur*sz[q[i]] %mod;
            cur = cur*pow3(n-sz[q[i]],mod-2)%mod;
            f[q[i]] = cur;
            ans = (ans + cur*cur%mod) % mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
发表更新acm5 分钟读完 (大约752个字)

[UVA11174] Stand in a line

Stand in a line

题意

给定$n-1​$组关系，节点$a​$不能站在节点$b​$的前面，使得$n​$站成一行，问有多少种站法。

题解

树形dp + 组合数学

  1. 先建树，把没有父亲的节点都并入$0$节点，这样我们就有一颗完整的树了。
  2. 寻找规律，假设$f[i]$为以$i$为根节点的方案数，那么当每增加一颗子树的时候，他的组合是相当于有一个有拓扑排序方案和另外一个拓扑排序方案相组合。

我们可以这样想像，假设拓扑排序是不存在的，这些点的排序忽略，那么点可以看做是同样颜色的点，那么$x_1,x_2$个数的点排列的排列数为$(x_1+x_2)! /(x_1! * x_2!)$。而这些点其实是不一样的，他们有自身的拓扑排序顺序，于是答案就是$f(x_1) f(x_2) (x_1+x_2)!/(x1! * x_2!)$。

  1. 于是乎，我们先处理好每个节点的子节点(包含他自身)，可以用拓扑排序直接做，不用递归，当然也可以递归，于是就是相当于从子树开始处理，把所有子树的节点数的阶乘除掉就可以了。

简单写一下从递推到通向。$c_i$表示是$root$的子节点，$s(i)$表示$i$节点的子节点数。

$f(root) = f(c1)f(c2)…f(c_k)*((s(root)-1)!/s(c_1)!/s(c_2)!/…/s(c_k)!)$

$f(c_1)=f(x_1)f(x_2)…f(x_z)*((s(c_1)-1)!/s(x_1)!/s(x_2)!/…/s(x_z)!)$

$s(c_1)和s(c_1-1)$可以约掉。而且到叶子节点$f(x_1)$都变成$1$了$s(x_1)$也变成了0.

$f(root)=(s(root)-1)!/s(1)/s(2)/…/s(n)$

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<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 = 4e4 + 10;
const ll mod = 1e9 + 7;
int T,n,m,cnt;
struct node{
    int to,next;
}G[maxn<<1];
int head[maxn],vis[maxn],sz[maxn],q[maxn],pre[maxn];
ll fac[maxn],f[maxn];
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    rep(i,0,n+1){
        vis[i] = 0;
        head[i] = -1;
        sz[i] = 0;
        pre[i] = 0;
        f[i] = 1;
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a % mod;
        b>>=1;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&T);
    fac[0] = 1;
    rep(i,1,maxn){
        fac[i] = fac[i-1]*i%mod;
    }
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,0,m){
            int u,v;scanf("%d%d",&v,&u);
            add(u,v);vis[v] = 1;
        }
        rep(i,1,n+1) if(!vis[i]) add(0,i);
        memset(vis,0,sizeof(vis));
        vis[0] = 1;
        int l=0,r=0; q[0] = 0;vis[0] = 1;
        while(l<=r){
            int u = q[l++];
            for(int i = head[u];~i;i=G[i].next){
                int v = G[i].to;
                if(vis[v]) continue;
                pre[v] = u;
                vis[u] = 1;
                q[++r] = v;
            }
        }
        per(i,1,n+1){
            sz[q[i]]++;
            sz[pre[q[i]]] += sz[q[i]];
        }
        sz[0]++;
        ll res = 0;
        ll cnt = fac[n];
        rep(i,1,n+1) cnt = cnt*pow3(sz[i],mod-2)%mod;
        printf("%lld\n",cnt);
    }
    return 0;
}

Reference:https://blog.csdn.net/xiao_k666/article/details/78609562

发表更新acm22 分钟读完 (大约3296个字)

[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;
}
发表更新acm4 分钟读完 (大约672个字)

[nowcoder1] J.Different Integers

[nowcoder1]J. Different Integers

题意

给出一段序列$a_1,a_2,…,a_n$，和$l,r$，求区间$[1,l],[r,n]$中不同数字的个数。

题解

树状数组+倍增序列

将查询的$l,r$转化为查询序列$[r,l+n]$中不同中数字的个数。

使用$pre[]$数组维护一个前缀不同种类数字的个数。针对查询就是$pre[r]-pre[l-1]$再加上同时出现在$[1,l-1]$和$[l,r]$上的元素，因为在计算$pre[r]$的时候对于和$[1,l-1]$序列中相同的元素是剔除的，但是减掉之后是需要再加上去的。

对于查询$a[l,…,r]$和$a[1,…,l-1]$内同时出现数字的种类，可以使用树状数组来进行维护。$bit[i]$表示$a[i]$已经在$1,…,l$出现过了。

先对区间查询进行离线排序操作，对于左端每次右移把对应的数的下一个位置加入到树状数组中即可。(嘤嘤嘤？)

tips:处理每个位置数字下一次出现位置的方式很巧妙哦！

1
2
3
4
5
6
7
8
9
10
11
12
//last 记录上一个出现该数字的位置
//nxt 记录下一个出现该数字的位置
rep(i,1,n+1){
    if(!vis[a[i]]){
        vis[a[i]] = 1;
        pre[i] = pre[i-1]+1;
    }else{
        pre[i] = pre[i-1];
    }
    if(last[a[i]]) nxt[last[a[i]]] = i;
    last[a[i]] = i;
}

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
75
76
77
#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 = 2e5 + 10;
int a[maxn],last[maxn],nxt[maxn],vis[maxn],pre[maxn],bit[maxn];
int n,q;
struct node{
    int l,r,id;
    bool operator<(const node& x){
        return l < x.l;
    }
}ask[maxn];
int lowbit(int x){return x&-x;}
void update(int x,int val){
    for(int i=x;i<=n*2;i+=lowbit(i)){
        bit[i] += val;
    }
}
int query(int x){
    int s = 0;
    for(int i=x;i;i-=lowbit(i)){
        s += bit[i];
    }
    return s;
}
int query(int l,int r){
    return query(r) - query(l-1);
}
void init(){
    memset(vis,0,sizeof(vis));
    memset(last,-1,sizeof(last));
    memset(nxt,-1,sizeof(nxt));
    memset(bit,0,sizeof(bit));
}
int main(){
#ifdef LOCAL
    freopen("j.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&q)){
        init();
        rep(i,1,n+1) scanf("%d",&a[i]),a[i+n] = a[i];
        rep(i,1,n+n+1){
            if(!vis[a[i]]){
                pre[i] = pre[i-1] + 1;
                vis[a[i]] = 1;
            }else{
                pre[i] = pre[i-1];
            }
            if(~last[a[i]]) nxt[last[a[i]]] = i;
            last[a[i]] = i;
        }
        rep(i,0,q){
            int l,r;scanf("%d%d",&l,&r);
            int temp = l;l = r;r = temp + n;
            ask[i].l = l;ask[i].r = r;ask[i].id = i;
        }
        sort(ask,ask+q);
        int nowl = 1;
        int ans[maxn];
        rep(i,0,q){
            while(nowl < ask[i].l){
                if(~nxt[nowl])update(nxt[nowl],1);
                nowl++;
            }
            ans[ask[i].id] = pre[ask[i].r] - pre[ask[i].l-1] +query(ask[i].l,ask[i].r);
        }
        rep(i,0,q) printf("%d\n",ans[i]);
    }
    return 0;
}

Reference:https://www.nowcoder.com/discuss/87249?type=101&order=0&pos=12&page=1

发表更新学习笔记11 分钟读完 (大约1661个字)

单调队列学习笔记

单调队列

定义

单调队列，就是指队列中的元素是单调的。

$a_1,a_2,a_3,…,a_n$满足$a1\leq a_2\leq a_3…\leq a_n$的序列便是单调序列。

运用单调队列可以简化问题，由于队列是单调的，那么我们存取最大最小值的复杂度均是$O(1)$。而每一个元素入队一次，出队一次的复杂度也是$O(1)$。

而单调队列和数据结构deque结合较好，如果题目的数据量不是很大，没有卡std，就可以使用deque实现。

维护

以单调增序列为例子：

  1. 如果队列长度一定，先判断队首元素是否在规定范围内，如果超范围就弹出队首。
  2. 每次加入元素和队尾比较，如果当前元素小于队尾元素并且队列非空，就弹出队尾指针，直到满足单调性为止。

例题1 合并果子

(题目太老，只能换个改版的。代码有一定问题，细心的人能看下出来。)

题解

建两个单调队列，寻找两个最小值加入其中一个堆中，有点像haffman编码的方式。

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
#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
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e4 + 10;
int n,ans;
int a[maxn];
int T;
int main(){
#ifdef LOCAL
    freopen("111.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,n){
        scanf("%d",&a[i]);
    }
    deque<int> dq1;
    deque<int> dq2;
    sort(a,a+n);
    rep(i,0,n) dq1.pb(a[i]);
    ans = 0;
    int x,y;
    rep(i,0,n-1){
        if(dq2.empty()){
            x = dq1.front();
            dq1.pop_front();
        }else if(dq1.empty()){
            x = dq2.front();
            dq2.pop_front();
        }else{
            if(dq1.front() < dq2.front()){
                x = dq1.front(),dq1.pop_front();
            }else{
                x = dq2.front(),dq2.pop_front();
            }
        }
        if(dq2.empty()){
            y = dq1.front();
            dq1.pop_front();
        }else if(dq1.empty()){
            y = dq2.front();
            dq2.pop_front();
        }else{
            if(dq1.front() < dq2.front()){
                y = dq1.front(),dq1.pop_front();
            }else{
                y = dq2.front(),dq2.pop_front();
            }
        }
        ans += (x+y);
        dq2.pb(x+y);
    }
    printf("%d\n",ans);
    return 0;
}

例题2 Sliding Window

题解

单调队列+维护一下队头指针不能超过$k$的范围。

由于有最大值和最小值，维护两个单调队列。

需要注意一下的就是如果是手写双向队列的话，我一般是定义

1
2
3
4
5
int st,ed;
st = ed = 0;
mmax[ed++] = a[0];
//判定的时候需要判定ed-1才是指向队尾的值
while(st<ed && mmax[ed-1]<=a[i]) ed--;

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
#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 = 1e6 + 10;
int n,k;
int a[maxn];
int mmax[maxn];
int mmin[maxn];
int main(){
#ifdef LOCAL
    freopen("12.in","r",stdin);
#endif
    scanf("%d%d",&n,&k);
    rep(i,0,n) scanf("%d",&a[i]);
    int st1,st2,ed1,ed2;
    st1 = st2 = ed2 = ed1 = 0;
    mmax[ed1++] = 0; mmin[ed2++] = 0; 
    rep(i,0,k-1){
        while(st1<ed1 && a[mmax[ed1-1]] <= a[i]) ed1--;
        mmax[ed1++] = i;
        while(st2<ed2 && a[mmin[ed2-1]] >= a[i]) ed2--;
        mmin[ed2++] = i;
    }
    rep(i,k-1,n){
        while(st2<ed2 && i-mmin[st2]+1 > k) st2++;
        while(st2<ed2 && a[mmin[ed2-1]] >= a[i]) ed2--;
        mmin[ed2++] = i;
        printf("%d%c",a[mmin[st2]],i==n-1?'\n':' ');
    }
    rep(i,k-1,n){
        while(st1<ed1 && i-mmax[st1]+1 > k) st1++;
        while(st1<ed1 && a[mmax[ed1-1]] <= a[i]) ed1--;
        mmax[ed1++] = i;
        printf("%d%c",a[mmax[st1]],i==n-1?'\n':' ');
    }
    return 0;
}

例题3 Max Sum of Max-K-sub-sequence

题意

给定一个序列，求不超过$k$长的最大连续子段和。

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
#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 T,n,k;
const int maxn = 1e5 + 123;
int a[maxn*3];
int b[maxn];
int main(){
#ifdef LOCAL
    freopen("11.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        rep(i,0,n) scanf("%d",&b[i]);
        rep(i,1,n*2+1) a[i] = (a[i-1] + b[(i-1)%n]);
        deque<int> dq;
        int ans = -INF;
        int l,r;
        rep(i,1,2*n+1){
            while(!dq.empty() && i-dq.front() > k) dq.pop_front();
            while(!dq.empty() && a[dq.back()] > a[i-1]) dq.pop_back();
            dq.push_back(i-1);
            int temp = a[i] - a[dq.front()];
            if(ans < temp){
                ans = temp;
                l = dq.front()+1; r = i;
                if(r>n) r-=n;
            }
        }
        printf("%d %d %d\n",ans,l,r);
    }
    return 0;
}

例题4 Subsequence

题意

给定一段序列，求最长的一段子序列，他的条件是

  • 最大和最小值的差不超过$k$也不小于$m$。

题解

建立两个单调队列，维护$i$之前最大值的下标和$i$之前最小值的下标。

  • 如果最大值最小值超过$k$就弹出下标较小的，并记录较小的位置。

答案是$i-pos$，如果之后的点满足条件了，那么说明$[pos+1,n]$是满足条件的，因为e.g.$a[min[st] 到min[st+1]]$中的元素都大于$a[min[st+1]]$，如果$a[min[st+1]]$满足那么，$a[min[st]+1]$肯定满足条件。

心路历程：我真是太弱了，这就是一道基础的单调队列题目，我想到用两个单调队列来维护，但是对于小于$k$和大于$m$这个条件，不知道怎么去掌控，妈蛋，其实可以靠单调队列的单调性来掌控他们之间的差距。因为一个是递增一个是递减，如果他们之间的差距过大，那么就可以pop掉队首元素，来减少他们的差距，那么大于$m$怎么维护呢？那就是特判他们之间差距是否大于$m$,大于的话就更新一下答案。对于每个$i$就是维护了他之前最大的值的下标和最小值的下标。

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
#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,k;
const int maxn = 1e5 + 10;
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    while(~scanf("%d%d%d",&n,&m,&k)){
        rep(i,1,n+1) scanf("%d",&a[i]);
        deque<int> dq1; //min
        deque<int> dq2; //max
        int ans = 0;int pos = 0;
        rep(i,1,n+1){
            while(!dq1.empty() && a[dq1.back()]>=a[i]) dq1.pop_back();
            dq1.push_back(i);
            while(!dq2.empty() && a[dq2.back()]<=a[i]) dq2.pop_back();
            dq2.push_back(i);
            while(!dq1.empty() && !dq2.empty() && a[dq2.front()]-a[dq1.front()]>k){
                if(dq1.front() < dq2.front())
                    pos = dq1.front(),dq1.pop_front();
                else
                    pos = dq2.front(),dq2.pop_front();
            }
            if(!dq1.empty() && !dq2.empty() && a[dq2.front()]-a[dq1.front()] >=m)
                ans = max(ans,i-pos);
        }
        printf("%d\n",ans);
    }
    return 0;
}

例题5 Trade

题意

股票交易

  • $i$天你可以以$APi$价格买入股票，$BPi$价格卖出股票
  • $i$天最多买$ASi$股，最多卖$BSi$股
  • 最多拥有$MaxP$股股票
  • 交易后有缓冲期$M$天

开始无限制的钱，问最多能赚多少钱？

题解

AC代码

例题6 Cut the Sequence

例题7 瑰丽华尔兹

例题8 Sequence Partitioning

http://www.voidcn.com/article/p-bcrxdtjx-nd.html

发表更新学习笔记3 分钟读完 (大约490个字)

最大子段和学习笔记

最大子段和学习笔记

什么是最大子段和？

给定$n$个整数(可以为负数)组成的序列$a_1,a_2,…,a_n$，求该序列连续的字段和最大值。显然如果都是负数最大值可以为0。

解决方案1

暴力枚举开始位置$i$和终止位置$j$，对每一种可能性计算和。

复杂度$O(n^3)$

解决方案2

使用前缀和优化，保存$\sum_{i=1}^{j-1}a[i]$的结果。

复杂度$O(n^2)$

解决方案3

采用分治策略优化复杂度。

将给定序列$a$分成长度两段子序列$a[1,n/2],a[n/2+1,n]$，分别求出这两段的最大子段和，而总序列的最大子段和有三种情况

  1. 和前半段相同
  2. 和后半段相同
  3. 由前半段的部分和后半段的部分组成的序列相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int MaxSubSum(vector<int> ve,int l,int r){
    int sum = 0;
    if(l==r) return max(ve[l],0);
    int mid = (l+r)>>1;
    int lm = MaxSubSum(ve,l,mid);
    int rm = MaxSubSum(ve,mid+1,r);
    int ls = 0;int lefts = 0;
    for(int i=mid;i>=l;i--){
        lefts += ve[i];
        ls = max(ls,lefts)  //遍历更新最大值
    }
    int rs = 0;int rights = 0;
    for(int i=mid+1;i<=r;i++){
        rights += ve[i];
        rs = max(rs,rights);
    }
    sum = ls + rs;
    sum = max(sum,max(lm,rm));
    return sum;
}

复杂度$O(nlogn)$

解决方案4

动态规划。

  • 设置$dp[i] = max(dp[i-1]+a[i],a[i])$，$dp[i]$表示以$i$为结尾的最长子串的和。
  • 对于每一个$a[i]$如果之前的最大子串小于$0$了，那么就要重新以他为开头建立一个子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int MaxSubSum(vector<int> ve,int n,int& l,int& r){
    int sum = -INF;int mmax = -INF;
    int L=0;int R = 0;
    for(int i=0;i<n;i++){
        if(sum < 0){
            sum = ve[i];
            L = R = i;
        }else{
            sum += ve[i];
            R ++;
        }
        if(mmax < sum){
            mmax = sum;
            l = L;r = R;
        }
    }
    return mmax;
}

复杂度$O(n)$

解决方案5

最大子段的左右两个数字必定为正数，最左边数字

reference:https://blog.csdn.net/zhong36060123/article/details/4381391

发表更新acm2 分钟读完 (大约267个字)

[hdoj6438]Buy and Resell

[hdoj6438]Buy and Resell

题意

给定$n$个城市和无限制的初始金钱你可以在每个城市里

  • 以$a_i$的价格买个商品
  • 以$a_i$的价格卖出商品
  • 啥都不做

问最多能赚多少钱？

题解

贪心 + 数据结构

假设每个城市都卖出商品。那么之前买入的最便宜的商品来卖。对于买卖次数就将假设买入的商品记录为两种

  • $1$表示他是之前买入并且在这次卖出
  • $2$表示他是没有买卖，直接抵消了。
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
#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 T,n;
ll ans = 0;
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        priority_queue<pII>pq; ans = 0;int cnt = 0;
        scanf("%d",&n);
        rep(i,0,n){
            int x;scanf("%d",&x);
            pq.push(make_pair(-x,1));
            pq.push(make_pair(-x,2));
            ll temp = x + pq.top().fi;
            if(pq.top().se == 1)  cnt+=2;
            ans += temp;
            pq.pop();
        }
        printf("%lld %d\n",ans,cnt);
    }
    return 0;
}

发表更新acm3 分钟读完 (大约504个字)

[hdoj6447] YJJ's Salesman

[hdoj6447] YJJ’s Salesman

题意

给定一个地图，只能向右或者向上走，地图上有很多点，有以下条件

  • 每个点有钱$val$
  • 你只能从该点的左下方进入点才可以拿钱。

问最多能获得多少钱。

题解

dp + 树状数组优化

单dp就是$O(n^2)$的复杂度。但是题目数据范围$1e5$所以不行。只有树状数组优化了。

树状数组处理的是$dp[i]$代表着以$i$点为重点的权值。

并且由于$x,y$范围是$1e9$所以必须离散化。

有一步我看了好久代码才看懂。在dp方程转移的时候，先对于$x$进行排列，之后在之后更大的$x$再更新之后的dp数组，保证每一次update的dp数组都是最优的。

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
#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;
struct node{
    int x,y,val;
    bool operator <(const node& t)const{
        return x < t.x;
    }
}a[maxn];
int T,n,tot;
int bit[maxn],dp[maxn];
int lowbit(int x){
    return x&-x;
}
void update(int x,int val){
    for(int i=x;i<=tot;i+=lowbit(i)) bit[i] = max(bit[i],val);
}
int query(int x){
    int s = 0;
    for(int i=x;i;i-=lowbit(i)){
        s = max(s,bit[i]);
    }
    return s;
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        vector<int> v;
        memset(bit,0,sizeof(bit));
        scanf("%d",&n);
        rep(i,0,n){
            int x,y,v;scanf("%d%d%d",&x,&y,&v);
            a[i].x = x;a[i].y = y;a[i].val = v;
        }
        rep(i,0,n) v.push_back(a[i].y);
        sort(v.begin(),v.end());
        sort(a,a+n);
        v.erase(unique(v.begin(),v.end()),v.end());
        tot = v.size();
        rep(i,0,n) a[i].y = lower_bound(v.begin(),v.end(),a[i].y) - v.begin() + 1;
        rep(i,0,n) dp[i] = a[i].val;
        int ans = 0;int pos = 0;
        rep(i,0,n){
            while(pos < i && a[pos].x < a[i].x){
                update(a[pos].y,dp[pos]);
                pos ++;
            }
            dp[i] = query(a[i].y-1) + a[i].val;
            ans = max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }  
    return 0;
}
发表更新acm6 分钟读完 (大约926个字)

51Nod-1593 公园晨跑

51Nod-1593 公园晨跑

题意

给定一个环，环上有$n$个点，每个点有一个权值$h$代表着如果从$i$到$j$的话，你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。

题解

线段树维护区间最大最小值的坐标和特判相同处理。

首先，面对环和方向性，我们可以把环拆成链式。形成一个$[1,n] \cup [1.n]$的区间对于$X,Y$的查找可以看成两种情况，

  • 一种是$X\leq Y$，那么我们寻找的范围就是$[Y+1,X+n-1]$。
  • 对于$X>Y$的情况，我们寻找的范围就是$[Y+1,X-1]$。

定义$d[x]$为$x$点到第一个点的距离(线性)。

对于给定的两个点$X,Y$，我们获得的权值是确定的，为$d[Y]-d[X]+2h[X]+2h[Y]$，我们可以将这个算式分为$X$部分和$Y$部分。于是我们就可以将式子转化为

$target = (d[Y]+2h[Y]) - (d[X]-2h[X])$

这个式子求最大值，就是对于每个点求第一部分的最大值和第二部分的最小值。之后由于$X != Y$，所以对于线段树维护的是区间内最大最小值的坐标。当坐标相同时，寻找次一级的最小值或者次一级的最大值。

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
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
105
106
107
108
109
110
111
112
#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
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const ll INF = 1e11;
//head
const int maxn = 2e5 + 10;
ll h[maxn],d[maxn],A[maxn],B[maxn];
int mmax[maxn<<2],mmin[maxn<<2];
template <class T>
bool read(T &x){
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-') op = 1;
        else if(c == EOF) return 0;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op) x = -x;
    return 1;
}
inline int Max(int a,int b){
    return A[a] > A[b] ? a : b;
}
inline int Min(int a,int b){
    return B[a] < B[b] ? a : b;
}
inline ll Mmax(ll a,ll b){
    return a>b?a:b;
}
int m,n;
void pushup(int rt){
    mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]);
    mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        mmax[rt] = l;
        mmin[rt] = l;
        return ;
    }
    int mid = (r+l)>>1;
    build(lson);build(rson);
    pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R) return mmax[rt];
    int mid = (l+r) >> 1;
    ll res = 0;
    if(L <= mid) res = Max(res,query_max(L,R,lson));
    if(mid < R) res = Max(res,query_max(L,R,rson));
    return res;
}
int query_min(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R) return mmin[rt];
    int mid = (l+r) >> 1;
    ll res = 0;
    if(L <= mid) res = Min(res,query_min(L,R,lson));
    if(mid < R) res = Min(res,query_min(L,R,rson));
    return res;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,2,n+2) read(d[i]),d[n+i] = d[i];
    rep(i,2,n*2+1) d[i] += d[i-1];
    rep(i,1,n+1){
        ll hh;read(hh);
        h[i] = h[i+n] = hh;
    }
    A[0] = -INF;B[0] = INF;
    rep(i,1,n+n+1){
        A[i] = 2*h[i] + d[i];
        B[i] = d[i] - 2*h[i];
    }
    build(1,n*2,1);
    while(m--){
        int l,r;read(l);read(r);
        if(l<=r){
            int st = query_max(r+1,l+n-1,1,2*n,1);
            int ed = query_min(r+1,l+n-1,1,2*n,1);
            ll ans;
            if(st == ed){
                int st1 = Max(query_max(st+1,l+n-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
                int ed1 = Min(query_min(ed+1,l+n-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
                ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
            }else ans = A[st] - B[ed];
            printf("%lld\n",ans);
        }else{
            int st = query_max(r+1,l-1,1,2*n,1);
            int ed = query_min(r+1,l-1,1,2*n,1);
            ll ans;
            if(st == ed){
                int st1 = Max(query_max(st+1,l-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
                int ed1 = Min(query_min(ed+1,l-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
                ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
            }else ans = A[st] - B[ed];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

reference:https://blog.csdn.net/ZLH_HHHH/article/details/74887389

发表更新acm2 分钟读完 (大约293个字)

nowcoder6 C.Generation I

Generation I

题解

首先放$k$种数字的情况，有$A_n^k$中可能。

由于操作后，前面的球就无法放置,就可以第一个放置该数字的点来确定该结果的区别。相当于将$k$种放在$n$个格子里面。使用隔板法$n\choose k$。

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
#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 ll mod = 998244353;
int T;
const int maxn = 1e6 + 10;
ll cur,p[maxn],q[maxn],inv[maxn];
ll n,m;
ll C(ll n,ll k){
    return p[n]*q[k]%mod*q[n-k]%mod;
}
ll c(ll n,ll k){
    if(n<maxn) return C(n,k);
    if(!k) return 1;
    return cur = cur*inv[k]%mod*((n-k+1)%mod)%mod;
}
void init(){
    p[0] = p[1] = q[0] = q[1] = inv[0] = inv[1] = 1;
    for(ll i = 2;i<maxn;i++){
        inv[i] = (mod-mod/i)*inv[mod%i]%mod;
        q[i] = q[i-1]*inv[i]%mod;
        p[i] = p[i-1] * i % mod;
    }
}
int main(){
#ifdef LOCAL
    freopen("j.in","r",stdin);
#endif
    init();
    scanf("%d",&T);
    rep(test_case,1,T+1){
        scanf("%lld%lld",&n,&m);
        ll len = min(n,m);
        ll ans = 0;
        cur = 1;
        for(ll i = 1;i<=len;i++){
            ans = (ans + (c(m,i)*p[i]%mod)*c(n-1,i-1)%mod)%mod;
        }
        printf("Case #%d: %lld\n",test_case,ans);
    }
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×