算法测试.

一.CodeForces 1829A

题意：

题目意思就是给你t个字符串，让你找出每个串与codeforces这个串有多少不同的字母；

题解：

定义一个变量循环比较字符串，不相同计数即可；

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int  i = h; i <= n; i++) 
#define down(i, h, n) for(int  i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 200005;
constexpr int MaxM = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;
 
 
void slove() {
	string s = "codeforces";
	string a;
	cin >> a;
	int ans = 0;
	up(i, 0, s.size()) {
		if (a[i] != s[i])
			ans++;
	}
	cout << ans << endl;
}
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		slove();
	}
}

二.CodeForces 17B

题意：

尼克的公司有 n 名员工。现在，尼克需要在公司中建立一个 "主管-同级 "关系的树状层次结构(也就是说，除了一名员工外，每名员工都有一名主管)。有 m 个应用程序以如下形式编写："员工 ai 愿意成为员工 bi 的主管，但需支付额外费用 ci "。已知每位员工的资质 qj ，对于每个申请，以下情况为真： qai > qbi 。

你能帮尼克计算出这样一个层次结构的最低成本吗？

题解：

贪心，把m条关系按照代价排序，当x的大于y的，且y没有主管即可能让x当y的主管；

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int  i = h; i <= n; i++) 
#define down(i, h, n) for(int  i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 200005;
constexpr int MaxM = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;
 
int a[1005];
int f[1005];
node {
	int x, y, c;
}e[10005];
int cmp(node x, node y) {
	return x.c < y.c;
}
int main() {
        int n;
	cin >> n;
	up(i, 1, n) {
		cin >> a[i];
	}
	int m;
	cin >> m;
	up(i, 1, m) {
		cin >> e[i].x >> e[i].y >> e[i].c;
	}
	sort(e + 1, e + m + 1, cmp);
	int ans = 0, num = 0;
	up(i, 1, m) {
		if (!f[e[i].y] && a[e[i].x] > a[e[i].y]) {
			f[e[i].y] = 1;
			ans += e[i].c;
			num++;
		}
		if (num == n - 1) {
			break;
		}
	}
	if (num == n - 1) {
		cout<<ans<<endl;
	}
	else cout<<-1<<endl;
}

三.熙巨打票

题解：

一道简单的题，注意用longlong就行

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int  i = h; i <= n; i++) 
#define down(i, h, n) for(int  i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 200005;
constexpr int MaxM = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;
 
 
void slove() {
	ll a, b, n;
	cin >> a >> b >> n;
	if (n <= 2) cout << b * n << endl;
	else if (a <= b) cout << b * n << endl;
	else cout << b*n+(n-1)/2*(a-b)<< endl;
}
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		slove();
	}
}

四.Colorful Beans

题意：

有N种豆子，这些豆子只能靠颜色来区分，每个豆子都有它的美味度；题目要求的是每种颜色豆子里面的美味度最小值的最大值；

题解：

运用map来存储最小的美味度，然后循环遍历找最大的美味度就好；

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
#include<map>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int  i = h; i <= n; i++) 
#define down(i, h, n) for(int  i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 200005;
constexpr int MaxM = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;
 
int main() {
	Ios;
	int n;
	cin >> n;
	map<int, int> p;
	up(i, 0, n - 1) {
		int a, c;
		cin >> a >> c;
		if (!p[c])p[c] = a;
		else p[c] = min(p[c], a);
	}
	int ans = 0;
	for (auto s : p) {
		ans = max(ans, s.second);
	}
	cout << ans << endl;
}

五.刻录光盘

题解：

运用floyd判断是否能拷贝给其他人，加上并查集，即可；

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int  i = h; i <= n; i++) 
#define down(i, h, n) for(int  i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 200005;
constexpr int MaxM = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;
 
int f[205];
int book[205][205];
int main() {
 
	Ios;
	int  n, t;
	cin >> n;
	up(i, 1, n) {
		cin >> t;
		while (t != 0) {
			book[i][t] = 1;
			cin >> t;
		}
	}
	up(i, 1, n) {
		f[i] = i;
	}
	up(k, 1, n) {
		up(i, 1, n) {
			up(j, 1, n) {
				if (book[i][k] && book[k][j])
					book[i][j] = 1;
			}
		}
	}
	up(i, 1, n) {
		up(j, 1, n) {
			if (book[i][j] == 1)
				f[j] = f[i];
		}
	}
	int ans = 0;
	up(i, 1, n) {
		if (f[i] == i) ans++;
	}
	cout << ans << endl;
	return 0;
}