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:=;
        if k= then exit();
        l:=;
        while k-l> do
        begin
                k:=k-l;
                inc(m);
                l:=l*;
        end;
        dec(k);
        ans:=;
        for j:= to m do
                ans:=ans*;
        if k= 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:= 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[][],u,v,n,m,k,b[],fal[];
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=;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        fal[u]+=<<(v-);   
    }
    dfs(,,);
    f[][]=;
    int l;
    for (int s=;s<<<n;++s)
    {
        for (int j=;j<=n;++j)
            if ((<<(j-))&s) 
            {       
                for (int i=b[s&fal[j]];i<=k;++i)
                    f[s][i]=(f[s][i]+f[s-(<<(j-))][i-b[(s&fal[j])]])%;
            }
    }
    int ss=(<<n)-,ans=;
    for (int i=;i<=k;++i)
        ans=(ans+f[ss][i])%;
    printf("%d\n",ans); 
}
void dfs(int x,int y,int z)
{
    if(x>n)
    {
        b[z]=y;
        return;
    }
    dfs(x+,y,z);
    dfs(x+,y+,z+(<<(x-)));
}
           

T3：【NOIP2017模拟A組模拟8.5】序列問題

http://172.16.0.132/senior/#contest/show/2065/2

分治問題，dg進去，每次分開兩個部分，mid的右邊和左邊。右邊預處理，左邊枚舉，用指針，于是就可以過啦。

const
        mo=;
var
        n,m,i,j:longint;
        a:array[..]of int64;
        min_r,max_r,smax,smin,sans:array[..]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 ;
        ans:=(find(l,mid)+find(mid+,r)) mod mo;
        max_r[mid]:=;
        smin[mid]:=;
        min_r[mid]:=maxlongint;
        sans[mid]:=;
        smax[mid]:=;
        for i:=mid+ to r do
        begin
                if a[i]>max_r[i-] then max_r[i]:=a[i] else max_r[i]:=max_r[i-];
                smin[i]:=(smin[i-]+max_r[i])mod mo;
                if a[i]<min_r[i-] then min_r[i]:=a[i] else  min_r[i]:=min_r[i-];
                sans[i]:=(sans[i-]+min_r[i])mod mo;
                smax[i]:=(smax[i-]+max_r[i]*min_r[i])mod mo;
        end;
        minl:=maxlongint;
        maxl:=;
        for i:=mid downto l do
        begin
                minl:=min(minl,a[i]);
                maxl:=max(maxl,a[i]);
                x:=mid+;
                y:=r;
                while x<y do
                begin
                        m:=(x+y)div ;
                        if max_r[m]>maxl then y:=m
                        else x:=m+;
                end;
                p:=x;
                x:=mid+;
                y:=r;
                while x<y do
                begin
                        m:=(x+y)div ;
                        if min_r[m]<minl then y:=m
                        else x:=m+;
                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--mid))mod mo;
                                ans:=(ans+maxl*(sans[r]-sans[q-]+mo)) mod mo;
                        end;
                        continue;
                end;
                if min_r[r]>=minl then
                begin
                        ans:=(ans+(maxl*minl mod mo)*(p--mid))mod mo;
                        ans:=(ans+(smin[r]-smin[p-]+mo)*minl)mod mo;
                        continue;
                end;
                if p<q then
                begin
                        ans:=(ans+(minl*maxl mod mo)*(p--mid)) mod mo;
                        ans:=(ans+(smin[q-]-smin[p-]+mo)*minl) mod mo;
                        ans:=(ans+smax[r]-smax[q-]+mo)mod mo;
                end;
                if q<p then
                begin
                        ans:=(ans+(minl*maxl mod mo)*(q--mid))mod mo;
                        ans:=(ans+(sans[p-]-sans[q-]+mo)*maxl)mod mo;
                        ans:=(ans+smax[r]-smax[p-]+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:= to n do
                read(a[i]);
        writeln(find(,n));
        close(input);
        close(output);
end.