24 条题解
-
0
raffica LV 10 @ 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
暴力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
-
huadongf @ 2016-10-30 19:05:56
暴力大法好
-
-
0
##**庆祝橙名！！！**
评测姬强硬啊！我的电脑（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; }-
ljt12138 @ 2016-08-14 11:41:02
强烈bs无思路无格式贴plain text代码的题解。。。
-
-
0
我自己随便random的数据都卡，交上来就AC了。。。
看来重要的是pruning要符合 作者的思路 || 作者的随机程序。├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 9ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：43ms为什么神牛都说要冲突少的先搜？ 觉得直觉上和很多题上都是冲突多的先搜嘛。。。
改了若干优化，从vijos_1593.cpp到vijos_1593_V6.cpp，终于V5还是AC了。。 -
0
编译通过...
├ 测试数据 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
我没有排序
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 25ms
├ 测试数据 05：答案正确... 72ms
├ 测试数据 06：答案正确... 72ms
├ 测试数据 07：答案正确... 72ms
├ 测试数据 08：答案正确... 166ms
├ 测试数据 09：答案正确... 103ms
├ 测试数据 10：答案正确... 212ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：722ms -
0
JoshuaBraynt LV 8 @ 2009-07-29 21:41:07
..哎呀呀。终于秒杀。。好久没做题。DFS都会错了呀。。
-
0
lijian3256 LV 10 @ 2009-07-27 20:59:42
Orz楼上的神牛。。。。。。
-
0
EZ_ray040123 LV 10 @ 2009-07-27 17:02:04
先排个序，得罪人多的往后靠
加一个剪枝就可以：剩下的人都拿上都及不上最优则不搜Accepted 有效得分：100 有效耗时：1519ms
（右边看到的讨论在哪里的？）
-
0
沙茶题留名……
问：我为什么不会做？
答：因为我是沙茶！
如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html -
0
编译通过...
├ 测试数据 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个人进行操作 取或者不取
当然要加一些剪枝啊
”
raffica
LV 10
@ 2016-11-11 23:44:17
