「CF685X」Codeforces Round #360 (Div. 1)
A. NP-Hard Problem
二分图染色
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n,m; int c[100005]; vector<int>a[2],e[100005]; void dfs(int x,int t) { if(c[x]!=-1) { if(c[x]!=t)flag=1; return; } c[x]=t; a[t].push_back(x); for(int i=0;i<e[x].size();i++) dfs(e[x][i],t^1); } int main() { memset(c,-1,sizeof(c)); n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++) if(c[i]==-1)dfs(i,1); if(flag)puts("-1"); else { for(int x=0;x<=1;x++) { printf("%d\n",a[x].size()); for(int i=0;i<a[x].size();i++) printf("%d ",a[x][i]); puts(""); } } return 0; } |
B. Remainders Game
将K分解为a1 ^ p1 * a2 ^ p2 … an ^ pn
则ai ^ pi要被 c 中的某个数整除
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K; int c[1000005]; bool check(int t) { for(int i=1;i<=n;i++) if(c[i]%t==0)return 1; return 0; } int main() { n=read();K=read(); for(int i=1;i<=n;i++)c[i]=read(); for(int i=2;i<=K;i++) { int t=1; while(K%(t*i)==0)t*=i; if(t!=1) if(!check(t)) { puts("No"); return 0; } K/=t; } puts("Yes"); return 0; } |
C.The Values You Can Make
用f(i,j)表示容量 i 和 j 的背包能不能同时取得
若f(x,K-x)则可以用K中的物品凑出X
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,ans; int f[505][505]; int main() { n=read();K=read(); f[0][0]=1; for(int i=1;i<=n;i++) { int x=read(); for(int j=K;j>=0;j--) for(int k=K;k>=0;k--) { if(j>=x)f[j][k]|=f[j-x][k]; if(k>=x)f[j][k]|=f[j][k-x]; } } for(int i=0;i<=K;i++) if(f[i][K-i])ans++; printf("%d\n",ans); for(int i=0;i<=K;i++) if(f[i][K-i])printf("%d ",i); return 0; } |
Subscribe