一.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;
}