Contest2156 - 2019-3-7 高一noip基础知识点 测试2

传送门

预计得分:100+70+100+50=320

实际得分100+63+77+30=270

Ctrl_C+Ctrl_V时不要粘贴翻译的,直接粘原文,

In a single line of the output print an integer — the maximum loyalty among all paths from the first node to the n-th one. If such paths do not exist or the maximum loyalty equals 0, print in a single line "Nice work, Dima!" without the quotes. 输出能从1出发到n的总数值数,如果没有,输出“Nice work,Dima!”
两个判错之间在逗号前差了一个空格 QAQ

 

T1

dfs+剪枝

对于搜到的一组(a,b,c),将a*t^2+b*t+1(t>=20)标记,下一次再经过时就直接return

代码

Contest2156 - 2019-3-7 高一noip基础知识点 测试2
#include<bits/stdc++.h>
using namespace std;
int n,k;
int numa,numb,numc,ans[100100],cnt;
int vis[100100];
bool sum[100100],pd;
inline int getsum(int a,int b,int c){return a*441+b*21+c;}
void dfs(int deep,int a,int b,int c)
{
    if(a>numa||b>numb||c>numc)return;
    //cout<<a<<"!"<<b<<"!"<<c<<endl;system("pause");
    sum[a*441+b*21+c]=1;
    if(!a)
    {
        if(!vis[c])ans[++cnt]=c;
        //cout<<c<<endl;
        vis[c]=1;   
    }
    if(a)
    {
        int k=getsum(0,a+b,c),kk=getsum(a+b-numb,numb,c);
        if(a+b<=numb&&!sum[k])sum[k]=1,dfs(deep+1,0,a+b,c);
        else
        {
            if(!sum[kk]&&a+b>numb) sum[kk]=1,dfs(deep+1,a+b-numb,numb,c);
        }
        k=getsum(0,b,a+c);kk=getsum(a+c-numc,b,numc);
        if(a+c<=numc&&!sum[k])sum[k]=1,dfs(deep+1,0,b,a+c);
        else
        {
            if(!sum[kk]&&a+c>numc) sum[kk]=1,dfs(deep+1,a+c-numc,b,numc);
        }
    }
    if(b)
    {
        int k=getsum(a+b,0,c),kk=getsum(numa,a+b-numa,c);
        if(a+b<=numb&&!sum[k])sum[k]=1,dfs(deep+1,a+b,0,c);
        else
        {
            if(!sum[kk]&&a+b>numa)sum[kk]=1,dfs(deep+1,numa,a+b-numa,c);
        }
        k=getsum(a,0,b+c);kk=getsum(a,b+c-numc,numc);
        if(b+c<=numc&&!sum[k])sum[k]=1,dfs(deep+1,a,0,b+c);
        else
        {
            if(!sum[kk]&&b+c>numc) sum[kk]=1,dfs(deep+1,a,b+c-numc,numc);
        }
    }
    if(c)
    {
        int k=getsum(a+c,b,0),kk=getsum(numa,b,a+c-numa);
        if(a+c<=numa&&!sum[k])sum[k]=1,dfs(deep+1,a+c,b,0);
        else
        {
            if(!sum[kk]&&a+c>numa) sum[k]=1,dfs(deep+1,numa,b,a+c-numa);
        }
        k=getsum(a,b+c,0);kk=getsum(a,numb,b+c-numb);
        if(b+c<=numb&&!sum[k])sum[k]=1,dfs(deep+1,a,b+c,0);
        else
        {
            if(!sum[kk]&&b+c>numb) sum[kk]=1,dfs(deep+1,a,numb,b+c-numb);
        }
    }
}
int main()
{
    scanf("%d%d%d",&numa,&numb,&numc);
    dfs(1,0,0,numc);
    sort(ans+1,ans+cnt+1);
    for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);
}
T1

 

T2

容易想到区间一定是连续的

但是这种容易想到的一般都是错的

例如数据

3 3

1 2 1 2

2 3 1 10000

1 2 7 8

显然区间不是连续的。

于是,我们的思路是枚举下界,二分上界,用dfs或是并查集维护1-n的连通

dfs太难打了,david-alwal太懒了,所以用了并查集

Contest2156 - 2019-3-7 高一noip基础知识点 测试2
#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int from,to,nxxt,le,ri;
}e[100100<<1];
int head[100100],n,m,cnt,t,maxx=-1,ans;
inline void addedge(int u,int v,int l,int r)
{
    cnt++;
    e[cnt].from=u;
    e[cnt].le=l;
    e[cnt].ri=r;
    e[cnt].to=v;
    e[cnt].nxxt=head[u];
    head[u]=cnt;
}
int lef[100100],num;
int f[100100];
int getroot(int x){if(x!=f[x])f[x]=getroot(f[x]);return f[x];}
inline int check(int l,int r)
{
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=cnt;i++)
    {
        int from=e[i].from,to=e[i].to;
        int le=e[i].le,ri=e[i].ri;
        if(le<=l&&ri>=r)
        {
            int f1=getroot(from);
            int f2=getroot(to);
            if(f1!=f2)f[f1]=f2;
        }
    }
    if(getroot(1)==getroot(n))return 1;return 0;
}
void ef(int l,int r,int k)
{
    if(l==r)
    {
        while(k<=l&&check(k,l)==0)l--;
        ans+=l-k+1;
        if(l>=k)
            t=max(t,l);
        return;
    }
    int mid=(l+r)>>1;
    if(check(k,mid+1))ef(mid+1,r,k);
    else ef(l,mid,k);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,l,r;
        scanf("%d%d%d%d",&u,&v,&l,&r);
        addedge(u,v,l,r);
        addedge(v,u,l,r);
        lef[++num]=l;
        maxx=max(maxx,r);
    }
    sort(lef+1,lef+num+1);
    for(int i=1;i<=num;i++)
    {
        if(lef[i]<=t)continue;
        else ef(lef[i],maxx,lef[i]);
    }
    if(ans<=0)puts("Nice work, Dima!");
    else printf("%d",ans);
}
T2

 

T3

个人认为是最简单的一道题

一个BFS就可以解决

下标不能为负数!!

上代码

Contest2156 - 2019-3-7 高一noip基础知识点 测试2
#include<bits/stdc++.h>
using namespace std;
int n,k;
queue<int>q;
int num[500100],vis[500100];
int maxx;
int main()
{
    scanf("%d%d",&n,&k);
    //if(n>=k){printf("%d",n-k);return 0;}
    maxx=max(n,k)<<1;
    q.push(n);
    vis[n]=1;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        if(now==k)break;
        if((!vis[now+1])&&(now+1<maxx))
        {
            num[now+1]=num[now]+1;
            vis[now+1]=1;
            q.push(now+1);
        }
        if((!vis[now<<1])&&((now<<1)<maxx))
        {
            num[now<<1]=num[now]+1;
            vis[now<<1]=1;
            q.push(now<<1);
        }
        if((!vis[now-1])&&(now-1>=0))
        {
            num[now-1]=num[now]+1;
            vis[now-1]=1;
            q.push(now-1);
        }
    }
    printf("%d",num[k]);
}
T3

T4

dfs+剪枝

剪枝1:,可行性剪枝:对于一个点(x,y),如果它左上角的颜色加上它走到底下的格子数大于k,就return 0

剪枝2,对称性剪枝:例如我们当前填到了某个格子,我们记录一下整个矩阵已使用的颜色,例如3,5都还没用,那么这个格子填上3或5,两者最终算出的方案数是相同的,这样我们就可以只计算3的方案数,5的直接加上3的就可以了。

用状压存状态特别方便

没有单独讲状态压缩的博客,只有讲状压DP的,大家就只看状压那部分的吧 详解状压 David-alwal太懒了

上代码

Contest2156 - 2019-3-7 高一noip基础知识点 测试2
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int m,n,k,a[101][101],f[101][101],num[101];
//f数组存状压之后的状态,例如5个颜色,f[x][y]=13的话, 
//因为13(10)=01101(2),这就代表了(x,y)左上角的点取了2,3,5,没有取1,4 
int dfs(int x,int y)
{
    if(y>m)x++,y=1;
    if(x>n)return 1;
    int ret=0,d=-1,now=f[x-1][y]|f[x][y-1],c=0;
    for(int i=now;i;i-=i&-i)c++;
    if(m+n-x-y+1>k-c)return 0;//剪枝1 
    int can=(~now)&((1<<k)-1);//能取的 
    for(int i=can;i;i-=i&(-i))//提取每一位二进制 
    {
        int temp=i&(-i);
        int t=log(temp+0.5)/log(2)+1;
        if(a[x][y]==0||a[x][y]==t)
        {
            f[x][y]=now|temp;
            num[t]++;
            if(num[t]==1)//剪枝2 
            {
                if(d==-1)d=dfs(x,y+1);
                ret+=d;
            }
            else ret+=dfs(x,y+1);
            ret%=mod;
            num[t]--;
        }
    }
    return ret;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if(n+m-1>k){puts("0");return 0;}//剪枝1 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j])num[a[i][j]]++;//统计数量 
        }
    printf("%d",dfs(1,1)%mod);
}
T4

 

上一篇:c – 使用HWLOC的NUMA系统的realloc()


下一篇:安装Mosquitto学习MOTT协议