[水题]大众比萨

2018-10-25 15:47

981

基本算法,进制压缩/位图

156 字

1 分钟内

一道水题，觉得用了点小技巧就放上来了。

首先是读入，前些天看了本省rank1的NOIP2017时间复杂度的代码，%%%全省最短（100分里面），读入用的是自定义的快读。说实话，以后字符串读入都用这种方式就好了，挺方便的。

还有就是用二进制表示状态，前几天考试也是靠这个骗了80分，最近还学了“位图”这种神奇的东西，感觉整个人都二进制了。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
bool jud[1<<17];
struct person{
    int a,b;
}p[25];
int t;
int f;

inline int read(){
    char ch='+';f=1;
    while(!isalpha(ch)){if(ch=='-')f=-1;if(ch==';')return inf;if(ch=='.')return -inf;ch=getchar();}
    return (ch-'A');
}


bool judge(int sta){
    for(int i=1;i<t;i++){
        if((sta&p[i].a)||(~sta)&p[i].b)continue;
        return 0;
    }
    return 1;
}

void out(int sta){
    printf("Toppings: ");
    int k=0;
    while(sta){
        if(sta&1)printf("%c",k+'A');
        k++;
        sta>>=1;
    }
}

int main(){
    t=1;
    while(1){
        int tmp=read();
        if(tmp==inf){t++;continue;}
        if(tmp==-inf)break;
        if(f==-1)p[t].b|=(1<<(tmp));
        else p[t].a|=(1<<tmp);
    }
    for(int i=0;i<=(1<<16);i++){
        if(judge(i)){
            out(i);
            return 0;
        }
    }
    printf("No pizza can satisfy these requests.");
    return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

const int inf=0x3f3f3f3f;

bool jud[1<<17];

struct person{

int a,b;

}p[25];

int t;

int f;

inline int read(){

char ch='+';f=1;

while(!isalpha(ch)){if(ch=='-')f=-1;if(ch==';')return inf;if(ch=='.')return -inf;ch=getchar();}

return (ch-'A');

}

bool judge(int sta){

for(int i=1;i<t;i++){

if((sta&p[i].a)||(~sta)&p[i].b)continue;

return 0;

}

return 1;

}

void out(int sta){

printf("Toppings: ");

int k=0;

while(sta){

if(sta&1)printf("%c",k+'A');

k++;

sta>>=1;

}

int main(){

t=1;

while(1){

int tmp=read();

if(tmp==inf){t++;continue;}

if(tmp==-inf)break;

if(f==-1)p[t].b|=(1<<(tmp));

else p[t].a|=(1<<tmp);

}

for(int i=0;i<=(1<<16);i++){

if(judge(i)){

out(i);

return 0;

}

printf("No pizza can satisfy these requests.");

return 0;

}

二进制

Lxp_Mike

6年前

2018-10-25 21:11:55

#include 
#include 
#include 
#include 
#include 
#define MAXN 107
using namespace std;

struct node{
    int YES,NO;
}peo[MAXN];
int tot=1,MAX;

inline void read(){
    char ch=getchar();
    while(ch!='.'){
        if(ch=='+'){ch=getchar(),peo[tot].YES|=(1&lt;&lt;(ch-'A')),MAX=max(MAX,ch-'A');}
        else if(ch=='-'){ch=getchar(),peo[tot].NO|=(1&lt;&lt;(ch-'A')),MAX=max(MAX,ch-'A');}
        else if(ch==';') ++tot;
        ch=getchar();
    }
    --tot;
}

inline void out(int x){
    printf("Toppings: ");
    for(int i=0;i&lt;MAX;++i){
        if((x&gt;&gt;i)&amp;1) printf("%c",'A'+i);
    }
}

inline bool jud(int x){
    for(int i=1;i&lt;=tot;++i){
        if((!(peo[i].YES&amp;x))&amp;&amp;(!(peo[i].NO&amp;(~x)))) return 0;
    }
    return 1;
}

inline void solve(){
    int up=(1&lt;&lt;(++MAX));
    for(int i=0;i&lt;up;++i){
        if(jud(i)){out(i);return;}
    }
    puts("No pizza can satisfy these requests.");
}

int main(){
    read();
    solve();
    return 0;
}

#include

#define MAXN 107

using namespace std;

struct node{

int YES,NO;

}peo[MAXN];

int tot=1,MAX;

inline void read(){

char ch=getchar();

while(ch!='.'){

if(ch=='+'){ch=getchar(),peo[tot].YES|=(1<<(ch-'A')),MAX=max(MAX,ch-'A');}

else if(ch=='-'){ch=getchar(),peo[tot].NO|=(1<<(ch-'A')),MAX=max(MAX,ch-'A');}

else if(ch==';') ++tot;

ch=getchar();

}

--tot;

}

inline void out(int x){

printf("Toppings: ");

for(int i=0;i<MAX;++i){

if((x>>i)&1) printf("%c",'A'+i);

}

inline bool jud(int x){

for(int i=1;i<=tot;++i){

if((!(peo[i].YES&x))&&(!(peo[i].NO&(~x)))) return 0;

}

return 1;

}

inline void solve(){

int up=(1<<(++MAX));

for(int i=0;i<up;++i){

if(jud(i)){out(i);return;}

}

puts("No pizza can satisfy these requests.");

}

int main(){

read();

solve();

return 0;

}

Lxp_Mike

6年前

2018-10-25 21:12:51

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define MAXN 107
using namespace std;

struct node{
    int YES,NO;
}peo[MAXN];
int tot=1,MAX;

inline void read(){
    char ch=getchar();
    while(ch!='.'){
        if(ch=='+'){ch=getchar(),peo[tot].YES|=(1<<(ch-'A')),MAX=max(MAX,ch-'A');}
        else if(ch=='-'){ch=getchar(),peo[tot].NO|=(1<<(ch-'A')),MAX=max(MAX,ch-'A');}
        else if(ch==';') ++tot;
        ch=getchar();
    }
    --tot;
}

inline void out(int x){
    printf("Toppings: ");
    for(int i=0;i<MAX;++i){
        if((x>>i)&1) printf("%c",'A'+i);
    }
}

inline bool jud(int x){
    for(int i=1;i<=tot;++i){
        if((!(peo[i].YES&x))&&(!(peo[i].NO&(~x)))) return 0;
    }
    return 1;
}

inline void solve(){
    int up=(1<<(++MAX));
    for(int i=0;i<up;++i){
        if(jud(i)){out(i);return;}
    }
    puts("No pizza can satisfy these requests.");
}

int main(){
    read();
    solve();
    return 0;
}

/*
+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.
*/