首页 > 其他分享 >P7859 [COCI2015-2016#2] GEPPETTO

P7859 [COCI2015-2016#2] GEPPETTO

时间:2024-04-05 13:33:33浏览次数:23  
标签:now int 题解 P7859 who 代表 ans GEPPETTO 2016

原题链接

这真的是橙题吗

题解

读题,每个材料都有用或不用两种选择,然后n的数据范围也很小,所以考虑二进制dp (别管我为什么不叫状态压缩)
遍历 0 到 \(2^{20}-1\)(十进制下),如果存在互相矛盾的1,代表这个状态不能用

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,map<int,int> > q;
int check(int now)
{
    vector<int> food;
    for(int i=0;i<n;i++)
    {
        if((now>>i)&1) food.push_back(i+1);
    }

    for(int i=0;i<food.size();i++)
    {
        for(int j=i+1;j<food.size();j++)
        {
            if(q[food[i]][food[j]]) return 0;
        }
    }
    return 1;
}



int main()
{

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        q[x][y]=q[y][x]=1;
    }

    int ans=0;
    for(int i=0;i<(1<<n);i++) if(check(i)) ans++;
    cout<<ans<<endl;


    return 0;
}

题解2,据说二进制dp等于爆搜??

爆搜,搜索深度代表第 \(i\) 个材料要不要用,如果前面没有出现矛盾代表能用

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
int para[25]={0};
void dfs(int who,int now)//now中,0代表可以选,1代表选过了或者无法选
{
    if(who==n+1){ans++;return;}
    dfs(who+1,now);//代表不选当前材料
    if(!((1<<who)&now)) dfs(who+1,now|para[who]);
//为什么这里要判断who能不能选而不是para符不符合?因为二进制dp只能表示两种状态,选了和没法选是不一样的,因此我们统一把1变成无法选,0代表可以选
//这样一来只需要判断能不能选就行了
}

int main()
{

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        para[x]|=(1<<y);
        para[y]|=(1<<x);
    }

    for(int i=1;i<=n;i++) para[i]|=(1<<i);
    dfs(1,0);

    cout<<ans;
    return 0;
}

标签:now,int,题解,P7859,who,代表,ans,GEPPETTO,2016
From: https://www.cnblogs.com/pure4knowledge/p/18115681

相关文章

  • P2824 [HEOI2016/TJOI2016] 排序
    简要题意给定一个长度为\(n\)的排列\(a\),有\(m\)次操作:将\([l,r]\)从小到大排序将\([l,r]\)从大到小排序求\(m\)次操作后\(a_q\)的值。\(n,m\leq10^5\)思路首先这种排序的数据结构没有什么想法,根本原因是因为值太多了。但是我们观察到这是一个排列,这对于解......
  • P2831 [NOIP2016 提高组] 愤怒的小鸟
    思路状压+优化代码#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<cmath>#include<string.h>#defineR(x)x=read()#defineFor(i,j,n)for(inti=j;i<=n;++i)usingnamespac......
  • ES2016新特性
    ES2016新特性本次更新改变的内容比较少,仅仅新增了includes()方法和简化幂运算的写法。Array.prototype.includesincludes()方法用来判断一个数组是否包含一个指定的值,根据情况,如果包含则返回true,否则返回false。[1,2,3].includes(2);//true[1,2,3].includes(4);//......
  • Imagemagick 命令注入漏洞(CVE-2016-3714)
    Imagemagick命令注入漏洞(CVE-2016-3714)漏洞介绍漏洞名称:Imagemagick命令注入漏洞(CVE-2016-3714)漏洞定级:高危漏洞描述:ImageMagick在处理恶意构造的图片文件时,对于文件中的URL未经严格过滤,可导致命令注入漏洞。通过命令注入漏洞,黑客可以在服务器上执行任意系统命令,获取服务......
  • 蓝桥杯2016年第十三届省赛真题-生日蜡烛
    一、题目生日蜡烛.某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来,他一共吹熄了236根蜡烛。请问,他从多少岁开始过生日party的?请填写他开始过生日party的年龄数。注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字......
  • 代码审计[一] [0CTF 2016]piapiapia
    代码审计[一][0CTF2016]piapiapia对着登录框一顿乱注,发现都没什么效果,于是转向目录爆破。gobuster不知道为什么爆不了,只能用dirsearch来了dirsearch-u[url]-s1-t10爆到了一整个源码备份压缩包,下载后进行分析源码分析index.php对于html部分,可以见到是登录界面,......
  • 转: ltrace 是如何工作的(2016)
    http://arthurchiao.art/blog/how-does-ltrace-work-zh/strace 是一个系统调用,也是一个信号跟踪器(signaltracer),主要用于跟踪系统调用,打印系统调用的参数、返回值、时间戳等很多信息。也可以跟踪和打印进程收到的信号。在前一篇文章strace是如何工作的 中介绍过, strace ......
  • ISC2016训练赛-phrackCTF-Smali
    ISC2016训练赛-phrackCTFSmali:类型:Reverse**题目描述:都说学好Smali是学习Android逆向的基础,现在刚好有一个smali文件,大家一起分析一下吧~~**解题方法:将题目附件下载下来之后发现是一个.smali文件,将它放进jadx-gui里面进行一下反编译得到:packagenet.bluelotus.tomorrow.eas......
  • buuctf之pwn1_sctf_2016
    一、查看属性首先还是必要的查看属性环节:可以知道该文件是一个x86架构下的32位小段ELF程序我们可以先执行一下看看:二、静态分析扔到IDA中看一下,主函数没什么用,这里的vuln函数是必进的,我们进去看看vuln函数这个函数整体分析下来,我也看不太明白是干啥,看到了fgets函数,但......
  • ISC2016训练赛-phrackCTF-FindKey
    ISC2016训练赛——phrackCTFReverse-FindKey:题目描述:FLAG就是你输入的key解题方法:将题目附件下载下来是一个无后缀名的文件,把他放进exeinfope.exe里查看一下它的信息这里我们看到它不是一个EXE文件,但是下面有提示说是用python,然后我们将他的后缀名改成.py文件,用python打开是......