20170723离线赛 · nanhan27's Blog

引言：感觉到自己的脑洞确实变大了那么一丢丢。

A、插队——原创By jiedai and nudun

关键字：单调栈，线段树，树状数组

【分析】

题目就是求出每一个点向左数第二个大于它的点的位置。

首先用一个单调递减的单调栈就能求出向左数第一个大于它的点。接下来就比较麻烦了。

如何求出第二个呢？难道再暴力往前for吗？

我的做法仍然是单调栈。对于每一个点，我们都可以知道第一次插队会插到谁那。既然这样，对于一个点，那些第一次插到它的点的关系又会是怎样的？一定是单调递增的！，而且，这些点当然比这个点小。这样按照pos从小到大的顺序在单调栈中查询，不会将前面的有效信息遗漏。

当然这种是比较难想的，大多数人都是用线段树求出第二个大于它的位置。

还有一种树状数组的写法，只是写起来比较麻烦，思路也没有线段树简洁，所以并没有人去写。

B、比赛——CODECHEF SEPT16

关键字：树形dp、倍增

【分析】

比较容易看出是树形dp，但是这个dp比较奇怪，dp转移是从某节点的祖先那里转移过来的。

快速敲完这题就去写第三题了。然后这题就爆炸了。

定义dp[t][u]表示u点往根的路径上$2^t$个点中答案的最小值。那么u点的最小花费就是:

$ans[u]=min(dp[t][F[d-1]],dp[t][F[d-1-k+(1<<t)]])+v)$

转移就比较简单了：

$dp[i][u]=min(dp[i-1][u],dp[i-1][F[d-(1<<i-1)]])$

复杂度$O(n*log(n))$。

【代码】


using namespace std;
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define ll long long
#define M 200005
#define S 20
struct {int k,v;};
ll ans[M],dp[S][M];
vector<int>e[M];
vector<MP>mp[M];
int n,m,q;
int F[M];
void chk(ll &x,ll y){
    if(x>y)x=y;
}
void dfs(int u,int f,int d){
    F[d]=u;
    for(int i=0;u!=1&&i<mp[u].size();i++){
        int k=min(mp[u][i].k,d-1);
        int v=mp[u][i].v;
        int t=0;
        while((1<<t+1)<=k)t++;
        chk(ans[u],min(dp[t][F[d-1]],dp[t][F[d-1-k+(1<<t)]])+v);
    }
    dp[0][u]=ans[u];
    for(int i=1;(1<<i)<=d;i++){
        dp[i][u]=min(dp[i-1][u],dp[i-1][F[d-(1<<i-1)]]);
    }
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v!=f)dfs(v,u,d+1);
    }
}
int main(){
    memset(ans,63,sizeof ans);
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("% 大专栏  20170723离线赛 · nanhan27's Blogd %d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    while(m--){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        mp[a].push_back((MP){b,c});
    }
    ans[1]=0;
    dfs(1,0,1);
    while(q--){
        int u;
        scanf("%d",&u);
        printf("%lldn",ans[u]);
    }
    return 0;
}

C、采油区域——APIO2009

关键字：dp，前缀和

【分析】

首先我们是做过两块区域的。记得当时的思路就是枚举一条将整个区域分成两块的线。

现在是分成三块区域。分成三块区域需要两条线，所以复杂度应该是$O(n^2)$，对于这道题应该是能过的。

三块区域的分布情况有6（4+2）种，而解决这些情况需要5种前缀信息，分别是普通的sum和左上、左下、右上、右下角边长为K的区域石油最多是多少。

接下来就是用sum来$O(n^2)$预处理出其他4个前缀信息，再用$O(n^2)$来从6种情况中更新答案了。

所以这道题对我有点启发，对于一个较难的题目，我们可以先弱化一些条件，在想出解决小问题后试着将同样的思路去解决大问题。

【代码】


#define debug(x) cout<<#x<<" = "<<x<<endl;
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(c);a>=(b);a--)
#define ll long long
using namespace std;
#define M 1505
int n,m,K,ans;
int sum[M][M];
int a[M][M];
int b[M][M];//右上 
int c[M][M];//左下 
int d[M][M];//右下 
void chk(int &x,int y){
    if(x<y)x=y;
}
void Init(){
    per(i,K,n)per(j,K,m)sum[i][j]=sum[i][j]-sum[i-K][j]-sum[i][j-K]+sum[i-K][j-K];
    rep(i,K,n)rep(j,K,m)a[i][j]=max(sum[i][j],max(a[i-1][j],a[i][j-1]));
    rep(i,K,n)per(j,K,m)b[i][j]=max(sum[i][j],max(b[i-1][j],b[i][j+1]));
    per(i,K,n)rep(j,K,m)c[i][j]=max(sum[i][j],max(c[i+1][j],c[i][j-1]));
    per(i,K,n)per(j,K,m)d[i][j]=max(sum[i][j],max(d[i+1][j],d[i][j+1]));
}
int main(){
    scanf("%d %d %d",&n,&m,&K);
    rep(i,1,n)rep(j,1,m){
        int x;
        scanf("%d",&x);
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
    }
    Init();
    rep(i,K,n-K)rep(j,K,m-K)chk(ans,a[i][j]+b[i][j+K]+c[i+K][m]);
    rep(i,K,n-K)rep(j,K+K,m)chk(ans,a[n][j-K]+b[i][j]+d[i+K][j]);
    rep(i,2*K,n)rep(j,K,m-K)chk(ans,a[i-K][m]+c[i][j]+d[i][j+K]);
    rep(i,K,n-K)rep(j,K,m-K)chk(ans,a[i][j]+b[n][j+K]+c[i+K][j]);
    rep(i,K,n)rep(j,K+K,m-K)chk(ans,sum[i][j]+a[n][j-K]+b[n][j+K]);
    rep(i,2*K,n-K)rep(j,K,m)chk(ans,sum[i][j]+a[i-K][m]+c[i+K][m]);
    printf("%dn",ans);
    return 0;
}