# 7 条题解

• @ 2015-12-06 23:20:04

记录信息

评测状态 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;

{
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;
}

• @ 2016-08-14 12:52:22

绝世傻题！！！
按位贪心即可
此题好像没有 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;
for i:=1 to n do
begin
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.
``````

以上！

• @ 2016-06-13 13:16:45

#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;
}

• @ 2016-03-18 07:55:30

#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;
}

• @ 2016-02-12 18:36:24
• @ 2015-10-27 20:38:27

#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;
}

• @ 2015-02-06 10:43:19

沙发

• 1

ID
1864

4

(无)

299

128

43%

1