3

猫粮寸断 LV 10 @ 2019-10-18 19:52:37

//注意到病的数量只有十种，那所有患病的情况也不过1024种
//于是可以把患病的情况看成一个点，用二进制来表示，初始每一位全为1，最终状态为0
//而一种药相当于在两个点间连一条边权为1的边
//最后直接bfs一遍即可出答案
#include<cstdio>
using namespace std;
int yao[110][11],map[1100][1100],d[1100],minn[1100];
int main()
{
    int n,m,i,j,k,ha,head=1,tail=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
     for(j=0;j<n;j++)
      scanf("%d",&yao[i][j]);
    for(i=0;i<(1<<n);i++)
     for(j=1;j<=m;j++)
      {
        ha=i;
        for(k=0;k<n;k++)
        {
            if(yao[j][k]==1)
             ha=(ha|(1<<k))^(1<<k);
            if(yao[j][k]==-1)
             ha=ha|(1<<k);
        }
        if(i!=ha)
         map[i][ha]=1;
      }   
    d[1]=(1<<n)-1;
    while(head<=tail)
    {
        int now=d[head];
        for(i=0;i<(1<<n);i++)
         {
            if(map[now][i])
             if(!minn[i])
            {
                minn[i]=minn[now]+1;
                tail++;
                d[tail]=i;
            }
         }
         head++;
    }
    if(minn[0])
     printf("%d",minn[0]);
    else
     printf("The patient will be dead.");
    return 0;
}

3

PowderHan LV 10 @ 2017-05-07 12:57:21

/*
数据是不是太弱了一点
不管是直接bfs+hash(用vector保存)还是二进制+SPFA都是0ms秒杀？
也是醉了
学习了~再一次感受到了隐式图搜索的内涵
和补丁vs漏洞差不多的叭~
其实搜索和最短路从某种程度上来说
本质上是一样的吧
这里我用的是二进制+SPFA
首先我们理清楚二进制的问题
因为我们发现病情不过就是10种对吧
那么我们如果用一个vector来保存肯定是会更麻烦并且更慢的对叭~
那么我们可以直接二进制位运算一搞
一个状态s其每个有效位上的0或者1必然就是表示与其对应的疾病的有无
比如最低位为1表示第一种病是有的
那么我们可以用两个数组a[],b[]分别记录下药性
a[i]的二进制位上为1表示i这种药可以治愈对应的病
同理b[i]的二进制位上为1表示i这种药可以导致得对应的病
那么我们可以先预处理出a[] b[]
然后我们就以所有病都有的状态s为源点开始SPFA    有s=(1<<n)-1
关键是如何建立隐式图？
即如何从一个结点状态扩展到另一个状态?
这就涉及到我们的update操作了
很奇妙的位运算
具体也有注释了
最后说说心得叭~
其实感觉所有的bfs都可以转换为最短路来做
只不过是d[i]有的时候i无法表示一个状态
所以不太好做
而位运算就是一种强大的工具将两者连接了起来
算法真是奇妙>3<
QAQ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=12;
const int MAXM=105;
const int MAX=(1<<10)+5;
const int INF=(1<<30)-1;
queue<int> q;
bool in[MAX];   int d[MAX];//SPFA相关
int a[MAXM];//记录治愈药性
int b[MAXM];//记录毒性
int n,m;
int s;//初始状态

void init()
{
    int x;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        for(int j=0;j<n;j++)
        {
            cin>>x;
            if(x==1)
                a[i]|=(1<<j);
            else    if(x==-1)
                b[i]|=(1<<j);
        }
    s=(1<<n)-1; //初始时所有患病
    for(int i=0;i<=(1<<n)-1;i++)
        d[i]=INF;
}

inline int update(int x,int k)
{
    x&=(~a[k]);//a[k]取反之后不能治愈的变为了1,只有两个都为1才会患病
    x|=b[k];//有一个为1则这种病会患上
    return x;
}

void SPFA()
{
    d[s]=0; q.push(s);  in[s]=1;
    while(!q.empty())
    {
        int u=q.front();    in[u]=0;    q.pop();
        for(int i=1;i<=m;i++)
        {
            int v=update(u,i);
            if(d[v]>d[u]+1)
            {
                d[v]=d[u]+1;
                if(!in[v])
                    q.push(v),in[v]=1;
            }
        }
    }
    if(d[0]==INF)
        cout<<"The patient will be dead."<<endl;
    else
        cout<<d[0]<<endl;
}

int main()
{
    init();
    SPFA();
    return 0;
}

1

hetao8552981 LV 8 @ 2025-06-25 20:41:53

#include<bits/stdc++.h>
using namespace std;
int n,m,start,med[105][15],dis[2005]; 
queue<int>q;
int main(){
    scanf("%d%d",&n,&m);//病总数，药总数 
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&med[i][j]);
    for(int i=0;i<n;i++)
        start+=(1<<i);
    q.push(start);//开始时所有疾病都有，全是1
    while(!q.empty()){//开始广搜
        int now=q.front();
        q.pop();
        if(now==0){//没病了，成功
            printf("%d",dis[now]);
            return 0;
        }
        for(int i=1;i<=m;i++){//枚举所有药 
            int tmp=now;
            for(int j=1;j<=n;j++){
                if((tmp&(1<<(j-1)))!=0&&med[i][j])//可以治愈这种疾病，如果现在有，则减掉，否则没影响
                    tmp-=(1<<(j-1));
                if((tmp&(1<<(j-1)))==0&&med[i][j]==-1)//会染上这种疾病，如果现在没有，则加上，否则本来就有了。
                    tmp+=(1<<(j-1));
            }
            if(!dis[tmp]&&tmp!=start)//不是起点且未访问过，则标记距离病访问
                q.push(tmp),dis[tmp]=dis[now]+1;
        }
    }
    printf("The patient will be dead.");//不行
    return 0;
}

0

2023gdsy119 LV 7 @ 2024-01-24 11:37:41

传送门
我乃一介蒟蒻，若有错误或不详细的地方，请各位神犇指出~

洛谷原题

这题目也是非常的乱啊，特别是我做的时候是在我们学校集训队的网站做的，连数据范围和输入格式都没分开，我也是特别的无语啊……

我在这里将题目简化一下吧。简单来说，就是有 \(n(n≤10)\) 种病和 \(m(0<m≤100)\) 种药，每种药都会输入属性，对于每种药，输入它对于每种病的效果， \(-1\) 表示会导致得这种病，\(0\) 表示没有影响，\(1\) 表示可以治疗。每种药都可以使用无限次，求最少用多少药才能治疗所有疾病。

题目分析

我们使用“状态压缩”，用一个数存储目前状态，它的二进制是1时，即得了这种病，是0时，即没得这种病。使用BFS搜索，每次枚举所有药物，若未搜索过，则继续搜。具体将在注释中讲解。

众所周知，二进制数中的一个1在十进制中有不同的权值，这里我们使用位运算来进行操作。这里解释一下代码中的几个位运算，想了解更多的可以自行查找。

1<<x 即将这个数的二进制左移x位，而其实左移一位就代表着乘以2；
& 即与运算，和 if 中的与相同。代码中的 1<<(j-1) 将这种疾病转化成十进制的数，以便加减。而与运算是为了判断是否有这种疾病。

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,m,start,med[105][15],dis[2005]; 
queue<int>q;
int main(){
    scanf("%d%d",&n,&m);//病总数，药总数 
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&med[i][j]);
    for(int i=0;i<n;i++)
        start+=(1<<i);
    q.push(start);//开始时所有疾病都有，全是1
    while(!q.empty()){//开始广搜
        int now=q.front();
        q.pop();
        if(now==0){//没病了，成功
            printf("%d",dis[now]);
            return 0;
        }
        for(int i=1;i<=m;i++){//枚举所有药 
            int tmp=now;
            for(int j=1;j<=n;j++){
                if((tmp&(1<<(j-1)))!=0&&med[i][j])//可以治愈这种疾病，如果现在有，则减掉，否则没影响
                    tmp-=(1<<(j-1));
                if((tmp&(1<<(j-1)))==0&&med[i][j]==-1)//会染上这种疾病，如果现在没有，则加上，否则本来就有了。
                    tmp+=(1<<(j-1));
            }
            if(!dis[tmp]&&tmp!=start)//不是起点且未访问过，则标记距离病访问
                q.push(tmp),dis[tmp]=dis[now]+1;
        }
    }
    printf("The patient will be dead.");//不行
    return 0;
}

谢谢各位神犇的观看~

0

Diogenes LV 4 @ 2018-02-26 19:52:04

我是一只蒟蒻，说的不对欢迎大佬指正。
似乎没有人提出，治病的时候不会用两次同一种药。
证明：
1.连着用两次同种药是赤裸裸的浪费。
2.先用一次药，治好了某些病，过了一段时间又用了一次药。那么第一次的治疗是无效的，一段时间后再用药不会比原来差。

#include<bits/stdc++.h>
using namespace std;
int ans=1e9;
int n,m,a[110][110],q[(1<<12)+10];
bool v[110];
void search(int s,int f)//标准剪枝dfs
{
if(s==0){
if(f<ans) ans=f;
return;
}
if(f>=ans) return;
if(q[s]<=f) return;
else q[s]=f; 
int p=s;
for(int t=0;t<m;t++) if(v[t]){//v[t]记录是否用过这种药,用过则不用第二次
v[t]=false;
for(int i=0;i<n;i++){
if(a[t][i]==-1) s|=(1<<i);
if(a[t][i]==1 && s&(1<<i))
s^=(1<<i); 
}
if(s==0){
v[t]=true;
if(f+1<ans) ans=f+1;
return;
}
search(s,f+1);
v[t]=true;
s=p;
}
return;
}
int main()
{
scanf("%d",&n);
scanf("%d",&m);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
memset(v,true,sizeof(v));
memset(q,127,sizeof(q));
search((1<<(n))-1,0);
if(ans>0&&ans<1e6)
printf("%d\n",ans);
else printf("The patient will be dead.\n");
return 0;
}

0

Diogenes LV 4 @ 2018-02-26 19:41:43

我是一只蒟蒻，说的不对欢迎大佬指正。

似乎没有人提出，治病的时候不会用两次同一种药。

证明：
1.连着用两次同种药是赤裸裸的浪费。
2.先用一次药，治好了某些病，过了一段时间又用了一次药。那么第一次的治疗是无效的，一段时间后再用药与先用一次药状态一样。

#include<bits/stdc++.h>
using namespace std;
int ans=1e9;
int n,m,a[110][110],q[(1<<12)+10];
bool v[110];
void search(int s,int f)//标准的剪枝dfs，具体参见下方某题解
{
    if(s==0){
        if(f<ans) ans=f;
        return;
    }
    if(f>=ans) return;
    if(q[s]<=f) return;
    else q[s]=f; 
    int p=s;
    for(int t=0;t<m;t++) if(v[t]){//v[t]记录治病过程中此药是否用过
        v[t]=false;
        for(int i=0;i<n;i++){
            if(a[t][i]==-1) s|=(1<<i);
            if(a[t][i]==1 && s&(1<<i))
                s^=(1<<i); 
        }
        if(s==0){
            v[t]=true;
            if(f+1<ans) ans=f+1;
            return;
        }
        search(s,f+1);
        v[t]=true;
        s=p;
    }
    return;
}
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    memset(v,true,sizeof(v));
    memset(q,127,sizeof(q));
    search((1<<(n))-1,0);
    if(ans>0&&ans<1e6)
        printf("%d\n",ans);
    else printf("The patient will be dead.\n");
    return 0;
}

0

Diogenes LV 4 @ 2018-02-26 19:41:43

我是一只蒟蒻，说的不对欢迎大佬指正。

似乎没有人提出，治病的时候不会用两次同一种药。

证明：
1.连着用两次同种药是赤裸裸的浪费。
2.先用一次药，治好了某些病，过了一段时间又用了一次药。那么第一次的治疗是无效的，一段时间后再用药与先用一次药状态一样。

#include<bits/stdc++.h>
using namespace std;
int ans=1e9;
int n,m,a[110][110],q[(1<<12)+10];
bool v[110];
void search(int s,int f)//标准的剪枝dfs，具体参见下方某题解
{
    if(s==0){
        if(f<ans) ans=f;
        return;
    }
    if(f>=ans) return;
    if(q[s]<=f) return;
    else q[s]=f; 
    int p=s;
    for(int t=0;t<m;t++) if(v[t]){//v[t]记录治病过程中此药是否用过
        v[t]=false;
        for(int i=0;i<n;i++){
            if(a[t][i]==-1) s|=(1<<i);
            if(a[t][i]==1 && s&(1<<i))
                s^=(1<<i); 
        }
        if(s==0){
            v[t]=true;
            if(f+1<ans) ans=f+1;
            return;
        }
        search(s,f+1);
        v[t]=true;
        s=p;
    }
    return;
}
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    memset(v,true,sizeof(v));
    memset(q,127,sizeof(q));
    search((1<<(n))-1,0);
    if(ans>0&&ans<1e6)
        printf("%d\n",ans);
    else printf("The patient will be dead.\n");
    return 0;
}

0

Bill_Yang LV 10 @ 2017-06-11 12:23:40

1019的弱化版。。。
此题由于n<=10，而2^10=1024因此可以使用状态压缩
那么可以想到一个简单的搜索，每一次用一种药。
这样的搜索加上hash判重以及最优性剪枝速度是比较快的。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
int n,m,ans=0x7fffffff/2,Effect[105][25],Hash[2505];
void Dfs(int state,int ttime) {
    if(ttime>ans)return;
    if(Hash[state]<=ttime)return;
    Hash[state]=ttime;
    if(state==0) {
        ans=min(ans,ttime);
        return;
    }
    int nextstate;
    for(int i=1; i<=m; i++) {
        nextstate=state;
        for(int j=1; j<=n; j++)
            if((state&(1<<(j-1)))&&Effect[i][j]==-1)nextstate^=1<<(j-1);
            else if(!(state&(1<<(j-1)))&&Effect[i][j]==1)nextstate^=1<<(j-1);
        Dfs(nextstate,ttime+1);
    }
}
int main() {
    n=Get_Int();
    m=Get_Int();
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            Effect[i][j]=-Get_Int();
    memset(Hash,0x3f,sizeof(Hash));
    Dfs((1<<n)-1,0);
    if(ans==0x7fffffff/2)puts("The patient will be dead.");
    else printf("%d\n",ans);
    return 0;
}

仔细思考，这样的搜索本质其实与最短路没有区别。
将状态看作点，状态转移看作边，时间（1）是边权。
那么我们的hash判重其实就是spfa的inque数组，因此可以跑一遍最短路。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
struct Edge {
    int from,to,dist;
};
vector<Edge>edges[2505];
int dist[2505],inque[2505],n,m,Effect[105][25];
void AddEdge(int x,int y,int v) {
    edges[x].push_back((Edge) {
        x,y,v
    });
}
void Spfa(int s) {
    memset(dist,0x3f,sizeof(dist));
    queue<int>Q;
    Q.push(s);
    inque[s]=1;
    dist[s]=0;
    while(!Q.empty()) {
        int Now=Q.front();
        inque[Now]=0;
        Q.pop();
        for(int i=0; i<edges[Now].size(); i++) {
            Edge& e=edges[Now][i];
            int Next=e.to;
            if(dist[Now]+e.dist<dist[Next]) {
                dist[Next]=dist[Now]+e.dist;
                if(!inque[Next]) {
                    inque[Next]=1;
                    Q.push(Next);
                }
            }
        }
    }
}
int Get_Next(int state,int num) {
    int nextstate=state;
    for(int j=1; j<=n; j++)
        if((state&(1<<(j-1)))&&Effect[num][j]==-1)nextstate^=1<<(j-1);
        else if(!(state&(1<<(j-1)))&&Effect[num][j]==1)nextstate^=1<<(j-1);
    return nextstate;
} 
int main() {
    n=Get_Int();
    m=Get_Int();
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            Effect[i][j]=-Get_Int();
    for(int i=0; i<=(1<<n)-1; i++)
        for(int j=1; j<=m; j++)
            AddEdge(i,Get_Next(i,j),1);
    Spfa((1<<n)-1);
    if(dist[0]==0x3f3f3f3f)puts("The patient will be dead.");
    else printf("%d\n",dist[0]);
    return 0;
}

0

Antinomy LV 8 @ 2016-12-04 00:10:40

评测结果
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 636 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 576 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 580 KiB, score = 10
Accepted, time = 45 ms, mem = 636 KiB, score = 100

总觉得有情况没考虑到但还是AC了。。。
记忆化BFS

代码
c++ #include<iostream> #include<iomanip> #include<cstring> #include<vector> #include<sstream> #include<algorithm> #include<string> #include<cstdio> #include<math.h> #include<map> #include<cctype> #include<queue> #include<functional> #define maxn 350 #define INF 66666666 #define min(a,b) (a)>(b)?(b):(a) #define Mem(a,b) memset((a),(b),sizeof((a))) using namespace std; struct Node { vector<int> diss; int step; Node(vector<int> a, int b) :diss(a), step(b) {} Node(){} friend bool operator < (Node a, Node b) { return a.step > b.step; } }; map<vector<int>, int> mem; int n, m; int drug[110][20]; bool judge(const vector<int>& a){ for (int i = 1; i <= n; i += 1) if (a[i] != 0) return false; return true; } int main(){ cin >> n >> m; for (int i = 1; i <= m; i += 1) for (int j = 1; j <= n; j += 1) cin >> drug[i][j]; priority_queue<Node> Q; Node s(vector<int> (n+1,-1), 0),now; Q.push(s); while (!Q.empty()){ now = Q.top(); Q.pop(); for (int i = 1; i <= m; i += 1){ s = now; for (int j = 1; j <= n; j += 1){ s.diss[j] += drug[i][j]; if (s.diss[j] >= 1) s.diss[j] = 0; if (s.diss[j] < -1) s.diss[j] = -1; } if (mem.count(s.diss)==0) { if (!judge(s.diss)) { s.step += 1; mem[s.diss] = 1; Q.push(s); } else { cout << s.step + 1 << endl; return 0; } } } } cout << "The patient will be dead." << endl; return 0; }

0

lolix LV 8 @ 2016-11-01 23:16:17

#include <cstdio>
#include <queue>
#define add(a,k) a|=(1<<k)
#define INF 999999999

int n,m;
int b1[150]={0},b2[150]={0};

std::queue<int> q;
int dist[1111];
int inque[1111]={0};

void spfa(int u){
for(int i=0;i<1111;i++)
dist[i]=INF;
dist[u]=0;
q.push(u),inque[u]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=0;
for(int i=1;i<=m;i++){
int p=t;
p&=(~b1[i]),p|=b2[i];
if(dist[p]>dist[t]+1){
dist[p]=dist[t]+1;
if(!inque[p]){
q.push(p);
inque[p]=1;
}
}
}
}
}

int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int k;
for(int j=0;j<n;j++){
scanf("%d",&k);
if(k==1)
add(b1[i],j);
if(k==-1)
add(b2[i],j);
}
}
int start=(1<<n)-1;
spfa(start);
if(dist[0]==INF)
printf("The patient will be dead.");
else
printf("%d",dist[0]);
return 0;
}

0

HBat LV 8 @ 2016-10-02 15:43:29

// 广度搜索+hash
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int n;//n疾病个数
int m;//m药剂个数
int ill[101][11];//药剂详情
vector <int> peo;//患者
queue <int> que;//队列
queue < vector <int> > qra;//治疗情况
queue <int> ans;//药剂个数
vector <int> ptt;//患者临时表

bool a[2000];//哈希表

bool kot = true;

inline bool dpra()
{
for (int i = 1; i <= n; ++i)
if (qra.back()[i] == -1)return false;//判断是否有效，无效返回false
return true;
}

inline bool hashx()//哈希表，如果病症出现过，就不需要入队了
{
int i;
long long x = 1, sd = 0;
for (i = 1; i <= n; ++i)
{
sd += ptt[i] * x+100;
x *= 2;
}
if (a[sd])return true;
a[sd] = true;
return false;
}

int bfs()
{
int head = 0, tail = 1;
que.push(0);
ans.push(0);
qra.push(peo);
int i, j;
do
{
for (i = 1; i <= m; ++i)
{
ptt.resize(0);
if (que.front() == i)continue;
ptt.push_back(-1);
for (j = 1; j <= n; ++j)
{
switch (ill[i][j])
{
case 1:
ptt.push_back(0);
break;
case -1:
ptt.push_back(-1);
break;
default://case 0:
ptt.push_back(qra.front()[j]);
break;
}
}
if (hashx())continue;
que.push(i);
ans.push(ans.front() + 1);
qra.push(ptt);
if (dpra()) { cout << ans.back(); kot = false; return 0; }
++tail;
}
++head;
que.pop();
qra.pop();
ans.pop();
} while (head < tail);
return 0;
}

int main()
{
int i, j;
cin >> n >> m;//n疾病个数，m药剂个数
for (i = 0; i <= n; ++i)
peo.push_back(-1);
for (i = 1; i <= m; ++i)
for (j = 1; j <= n; ++j)
cin >> ill[i][j];
bfs();
if (kot)cout << "The patient will be dead.";
system("pause");
return 0;
}

Antinomy @ 2016-12-03 19:47:50

感谢dalao的思路

0

HBat LV 8 @ 2016-10-02 15:42:17

测试数据 #0: Accepted, time = 0 ms, mem = 584 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 588 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 592 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 588 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 588 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 588 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 584 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 588 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 588 KiB, score = 10
Accepted, time = 0 ms, mem = 592 KiB, score = 100

0

wuwangmao LV 8 @ 2016-09-17 22:18:11

发一个广搜+hash+二进制的代码
c++ #include<iostream> #include<cstdio> using namespace std; int n,m,ans=150; int tre[110][15]; int hash_[1050]={0}; int st[15],d[1050][15]={0}; int finish; int Hash_(int a[]){ int i,x=1,s=0; for(i=1;i<=n;i++){ s+=a[i]*x; x*=2; } return s; } void bfs(){ int i,j,head=1,tail=2; hash_[0]=1; finish=(1<<n)-1;//末态 while(head<tail){ for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(tre[i][j]==1) st[j]=1; else if(tre[i][j]==-1) st[j]=0; else st[j]=d[head][j];//如果无影响，则该病的状态为上次的状态 } int x=Hash_(st); if(!hash_[x]){ hash_[x]=1; for(j=1;j<=n;j++){ d[tail][j]=st[j];//记录下当前的每种病的状态； } d[tail][0]=d[head][0]+1;//加入队列中的状态由当前状态得到 tail++; } if(hash_[finish]){//如果当前已完成末态，则输出 cout<<d[tail-1][0];//注意是tail-1；因为tail++； return; } } head++; } cout<<"The patient will be dead."; } int main(){ freopen("in.txt","r",stdin); int i,j; scanf("%d %d",&n,&m); for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ scanf("%d",&tre[i][j]); } } bfs(); return 0; }

0

chronix LV 8 @ 2016-08-19 16:43:44

位运算+SPFA 和补丁vs错误很像
#include <cstdio>
#include <cstring>
#include <queue>
#define add(A,K) A|=1<<K

int n,m,st;
int A[110]={0},B[110]={0};

int update(int x,int way){
x&=(~A[way]);
x|=B[way];
return x;
}

std::queue<int> q;
int inque[1<<10+10]={0};
int dist[1<<10+10];

void spfa(){
dist[st]=0,q.push(st),inque[st]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=0;
for(int i=1;i<=m;i++){
int v=update(t,i);
if(dist[t]+1<dist[v]){
dist[v]=dist[t]+1;
if(inque[v]==0){
q.push(v);
inque[v]=1;
}
}
}
}
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
for(int j=0;j<n;j++){
int q;
scanf("%d",&q);
if(q==1)
add(A[i],j);
else if(q==-1)
add(B[i],j);
}
st=(1<<n)-1;
for(int i=0;i<=1<<10+5;i++)
dist[i]=99999999;
spfa();
if(dist[0]==99999999)
printf("Don't copy my code or you will get a WA!");
else
printf("%d",dist[0]);

return 0;
}

0

dkax LV 8 @ 2016-01-24 12:57:20

好吧。。。。我承认自己的代码比较蠢。。。但是对初学者还是可能有用的吧。。请求各位大神不要嘲笑我。。
#include<iostream>
#include<cmath>
using namespace std;
struct qu { bool sta[17];} ;
int n, m;//疾病种数，药剂数
int in[107][17];
qu now[2000000];
bool used[1030] = {0};
bool check(qu l)
{
for(int i = 1; i <= n; i++)
if(l.sta[i] == 0)
return 0;
return 1;
}
bool j(bool a, int b)//0代表有病，1代表没病
{
if(a == 1 && b == 1)
return 1;
if(a == 0 && b == -1)
return 0;
return a + b;
}
qu jia(int mm, qu l)
{
for(int i = 1; i <= n; i++)
l.sta[i] = j(l.sta[i], in[mm][i]);
return l;
}
int cnt = 0;
int find(qu l)
{
int k = 0;
for(int i = 1; i <= n; i++)
if(l.sta[i])
k += (int)pow(2, i - 1);
return k;
}
void bfs()
{
int head = 0, tail = 0;
for(int i = 1; i <= n; i++)
{
now[tail].sta[i] = 0;
}
while(head <= tail)
{
int cur = tail, x = 0;
for( ; head <= cur; head++)
{
for(int i = 1; i <= m; i++)
{
qu l = now[head];
l = jia(i, l);
int j = find(l);
if(check(l))
{
x = 1;
used[j] = 1;
}
else if(!used[j])
{
tail++;
used[j] = 1;
now[tail] = l;
}
}
}
cnt++;
if(x == 1)
break;
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
cin >> in[i][j];
bfs();
if(used[(int)pow(2, n) - 1])
cout << cnt;
else cout << "The patient will be dead.";
return 0;
}

0

starli LV 10 @ 2015-11-03 08:39:15

最简单的BFS 用一个int来记录当前情况每一位表示有没有患病
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct state{
int x,dis;
state(int x,int dis):x(x),dis(dis){}
};
queue<state> q;
int n,m,med[110][20],vis[2000],l,r;

int main(){
freopen("1026.in","r",stdin);freopen("1026.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++) scanf("%d",&med[i][j]);
int s=~0u>>(32-n);
q.push(state(s,0));vis[s]=true;
while(!q.empty()){
state t=q.front();q.pop();
for(int i=1;i<=m;i++){
int tmp=t.x;
for(int j=1;j<=n;j++)
if(med[i][j]== 1) tmp&=~(1<<(j-1));
else if(med[i][j]==-1) tmp|=(1<<(j-1));
if(tmp==0) {printf("%d",t.dis+1); return 0;}
else if(!vis[tmp]) q.push(state(tmp,t.dis+1)),vis[tmp]=true;
}
}
printf("The patient will be dead.");
return 0;
}

0

wang_yanheng LV 10 @ 2015-10-31 11:10:55

状态压缩的BFS，类似 P1019 和 P1197
数据范围很小，可以秒杀，估计把疾病数上升到20，药品数上升到200也是可以的

//vijos p1206
#include <stdio.h>
#define STATUS 0
#define STEP 1

int table[120][10];
short searched[1<<15];
int queue[1<<15][2];
int head, tail;

void addToQueue(int status, int step){
if(!searched[status]){
searched[status] = 1;
queue[tail][STATUS] = status;
queue[tail][STEP] = step;
tail++;
}
}
int bfs(int numIllness, int numDrug){
int status, step, i, j, tmp, target;
head = tail = 0;
target = (1<<numIllness) - 1; //all illnesses have been cured
addToQueue(0, 0); //all illnesses haven't been cured
while(head < tail){
status = queue[head][STATUS];
step = queue[head][STEP];
if(status == target)
return step;
for(i=0; i<numDrug; i++){
tmp = status;
for(j=0; j<numIllness; j++){
switch(table[i][j]){
case 1:
tmp |= (1<<j);
break;
case -1:
tmp &= (target^(1<<j));
}
}
addToQueue(tmp, step+1);
}
head++;
}
return -1;
}
int main(){
int numIllness, numDrug;
int i, j;

scanf("%d %d", &numIllness, &numDrug);
for(i=0; i<numDrug; i++){
for(j=0; j<numIllness; j++)
scanf("%d", &table[i][j]);
}
for(i=0; i<(1<<numIllness); i++)
searched[i] = 0;

i = bfs(numIllness, numDrug);
if(i < 0)
printf("The patient will be dead.\n");
else
printf("%d\n", i);

return 0;
}

0

dkfleet LV 10 @ 2015-01-24 18:32:53

把每个"得病状态"(得了哪些病,没得哪些病)当做节点.
总结点数不会超过2^n个.
如果状态i能通过吃一种药到达状态j,就连一条i到j的有向边
跑无权最短路就好了......
用位运算广搜秒掉了....
不用位运算的常数应该也可以承受....

0

Tunix LV 8 @ 2014-11-03 16:41:03

原来大神们都是用位运算的啊……我是渣渣，这里写一个非位运算的宽搜：倒着往前搜……
还是看代码吧，我加了注释，应该很好理解。

//Vijos 1026
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define r(i,j,n) for(int i=j;i<=n;++i)
#define pb push_back
using namespace std;
const int N=101;
//倒着搜：因为现在治不好的以后不知道什么时候可能能治好
//而倒着搜的话，只有现在能治好的病，过去才可以得
int n,m,a[N][11],b[220][11],Q[220],num[220];

void out(int x)
{
printf("this is %d\n",x);
r(i,1,n)
printf("%d ",b[x][i]);
cout <<endl;
}//debug

int main()
{
freopen("file.in","r",stdin);
// freopen("file.out","w",stdout);
scanf("%d%d",&n,&m);
int l=0,r=0;
r(i,1,m){
int sign=1;
r(j,1,n){
scanf("%d",&a[i][j]);
if (a[i][j]==-1) sign=0;
}
if (sign) { Q[r++]=i; num[r-1]=1; r(k,1,n) b[r-1][k]=a[i][k]; }
}

if (!r) {printf("The patient will be dead.\n"); return 0;}

while(l!=r){
bool check=1;
r(k,1,n) if (b[l][k]!=1){check=0;break;}
if (check) {printf("%d\n",num[l]);}
r(j,1,m){
if (j==Q[l]) continue;//刚刚吃过的药再吃没意义……
// out(l);
bool sign1=1,sign2=0;
r(k,1,n)
if (a[j][k]==-1 && b[l][k]!=1) {sign1=0;break;}//如果过去要得的病现在治不了，则不扩展
r(k,1,n)
if (a[j][k]==1 && b[l][k]==0) {sign2=1;break;}//如果对当前状态无增益（不能多治任何一种病）则不扩展
// cout <<sign1<<" "<<sign2<<endl;
if (sign1 && sign2) {
Q[r]=j;
num[r]=num[l]+1;//用的药的数量加一
r(k,1,n)
if(a[j][k]==1) b[r][k]=1;
else b[r][k]=b[l][k];//更新状态
r=(r+1)%200;//循环队列，队尾指针加一
// out(r-1);
bool check=1;
r(k,1,n) if (b[r-1][k]!=1){check=0;break;}
if (check) {printf("%d\n",num[r-1]); return 0;}//判断当前是否能治愈
}
}
l=(l+1)%200;//队首指针+1（循环队列）
}
printf("The patient will be dead.\n");
return 0;
}
//90

Tunix @ 2014-11-03 16:42:17

PS：那个队列的长度200是不够的，我就因为这个只得了90分……改长以后才AC的，一定要吸取教训啊！
循环队列如果空间允许千万不要抠门！！尽量多开

0

Tachibana LV 9 @ 2013-10-17 09:37:08

and 和 or 的优先级弄错了导致WA了4次- -、

var
n,m,way,i,zy,bzy,medicine,j,k,l,r : longint;
dis : array[0..1027] of longint;
q : array[0..10007] of longint;
vis : array[0..1027] of boolean;
map : array[0..1027,0..1027] of boolean;

begin
readln(n); readln(m);
way := (1<<n)-1;
for i := 1 to m do begin
zy := 0; bzy := way;
for j := 1 to n do begin
read(medicine);
if medicine=1 then zy := zy or (1<<(j-1)) else
if medicine=-1 then bzy := bzy and (not (1<<(j-1)));
end;
for k := 0 to way do
map[k,(k or zy) and bzy] := true;
end;
l := 1; r := 1; q[1] := 0; dis[0] := 0; vis[0] := true;
while l<=r do begin
k := q[l];
for i := 0 to way do
if (map[k,i])and(not vis[i]) then begin
inc(r); q[r] := i; dis[i] := dis[k]+1; vis[i] := true;
end;
inc(l);
end;
if dis[way]=0 then writeln('The patient will be dead.') else writeln(dis[way]);
end.

题解

150 条题解

题目分析

完整代码

毒药？解药？

信息

状态

开发

支持

题解

150 条题解

题目分析

完整代码

毒药？解药？

信息

状态

开发

支持

还没有账户？

登录