2017.8.26 noip模拟赛 总结

装作有题目的样子。。。

由于是自己的题，题面这种东西就不太好往上面放。。

标准NOIP难度，第一题约等于day2T1,第二题约等于day2T2,第三题约等于day1T3。

第一道题：

由于和bzoj上某道题比较类似，放个那道题的链接吧。。

题目

总之，就是一道加了一点细节的递推题，想到递推矩阵会发生变化后就比较好想了。而且，这类题目还很好对拍，是比较稳的了。

#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#define mod 1000000007
using namespace std;
long long n,tmp,k;
long long f[20];
struct matrix{
    int h;
    int l;
    long long data[5][5];
};
matrix a,b,c;
matrix multiply(matrix A,matrix B)
{
    matrix ans;
    ans.h=A.h,ans.l=B.l;
    for(int i=1;i<=ans.h;i++)
        for(int j=1;j<=ans.l;j++)
            ans.data[i][j]=0;
    for(int i=1;i<=ans.h;i++)
        for(int j=1;j<=ans.l;j++)
            for(int k=1;k<=A.l;k++)
                ans.data[i][j]=(ans.data[i][j]+A.data[i][k]*B.data[k][j])%mod;
    return ans;
}
void write(matrix A)
{
    for(int i=1;i<=A.h;i++)
    {
        for(int j=1;j<=A.l;j++)
            cout<<A.data[i][j]<<" ";
        cout<<endl;
    }
}
matrix ksm(matrix A,long long B)
{
    matrix ans;
    ans.h=A.h,ans.l=A.l;
    for(int i=1;i<=ans.h;i++)
        for(int j=1;j<=ans.l;j++)
            ans.data[i][j]=(i==j);
    while(B)
    {
        if(B&1)ans=multiply(ans,A);
        B>>=1;
        A=multiply(A,A);
    }
    return ans;
}
int main()
{
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    cin>>n;
    if(n<=100000)
    {
        for(int i=1;i<=min((long long)9,n);i++)
            tmp=(tmp*10+i)%mod;
        for(int i=10;i<=min((long long)99,n);i++)
            tmp=(tmp*100+i)%mod;
        for(int i=100;i<=min((long long)999,n);i++)
            tmp=(tmp*1000+i)%mod;
        for(int i=1000;i<=min((long long)9999,n);i++)
            tmp=(tmp*10000+i)%mod;
        for(int i=10000;i<=min((long long)99999,n);i++)
            tmp=(tmp*100000+i)%mod;
        for(int i=100000;i<=min((long long)999999,n);i++)
            tmp=(tmp*1000000+i)%mod;
        cout<<tmp%mod;
        return 0;
    }
    f[0]=1;
    for(int i=1;i<=18;i++)f[i]=f[i-1]*10;
    a.h=1,a.l=3,a.data[1][1]=0;a.data[1][2]=1;a.data[1][3]=1;
    b.h=3,b.l=3,b.data[1][1]=1;b.data[1][2]=0;b.data[1][3]=0;
    b.data[2][1]=1;b.data[2][2]=1;b.data[2][3]=0;
    b.data[3][1]=0;b.data[3][2]=1;b.data[3][3]=1;
    for(int i=1;n>0;i++)
    {
        b.data[1][1]=f[i]%mod;
        if(f[i]==0)k=n;
        else k=min(n,f[i]-f[i-1]);
        c=ksm(b,k);
        a=multiply(a,c);
        n-=k;
    }
    cout<<a.data[1][1];
    return 0;
} 

贴个代码，当然，为了更加稳健，加了一个，if语句，考试技巧啊。。

不过，noipt1真的会考矩阵吗233（希望不是个flag）。。。

第二道题：

一道和中位数相关的题，求每个节点到根的路径中的所有数的中位数。。。

根据中位数定义，就是求树上的区间第k大。。。，由于是到根，自然而然就想到了用dfs序，我习惯用括号序列，就是入栈时插入一次，出栈时再插入一次。然后，第一次出现给它存入权值线段树中，然后get答案，第二次出现就弹出来。

#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#define N 100000
using namespace std;
int n,A[N+1],B[N+1],tmp[N+1],m;
int first[N+1],nex[2*N+1],to[2*N+1],siz;
int seq[2*N+1],cnt,x,y; 
int tot,f[N+1],k;
bool E[N+1];
struct Tree{
    int l;
    int r;
    int data;
};Tree T[N*4+1];
inline void add(int x,int y)
{
    nex[siz]=first[x];
    first[x]=siz;
    to[siz]=y;
    siz++;
}
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0,b=1;
    char c=nc();
    for(;!(c<='9'&&c>='0');c=nc())if(c=='-')b=-1;
    for(;c<='9'&&c>='0';c=nc())x=x*10+c-'0';
    return x*b;
}
void build(int rt,int l,int r)
{
    T[rt].l=l,T[rt].r=r;
    if(l==r)return;
    int mid=(l+r)/2;
    build(rt*2,l,mid),build(rt*2+1,mid+1,r);
}
void pushup(int rt)
{
    T[rt].data=T[rt*2].data+T[rt*2+1].data;
}
void modify(int rt,int pos,int val)
{
    if(T[rt].l==pos&&T[rt].r==pos)
    {
        T[rt].data+=val;
        return;
    }
    int mid=(T[rt].l+T[rt].r)/2;
    if(pos<=mid)modify(rt*2,pos,val);
    else modify(rt*2+1,pos,val);
    pushup(rt);
}
int find(int k)
{
    int pos=1;
    while(T[pos].l!=T[pos].r)
    {
        if(k<=T[pos*2].data)pos=pos*2;
        else k-=T[pos*2].data,pos=pos*2+1;
    }
    return T[pos].l;
}
inline void DFS(int x,int fa)
{
    seq[++cnt]=x;
    for(int i=first[x];i!=-1;i=nex[i])
    {
        int u=to[i];
        if(u==fa)continue;
        DFS(u,x);
    }
    seq[++cnt]=x;
}
int main()
{
    freopen("caculattree.in","r",stdin);
    freopen("caculattree.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)A[i]=read();
    for(int i=1;i<=n;i++)B[i]=A[i],tmp[i]=A[i];
    sort(tmp+1,tmp+n+1);
    m=unique(tmp+1,tmp+n+1)-tmp-1;
    for(int i=1;i<=m;i++)A[i]=tmp[i];
    for(int i=1;i<=n;i++)B[i]=lower_bound(tmp+1,tmp+m+1,B[i])-tmp;
    memset(first,-1,sizeof(first));
    for(int i=1;i<n;i++)
    {
        x=read(),y=read();
        add(x,y),add(y,x);
    }
    DFS(1,0);build(1,1,n);
    for(int i=1;i<=cnt;i++)
    {
        if(!E[seq[i]])
        {
            tot++;
            modify(1,B[seq[i]],1);
            E[seq[i]]=true;
            if(tot%2==0)k=tot/2;
            else k=tot/2+1;
            f[seq[i]]=find(k);
        }
        else modify(1,B[seq[i]],-1),tot--;
    }
    for(int i=1;i<=n;i++)printf("%d ",A[f[i]]);
    return 0;
} 

再次吐槽，这真的是t2吗。。。

天天爱跑步。。。

第三题：

一眼望去，就是一道状压dp的题。

但是，我不会呀233。

打个暴力就跑吧。。。
不愧是t3。。。

没有代码。。

等待了好久好久，途中吃了一顿火锅233。

成绩出来了，很稳呀，该拿的分都拿了。

这样的话，在SN弱省一等奖还是可以的吧。。。