Codeforces Round #485 (Div. 2)

第2次CF，前半个小时发现前面3题都是水题，直接1A，第4题是求最短路，用BFS跑了一下，感觉题目的限制应该不会超时，交了以后也过了，第5题是关于随机排列的题目，模拟了交换最少次数，交了之后也过了，第6题是求图的连通分量，但是图很大，边是由两个数字的&性质决定的，用一个set，学会了边删除边遍历。由于一直在queue中，睡一觉后发现还是没过，但是值得庆幸的是我的其他5题没有被hack。所以排到了134名，感觉妥妥的，rateing飙升160，现在有1660蓝名，希望接下来到暑假可以冲击紫名。

http://codeforces.com/contest/987

A：太水略过

B：求x^y 和y^x大小

取对数，比赛的时候怕精度问题，用了eps判等于，结果过了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int main()
 5 {
 6     double x, y, eps = 1e-12;
 7     cin >> x >> y;
 8     double ans = x * log(y) - y * log(x);
 9     if(fabs(ans) < eps)cout<<"="<<endl;
10     else if(ans > 0) cout<<"<"<<endl;
11     else cout<<">"<<endl;
12     return 0;
13 }

C：给数组s和c，满足i<j<k 且 si < sj < sk 使ci + cj + ck最小

直接DP，DP[i][j]为以i结尾长度为j的最大价值。最终求最小的DP[i][3]

初始化DP[i][1] = s[i]

注意，dp[i][2]中i从2开始递推，dp[i][3]中i从3开始递推，为了防止出错，写了两个二重循环。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 5000;
 5 const int INF = 1e9 + 7;
 6 ll a[maxn], b[maxn], dp[maxn][5];
 7 int main()
 8 {
 9     int n;
10     cin >> n;
11     for(int i = 1; i <= n; i++)cin >> a[i];
12     for(int i = 1; i <= n; i++)cin >> b[i], dp[i][1] = b[i];
13     for(int i = 2; i <= 3; i++)
14         for(int j = 1; j <= n; j++)dp[j][i] = INF;
15     ll ans = INF;
16     for(int i = 2; i <= n; i++)
17     {
18         for(int j = 1; j < i; j++)
19             if(a[j] < a[i])
20             dp[i][2] = min(dp[i][2], dp[j][1] + b[i]);
21     }
22     for(int i = 3; i <= n; i++)
23     {
24         for(int j = 2; j < i; j++)
25             if(a[j] < a[i])
26             dp[i][3] = min(dp[i][3], dp[j][2] + b[i]);
27     }
28     for(int i = 1; i <= n; i++)ans = min(ans, dp[i][3]);
29     if(ans == INF)cout<<"-1"<<endl;
30     else cout<<ans<<endl;
31     return 0;
32 }

D：n个城市，m条无向路，共有k种货物，每个城市只有一种货物，让你求在城市i举办交易会，至少有s种货物参加，求最少的路径之和

由于s和k最大为100，可以用BFS跑每一个点，跑到货物种类等于s的时候返回路径和（这里是种类不是数量）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 100000 + 10;
 5 const int INF = 1e9 + 7;
 6 bool vis[maxn], v[maxn];
 7 int dis[maxn], a[maxn];
 8 vector<int>G[maxn];
 9 int n, m, k, S;
10 int BFS(int s)
11 {
12     memset(vis, 0,sizeof(vis));
13     memset(v, 0,sizeof(v));
14     vis[s] = 1;
15     dis[s] = 0;
16     int tot = 0, now, ans = 0, u;
17     queue<int>q;
18     q.push(s);
19     while(!q.empty())
20     {
21         now = q.front();
22         q.pop();
23         if(!v[a[now]])
24         {
25             v[a[now]] = 1;
26             tot++;
27             ans += dis[now];
28             if(tot == S)return ans;
29         }
30         for(int i = 0; i < G[now].size(); i++)
31         {
32             u = G[now][i];
33             if(!vis[u])
34             {
35                 vis[u] = 1;
36                 dis[u] = dis[now] + 1;
37                 q.push(u);
38             }
39         }
40     }
41 }
42 int main()
43 {
44     scanf("%d%d%d%d", &n, &m, &k, &S);
45     for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
46     int u, v;
47     while(m--)
48     {
49         scanf("%d%d", &u, &v);
50         G[u].push_back(v);
51         G[v].push_back(u);
52     }
53     //BFS(1);
54     printf("%d", BFS(1));
55     for(int i = 2; i <= n; i++)printf(" %d", BFS(i));
56     puts("");
57     return 0;
58 }

E：给出一个1-n随机排列，Petr的随机化排列方法是随机交换3*n次，Um_nik的随机化排列方法是随机交换7*n+1次。问给出的排列是谁随机化得到的。

初始排列 1,2,3...n

模拟了一下最小交换次数tot，如果3*n - tot是偶数的话，那么就是Petr的，否则就是Um_nik的

数组a存储序列，数组b的b[i]表示a[j] = i的j的值

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1000000 + 10;
 5 const int INF = 1e9 + 7;
 6 int a[maxn], b[maxn];
 7 int main()
 8 {
 9     int n;
10     cin >> n;
11     for(int i = 1; i <= n; i++)
12     {
13         scanf("%d", &a[i]);
14         b[a[i]] = i;
15     }
16     int tot = 0, u;
17     for(int i = 1; i <= n; i++)
18     {
19         if(a[i] == i)continue;
20         tot++;
21         u = b[i];
22         swap(b[i], b[a[i]]);
23         swap(a[i], a[u]);
24     }
25     tot = 3 * n - tot;
26     if(tot % 2 == 0)cout<<"Petr"<<endl;
27     else cout<<"Um_nik"<<endl;
28     return 0;
29 }

F：给n和m，还有m个互不相同的数，均小于1<<n，如果m个数字中a & b = 0，那么a 和b有边相连，问有多少个连通分量

比赛的时候，用set存储每个数，每次取出第一个数，在set中删去与他相邻的点，重复，但是还是超时了，不过学到了如何用set边删除边遍历。

对于迭代器it，如果需要删除it指向的位置

　　先用it2 = it存下这个位置

　　it++

　　s.erase(it2)

这样就可以遍历的时候删除了

题目正解应该是，把每个数看做一个01集合，对于在m个数中的数，求它的补集的子集个数即可

这里用4位来举个例子，

比如5(0101)，补集：(1010)，补集的子集：(1010) (1000) (0010) (0000)

补集的子集和该集合的&运算的结果为0，满足条件。

那么就可以枚举0 - ((1<<n) - 1)进行DFS即可。每次找到所有联通的点。

时间复杂度O(1<<n)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = (1<<23);
 5 bool vis[maxn], num[maxn];
 6 int n, m;
 7 void dfs(int x)
 8 {
 9     if(vis[x])return;
10     vis[x] = 1;
11     for(int i = 0; i < n; i++)//遍历x的子集
12     {
13         if(x & (1 << i))
14             dfs(x ^ (1 << i));
15     }
16     if(num[x])dfs(((1<<n) - 1) & (~x));//如果是num中的元素，就寻找x的补集的子集
17 }
18 int main()
19 {
20     int x;
21     scanf("%d%d", &n, &m);
22     for(int i = 1; i <= m; i++)
23     {
24         scanf("%d", &x);
25         num[x] = 1;
26     }
27     int ans = 0;
28     for(int i = 0; i < (1 << n); i++)
29     {
30         if(num[i] && !vis[i])
31             dfs(((1<<n) - 1) & (~i)), ans++;//dfs其补集
32     }
33     cout<<ans<<endl;
34     return 0;
35 }