CodeForces 687A NP-Hard Problem

Portal:http://codeforces.com/problemset/problem/687/A

二分图染色 好模板题 有SPJ

值得注意的是,因为C++的奇妙的运算机制

若在vector变量x.size()=0,则x.size()-1会溢出(此处坑了我3h)

这不禁让我想起了文明2里的甘地

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 #define FOR(i,j,k) for(int i=j;i<=k;i++)
10 #define FORD(i,j,k) for(int i=j;i>=k;i--)
11 #define LL long long
12 #define maxn 100010
13 #define SZ(x) int(x.size())
14 int n,m,j,x,y;
15 bool flag=true;
16 vector<int> a[maxn];
17 vector<int> ans[2];
18 int col[maxn],len[maxn],vis[maxn];
19 bool dfs(int s,int color)
20 {
21     col[s]=color;
22     vis[s]=1;
23     FOR(i,0,SZ(a[s])-1)
24     {
25     if(vis[a[s][i]]) {if(col[a[s][i]]==color) return false;}
26     else if(!dfs(a[s][i],-color)) return false;
27     }
28     if(color==1) ans[0].push_back(s); else ans[1].push_back(s);
29     return true;
30 }
31 int main()
32 {
33 cin>>n>>m;
34 FOR(i,1,m)
35 {
36     cin>>x>>y;
37     a[x].push_back(y);
38     a[y].push_back(x);
39 }
40 FOR(i,1,n)
41 {
42 if(!vis[i]) if(!dfs(i,1)) flag=false;
43 }
44 if(flag)
45 FOR(i,0,1)
46 {
47     cout<<SZ(ans[i])<<endl;
48     FOR(j,0,SZ(ans[i])-1) cout<<ans[i][j]<<‘ ‘;
49     cout<<endl;
50 }
51 else cout<<-1<<endl;
52 return 0;
53 }

神奇代码

神奇的(一劳永逸的?)做法

#define SZ(x) int(x.size())

嘿嘿嘿 define大法好

时间: 07-02

CodeForces 687A NP-Hard Problem的相关文章

http://codeforces.com/contest/575/problem/B

题目链接: http://codeforces.com/contest/575/problem/B 题解: 代码: #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1e5 + 10; const int DEG = 22; const in

Codeforces 442B Andrey and Problem(贪心)

题目链接:Codeforces 442B Andrey and Problem 题目大意:Andrey有一个问题,想要朋友们为自己出一道题,现在他有n个朋友,每个朋友想出题目的概率为pi,但是他可以同时向多个人寻求帮助,不过他只能要一道题,也就是如果他向两个人寻求帮助,如果两个人都成功出题,也是不可以的. 解题思路:贪心,从概率最大的人开始考虑,如果询问他使得概率变大,则要询问. #include <cstdio> #include <cstring> #include <a

http://codeforces.com/contest/741/problem/B B. Arpa&#39;s weak amphitheater and Mehrdad&#39;s valuable Hoses

题意: 给出上限体重W 然后还给出每个人的体重wi 和 魅力值 bi 互为伙伴的对(xi, yi) 可以凑成group 思路: 并查集找出所有的group 暴力背包 对于每一个group 要选出这一组内选一个人时的最优结果, 如果所有人的体重和小于等于W,还得考虑选所有人的情况 #include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include &l

CodeForces 633B A Trivial Problem

传送门:http://codeforces.com/problemset/problem/633/B 题意:给你一个常数m,要你找出几个数,这几个数的阶乘的最后m位 都是0. 显然 末尾有0 一定能除以10 10可以换成5*2的形式, 那么我们就可以找5的倍数,(如果有5出现 也一定有2) ———————————————————————————————————— 渣渣之见,随便转载. #include<cstdio> int main() { long long n,k=0; // 看i阶乘的

Codeforces 713C Sonya and Problem Wihtout a Legend(单调DP)

[题目链接] http://codeforces.com/problemset/problem/713/C [题目大意] 给出一个数列,请你经过调整使得其成为严格单调递增的数列,调整就是给某些位置加上或者减去某个数,调整的代价是加上或者减去的数的绝对值之和,请你输出最小代价. [题解] 先考虑这样一个问题,如果是非严格单调递增该如何做,我们会发现每次调整,都是调整某个数字为原先数列中存在的数字,最后才是最优的,所以,我们设DP[i][j]表示前i个数字,最后一个数为原先数列排序后第j大的数字的最

Codeforces 706 C. Hard problem (dp)

题目链接:http://codeforces.com/problemset/problem/706/C 给你n个字符串,可以反转任意一个字符串,反转每个字符串都有其对应的花费ci. 经过操作后是否能满足字符串str[i]>=str[i-1],能就输出最小花费,不能输出-1. dp[i][0] 表示不反转i的最小花费(str[i] >= str[i - 1] || str[i] >= reverse(str[i - 1])) dp[i][1] 则表示反转i的最小花费... 初始dp[1][

http://codeforces.com/gym/100694/problem/M The Fifth Season (巴什博奕)

题目链接 一直觉得巴什博奕是最简单的博弈遇到肯定没问题,结果被虐惨了,看完标程错了10多遍都没反应过来,当然标程题解和代码的意思也写反了,但是还是想对自己说一句mdzz,傻啊!!!这道题很不错,我觉得很有必要拿来写一篇博客. 题意:n个石子,两个人轮流取,q次询问,每次询问给定k和l,取的石子数目在k到l之间,假设两个人的取法都为最佳即向着自己赢的目标取,问一共能取多少次. 题解:巴什博奕,接下来的叙述中用a和b代替k和l.根据巴什博奕,首先ans=n%(a+b)*2是肯定的,问题就在于余数p.

Codeforces 513G1 513G2 Inversions problem 概率dp

题目链接:点击打开链接 题意: 给定n ,k 下面n个数表示有一个n的排列, 每次操作等概率翻转一个区间,操作k次. 问: k次操作后逆序数对个数的期望. 思路: dp[i][j]表示 a[i] 在a[j] j前面的概率 初始就是 dp[i][j]  = 1( i < j ) 则对于翻转区间 [i, j], 出现的概率 P = 1 / ( n * (n+1) /2) 并且会导致 [i, j]内元素位置交换,枚举这次翻转的区间时所有的转移情况 #include <stdio.h> #inc

http://codeforces.com/contest/776/problem/G

题意: 讲一个16进制的数字num的每一位拆分下来 也就是sum = $\sigma(2 ^ a_i)$ 每一个a_i 都是不同的 举个栗子: $1014_16$ 就是 $2^1 + 2 ^ 0 + 2 ^ 4$ 求得的sum是个十进制的数字 然后将sum和num都化为二进制进行异或,如果异或后的值小于num那么++ans 现在题目是给出一个区间[l, r] 问这个区间内有多少个满足条件的数,也就是区间内ans的大小 思路: 贪心+数位dp, 定义三个状态 dp[mask1][mask2][le