如果您想了解CF思维联系--CodeForces-214C(拓扑排序+思维+贪心）的相关知识，那么本文是一篇不可错过的文章，我们将为您提供关于CF--思维练习--CodeForces-216C-Hir
如果您想了解CF 思维联系 --CodeForces -214C (拓扑排序 + 思维 + 贪心）的相关知识，那么本文是一篇不可错过的文章，我们将为您提供关于CF--思维练习--CodeForces - 216C - Hiring Staff （思维+模拟）、CF思维联系--CodeForces - 218C E - Ice Skating （并查集）、CF思维联系– Codeforces-987C - Three displays （ 动态规划）、CF思维联系–CodeForces - 222 C Reducing Fractions(数学+有技巧的枚举）的有价值的信息。
本文目录一览：- CF 思维联系 --CodeForces -214C (拓扑排序 + 思维 + 贪心）
- CF--思维练习--CodeForces - 216C - Hiring Staff （思维+模拟）
- CF思维联系--CodeForces - 218C E - Ice Skating （并查集）
- CF思维联系– Codeforces-987C - Three displays （ 动态规划）
- CF思维联系–CodeForces - 222 C Reducing Fractions(数学+有技巧的枚举）
CF 思维联系 --CodeForces -214C (拓扑排序 + 思维 + 贪心）
ACM 思维题训练集合
Furik and Rubik love playing computer games. Furik has recently found a new game that greatly interested Rubik. The game consists of n parts and to complete each part a player may probably need to complete some other ones. We know that the game can be fully completed, that is, its parts do not form cyclic dependencies.
Rubik has 3 computers, on which he can play this game. All computers are located in different houses. Besides, it has turned out that each part of the game can be completed only on one of these computers. Let''s number the computers with integers from 1 to 3. Rubik can perform the following actions:
Complete some part of the game on some computer. Rubik spends exactly 1 hour on completing any part on any computer.
Move from the 1-st computer to the 2-nd one. Rubik spends exactly 1 hour on that.
Move from the 1-st computer to the 3-rd one. Rubik spends exactly 2 hours on that.
Move from the 2-nd computer to the 1-st one. Rubik spends exactly 2 hours on that.
Move from the 2-nd computer to the 3-rd one. Rubik spends exactly 1 hour on that.
Move from the 3-rd computer to the 1-st one. Rubik spends exactly 1 hour on that.
Move from the 3-rd computer to the 2-nd one. Rubik spends exactly 2 hours on that.
Help Rubik to find the minimum number of hours he will need to complete all parts of the game. Initially Rubik can be located at the computer he considers necessary.Input
The first line contains integer n (1 ≤ n ≤ 200) — the number of game parts. The next line contains n integers, the i-th integer — ci (1 ≤ ci ≤ 3) represents the number of the computer, on which you can complete the game part number i.
Next n lines contain descriptions of game parts. The i-th line first contains integer ki (0 ≤ ki ≤ n - 1), then ki distinct integers ai, j (1 ≤ ai, j ≤ n; ai, j ≠ i) — the numbers of parts to complete before part i.
Numbers on all lines are separated by single spaces. You can assume that the parts of the game are numbered from 1 to n in some way. It is guaranteed that there are no cyclic dependencies between the parts of the game.Output
On a single line print the answer to the problem.Examples
Input
1
1
0
Output
1
Input
5
2 2 1 1 3
1 5
2 5 1
2 5 4
1 5
0
Output
7Note
Note to the second sample: before the beginning of the game the best strategy is to stand by the third computer. First we complete part 5. Then we go to the 1-st computer and complete parts 3 and 4. Then we go to the 2-nd computer and complete parts 1 and 2. In total we get 1+1+2+1+2, which equals 7 hours.题解：
现在有三个工作站，有三种工作，每种工作需要完成前置任务才能进行当前工作，三个工作站之间转换需要花费时间，问将所有任务都完成需要花费的最少时间。一开始可以在任意一个工作站开始工作。
贪心一下，如果在一台电脑上能够完成多项任务，就让他都完成，然后在考虑转移，转移的话无非就是 1-2
2-3 3-1 还有就是 3-2 2-1 1-3 这种，一种是 1 另一种是 2，所以我们不走 1-3 这种用两段 1-2 2-3 代替花费相同，这样在进行拓扑排序完事了。
吐槽一下数据思路错了也能过。
后来想了一下如果一开始三台电脑都能开始一个工作，那么先从哪台开始呢，不知道，所以三台为起始点进行拓扑选最小的的答案输出。
#include <bits/stdc++.h>
using namespace std;
vector<int> mp[15000];
int d[5][5], a[250], deg[250], temp[205], n;
int tooper(int ss)
{
queue<int> s;
int ans = n, cnt = 0, now = ss;
while (1)
{
while (1)
{
int flag = 0;
for (int i = 1; i <= n; ++i)
{
if (deg[i] == 0 && a[i] == now)
{
flag = 1;
deg[i] = -1;
cnt++;
for (int j = 0; j < mp[i].size(); ++j)
{
int v = mp[i][j];
deg[v]--;
}
}
}
if (flag == 0)
break;
}
if (cnt == n)
break;
now++;
ans++;
now = (now == 4 ? 1 : now);
}
return ans;
}
int main()
{
d[1][1] = d[2][2] = d[3][3] = 0;
d[1][2] = d[2][3] = d[3][1] = 1;
d[2][1] = d[3][2] = d[1][3] = 0x3f3f3f3f;
cin>>n;
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
{
int k;
scanf("%d", &k);
for (int j = 1; j <= k; ++j)
{
int x;
scanf("%d", &x);
mp[x].push_back(i);
deg[i]++;
}
}
for (int i = 1; i <= n; ++i)
temp[i] = deg[i];
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; ++i)
deg[i] = temp[i];
ans = min(ans, tooper(1));
for (int i = 1; i <= n; ++i)
deg[i] = temp[i];
ans = min(ans, tooper(2));
for (int i = 1; i <= n; ++i)
deg[i] = temp[i];
ans = min(ans, tooper(3));
printf("%d\n", ans);
}
CF--思维练习--CodeForces - 216C - Hiring Staff （思维+模拟）
ACM思维题训练集合
A new Berland businessman Vitaly is going to open a household appliances’ store. All he’s got to do now is to hire the staff.
The store will work seven days a week, but not around the clock. Every day at least k people must work in the store.
Berland has a law that determines the order of working days and non-working days. Namely, each employee must work for exactly n consecutive days, then rest for exactly m days, then work for n more days and rest for m more, and so on. Vitaly doesn’t want to break the law. Fortunately, there is a loophole: the law comes into force on the day when the employee is hired. For example, if an employee is hired on day x, then he should work on days [x, x + 1, …, x + n - 1], [x + m + n, x + m + n + 1, …, x + m + 2n - 1], and so on. Day x can be chosen arbitrarily by Vitaly.
There is one more thing: the key to the store. Berland law prohibits making copies of keys, so there is only one key. Vitaly is planning to entrust the key to the store employees. At the same time on each day the key must be with an employee who works that day — otherwise on this day no one can get inside the store. During the day the key holder can give the key to another employee, if he also works that day. The key will handed to the first hired employee at his first working day.
Each employee has to be paid salary. Therefore, Vitaly wants to hire as few employees as possible provided that the store can operate normally on each day from 1 to infinity. In other words, on each day with index from 1 to infinity, the store must have at least k working employees, and one of the working employees should have the key to the store.
Help Vitaly and determine the minimum required number of employees, as well as days on which they should be hired.
Input
The first line contains three integers n, m and k (1 ≤ m ≤ n ≤ 1000, n ≠ 1, 1 ≤ k ≤ 1000).
Output
In the first line print a single integer z — the minimum required number of employees.
In the second line print z positive integers, separated by spaces: the i-th integer ai (1 ≤ ai ≤ 104) should represent the number of the day, on which Vitaly should hire the i-th employee.
If there are multiple answers, print any of them.
Examples
Input
4 3 2
Output
4
1 1 4 5
Input
3 3 1
Output
3
1 3 5
Sponsor
**这个题之前做过，今天写了1个半小时才写出来，思维真的是不行了。**还是不能落下训练，。
发现直接模拟就能过，想搞点简单wa了N多遍。
思路就是第一天肯定是K个人，直接模拟那K个人休息的M天，让其也保持K人就行，一定要注意第m天结束时一定要有人把钥匙送回第一拨人手上。
#include <bits/stdc++.h>
using namespace std;
int a[10000];
int ans[10000];
int main()
{
int n, m, k;
cin >> n >> m >> k;
if (m <= n - 2)
{
cout << 2 * k << endl;
for (int i = 0; i < k; i++)
printf("1 ");
printf("%d ", n);
n++;
for (int i = 1; i < k; i++)
printf("%d ", n);
puts("");
}
else
{
int cnt = k + 1;
for (int i = 1; i <= m; i++)
{
if (a[i] == k)
continue;
if (a[i] == 0)
{
ans[cnt++] = i - 1;
for (int j = 0; j < n - 1; j++)
a[i + j]++;
}
int w = k - a[i];
for (int j = 0; j < n; j++)
a[i + j] += w;
for (int j = 0; j < w; j++)
ans[cnt++] = i;
}
if (a[m + 1] == 0)
ans[cnt++] = m;
cout << cnt - 1 << endl;
for (int i = 0; i < k; i++)
printf("1 ");
for (int i = k + 1; i < cnt; i++)
printf("%d ", ans[i] + n);
puts("");
}
}
CF思维联系--CodeForces - 218C E - Ice Skating （并查集）
题目地址：24道CF的DIv2 CD题有兴趣可以做一下。
ACM思维题训练集合
Bajtek is learning to skate on ice. He’s a beginner, so his only mode of transportation is pushing off from a snow drift to the north, east, south or west and sliding until he lands in another snow drift. He has noticed that in this way it’s impossible to get from some snow drifts to some other by any sequence of moves. He now wants to heap up some additional snow drifts, so that he can get from any snow drift to any other one. He asked you to find the minimal number of snow drifts that need to be created.
We assume that Bajtek can only heap up snow drifts at integer coordinates.
Input
The first line of input contains a single integer n (1 ≤ n ≤ 100) — the number of snow drifts. Each of the following n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 1000) — the coordinates of the i-th snow drift.
Note that the north direction coinсides with the direction of Oy axis, so the east direction coinсides with the direction of the Ox axis. All snow drift’s locations are distinct.
Output
Output the minimal number of snow drifts that need to be created in order for Bajtek to be able to reach any snow drift from any other one.
Examples
Input
2
2 1
1 2
Output
1
Input
2
2 1
4 1
Output
0
这道题做过但是不记得当时怎么做的了，每次做都有新的感受。
并查集，一般的并查集不太行，如图
代码
#include <bits/stdc++.h>
using namespace std;
int fa[105];
int find(int n)
{
if(fa[n]==n) return n;
else return fa[n]=find(fa[n]);
}
struct Node{
int x,y;
}node[105];
bool check(Node a,Node b)
{
if(a.x==b.x) return 1;
else if(a.y==b.y)return 1;
else return 0;
}
set<int> cnt;
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
fa[i]=i;
cin>>node[i].x>>node[i].y;
for(int j=0;j<i;j++)
{
if(check(node[i],node[j])){
fa[find(j)]=find(i);
// cout<<fa[j]<<endl;
}
}
}
for(int i=0;i<n;i++)
{
//cout<<find(fa[i])<<endl;
cnt.insert(find(i));
}
cout<<cnt.size()-1<<endl;
}
CF思维联系– Codeforces-987C - Three displays （ 动态规划）
ACM思维题训练集合
It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.
There are n displays placed along a road, and the i-th of them can display a text with font size si only. Maria Stepanovna wants to rent such three displays with indices i<j<k that the font size increases if you move along the road in a particular direction. Namely, the condition si<sj<sk should be held.
The rent cost is for the i-th display is ci. Please determine the smallest cost Maria Stepanovna should pay.
Input
The first line contains a single integer n (3≤n≤3000) — the number of displays.
The second line contains n integers s1,s2,…,sn (1≤si≤109) — the font sizes on the displays in the order they stand along the road.
The third line contains n integers c1,c2,…,cn (1≤ci≤108) — the rent costs for each display.
Output
If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices i<j<k such that si<sj<sk.
Examples
Input
5
2 4 5 4 10
40 30 20 10 40
Output
90
Input
3
100 101 100
2 4 5
Output
-1
Input
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
Output
33
一看到这题，我觉得像是个背包，实际上差不多，只不过就是有了限制条件，后选的序号一定大于之前的序号，且给定的S[i]也需要大于之前选的。然后这个题我觉得数据有点水 n 2 n^2 n2的复杂度竟然能这么快。
#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
int f = 1;
while (ch < ''0'' || ch > ''9'')
f = (ch == ''-'' ? -1 : f), ch = getchar();
while (ch >= ''0'' && ch <= ''9'')
x = x * 10 + ch - ''0'', ch = getchar();
x *f;
}
#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define rep(m, n, i) for (int i = m; i < n; ++i)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
//---------------https://lunatic.blog.csdn.net/-------------------//
const int N = 3005;
const int INF = 0x3f3f3f3f;
int s[N], cost[N], maxi[N];
int dp[N][10], weight[N][10];
int main()
{
int n;
read(n);
rep(1, n + 1, i)
{
read(s[i]);
}
rep(1, n + 1, i)
{
read(cost[i]);
}
memset(dp, 0x3f, sizeof(dp));
//rep(0, n + 1, i) weight[i] =s[i];
rep(1, n, i)
{
dp[i][1]=cost[i];
weight[i][1]=s[i];
for (int j =2; j <= 3; j++)
{
for (int k = i+1; k <= n; k++)
if (s[k] > weight[i][j-1])
{
//cout<<1;
if (dp[k][j] > dp[i][j - 1] + cost[k])
{
//cout<<2;
dp[k][j] = dp[i][j - 1] + cost[k];
weight[k][j] = s[k];
}
}
}
}
int ans = INF;
rep(1, n + 1, i)
ans = min(ans, dp[i][3]);
if (ans == INF)
puts("-1");
else
{
wi(ans);
P;
}
}
CF思维联系–CodeForces - 222 C Reducing Fractions(数学+有技巧的枚举）
ACM思维题训练集合
To confuse the opponents, the Galactic Empire represents fractions in an unusual format. The fractions are represented as two sets of integers. The product of numbers from the first set gives the fraction numerator, the product of numbers from the second set gives the fraction denominator. However, it turned out that the programs that work with fractions in this representations aren’t complete, they lack supporting the operation of reducing fractions. Implement this operation and the Empire won’t forget you.
Input
The first input line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) that show how many numbers the first set (the numerator) and the second set (the denominator) contain, correspondingly.
The second line contains n space-separated integers: a1, a2, …, an (1 ≤ ai ≤ 107) — the numbers that are multiplied to produce the numerator.
The third line contains m space-separated integers: b1, b2, …, bm (1 ≤ bi ≤ 107) — the numbers that are multiplied to produce the denominator.
Output
Print the answer to the problem in the form, similar to the form of the input data. The number of values in the sets you print nout, mout must satisfy the inequality 1 ≤ nout, mout ≤ 105, and the actual values in the sets aout, i and bout, i must satisfy the inequality 1 ≤ aout, i, bout, i ≤ 107.
Separate the values in the lines by spaces. The printed fraction must be reduced, that is, there mustn’t be such integer x (x > 1), that the numerator and the denominator of the printed fraction are divisible by x. If there are several matching answers, print any of them.
Examples
Input
3 2
100 5 2
50 10
Output
2 3
2 1
1 1 1
Input
4 3
2 5 10 20
100 1 3
Output
1 1
20
3
Note
In the first test sample the numerator equals 1000, the denominator equals 500. If we reduce fraction 1000/500 by the greatest common divisor of the numerator and the denominator (by 500), we obtain fraction 2/1.
In the second test sample the numerator equals 2000, the denominator equals 300. If we reduce fraction 2000/300 by the greatest common divisor of the numerator and the denominator (by 100), we obtain fraction 20/3.
日常WA一天
不看跑的数据，我都不知道自己怎么错的，老天爷。我的输出超出了限制100001不能超过100000，我觉得那时候，那些没有过的，一定是这个原因，出题人真是丧心病狂。
第一个代码是错的，第二个是修改了的，换了方式。
#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
int f = 1;
while (ch < ''0'' || ch > ''9'')
f = (ch == ''-'' ? -1 : f), ch = getchar();
while (ch >= ''0'' && ch <= ''9'')
x = x * 10 + ch - ''0'', ch = getchar();
x *f;
}
bitset<100000010> v;
int prime[6000001];
int m = 0;
void primes(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (!v[i])
{
for (int j = i * i; j <= n; j += i)
v[j] = 1;
}
}
for (int i = 2; i <= n; i++)
if (!v[i])
prime[m++] = i;
}
vector<int> a[4];
unordered_map<int, int> c, d;
int main()
{
int n, m, maxi = 0;
read(n), read(m);
primes(10000005);
for (int i = 0; i < n; i++)
{
int tem;
read(tem);
maxi = max(maxi, tem);
c[tem]++;
}
for (int i = 0; i < m; i++)
{
int tem;
read(tem);
maxi = max(maxi, tem);
d[tem]++;
}
//cout << 1 << endl;
for (int i = 0; prime[i] <= maxi; i++)
{
// cout<<i<<endl;
int cnt = 0, ans = 0, cnt2 = 0;
int flag = 1;
for (auto po = c.begin(); po != c.end();)
{
// cout<<1<<endl;
pair<int, int> tem = *po;
cnt = 0;
if (tem.first < prime[i])
{
po++;
continue;
}
else
{
flag = 0;
while (tem.first % prime[i] == 0)
{
tem.first /= prime[i];
cnt++;
//cout<<i<<endl;
}
cnt *= tem.second;
auto pi = po;
po++;
c.erase(pi);
if (tem.first != 1)
c[tem.first] += tem.second;
}
ans += cnt;
}
cnt2 = ans;
ans = 0;
for (auto po = d.begin(); po != d.end();)
{
pair<int, int> tem = *po;
cnt = 0;
if (tem.first < prime[i])
{
po++;
continue;
}
else
{
flag = 0;
while (tem.first % prime[i] == 0)
{
tem.first /= prime[i];
cnt++;
//cout<<i<<endl;
}
cnt *= tem.second;
auto pi = po;
po++;
d.erase(pi);
if (tem.first != 1)
d[tem.first] += tem.second;
}
ans += cnt;
}
cnt = cnt2 - ans;
if (cnt == 0)
continue;
else if (cnt < 0)
{
cnt = -cnt;
int temp = 1;
int j = 0;
for (; j < cnt; j++)
{
temp *= prime[i];
if (temp * prime[i] > 10000000)
{
a[3].push_back(temp);
// cout << 1 << endl;
temp = 1;
}
}
a[3].push_back(temp);
}
else
{
int temp = 1;
int j = 0;
for (; j < cnt; j++)
{
temp *= prime[i];
if (temp * prime[i] > 10000000)
{
a[2].push_back(temp);
// cout << 1 << endl;
temp = 1;
}
}
a[2].push_back(temp);
}
if (flag)
break;
}
if (a[2].size() == 0)
a[2].push_back(1);
if (a[3].size() == 0)
a[3].push_back(1);
cout << a[2].size() << " " << a[3].size() << endl;
for (int i = 0; i < a[2].size(); ++i)
printf("%d ", a[2][i]);
puts("");
for (int i = 0; i < a[3].size(); ++i)
printf("%d ", a[3][i]);
puts("");
}#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, tot, a[100005], b[100005], z[10000005], pos[10000005], q[1000005], t1[1000005], t2[1000005];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i)
scanf("%d", &b[i]);
for (int i = 2; i <= 10000000; ++i)
if (!z[i])
{
for (int j = i; j <= 10000000; j += i)
z[j] = i;
q[++tot] = i;
pos[i] = tot;
}
for (int i = 1; i <= n; ++i)
{
int k = a[i];
while (k != 1)
{
t1[pos[z[k]]]++;
k /= z[k];
}
}
for (int i = 1; i <= m; ++i)
{
int k = b[i];
while (k != 1)
{
t2[pos[z[k]]]++;
k /= z[k];
}
}
for (int i = 1; i <= tot; ++i)
{
t1[i] = min(t1[i], t2[i]);
t2[i] = t1[i];
}
printf("%d %d\n", n, m);
for (int i = 1; i <= n; ++i)
{
int k = a[i], p = a[i];
while (k != 1)
{
if (t1[pos[z[k]]])
{
p /= z[k];
t1[pos[z[k]]]--;
}
k /= z[k];
}
printf("%d ", p);
}
printf("\n");
for (int i = 1; i <= m; ++i)
{
int k = b[i], p = b[i];
while (k != 1)
{
if (t2[pos[z[k]]])
{
p /= z[k];
t2[pos[z[k]]]--;
}
k /= z[k];
}
printf("%d ", p);
}
printf("\n");
return 0;
}我们今天的关于CF 思维联系 --CodeForces -214C (拓扑排序 + 思维 + 贪心）的分享已经告一段落，感谢您的关注，如果您想了解更多关于CF--思维练习--CodeForces - 216C - Hiring Staff （思维+模拟）、CF思维联系--CodeForces - 218C E - Ice Skating （并查集）、CF思维联系– Codeforces-987C - Three displays （ 动态规划）、CF思维联系–CodeForces - 222 C Reducing Fractions(数学+有技巧的枚举）的相关信息，请在本站查询。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
