“2018宁夏邀请赛 ” 兼 “The 2019 Asia Yinchuan First Round Online Programming”

------------7题弟弟，被各位半小时13题的大佬打惨了（滑稽）----------

签到题就不写了。

F ：Moving On (1247ms）

题意：给定大小为N的带点权，带边权的完全图，N<200。然后Q次询问，每次给出(u,v,w)，让你求在除了起点终点的其他途经点的点权都<=w的条件下的最短路。

思路：可以离线做的话，显然就是需要排序了。然后想到floyd就是一个用点更新的最短路算法。那么我们把floyd的第一层按点权排个序即可。那么第k层的dis[i][j]，就表示途经点都<=w[k]的最短路。为了方便，这里所有的点权和询问的w都离散化了。（比赛因为没有初始化WA了半天，哭）（网上看了其他人的写法大都是三维的，显然没必要，很明显是滚动的，在可以离线的情况下，第一维没什么用）。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=210;
const int maxm=20010;
int mp[maxn][maxn],b[maxn],tot,ans[maxm];
struct in{
    int u,v,w,id;
};
vector<in>G[maxn];
pii a[maxn];
int main()
{
    int T,N,M,C=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        rep(i,1,N) scanf("%d",&a[i].first),a[i].second=i;
        rep(i,1,N) b[i]=a[i].first;
        sort(b+1,b+N+1);
        tot=unique(b+1,b+N+1)-(b+1);
        rep(i,0,tot) G[i].clear();
        rep(i,1,N) a[i].first=lower_bound(b+1,b+tot+1,a[i].first)-b;
        sort(a+1,a+N+1);
        rep(i,1,N) rep(j,1,N) scanf("%d",&mp[i][j]);
        rep(i,1,M) {
            in t;
            scanf("%d%d%d",&t.u,&t.v,&t.w);
            ans[i]=mp[t.u][t.v];
            t.w=upper_bound(b+1,b+tot+1,t.w)-b;
            t.w--; t.id=i;
            G[t.w].push_back(t);
        }
        rep(k,1,N) {
            int tk=k; while(tk+1<=N&&a[tk+1].first==a[k].first) tk++;
            rep(p,k,tk) {
              rep(i,1,N)
               rep(j,1,N){
                 int kk=a[p].second;
                 mp[i][j]=min(mp[i][j],mp[i][kk]+mp[kk][j]);
              }
            }
            for(int i=0;i<G[a[k].first].size();i++){
                in t=G[a[k].first][i];
                ans[t.id]=min(ans[t.id],mp[t.u][t.v]);
            }
            k=tk;
        }
        printf("Case #%d:
",++C);
        rep(i,1,M) printf("%d
",ans[i]);
    }
    return 0;
}

View Code

G：Factories （1036ms）

题意：给定一个大小为N的无根树，让你选K个叶子，使得两两间距离和最短。 (N<1e5, K<100)；

思路：这类题可能会想到换根DP，然后这里想了想没必要。如果有度数大于1的，它就可以作为根，然后就是一个树上背包题，而谁作为根，效果是一样的，所以没必要换根DP。然后发现想不出O(NK)的写法，所以瞎交了一发O(NK^2)。居然过了。玄学。

update：这样实际的复杂度是O(NK)的。

参考：https://www.cnblogs.com/ouuan/p/BackpackOnTree.html

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=100010;
const ll inf=1LL<<60;
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],len[maxn<<1],cnt;
int ind[maxn],rt,sz[maxn],K;
void add(int u,int v,int w){
    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; len[cnt]=w;
}
ll dp[maxn][101],ans;
void read(int &x){
    x=0; char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}
void dfs(int u,int f)
{
    sz[u]=0; int leaf=1;  dp[u][0]=0;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i]; if(v==f) continue;
        leaf=0; dfs(v,u);
        for(int k=sz[u];k>=0;k--){
            for(int j=min(K-k,sz[v]);j>=1;j--){
                dp[u][k+j]=min(dp[u][k+j],dp[u][k]+dp[v][j]+1LL*(K-j)*j*len[i]);
            }
        }
        sz[u]+=sz[v];
    }
    if(leaf) sz[u]=1,dp[u][1]=0;
    if(sz[u]>=K) ans=min(ans,dp[u][K]);
}
int main()
{
    int T,N,C=0,u,v,w;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&K);
        rep(i,1,N) Laxt[i]=0; cnt=0;
        rep(i,0,N+1) rep(j,0,K) dp[i][j]=inf; ans=inf;
        rep(i,1,N) ind[i]=0;
        rep(i,1,N-1){
            read(u); read(v); read(w);
            add(u,v,w); add(v,u,w);
            ind[u]++; ind[v]++;
        }
        if(N==1||K<=1) ans=0;
        else if(N==2) ans=len[1];
        else {
            rep(i,1,N) if(ind[i]>1) {
                rt=i; break;
            }
            dfs(rt,0);
        }
        printf("Case #%d: %lld
",++C,ans);
    }
    return 0;
}

View Code

I： Bubble Sort

题意：如果K轮冒泡排序后LIS>=N-1，则说这个排列是ok的，给次给出N和K，问有多少个是ok的。

思路：不难想到可以DP做。

（代码晚点再放。

K：Vertex Covers （1060ms）

题意：给定N点M边的无向图，每个点有点权。点覆盖表示某个点集S{}覆盖了所有的边，其贡献是点权S之积。现在让你求所有的贡献之和。N<36，保证无重边，自环。

思路：点覆盖的问题，而且N比较小，不难想到状压。可以这里N最大为36，显然还需要一个折半枚举，然后想办法合并两边。

那么我们把点分为L，R两个集合。那么边有三类： 1，两端点在L中； 2，两端点在R中； 3，两端点在L和R中各一个。

那么显然，对于1类边，两个端点至少一个要选；对于2类边同理；对于第3类边，如果L中没选，那么R中必选，即补集的超集，而超集我们可以用高维前缀和搞定。所以这题就完了。（那些100ms跑出来的人都是神仙吧）

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2000010;
int a[maxn],sum[maxn],ltl[40],ltr[40],rtr[40],Mod;
void MOD(int &x){ if(x>=Mod) x-=Mod;}
int main()
{
    int T,N,M,u,v,C=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&N,&M,&Mod);
        rep(i,0,N-1) scanf("%d",&a[i]);
        rep(i,0,N-1) ltl[i]=ltr[i]=rtr[i]=0;
        int L=(N+1)/2, R=N-L, ans=0;
        rep(i,1,M){
            scanf("%d%d",&u,&v);
            u--, v--;
            if(u>v) swap(u,v);
            if(u<L){
                if(v<L) ltl[u]|=(1<<v);
                else ltr[u]|=(1<<(v-L));
            }
            else rtr[u]|=(1<<(v-L));
        }
        rep(i,0,(1<<R)-1){
            int res=1;
            rep(j,0,R-1){
                if(i&(1<<j)) res=1LL*res*a[j+L]%Mod;
                else {
                    res=res*((rtr[j+L]|i)==i);
                    if(!res) break;
                }
            }
            sum[i]=res;
        }
        rep(i,0,R-1) {
            rep(j,0,(1<<R)-1) {
                if(!(j&(1<<i))) MOD(sum[j]+=sum[j|(1<<i)]);
            }
        }
        rep(i,0,(1<<L)-1){
            int res=1,need=0;
            rep(j,0,L-1) {
                if(i&(1<<j)) res=1LL*res*a[j]%Mod;
                else {
                    res=res*((ltl[j]|i)==i),need|=ltr[j];
                    if(!res) break;
                }
            }
            MOD(ans+=1LL*res*sum[need]%Mod);
        }
        printf("Case #%d: %d
",++C,ans);
    }
    return 0;
}

View Code

L：Continuous Intervals （1075ms）

题意：给定长度为N的序列，求有多少个子区间，满足这个区间排序后，相邻的数相差<=1；

思路：即是问，有多少个区间满足max-min+1==cnt，max和min是区间最大最小值，cnt是区间种类数。

分治吗？没法分，没法治。启发式分治吗？没法找mid。

所以试一试暴力？我们枚举右端点R，那么就是统计多少个L合法。假设得到了[1,R-1]的所有信息，现在加入一个R进去，

1，可能会对某些区间的极值产生影响； 2，可能会对某个区间的cnt产生影响。

我们只需要维护好每个L点的信息，用来表示后缀的极值和cnt即可。

如何维护区间极值：线段树。

如何减少维护次数：单调队列+lazy。

对于cnt：影响的只有[laxt[a[R]]+1,R]这个区间。

所以综上，只需要维护三个lazy即可。然后右移R，修改线段树，统计有多少个max-min+1=cnt，即max-min-cnt==-1的区间即可。

由于有三种变量，所以维护三个lazy会比较麻烦。我们直接维护一个差值，这样可以统一，变成每次都是维护一个差值可以了。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2000010;
int Mn[maxn],lazy[maxn],sum[maxn],a[maxn];
int q1[maxn],t1,q2[maxn],t2;
map<int,int>mp;
void build(int Now,int L,int R)
{
    sum[Now]=R-L+1; Mn[Now]=lazy[Now]=0;
    if(L==R) return ; int Mid=(L+R)>>1;
    build(Now<<1,L,Mid);
    build(Now<<1|1,Mid+1,R);
}
void pushdown(int Now)
{
    if(!lazy[Now]) return ;
    Mn[Now<<1]+=lazy[Now]; Mn[Now<<1|1]+=lazy[Now];
    lazy[Now<<1]+=lazy[Now]; lazy[Now<<1|1]+=lazy[Now];
    lazy[Now]=0;
}
void pushup(int Now)
{
    Mn[Now]=min(Mn[Now<<1],Mn[Now<<1|1]);
    if(Mn[Now<<1]==Mn[Now<<1|1]) sum[Now]=sum[Now<<1]+sum[Now<<1|1];
    else if(Mn[Now<<1]<Mn[Now<<1|1]) sum[Now]=sum[Now<<1];
    else sum[Now]=sum[Now<<1|1];
}
void update(int Now,int L,int R,int l,int r,int v)
{
    if(l>r) return ;
    if(L==R) {
        Mn[Now]+=v;
        return ;
    }
    if(l<=L&&r>=R){
        Mn[Now]+=v; lazy[Now]+=v;
        return ;
    }
    int Mid=(L+R)>>1; pushdown(Now);
    if(l<=Mid) update(Now<<1,L,Mid,l,r,v);
    if(r>Mid) update(Now<<1|1,Mid+1,R,l,r,v);
    pushup(Now);
}
int main()
{
    int T,N,C=0; ll ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        rep(i,1,N) scanf("%d",&a[i]);
        build(1,1,N);
        t1=t2=0; ans=0;  mp.clear();
        rep(i,1,N){
            update(1,1,N,i,i,-1);
            while(t1&&a[i]>=a[q1[t1]]){
                update(1,1,N,q1[t1-1]+1,q1[t1],a[i]-a[q1[t1]]);
                t1--;
            }
            q1[++t1]=i;

            while(t2&&a[i]<=a[q2[t2]]){
                update(1,1,N,q2[t2-1]+1,q2[t2],a[q2[t2]]-a[i]);
                t2--;
            }
            q2[++t2]=i;

            update(1,1,N,mp[a[i]]+1,i-1,-1); mp[a[i]]=i;
            ans+=sum[1];
        }
        printf("Case #%d: %lld
",++C,ans);
    }
    return 0;
}

View Code