题解

24 条题解

  • 0
    @ 2016-11-11 23:44:17

    没有任何剪枝,还以为要挂,结果1A了...
    测试数据 #0: Accepted, time = 0 ms, mem = 648 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 648 KiB, score = 10
    测试数据 #2: Accepted, time = 46 ms, mem = 648 KiB, score = 10
    测试数据 #3: Accepted, time = 234 ms, mem = 648 KiB, score = 10
    测试数据 #4: Accepted, time = 218 ms, mem = 648 KiB, score = 10
    测试数据 #5: Accepted, time = 250 ms, mem = 648 KiB, score = 10
    测试数据 #6: Accepted, time = 203 ms, mem = 648 KiB, score = 10
    测试数据 #7: Accepted, time = 343 ms, mem = 648 KiB, score = 10
    测试数据 #8: Accepted, time = 359 ms, mem = 648 KiB, score = 10
    测试数据 #9: Accepted, time = 421 ms, mem = 648 KiB, score = 10
    Accepted, time = 2074 ms, mem = 648 KiB, score = 100
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <stack>
    #define INF 0x3f3f3f3f
    using namespace std;

    int n, m;
    int disable[150][150];
    int ans;
    int _ans[150];
    int stk[150];

    inline void in() {
    int a, b, i;
    scanf("%d%d", &n, &m);
    for(i = 1;i <= n;i ++) disable[i][i] = 1;
    for(i = 0;i < m;i ++) {
    scanf("%d%d", &a, &b);
    disable[a][b] = disable[b][a] = 1;
    }
    }

    void DFS(int x, int depth) {
    int i, j, flag;
    for(i = x;i <= n;i ++) {
    flag = 0;
    for(j = 0;j < depth;j ++) {
    if(disable[stk[j]][i]) {
    flag = 1;
    break;
    }
    }
    if(!flag) {
    stk[depth] = i;
    DFS(i, depth+1);
    }
    }
    if(depth > ans) {
    ans = depth;
    memset(_ans, 0, sizeof(_ans));
    for(i = 0;i < depth;i ++) {
    _ans[stk[i]] = 1;
    }
    }
    }

    inline void solve() {
    int i;
    ans = 1;
    for(i = 1;i <= n;i ++) {
    stk[0] = i;
    DFS(i, 1);
    }
    cout << ans << endl;
    for(i = 1;i <= n;i ++) cout << _ans[i] << ' ';
    }

    int main() {
    in();
    solve();
    return 0;
    }
    ```

  • 0
    @ 2016-10-30 18:48:12

    暴力AC
    测试数据 #0: Accepted, time = 0 ms, mem = 4996 KiB, score = 10

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

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

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

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

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

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

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

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

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

  • 0
    @ 2016-08-14 11:39:45

    ##**庆祝橙名!!!**

    评测姬强硬啊!我的电脑(core m5【雾)随机数据要跑10s,然而。。。
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 624 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 620 KiB, score = 10
    测试数据 #2: Accepted, time = 31 ms, mem = 620 KiB, score = 10
    测试数据 #3: Accepted, time = 140 ms, mem = 620 KiB, score = 10
    测试数据 #4: Accepted, time = 187 ms, mem = 628 KiB, score = 10
    测试数据 #5: Accepted, time = 203 ms, mem = 628 KiB, score = 10
    测试数据 #6: Accepted, time = 187 ms, mem = 628 KiB, score = 10
    测试数据 #7: Accepted, time = 312 ms, mem = 628 KiB, score = 10
    测试数据 #8: Accepted, time = 343 ms, mem = 624 KiB, score = 10
    测试数据 #9: Accepted, time = 359 ms, mem = 628 KiB, score = 10
    

    ####Accepted, time = 1762 ms, mem = 628 KiB, score = 100

    发一个bitset位运算不加排序优化的题解,用bitset表示当前选的和不能选的集合。先预处理出每一个点的仇敌bitset,然后每次只需要或运算连接起来,暴力搜加一个最优化剪枝+可行性剪枝

    #include <bits/stdc++.h>
    using namespace std;
    
    int fuck[125][125];
    int mark[125];
    int n, m, x, y;
    int ans = 1;
    bitset<121> ans_set, tmp, tmp2;
    bitset<121> fucks[125];
    
    void dfs(int i, const bitset<121> &bt, const bitset<121> &fail, int cho = 0)
    {
            if (n-i+1+cho <= ans) return;
            if (i == n+1 && cho > ans) {
                    ans = cho;
                    //cout << ans << endl;
                    ans_set = bt;
            } if (i == n+1) return;
            if (fail[i] != 1)
                    dfs(i+1, bt | (tmp<<i), fail | fucks[i], cho + 1);
            dfs(i+1, bt, fail, cho);
    }
    
    int main()
    {
            //freopen("date.in", "r", stdin);
            memset(fuck, 0, sizeof fuck);
            scanf("%d%d", &n, &m);
            for (int i = 1; i <= m; i++) {
                    scanf("%d%d", &x, &y);
                    fuck[x][y] = fuck[y][x] = 1;
            }
            tmp = 1;
            for (int i = 1; i <= n; i++)
                    for (int j = 1; j <= n; j++)
                            if (fuck[i][j])
                                    fucks[i] = fucks[i] | (tmp<<j);
            bitset<121> st, fal;
            st = fal = 0;
            dfs(1, st, fal);
            cout << ans << endl;
            for (int i = 1; i <= n; i++)
                    cout << ans_set[i] << " ";
            return 0;
    }
    
    
    • @ 2016-08-14 11:41:02

      强烈bs无思路无格式贴plain text代码的题解。。。

  • 0
    @ 2015-03-04 10:06:01

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    int n,m,s,a[300][300];
    bool b[300],d[300];

    void go(int x,int y)
    {
    if(y+n-x+1<=s)
    return;
    if(x>n)
    {
    if(y>s)
    {

    int j;
    s=y;
    for(j=1;j<=n;j++)
    d[j]=b[j];
    }
    return;
    }
    if (!b[x])
    {
    go(x+1,y);
    return;
    }
    int i,t,c[300];
    t=0;
    for(i=1;i<=a[x][0];i++)
    if(b[a[x][i]])
    {
    c[++t]=a[x][i];
    b[a[x][i]]=false;
    }
    go(x+1,y+1);
    for(i=1;i<=t;i++)
    b[c[i]]=true;
    b[x]=false;
    go(x+1,y);
    b[x]=true;
    }
    int main()
    {
    cin>>n>>m;
    int i,x,y;
    for(i=1;i<=m;i++)
    {
    cin>>x>>y;
    if(x<y)
    a[x][++a[x][0]]=y;
    else
    a[y][++a[y][0]]=x;
    }
    s=0;
    memset(b,1,sizeof(b));
    go(1,0);
    cout<<s<<endl;
    for(i=1;i<=n;i++)
    cout<<(d[i]==1)<<' ';
    cout<<endl;
    return 0;
    }

  • 0
    @ 2014-11-06 19:44:15

    怎么写啊, 排了序也剪了枝。怎么还是8000对MS超时啊

  • 0
    @ 2010-03-04 14:10:31

    我自己随便random的数据都卡,交上来就AC了。。。

    看来重要的是pruning要符合 作者的思路 || 作者的随机程序。

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

    ├ 测试数据 08:答案正确... 9ms

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 25ms

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

    Accepted 有效得分:100 有效耗时:43ms

    为什么神牛都说要冲突少的先搜? 觉得直觉上和很多题上都是冲突多的先搜嘛。。。

    改了若干优化,从vijos_1593.cpp到vijos_1593_V6.cpp,终于V5还是AC了。。

  • 0
    @ 2009-11-10 16:44:08

    WA 26 次的RP 呀……

    我的战绩够辉煌了吧~~

    就因为没加排序剪枝?!

    质疑机子的稳定性……

  • 0
    @ 2009-08-13 12:11:09

    怎么剪枝啊?

  • 0
    @ 2009-08-11 19:48:34

    输入的处理确实十分猥琐

  • 0
    @ 2009-07-31 09:15:55

    编译通过...

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

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

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

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

    ├ 测试数据 05:答案正确... 9ms

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

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

    ├ 测试数据 08:答案正确... 41ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 88ms

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

    Accepted 有效得分:100 有效耗时:194ms

    强烈要求修改输入数据

    极度猥琐

    我把ac率降到7%

    由把它搞回8%

    读入处理(猥琐到爆,浪费了我1个多小时,身心健康受到严重影响)

    排序剪枝

    开除的人大于最优解时开除的人都时候剪枝

  • 0
    @ 2009-07-30 09:19:01

    我没有排序

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

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

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

    ├ 测试数据 04:答案正确... 25ms

    ├ 测试数据 05:答案正确... 72ms

    ├ 测试数据 06:答案正确... 72ms

    ├ 测试数据 07:答案正确... 72ms

    ├ 测试数据 08:答案正确... 166ms

    ├ 测试数据 09:答案正确... 103ms

    ├ 测试数据 10:答案正确... 212ms

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

    Accepted 有效得分:100 有效耗时:722ms

  • 0
    @ 2009-07-29 21:41:07

    ..哎呀呀。终于秒杀。。好久没做题。DFS都会错了呀。。

  • 0
    @ 2009-07-28 14:02:19

    可能有用的一些话:

    数据中有这样的关系:自己和自己是仇敌,而答案是可以把这样的人加入队伍

  • 0
    @ 2009-07-27 21:10:19

    这个排序剪枝谁都想得出来,

    可是排序后原来第一的人就不是第一个人了,

    那有怎么保证编号小的在前边呢?

    终于知道为什么不加那个搜索剪枝爆搜会WA。

    BS出题人,无敌水题!

  • 0
    @ 2009-07-27 20:59:42

    Orz楼上的神牛。。。。。。

  • 0
    @ 2009-07-27 17:02:04

    先排个序,得罪人多的往后靠

    加一个剪枝就可以:剩下的人都拿上都及不上最优则不搜

    Accepted 有效得分:100 有效耗时:1519ms

    (右边看到的讨论在哪里的?)

  • 0
    @ 2009-08-09 11:45:24

    沙茶题留名……

    问:我为什么不会做?

    答:因为我是沙茶!

    如对本题有疑问可以参看我的题解:http://xujieqi.blog.hexun.com/35722312_d.html

  • 0
    @ 2009-07-27 16:11:31

    编译通过...

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

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

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

    ├ 测试数据 04:答案正确... 244ms

    ├ 测试数据 05:答案正确... 338ms

    ├ 测试数据 06:答案正确... 384ms

    ├ 测试数据 07:答案正确... 353ms

    ├ 测试数据 08:答案正确... 588ms

    ├ 测试数据 09:答案正确... 619ms

    ├ 测试数据 10:答案正确... 634ms

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

    Accepted 有效得分:100 有效耗时:3160ms

    丫丫 第二个通过了啊啊啊O(∩_∩)O哈哈~

    这个要剪3个枝左右

    还有对于刚开始读入的时候我就处理了一下数据

    偷偷说:“搜索应该依次对于第i个人进行操作 取或者不取

    当然要加一些剪枝啊

  • 0
    @ 2009-07-27 08:29:48

    回SKYHACKER:

    不是N个1的问题,应该是N的位数大于答案总数的位数

  • 0
    @ 2009-11-11 18:54:03

    哇~

    ORZ 怪盗~基德,唐钰小宝,玛维3位大牛成功秒杀了~

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

    其实这道题真的不难……就像楼下教主说的再+一点点剪枝就够了……不用排序剪枝,各位千万别想复杂了……

信息

ID
1593
难度
9
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
1286
已通过
89
通过率
7%
被复制
1
上传者