8 条题解

  • 1
    @ 2019-07-30 21:39:04

    有意思,用DFS暴力搜索过的,但是加了点小技巧。直接看代码。
    因为取最小值,所以一但找到0,就不需要往下找了。
    没有判断0那句if,后面5个点都过不了,说明了数字足够多的时候,怎么组合都能出0.

    #include <iostream>
    #define ULL unsigned long long
    
    using namespace std;
    
    int n;
    ULL a[100];
    
    ULL work(int ni,ULL now)
    {
        ULL ans=1e19;
        if(ni==n)
        {
            return now;
        }
        else
        {
            ans=min(ans,work(ni+1,now&a[ni]));
            if(ans==0)
            {
                return 0;
            }
            ans=min(ans,work(ni+1,now|a[ni]));
            if(ans==0)
            {
                return 0;
            }
            ans=min(ans,work(ni+1,now^a[ni]));
            if(ans==0)
            {
                return 0;
            }
            ans=min(ans,work(ni+1,now&~a[ni]));
            if(ans==0)
            {
                return 0;
            }
            ans=min(ans,work(ni+1,now|~a[ni]));
            if(ans==0)
            {
                return 0;
            }
            ans=min(ans,work(ni+1,now^~a[ni]));
            if(ans==0)
            {
                return 0;
            }
        }
        return ans;
    }
    
    int main()
    {
        int t,i,j;
        cin>>t;
        for(i=1;i<=t;i++)
        {
            cout<<"Case #"<<i<<": ";
            cin>>n;
            for(j=0;j<n;j++)
            {
                cin>>a[j];
            }
            if(n==1)
            {
                cout<<a[0]<<endl;
            }
            else
            {
                cout<<min(work(1,a[0]),work(1,~a[0]))<<endl;
            }
        }
        return 0;
    }
    
  • 0
    @ 2016-08-24 14:47:29

    ╭══╮╭══╮╭══╮
    ║╭╮║║╭╮║╰═╮║
    ║║║║║╰╯║ ╭╯╯
    ║║║║║╭╭╯╭╯╯ 
    ║╰╯║║║╰╮║╰═╮
    ╰══╯╰╯╰╯╰══╯

  • 0
    @ 2016-08-24 14:47:25

    ╭══╮╭══╮╭══╮
    ║╭╮║║╭╮║╰═╮║
    ║║║║║╰╯║ ╭╯╯
    ║║║║║╭╭╯╭╯╯ 
    ║╰╯║║║╰╮║╰═╮
    ╰══╯╰╯╰╯╰══╯

  • 0
    @ 2015-08-03 16:02:36

    ╭══╮╭══╮╭══╮
    ║╭╮║║╭╮║╰═╮║
    ║║║║║╰╯║ ╭╯╯
    ║║║║║╭╭╯╭╯╯ 
    ║╰╯║║║╰╮║╰═╮
    ╰══╯╰╯╰╯╰══╯

  • 0
    @ 2014-11-05 20:05:16

    ╭══╮╭══╮╭══╮
    ║╭╮║║╭╮║╰═╮║
    ║║║║║╰╯║ ╭╯╯
    ║║║║║╭╭╯╭╯╯ 
    ║╰╯║║║╰╮║╰═╮
    ╰══╯╰╯╰╯╰══╯

  • 0
    @ 2014-11-03 12:18:42

    type
    papapa=record
    data:qword;
    method:integer;
    end;
    var
    stack:array[1..100]of papapa;
    list:array[1..100]of qword;
    i,j,t,n:longint;
    min:qword;
    procedure clearstack;
    var
    sum:qword;
    p:longint;
    begin
    p:=0;sum:=0;//qwq我的AC率!
    for p:=1 to n do case stack[p].method of
    1:sum:=sum and stack[p].data;
    2:sum:=sum or stack[p].data;
    3:sum:=sum xor stack[p].data;
    end;
    if sum<min then min:=sum;
    end;
    procedure run(x:longint);
    var
    i,j:longint;
    begin
    if x=n+1 then begin
    clearstack;exit; end;
    for i:=0 to 1 do
    for j:=1 to 3 do case i of
    0:begin
    stack[x].data:=list[x];
    stack[x].method:=j;
    if x=1 then stack[x].method:=2;
    run(x+1);
    end;
    1:begin
    stack[x].data:=not list[x];
    stack[x].method:=j;
    if x=1 then stack[x].method:=2;
    run(x+1);
    end;
    end;
    end;
    begin
    readln(t);
    for i:=1 to t do begin
    readln(n);
    for j:=1 to n do read(list[j]);
    if n>7 then begin
    writeln('Case #',i,': 0');continue;end;
    min:=18446744073709551615;
    run(1);
    writeln('Case #',i,': ',min);
    end;
    end.
    我勒个去第一次交的时候过程里头的变量忘了重置浪费了一次提交啊啊啊!

    • @ 2014-11-03 15:39:19

      papapa...重口味= =

  • 0
    @ 2014-11-02 14:18:22
    • @ 2014-11-02 16:59:34

      竟然是这么回事。。。。交程序把取反打成‘!’了。。。

    • @ 2014-11-08 00:47:34

      比赛的时候我快速写了一个O(8^N)的暴力搜索,随机了若干组数据。当我随机了100个N=8的数据的时候,我发现答案全都是0了。如果说N=8的时候己经有方法可以变成0, 那么当N>8的时候,必然可以选择将后面的全都用&符号连接,仍然得到答案0。
      我们发现对于任何的数字X,一定x和~x中有个包含不少于32位的数字0。如果 我们恰当选择x和~X,并用&连接,则只需要8个就可以得到0。

      至此,对于N>7的情况,我们直接返回0。其他情况,我们依然暴力枚举。这样就 可以通过所有的数据了。

    • @ 2018-02-03 15:08:42

      222222222222222222222222222222222222222222222222222222222222@chensy98:

  • 0
    @ 2014-11-01 22:00:53

    !Orz

    • @ 2018-02-03 15:08:29

      11111111111111111111111111111111111111111111111111

  • 1

信息

ID
1904
难度
7
分类
(无)
标签
(无)
递交数
421
已通过
82
通过率
19%
被复制
4
上传者