2017.08.05【NOIP提高组】模拟赛B组总结

好久没写过比赛总结了~
今天的比赛真是难~比赛的时候160分：100+30+30=160分。
下面就每题总结一下吧：
T1：袁绍的刁难(recruitment.pas/cpp)
http://172.16.0.132/senior/#contest/show/2065/0
比赛是就A了，这说明还是很水的，我这个蒟蒻~
其实，我用了一种比较笨的方法，dfs，这里就不介绍了。
后来我才发现，其实只用把k转成2进制，再转成把每个有1的放转成3的次方，就好了。

var
        i,n,k:longint;
function find(k:longint):int64;
var
        i,m,j:longint;
        ans,l:int64;
begin
        m:=0;
        if k=1 then exit(1);
        l:=1;
        while k-l>0 do
        begin
                k:=k-l;
                inc(m);
                l:=l*2;
        end;
        dec(k);
        ans:=1;
        for j:=1 to m do
                ans:=ans*3;
        if k=0 then exit(ans)
        else exit(find(k)+ans);
end;
begin
        assign(input,'recruitment.in');reset(input);
        assign(output,'recruitment.out');rewrite(output);
        readln(n);
        for i:=1 to n do
        begin
                readln(k);
                writeln(find(k));
        end;
        close(input);
        close(output);
end.

T2：【NOIP2017模拟A组模拟8.5】队伍统计
http://172.16.0.132/senior/#contest/show/2065/1
这是一道状压dp题，我们设f[s][i]表示状态为s，违反了i条规则的总方案数。
再加个优化，就好了。

#include<cstdio>
#include<iostream>
using namespace std;
int f[1048577][21],u,v,n,m,k,b[1048577],fal[21];
void dfs(int x,int y,int z);
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        fal[u]+=1<<(v-1);   
    }
    dfs(1,0,0);
    f[0][0]=1;
    int l;
    for (int s=1;s<1<<n;++s)
    {
        for (int j=1;j<=n;++j)
            if ((1<<(j-1))&s) 
            {       
                for (int i=b[s&fal[j]];i<=k;++i)
                    f[s][i]=(f[s][i]+f[s-(1<<(j-1))][i-b[(s&fal[j])]])%1000000007;
            }
    }
    int ss=(1<<n)-1,ans=0;
    for (int i=0;i<=k;++i)
        ans=(ans+f[ss][i])%1000000007;
    printf("%d\n",ans); 
}
void dfs(int x,int y,int z)
{
    if(x>n)
    {
        b[z]=y;
        return;
    }
    dfs(x+1,y,z);
    dfs(x+1,y+1,z+(1<<(x-1)));
}

T3：【NOIP2017模拟A组模拟8.5】序列问题
http://172.16.0.132/senior/#contest/show/2065/2
分治问题，dg进去，每次分开两个部分，mid的右边和左边。右边预处理，左边枚举，用指针，于是就可以过啦。

const
        mo=1000000007;
var
        n,m,i,j:longint;
        a:array[0..500000]of int64;
        min_r,max_r,smax,smin,sans:array[0..500000]of int64;
function max(x,y:int64):int64;
begin
        if x>y then exit(x);
        exit(y);
end;
function min(x,y:int64):int64;
begin
        if x<y then exit(x);
        exit(y);
end;
function find(l,r:longint):int64;
var
        i,x,y,j,m:longint;
        p,q,mid,ans,minl,maxl:int64;
begin
        if l=r then
        begin
                ans:=(a[l]*a[r]) mod mo;
                exit(ans);
        end;
        mid:=(l+r)div 2;
        ans:=(find(l,mid)+find(mid+1,r)) mod mo;
        max_r[mid]:=0;
        smin[mid]:=0;
        min_r[mid]:=maxlongint;
        sans[mid]:=0;
        smax[mid]:=0;
        for i:=mid+1 to r do
        begin
                if a[i]>max_r[i-1] then max_r[i]:=a[i] else max_r[i]:=max_r[i-1];
                smin[i]:=(smin[i-1]+max_r[i])mod mo;
                if a[i]<min_r[i-1] then min_r[i]:=a[i] else  min_r[i]:=min_r[i-1];
                sans[i]:=(sans[i-1]+min_r[i])mod mo;
                smax[i]:=(smax[i-1]+max_r[i]*min_r[i])mod mo;
        end;
        minl:=maxlongint;
        maxl:=0;
        for i:=mid downto l do
        begin
                minl:=min(minl,a[i]);
                maxl:=max(maxl,a[i]);
                x:=mid+1;
                y:=r;
                while x<y do
                begin
                        m:=(x+y)div 2;
                        if max_r[m]>maxl then y:=m
                        else x:=m+1;
                end;
                p:=x;
                x:=mid+1;
                y:=r;
                while x<y do
                begin
                        m:=(x+y)div 2;
                        if min_r[m]<minl then y:=m
                        else x:=m+1;
                end;
                q:=x;
                if max_r[r]<=maxl then
                begin
                        if min_r[r]>=minl then
                        begin
                                ans:=(ans+(maxl*minl mod mo)*(r-mid))mod mo;
                        end
                        else
                        begin
                                ans:=(ans+(maxl*minl mod mo)*(q-1-mid))mod mo;
                                ans:=(ans+maxl*(sans[r]-sans[q-1]+mo)) mod mo;
                        end;
                        continue;
                end;
                if min_r[r]>=minl then
                begin
                        ans:=(ans+(maxl*minl mod mo)*(p-1-mid))mod mo;
                        ans:=(ans+(smin[r]-smin[p-1]+mo)*minl)mod mo;
                        continue;
                end;
                if p<q then
                begin
                        ans:=(ans+(minl*maxl mod mo)*(p-1-mid)) mod mo;
                        ans:=(ans+(smin[q-1]-smin[p-1]+mo)*minl) mod mo;
                        ans:=(ans+smax[r]-smax[q-1]+mo)mod mo;
                end;
                if q<p then
                begin
                        ans:=(ans+(minl*maxl mod mo)*(q-1-mid))mod mo;
                        ans:=(ans+(sans[p-1]-sans[q-1]+mo)*maxl)mod mo;
                        ans:=(ans+smax[r]-smax[p-1]+mo)mod mo;
                end;
        end;
        exit(ans);
end;
begin
        assign(input,'seq.in');reset(input);
        assign(output,'seq.out');rewrite(output);
        readln(n);
        for i:=1 to n do
                read(a[i]);
        writeln(find(1,n));
        close(input);
        close(output);
end.