/ Vijos / 题库 / 神秘配方 /

题解

28 条题解

  • 3
    @ 2017-01-23 20:40:29

    #include <bits/stdc++.h>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;

    struct BigInteger {
    typedef unsigned long long LL;

    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;

    BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
    BigInteger(LL num = 0) {*this = num;}
    BigInteger(string s) {*this = s;}
    BigInteger& operator = (long long num) {
    s.clear();
    do {
    s.push_back(num % BASE);
    num /= BASE;
    } while (num > 0);
    return *this;
    }
    BigInteger& operator = (const string& str) {
    s.clear();
    int x, len = (str.length() - 1) / WIDTH + 1;
    for (int i = 0; i < len; i++) {
    int end = str.length() - i*WIDTH;
    int start = max(0, end - WIDTH);
    sscanf(str.substr(start,end-start).c_str(), "%d", &x);
    s.push_back(x);
    }
    return (*this).clean();
    }

    BigInteger operator + (const BigInteger& b) const {
    BigInteger c; c.s.clear();
    for (int i = 0, g = 0; ; i++) {
    if (g == 0 && i >= s.size() && i >= b.s.size()) break;
    int x = g;
    if (i < s.size()) x += s[i];
    if (i < b.s.size()) x += b.s[i];
    c.s.push_back(x % BASE);
    g = x / BASE;
    }
    return c;
    }
    BigInteger operator - (const BigInteger& b) const {
    assert(b <= *this); // 减数不能大于被减数
    BigInteger c; c.s.clear();
    for (int i = 0, g = 0; ; i++) {
    if (g == 0 && i >= s.size() && i >= b.s.size()) break;
    int x = s[i] + g;
    if (i < b.s.size()) x -= b.s[i];
    if (x < 0) {g = -1; x += BASE;} else g = 0;
    c.s.push_back(x);
    }
    return c.clean();
    }
    BigInteger operator * (const BigInteger& b) const {
    int i, j; LL g;
    vector<LL> v(s.size()+b.s.size(), 0);
    BigInteger c; c.s.clear();
    for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
    for (i = 0, g = 0; ; i++) {
    if (g ==0 && i >= v.size()) break;
    LL x = v[i] + g;
    c.s.push_back(x % BASE);
    g = x / BASE;
    }
    return c.clean();
    }
    BigInteger operator / (const BigInteger& b) const {
    assert(b > 0); // 除数必须大于0
    BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
    BigInteger m; // 余数:初始化为0
    for (int i = s.size()-1; i >= 0; i--) {
    m = m*BASE + s[i];
    c.s[i] = bsearch(b, m);
    m -= b*c.s[i];
    }
    return c.clean();
    }
    BigInteger operator % (const BigInteger& b) const { //方法与除法相同
    BigInteger c = *this;
    BigInteger m;
    for (int i = s.size()-1; i >= 0; i--) {
    m = m*BASE + s[i];
    c.s[i] = bsearch(b, m);
    m -= b*c.s[i];
    }
    return m;
    }
    // 二分法找出满足bx<=m的最大的x
    int bsearch(const BigInteger& b, const BigInteger& m) const{
    int L = 0, R = BASE-1, x;
    while (1) {
    x = (L+R)>>1;
    if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
    else R = x;
    }
    }
    BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
    BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
    BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
    BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
    BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}

    bool operator < (const BigInteger& b) const {
    if (s.size() != b.s.size()) return s.size() < b.s.size();
    for (int i = s.size()-1; i >= 0; i--)
    if (s[i] != b.s[i]) return s[i] < b.s[i];
    return false;
    }
    bool operator >(const BigInteger& b) const{return b < *this;}
    bool operator<=(const BigInteger& b) const{return !(b < *this);}
    bool operator>=(const BigInteger& b) const{return !(*this < b);}
    bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
    bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
    };

    ostream& operator << (ostream& out, const BigInteger& x) {
    out << x.s.back();
    for (int i = x.s.size()-2; i >= 0; i--) {
    char buf[20];
    sprintf(buf, "%08d", x.s[i]);
    for (int j = 0; j < strlen(buf); j++) out << buf[j];
    }
    return out;
    }

    istream& operator >> (istream& in, BigInteger& x) {
    string s;
    if (!(in >> s)) return in;
    x = s;
    return in;
    }

    const int N = 200 + 5;

    int n, m, pa[N << 1];
    bool vis[N];

    int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

    int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n * 2; i++) pa[i] = i;
    for (int i = 1; i <= m; i++) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if (b == d) {
    if (findset(a) == findset(c + n)) {
    printf("No Answer\n");
    return 0;
    }
    pa[findset(a)] = findset(c);
    pa[findset(a + n)] = findset(c + n);
    } else {
    if (findset(a) == findset(c)) {
    printf("No Answer\n");
    return 0;
    }
    pa[findset(a)] = findset(c + n);
    pa[findset(a + n)] = findset(c);
    }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    if (!vis[findset(i)] && findset(i) <= n) {
    cnt++;
    vis[findset(i)] = 1;
    }
    BigInteger ans = 1;
    for (int i = 1; i <= cnt; i++) ans = ans * 2;
    cout << ans << endl;
    return 0;
    }

  • 2
    @ 2015-02-03 14:31:40

    注意如果用拆点并查的方法,统计集合一定要多加注意...
    可以试一下数据
    2 1
    1 0 2 1
    结果应该是2而不是1或4.

    <大整数bign模板省略>

    //union find
    int f[1000];
    void INIT(int size)
    { for(int i=0;i<=size;i++) f[i]=i; }
    int findf(int x)
    { return x==f[x] ? x : f[x]=findf(f[x]); }
    void con(int a,int b)
    { f[findf(a)]=findf(b); }

    int n,m;

    #define A(i) (i)
    #define B(i) ((i)+n)

    int used[1000];
    bign res("1",1);

    int main()
    {
    n=getint();
    m=getint();

    int tot=n;
    INIT(n*2+2);

    for(int i=0;i<m;i++)
    {
    int a=getint()-1,x1=getint(),b=getint()-1,x2=getint();
    int x=x1^x2;

    #define FA(i) findf(A(i))
    #define FB(i) findf(B(i))

    if(x==1) //make difference
    {
    if(FA(a)==FA(b) || FB(a)==FB(b))
    {
    printf("No Answer\n");
    return 0;
    }
    else
    {
    if(FA(a)!=FB(b) && FB(b)!=FA(a)) tot--;
    con(A(a),B(b));
    con(A(b),B(a));
    }
    }
    else if(x==0) //make same
    {
    if(FA(a)==FB(b) || FB(a)==FA(b))
    {
    printf("No Answer\n");
    return 0;
    }
    else
    {
    if(FA(a)!=FA(b) && FB(a)!=FB(b)) tot--;
    con(A(a),A(b));
    con(B(a),B(b));
    }
    }
    }

    for(int i=0;i<tot;i++)
    res=res+res;

    res.output();

    return 0;
    }

  • 0
    @ 2015-06-03 22:26:27

    解模2方程可行吗？

  • 0
    @ 2014-12-17 21:26:31

    设有k个集合，答案则是2^k

  • 0
    @ 2014-01-22 22:15:09

    #include<stdio.h>
    #include<string.h>

    #define MAXN 201
    #define N 1000

    int fa[MAXN+N+10],visit[MAXN],a[1000],c[1000];

    int root(int x)
    {
    if (!fa[x]) return x;

    return fa[x]=root(fa[x]);
    }

    void unit(int x ,int y)
    {
    x=root(x);
    y=root(y);

    if (x!=y)
    fa[x]=y;
    }

    int main()
    {
    int cnt,i,j,n,m,l,x1,y1,x2,y2;

    scanf("%d%d",&n,&m);

    for (i=1;i<=m;++i)
    {
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

    if (y1==y2)
    {
    if (root(x1)==root(x2+N))
    {
    printf("No Answer\n");
    return 0;
    }
    unit(x1,x2);
    unit(x1+N,x2+N);
    }
    else
    {
    if (root(x1)==root(x2))
    {
    printf("No Answer\n");
    return 0;
    }
    else
    {
    unit(x1,x2+N);
    unit(x1+N,x2);
    }

    }

    }

    cnt=0;
    for (i=1;i<=n;++i)
    {
    if (!visit[root(i)]&&(root(i)<=n))
    {
    ++cnt;
    visit[root(i)]=1;
    }
    }

    a[0]=1; l=1;
    for (i=0;i<cnt;++i)
    {
    for (j=0;j<l;++j)
    {
    c[j]+=a[j]*2;
    c[j+1]+=c[j]/10;
    c[j]%=10;
    }
    ++l;
    while (l>=0&&c[l]==0) --l;
    ++l;

    for (j=0;j<l;++j) a[j]=c[j];
    memset(c,0,sizeof(c));
    }

    for (i=l-1;i>=0;--i) printf("%d",a[i]);

    //while (1);
    return 0;
    }
    谁能解释一下这个程序为啥能ac。。。。

    • @ 2017-01-23 20:40:18

      最后检查一下并查集形成几个集合。。

  • 0
    @ 2013-12-13 23:02:22

    忘记加格式了

    代码

    var n,m,i,j,a,b,c,d:longint;
    b1,b2:boolean;
    father:array[1..200]of longint;
    relation:array[1..200]of boolean;
    ans:array[0..100]of longint;
    function f(i:longint):longint;
    var b:boolean;
    begin
    if father[i]=0 then exit(i)else if father[father[i]]=0 then exit(father[i]) else f:=f(father[i]);
    relation[i]:=not(relation[i]xor relation[father[i]]);
    father[i]:=f;
    end;
    procedure noans;
    begin
    writeln('No Answer');
    halt;
    end;
    begin
    readln(n,m);
    fillchar(relation,sizeof(relation),true);
    for i:=1 to m do
    begin
    readln(a,b,c,d);
    if b=1 then b1:=true else b1:=false;
    if d=1 then b2:=true else b2:=false;
    if f(a)=f(c) then
    if (relation[a] xor relation[c])<>(b1 xor b2) then
    noans
    else continue;
    relation[f(c)]:=not((not(b1 xor b2))xor relation[c]);
    father[f(c)]:=a;
    end;
    ans[0]:=1;
    ans[1]:=1;
    for i:=1 to n do if f(i)=i then
    begin
    for j:=1 to ans[0] do ans[j]:=ans[j]*2;
    for j:=1 to ans[0] do
    begin
    ans[j+1]:=ans[j+1]+(ans[j]div 10);
    ans[j]:=ans[j] mod 10;
    end;
    if ans[ans[0]+1]<>0 then ans[0]:=ans[0]+1;
    end;
    for i:=ans[0] downto 1 do write(ans[i]);writeln;
    end.

  • 0
    @ 2013-12-13 22:59:03

    lhf用的什么奇葩算法，竟然用得着hash，欺负我们不会用的是不是？
    奉上50行的程序，秒杀你的120+行。

    var n,m,i,j,a,b,c,d:longint;
    b1,b2:boolean;
    father:array[1..200]of longint;
    relation:array[1..200]of boolean;
    ans:array[0..100]of longint;
    function f(i:longint):longint;
    var b:boolean;
    begin
    if father[i]=0 then exit(i)else if father[father[i]]=0 then exit(father[i]) else f:=f(father[i]);
    relation[i]:=not(relation[i]xor relation[father[i]]);
    father[i]:=f;
    end;
    procedure noans;
    begin
    writeln('No Answer');
    halt;
    end;
    begin
    readln(n,m);
    fillchar(relation,sizeof(relation),true);
    for i:=1 to m do
    begin
    readln(a,b,c,d);
    if b=1 then b1:=true else b1:=false;
    if d=1 then b2:=true else b2:=false;
    if f(a)=f(c) then
    if (relation[a] xor relation[c])<>(b1 xor b2) then
    noans
    else continue;
    relation[f(c)]:=not((not(b1 xor b2))xor relation[c]);
    father[f(c)]:=a;
    end;
    ans[0]:=1;
    ans[1]:=1;
    for i:=1 to n do if f(i)=i then
    begin
    for j:=1 to ans[0] do ans[j]:=ans[j]*2;
    for j:=1 to ans[0] do
    begin
    ans[j+1]:=ans[j+1]+(ans[j]div 10);
    ans[j]:=ans[j] mod 10;
    end;
    if ans[ans[0]+1]<>0 then ans[0]:=ans[0]+1;
    end;
    for i:=ans[0] downto 1 do write(ans[i]);writeln;
    end.

  • 0
    @ 2013-11-03 19:16:56

    const
    p=59;
    ma=400; //400000
    var
    j,s1,s,y,x,ss,i,pp,qq,n,m,q1,q2,a1,a2:longint;
    o,fa,a,b,l,q,c,h:array[0..ma]of longint;

    function gf(x:longint):longint;
    //var //
    begin
    if x=fa[x] then
    exit(x);
    gf:=gf(fa[x]);
    c[x]:=(c[x]+c[fa[x]])mod 2;
    fa[x]:=gf;
    end;
    function search(qq:longint):longint;
    var
    x,s1,y:longint;
    begin
    x:=qq mod p;
    s1:=l[x];
    while s1<>0 do
    begin
    y:=h[s1];
    if y=qq then
    begin
    search:=s1;
    exit;
    end;
    s1:=q[s1];
    end;
    end;
    procedure unite(x,y,z:longint);
    var
    pp,qq:longint;
    begin
    pp:=gf(x);
    qq:=gf(y);
    c[pp]:=(c[y]-c[x]-z+2)mod 2;
    fa[pp]:=qq;
    end;
    procedure hash(qq:longint);
    var
    x,s1,y:longint;
    begin
    x:=qq mod p;
    s1:=l[x];
    while s1<>0 do
    begin
    y:=h[s1];
    if y=qq then
    exit;
    s1:=q[s1];
    end;
    ss:=ss+1;
    h[ss]:=qq;
    fa[ss]:=ss;
    q[ss]:=l[x];
    l[x]:=ss;
    end;
    begin

    // assign(input,'1221.in');
    //reset(input);

    readln(n,m);
    for i:=1 to n do
    begin
    x:=i mod p;
    s1:=l[x];
    { while s1<>0 do
    begin
    y:=h[s1];
    if y=qq then
    exit;
    s1:=q[s1];
    end; }
    ss:=ss+1;
    h[ss]:=i;
    fa[ss]:=ss;
    q[ss]:=l[x];
    l[x]:=ss;
    end;
    //ss:=0;
    fillchar(b,sizeof(b),0);
    { for i:=1 to n do
    begin
    fa[i]:=i;
    c[i]:=0;
    end; }
    for i:=1 to m do
    begin
    readln(q1,a1,q2,a2);
    hash(q1);
    hash(q2);
    pp:=search(q1);
    qq:=search(q2);

    if gf(pp)=gf(qq) then
    begin
    if ((c[pp]mod 2=c[qq]mod 2)and(a1<>a2))or((c[pp]mod 2<>c[qq]mod 2)and(a1=a2)) then
    begin
    writeln('No Answer');
    close(input);
    close(output);
    halt;
    end;
    end else unite(pp,qq,a1 xor a2);
    end;
    s:=0;
    for i :=1 to ss do
    if gf(i)=i then
    s:=s+1;
    // s:=16;
    o[1]:=1;
    x:=1;
    for j:=1 to s do
    begin

    for i:=1 to x do
    o[i]:=o[i]*2;
    for i:=1 to x do
    begin
    o[i+1]:=o[i] div 10000+o[1+i];
    o[i]:=o[i] mod 10000;
    end;
    while o[x+1]>0 do
    begin
    x:=x+1;
    o[x+1]:=o[x+1]+o[x] div 10000;
    o[x]:=o[x] mod 10000;
    end;
    end;
    write(o[x]);
    for i:=x-1 downto 1 do
    begin
    if o[i]=0 then
    y:=0 else y:=trunc(ln(o[i])/ln(10));
    while y+1<4 do
    begin
    write(0);
    y:=y+1;
    end;
    write(o[i]);
    end;
    writeln;

    end.

    我了个去 数组就开了400竟然还a 了 话说同志们 我代码写的有点麻烦（+hash）可无视

  • 0
    @ 2013-10-12 19:58:24

    并查集，f，e表示两个问题答案是一致的还是不一致的，f2表示和这个问题一起确定的问题集合，
    答案=2^不同的f2总数

  • 0
    @ 2010-04-16 20:19:40

    类似小胖的奇偶……

    随便并。

  • 0
    @ 2009-11-09 11:00:10

    是经典题吧，和食物链用了同样的方法吧，并查集，犯了个傻逼错啊，降RP啊

  • 0
    @ 2009-10-09 22:11:12

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    一次AC的感觉 很爽

  • 0
    @ 2009-10-09 21:16:34

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    ...... 交了3次。。

  • 0
    @ 2009-05-25 21:47:58

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    并查集吧，最后别忘了高精度，哈哈，一次就AC！！！

  • 0
    @ 2009-04-06 11:15:56

    FloodFill也不错.

  • 0
    @ 2009-02-04 17:44:55

    并查集+高精度2^k=AC

  • 0
    @ 2008-11-10 10:43:54

    在TRUE1023牛的讲解下，发现很EASY

    最后的高精度打错了，让我找了1个小时。。。。。

  • 0
    @ 2008-11-10 09:14:47

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

  • 0
    @ 2008-11-06 23:32:14

    fammiebright大牛，您的程序连样例都过不了，竟然A了！真不可思议~~

  • 0
    @ 2008-11-03 15:34:08

    终于Ac了……

    http://dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!464.entry

神秘配方

信息

ID
1221
难度
6
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
760
已通过
194
通过率
26%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1