Codeforces Round #485 (Div. 2)

内容预览:
  • 第2次CF,前半个小时发现前面3题都是水题,直接1A,第4题是求最短路,用...~
  •   http://codeforces.com/contest/987 A:太水略过 B:求x^y 和y^x...~
  • 对于迭代器it,如果需要删除it指向的位置   先用it2 = it存下这个位置...~

第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 }

 

以上就是:Codeforces Round #485 (Div. 2) 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论