记录信息

评测状态 Accepted
题目 P1864 起床困难综合症
递交时间 2015-12-06 23:19:33
代码语言 C++
评测机 VijosEx
消耗时间 558 ms
消耗内存 1060 KiB
评测时间 2015-12-06 23:19:35

评测结果

编译成功

测试数据 #0: Accepted, time = 31 ms, mem = 1060 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 1060 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 1060 KiB, score = 10

测试数据 #3: Accepted, time = 93 ms, mem = 1056 KiB, score = 10

测试数据 #4: Accepted, time = 62 ms, mem = 1056 KiB, score = 10

测试数据 #5: Accepted, time = 78 ms, mem = 1056 KiB, score = 10

测试数据 #6: Accepted, time = 46 ms, mem = 1056 KiB, score = 10

测试数据 #7: Accepted, time = 78 ms, mem = 1056 KiB, score = 10

测试数据 #8: Accepted, time = 62 ms, mem = 1056 KiB, score = 10

测试数据 #9: Accepted, time = 93 ms, mem = 1056 KiB, score = 10

Accepted, time = 558 ms, mem = 1060 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

inline int read()
{
int x = 0 , f = 1; char ch = getchar();
while( ch < '0' || ch > '9' ){ if( ch == '-' ) f = -1; ch = getchar(); }
while( ch >= '0' && ch <= '9' ){ x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}

int n , m;
char s[5];
int a[100000 + 2] , b[100000 + 2] , temp , able[40] , now , ans;

inline int cal( int x )
{
for( register int i = 1 ; i <= n ; i++ )
if( a[i] == 1 ) x &= b[i];
else if( a[i] == 2 ) x |= b[i];
else x ^= b[i];
return x;
}

int main()
{
n = read() , m = read();
for( register int i = 1 ; i <= n ; i++ )
{
scanf( "%s" , s ) , b[i] = read();
if( s[0] == 'A' ) a[i] = 1;
else if( s[0] == 'O' ) a[i] = 2;
else a[i] = 3;
}
for( register int i = 0 ; i <= 30 ; i++ ) able[i] = cal( 1 << i ) & ( 1 << i );
temp = cal( 0 );
for( register int i = 30 ; i >= 0 ; i-- )
if( ( 1 << i ) & temp ) ans += ( 1 << i );
else if( now + ( 1 << i ) <= m && able[i] )
now += ( 1 << i ) , ans += ( 1 << i );
cout << ans << endl;
return 0;
}

绝世傻题！！！
按位贪心即可
此题好像没有 Free Pascal 的题解！
没关系！！我来一发！！

编译通过...
测试数据 #0: Accepted, time = 46 ms, mem = 83488 KiB, score = 10
测试数据 #1: Accepted, time = 62 ms, mem = 83492 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 83492 KiB, score = 10
测试数据 #3: Accepted, time = 265 ms, mem = 83492 KiB, score = 10
测试数据 #4: Accepted, time = 218 ms, mem = 83492 KiB, score = 10
测试数据 #5: Accepted, time = 250 ms, mem = 83492 KiB, score = 10
测试数据 #6: Accepted, time = 296 ms, mem = 83484 KiB, score = 10
测试数据 #7: Accepted, time = 218 ms, mem = 83488 KiB, score = 10
测试数据 #8: Accepted, time = 187 ms, mem = 83488 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 83488 KiB, score = 10
Accepted, time = 1806 ms, mem = 83492 KiB, score = 100

以下为伪代码：

Pasca Code

type    int=longint;
var
        s:string;
        n,m,i,j,k,p,t:int;
        ans:int64;
        c:array[0..100001]of char;
        a:array[0..100001]of int;
        d:array[0..41]of int;
        b:array[0..500001,0..41]of int;
    e:array[0..40]of int64=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,
    16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,
    33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,
    8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,
        549755813888,1099511627776);

begin;
        readln(n,m);
        for i:=1 to n do
        begin
                readln(s);
                p:=pos(' ',s);
                val(copy(s,p+1,length(s)-p),a[i]);
                c[i]:=s[1];
        end;
        fillchar(b,sizeof(b),0);
        for i:=1 to n do
        begin
                p:=a[i];
                k:=0;
                repeat
                        b[i,k]:=p mod 2;
                        p:=p div 2;
                        inc(k);
                until   p=0;
        end;
        ans:=0;
        for j:=40 downto 0 do
        begin
                for p:=0 to 1 do
                begin
                t:=p;
                for i:=1 to n do
                begin
                        if c[i]='A' then t:=t and b[i,j];
                        if c[i]='O' then t:=t or b[i,j];
                        if c[i]='X' then t:=t xor b[i,j];
                end;
                if (p=0) and (t=1) then
                begin
                        inc(ans,e[j]);
                        break;
                end;
                if (p=1) and (t=1) then
                begin
                        if e[j]<=m then
                        begin
                                dec(m,e[j]);
                                inc(ans,e[j]);
                        end;
                end;
                end;
        end;
        writeln(ans);
end.

以上！

#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxN=100005;

bool prm[maxN][32];
bool rg[32];
bool opt[32];

int N,M;
int cmd[maxN];

void init()
{
memset(prm,0,sizeof(prm));
memset(rg,0,sizeof(rg));
memset(opt,0,sizeof(opt));
}

inline void binCode(bool* dest,int val)
{
for(int i=0;val;i++)
{
dest[i]=(val&1);
val>>=1;
}
}

const char* XOR="XOR";
const char* OR="OR";
const char* AND="AND";

void input()
{
init();
scanf("%d%d",&N,&M);
binCode(rg,M);
int val;
char cm[5];
for(int i=0;i<N;i++)
{
scanf("%s%d",cm,&val);
if(strcmp(cm,XOR)==0) cmd[i]=1;
else if(strcmp(cm,OR)==0) cmd[i]=2;
else cmd[i]=3;
binCode(prm[i],val);
}
}

bool calc(int pos,bool val)
{
for(int i=0;i<N;i++)
switch(cmd[i])
{
case 1:val^=prm[i][pos]; break;
case 2:val|=prm[i][pos]; break;
case 3:val&=prm[i][pos]; break;
}
return val;
}

int solve()
{
for(int d=30;d>=0;d--)
{
bool rt=calc(d,true);
bool rf=calc(d,false);
if(rf)
{
opt[d]=true;
if(rg[d])
for(int i=d-1;i>=0;i--)
rg[i]=true;
}
else if(rt && rg[d]) opt[d]=true;
else if(rg[d])
for(int i=d-1;i>=0;i--)
rg[i]=true;
}
int res(0);
for(int i=0;i<31;i++)
if(opt[i]) res+=(1<<i);
return res;
}

int main()
{
input();
printf("%d\n",solve());
return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define b(i) (1 << (i))

const int maxn = 100009;
const int L = 30;

char opt[maxn];
int x[maxn], N, M, ans[50][2];

void init() {
scanf("%d%d", &N, &M);
char s[10];
for(int i = 0; i < N; i++) {
scanf("%s", s);
scanf("%d", x + i);
opt[i] = s[0];
}
}

void work() {
for(int i = 0; i < L; i++)
for(int j = 0; j < 2; j++) {
int t = j;
for(int k = 0; k < N; k++) switch(opt[k]) {
case 'A' : t &= (b(i) | x[k]) == x[k]; break;
case 'O' : t |= (b(i) | x[k]) == x[k]; break;
case 'X' : t ^= (b(i) | x[k]) == x[k]; break;
default : break;
}
ans[i][j] = t;
}
int ANS = 0, c = 0;
for(int i = L; i--; )
if(ans[i][0]) ANS |= b(i);
else if(ans[i][1] && (b(i) | c) <= M)
c |= b(i), ANS |= b(i);
printf("%d\n", ANS);
}

int main() {

init();
work();

return 0;
}

http://www.cnblogs.com/JSZX11556/p/4783089.html 贪心

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100000 + 10;

int n, m, a[MAXN], num[MAXN], f[40];

int cal(int x){
for(int i=1; i<=n; i++){
if(a[i] == 1) x = x&num[i];
else if(a[i] == 2) x = x|num[i];
else x = x^num[i];
}
return x;
}

int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
char s[5];
scanf("%s%d", s, &num[i]);
if(s[0] == 'A') a[i] = 1;
else if(s[0] == 'O') a[i] = 2;
else a[i] = 3;
}
int t = cal(0);
for(int i=0; i<=30; i++)
f[i] = (cal(1<<i) & (1<<i));
int ans = 0, tot = 0;
for(int i=30; i>=0; i--){
if((1<<i)&t) ans += (1<<i);
else if((tot + (1<<i) <= m) && f[i]){
ans += f[i];
tot += f[i];
}
}
printf("%d", ans);
return 0;
}

沙发