欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-18 23:08:04
...

好久没写过比赛总结了~
今天的比赛真是难~比赛的时候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.