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=+;
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,,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=;
        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=;i<=n;i++)A[i].rd(),A[i].id=i;
    sort(A+,A+n+);
    for(int i=;i<=q;i++)
        Q[i].rd(),Q[i].id=i;
    sort(Q+,Q+q+);
    for(int i=,j=;i<=q;i++){
        while(Q[i].z>=A[j].w&&j<=n){
            //每次都把比z小的w加進來
            //利用Bit來計算字首和 
            Bit_m.Add(A[j].id,);
            Bit_v.Add(A[j].id,l*A[j].p*A[j].p);
            Bit_s.Add(A[j].id,l*A[j].p);
            j++;
        }
        int m=Bit_m.Query(Q[i].y)-Bit_m.Query(Q[i].x-);
        ll s=Bit_s.Query(Q[i].y)-Bit_s.Query(Q[i].x-);
        ll v=Bit_v.Query(Q[i].y)-Bit_v.Query(Q[i].x-);
        if(!m)ans[Q[i].id]=-;
        else ans[Q[i].id]=l*m*v-l*s*s;
    }
    for(int i=;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=+;
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&;
    for(int i=;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+,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=,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(,,);
    int l1=,l2=;

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

    for(int i=;i<=l1;i++)
        Q.push((node){A[i]+B[],i,});
    int has=;
    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 ;}
    }puts("Stupid Mike");
}