2023牛客寒假算法基础集训营1(10/13)
World Final? World Cup! (I)
后面不用踢当且仅当即便后面全进，也赶不上另一方，注意还能踢几次球的计算
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int len = s.size();
int cnt1 = 0, cnt2 = 0, ans = -1;
for (int i = 0; i < len; i++) {
if (i & 1) {
if (s[i] == '1') {
cnt2++;
}
if (cnt1 > cnt2 + 5 - (i + 1) / 2 || cnt2 > cnt1 + 5 - (i + 1) / 2) {
ans = i + 1;
break;
}
} else {
if (s[i] == '1') {
cnt1++;
}
if (cnt1 > cnt2 + 5 - i / 2 || cnt2 > cnt1 + 4 - i / 2) {
ans = i + 1;
break;
}
}
}
cout << ans << '\n';
}
return 0;
}现在是，学术时间 (I)
贪心地想，只要每个教授发表自己的，引用量大于等于1即可获得1点H指数，所以统计非正数即可
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int ans = 0;
vector<LL> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > 0) {
ans++;
}
}
cout << ans << '\n';
}
return 0;
}现在是，学术时间 (II)
根据数据范围发现，点一定都在第一象限内，所以讨论p点的相对位置即可
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct point {
long long x, y;
point operator + (const point& p) {
return {x + p.x, y + p.y};
}
point operator - (const point& p) {
return {x - p.x, y - p.y};
}
double dot(const point& p) const {
return 1.0 * x * p.x + 1.0 * y * p.y;
}
double cross(const point& p) const {
return 1.0 * x * p.y - 1.0 * y * p.x;
}
double dist(const point& p) const {
return sqrt(1.0 * (x - p.x) * (x - p.x) + 1.0 * (y - p.y) * (y - p.y));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
point a, b, o;
o.x = 0;
o.y = 0;
cin >> a.x >> a.y >> b.x >> b.y;
point c, d;
c.x = a.x;
c.y = 0;
d.y = a.y;
d.x = 0;
double ans;
function<double(point, point)> calc = [&](point x, point y) {
double res = 1.0 * abs(x.x - y.x) * abs(x.y - y.y);
return res;
};
if (b.x >= a.x && b.y >= a.y) {
ans = (1.0 * a.x * a.y) / (1.0 * b.x * b.y);
} else if (b.x < a.x && b.y >= a.y) {
ans = max((calc(b, o) - calc(b, d)) / (calc(b, d) + 1.0 * a.x * a.y), (calc(b, c) - calc(b, a)) / (calc(b, a) + 1.0 * a.x * a.y));
} else if (b.x >= a.x && b.y < a.y) {
ans = max((calc(b, d) - calc(b, a)) / (calc(b, a) + 1.0 * a.x * a.y), (calc(b, o) - calc(b, c)) / (calc(b, c) + 1.0 * a.x * a.y));
} else {
ans = max({calc(b, o), calc(b, a), calc(b, c), calc(b, d)}) / (1.0 * a.x * a.y);
}
cout << fixed << setprecision(10) << ans << '\n';
}
return 0;
}鸡算几何
根据题意，判断有没有操作三，就判断铁丝是否发生了镜像的变化，因为铁丝是不会发生形变的，而且ABC和DEF不一定对应，就考虑叉积判断修改C和F是否都在AB和DE线段的逆时针方向，然后再判断此时AB和DE，BC和EF长度是否相等
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct point {
double x, y;
point operator + (const point& p) {
return {x + p.x, y + p.y};
}
point operator - (const point& p) {
return {x - p.x, y - p.y};
}
double dot(const point& p) const {
return 1.0 * x * p.x + 1.0 * y * p.y;
}
double cross(const point& p) const {
return 1.0 * x * p.y - 1.0 * y * p.x;
}
double dist(const point& p) const {
return sqrt(1.0 * (x - p.x) * (x - p.x) + 1.0 * (y - p.y) * (y - p.y));
}
};
const double eps = 1e-8;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
point a, b, c, d, e, f;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
cin >> d.x >> d.y >> e.x >> e.y >> f.x >> f.y;
point x, y, i, j;
x.x = a.x - b.x;
x.y = a.y - b.y;
y.x = c.x - b.x;
y.y = c.y - b.y;
i.x = d.x - e.x;
i.y = d.y - e.y;
j.x = f.x - e.x;
j.y = f.y - e.y;
if (x.cross(y) < 0) {
point z = a;
a = c;
c = z;
}
if (i.cross(j) < 0) {
point z = d;
d = f;
f = z;
}
x.x = a.x - b.x;
x.y = a.y - b.y;
y.x = c.x - b.x;
y.y = c.y - b.y;
i.x = d.x - e.x;
i.y = d.y - e.y;
j.x = f.x - e.x;
j.y = f.y - e.y;
if (sqrt(x.dot(x)) - sqrt(i.dot(i)) > eps || sqrt(y.dot(y)) - sqrt(j.dot(j)) > eps) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}鸡玩炸蛋人
因为图是无向图，所以先考虑没有一个炸弹的情况时，在一个联通块里的方案数是联通块大小的平方，那么答案就是所有联通块大小平方的和，如果一个联通块里存在炸弹，那么答案为存在炸弹的联通块大小的平方，如果多个联通块存在炸弹，无解
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> G(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
int root = -1;
vector<int> c(n + 1);
vector<bool> vis(n + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
if (c[i] > 0) {
root = i;
}
}
int sz = 0;
function<void(int)> dfs = [&](int u) {
for (auto v : G[u]) {
if (!vis[v]) {
vis[v] = true;
sz++;
dfs(v);
}
}
};
LL ans = 0;
if (root == -1) {
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = true;
sz = 1;
dfs(i);
ans = ans + 1LL * sz * sz;
}
}
} else {
vis[root] = true;
sz = 1;
dfs(root);
for (int i = 1; i <= n; i++) {
if (c[i] > 0 && !vis[i]) {
cout << "0\n";
return 0;
}
}
ans = ans + 1LL * sz * sz;
}
cout << ans << '\n';
return 0;
}鸡格线
通过暴力跑f(x)=round(10*sqrt(x))发现，0无论跑多少次都是0，[1,99]跑有限次就达到99不再变化，[100,∞]也是跑有限次达到100后就不再变化，所以只需要存储下来非0的下标，以及多少次操作后就不再变化的操作数，操作时只修改还会变化的，否则从数组中删去，并修改所有数的和
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b, c;
vector<bool> vis(n + 1);
LL sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
int x = a[i];
int cnt = 0;
if (x >= 100) {
while (x != 100) {
x = round(10 * sqrt(x));
cnt++;
}
b.push_back(i);
c.push_back(cnt);
} else if (x > 0) {
while (x != 99) {
x = round(10 * sqrt(x));
cnt++;
}
b.push_back(i);
c.push_back(cnt);
}
sum += a[i];
}
while (m--) {
int op;
cin >> op;
if (op == 2) {
cout << sum << '\n';
} else {
int l, r, k;
cin >> l >> r >> k;
int p = lower_bound(b.begin(), b.end(), l) - b.begin();
int q = upper_bound(b.begin(), b.end(), r) - b.begin();
int len = b.size();
if (len == 0) {
continue;
}
if (p == q) {
continue;
} else {
vector<int> z;
for (int i = p; i < q; i++) {
c[i] -= k;
if (c[i] <= 0) {
z.push_back(i);
if (a[b[i]] >= 100) {
sum -= a[b[i]];
sum += 100;
} else {
sum -= a[b[i]];
sum += 99;
}
} else {
sum -= a[b[i]];
for (int j = 0; j < k; j++) {
a[b[i]] = round(10 * sqrt(a[b[i]]));
}
sum += a[b[i]];
}
}
int len1 = z.size();
int cnt = 0;
for (int i = 0; i < len1; i++) {
b.erase(z[i] + b.begin() - cnt);
c.erase(z[i] + c.begin() - cnt);
cnt++;
}
}
}
}
return 0;
}本题主要考察了DFS
因为这张图是完整的，所以考虑一个边有多少个凸出来的以及需要有多少凹进去的与他对应，没有恰好相等的，一定需要最后一块拼图给补上缺口
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
n *= n;
vector<string> a(n);
vector<int> cnt1(4), cnt2(4);
for (int i = 1; i < n; i++) {
cin >> a[i];
for (int j = 0; j < 4; j++) {
if (a[i][j] == '1') {
cnt1[j]++;
} else if (a[i][j] == '2') {
cnt2[j]++;
}
}
}
int ans = 10;
for (int i = 0; i < 4; i++) {
if (cnt1[i] == cnt2[(i + 2) % 4]) {
} else {
if (cnt1[i] > cnt2[(i + 2) % 4]) {
ans++;
} else {
ans--;
}
}
}
cout << ans << '\n';
}
return 0;
}本题主要考察了dp
贪心地考虑，类似于100100100...1111放置，这样一定能保证坏区间是最小的
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
string s = "";
for (int i = 1; i <= n; i++) {
if (n - i >= m) {
if (i % 3 == 1) {
s += '1';
m--;
} else {
s += '0';
}
} else {
while (m) {
s += '1';
m--;
}
break;
}
}
int ans = 0;
for (int i = 0; i < n - 2; i++) {
int cnt = (s[i] == '1' ? 1 : 0) + (s[i + 1] == '1' ? 1 : 0) + (s[i + 2] == '1' ? 1 : 0);
if (cnt >= 2) {
ans++;
}
}
cout << ans << '\n';
return 0;
}本题主要考察了运气
因为问团队和问第几个人相对独立，所以分别考虑他们两个各自期望操作数是多少
问团队：一次问出，两次问出，三次问出，四次问出，四次问出，最多需要四次就能判断出，那么期望就是(1+2+3+4+4)/5
问第几个人：一次问出，两次问出，三次问出，三次问出，最多需要三次就能判断出，那么期望就是(1+2+3+3)/4
两者加起来2.8+2.25=4.05，答案为32
AC代码：
32本题主要考察了找规律
01背包，n个人背包容量为m，dp[i][j]就可以表示为前i个人占用j个空间时最大价值，因为题目没有给出物品体积，即每次需要枚举[0,m]所有体积，如果不选dp[i][j]=dp[i-1][j]，如果选，首先占用的空间不能超过背包目前占用空间j，并且此时手里有的仙贝数要大于0，此时(这次还没分配)手里的仙贝数就是(m-j+所选物品的体积)，所以产生的价值就是 所选物品体积/此时(这次还没分配)手里的仙贝数
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<double>> dp(n + 1, vector<double> (m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
for (int k = 0; k <= m; k++) {
if (j >= k && m - j + k > 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + 1.0 * k / (m - j + k));
}
}
}
}
double ans = 0.0;
for (int i = 0; i <= m; i++) {
ans = max(ans, dp[n][i]);
}
cout << fixed << setprecision(10) << ans << '\n';
return 0;
}