2017.3.10NOIP模拟赛题解及反思（伪）

我没有参加本次考试。。。。。。

第一题

我们发现对于一个{1~i}的序列有k个逆序对，如果想让它增加a(0<=a<=i)个其方案是唯一的
所以
我们用 dp[i][j] 表示用了{1~i}的序列形成了j个逆序对的方案数
dp[i][j]=∑ja=0 dp[i−1][a]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[2][3005],sum[2][3005],ans,P=1e10+7;
int main(){
 int n,k,c=0;
 scanf("%d %d",&n,&k);
 dp[0][1]=1;k++;
 for(int i=1;i<=k;i++)sum[0][i]=1;
 for(int i=1;i<n;i++){
 c=!c;
 for(int j=0;j<=k;j++)sum[c][j]=dp[c][j]=0;
 for(int j=1;j<=k;j++){
 int l=max(j-i-1,0);
 dp[c][j]=(sum[!c][j]-sum[!c][l]+P)%P;
 sum[c][j]=(dp[c][j]+sum[c][j-1])%P;
 }
 }cout<<sum[c][k];
}

第二题

我们发现这一题对权值有很恶心的限制，只有权值小于询问（x,y,z）中z的元素才对答案有贡献
于是我们有一个很巧妙的方法即：要多少求多少
我们把两者均以权值排序后把元素依次加入容器里即可
这样当我们要找（x,y,z）使我们发现容器中的都是合法的元素了

#include<bits/stdc++.h>
typedef long long ll;
const int M=4e5+5;
using namespace std;
int n,q;
struct node{
    int p,w,id;
    bool operator <(const node &a)const{
        return w<a.w;
    }void rd(){scanf("%d%d",&w,&p);}
}A[M];
struct Bit{
    ll num[M];
    Bit(){memset(num,0,sizeof(num));}

    inline void Add(int x,ll v){
        while(x<=n)num[x]+=v,x+=x&-x;
    }
    inline ll Query(int x){
        ll res=0;
        while(x)res+=num[x],x-=x&-x;
        return res;
    }

}Bit_m,Bit_s,Bit_v;
struct Qu{
    int x,y,z,id;
    bool operator <(const Qu &a)const{
        return z<a.z;
    }void rd(){scanf("%d%d%d",&x,&y,&z);}
}Q[M];
ll ans[M];
int main(){
    //由于只有A[i].w小于Q[a].z的才对a有贡献所以可以将w,z从小到大排序 
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)A[i].rd(),A[i].id=i;
    sort(A+1,A+n+1);
    for(int i=1;i<=q;i++)
        Q[i].rd(),Q[i].id=i;
    sort(Q+1,Q+q+1);
    for(int i=1,j=1;i<=q;i++){
        while(Q[i].z>=A[j].w&&j<=n){
            //每次都把比z小的w加进来
            //利用Bit来计算前缀和 
            Bit_m.Add(A[j].id,1);
            Bit_v.Add(A[j].id,1ll*A[j].p*A[j].p);
            Bit_s.Add(A[j].id,1ll*A[j].p);
            j++;
        }
        int m=Bit_m.Query(Q[i].y)-Bit_m.Query(Q[i].x-1);
        ll s=Bit_s.Query(Q[i].y)-Bit_s.Query(Q[i].x-1);
        ll v=Bit_v.Query(Q[i].y)-Bit_v.Query(Q[i].x-1);
        if(!m)ans[Q[i].id]=-1;
        else ans[Q[i].id]=1ll*m*v-1ll*s*s;
    }
    for(int i=1;i<=q;i++){
        if(~ans[i])cout<<ans[i]<<'\n';
        else puts("empty");
    }
}

第三题

题目的性质非常巧妙即
<1>奇数边
<2>边权正负交错
由于数据非常大我们需要O（n）的求出两点间的距离
我们可以这样考虑如果是线性的元素我们只要前缀和维护即可开始对于树要怎么帮呢？
我们建一个树

我们发现ans（3,4）=ans(2,3)+ans(2,4)
ans(2,3)=dis[3]-dis[2];
ans(2,4)=dis[3]-dis[2];
由于dis[4]处在偶数层我们不妨把他取负
得到ans（3,4）=dis[3]+dis[4];（dis[son]=-dis[fa]+v）

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
typedef long long ll;
struct edge{int t,c;};
vector<edge>G[M]; 
ll pos[M],A[M],B[M];
bool dep[M];
int n,k;
void dfs(int x,int d,int pre){
    dep[x]=d&1;
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i].t,c=G[x][i].c;
        if(y==pre)continue;
        pos[y]=c-pos[x];
        dfs(y,d+1,x);
    }
}
struct node{
    ll val;
    int i,j;
    bool operator<(const node&A)const{
        return val>A.val;
    }
}nw;
priority_queue<node>Q;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1,a,b,c;i<n;i++){
        scanf("%d %d %d",&a,&b,&c);
        G[a].push_back((edge){b,c});
        G[b].push_back((edge){a,c});
    }dfs(1,1,0);
    int l1=0,l2=0;

    for(int i=1;i<=n;i++){
        if(dep[i])A[++l1]=pos[i];
        else B[++l2]=pos[i];
    }
    sort(A+1,A+1+l1);
    sort(B+1,B+1+l2);

    for(int i=1;i<=l1;i++)
        Q.push((node){A[i]+B[1],i,1});
    int has=0;
    while(!Q.empty()){
        nw=Q.top();
        Q.pop();
        int i=nw.i,j=nw.j;
        ll val=nw.val;
        if(j++<l2) Q.push((node){A[i]+B[j],i,j});
        if(k==++has){cout<<val<<endl;return 0;}
    }puts("Stupid Mike");
}