2024.2.5 寒假训练记录（19）

牛客 寒假集训2A Tokitsukaze and Bracelet

题目链接

模拟

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;void solve()
{int n;cin >> n;while (n -- ){int a, b, c;cin >> a >> b >> c;int ans = 0;if (a == 150) ans ++ ;else if (a == 200) ans += 2;if (b == 34 || b == 36 || b == 38 || b == 40) ans ++ ;else if (b == 45) ans += 2;if (c == 34 || c == 36 || c == 38 || c == 40) ans ++ ;else if (c == 45) ans += 2;cout << ans << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

牛客 寒假集训2B Tokitsukaze and Cats

题目链接

定义一个表示边界的坐标就可以了

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;void solve()
{int n, m, k;cin >> n >> m >> k;vector<bool> h(n * m + m), s(n * m + n);int ans = 0;while (k -- ){int x, y;cin >> x >> y;if (h[(x - 1) * m + y] == false) ans ++ , h[(x - 1) * m + y] = true;if (h[x * m + y] == false) ans ++ , h[x * m + y] = true;if (s[(y - 1) * n + x] == false) ans ++, s[(y - 1) * n + x] = true;if (s[y * n + x] == false) ans ++ , s[y * n + x] = true;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

牛客 寒假集训2D Tokitsukaze and Slash Draw

题目链接

想dp想了好久，本来打算如果所有状态都没变化就break，结果t了，原来是队列bfs，可以记住的trick

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;
const int mod = 1e9 + 7;void solve()
{int n, m, k;cin >> n >> m >> k;vector<PII> info(m);vector<int> ans(n, 0x3f3f3f3f3f3f3f3f);ans[0] = 0;for (int i = 0; i < m; i ++ ) cin >> info[i].first >> info[i].second;	queue<int> q;q.push(0);while (q.size()){auto t = q.front();q.pop();for (int j = 0; j < m; j ++ ){int tmp = (t + info[j].first) % n;if (ans[tmp] > ans[t] + info[j].second){ans[tmp] = ans[t] + info[j].second;q.push(tmp);}}}if (ans[n - k] == 0x3f3f3f3f3f3f3f3f) cout << -1 << '\n';else cout << ans[n - k] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

牛客 寒假集训2E Tokitsukaze and Eliminate (easy)

题目链接

牛客 寒假集训2F Tokitsukaze and Eliminate (hard)

题目链接

两道题一起说，从后往前的贪心，用set存出现过的颜色，所有颜色都出现一遍了就ans++

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;void solve()
{int n;cin >> n;vector<int> a(n);map<int, int> mp;int sum = 0;for (int i = 0; i < n; i ++ ){cin >> a[i];if (mp[a[i]] == 0) mp[a[i]] ++ , sum ++ ;else mp[a[i]] ++ ;}int ans = 0;int tmp = 0;set<int> st;int lst = n - 1;for (int i = n - 1; i >= 0; i -- ){if (st.find(a[i]) == st.end()) tmp ++ , st.insert(a[i]);if (tmp == sum){ans ++ ;for (int j = i; j <= lst; j ++ ){mp[a[j]] -- ;if (mp[a[j]] == 0) sum -- ;}st.clear();tmp = 0;lst = i - 1;}}if (!st.empty()) ans ++ ;cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

牛客 寒假集训2I Tokitsukaze and Short Path (plus)

题目链接

大的点先算，然后就没有了

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;void solve()
{int n;cin >> n;vector<int> a(n);int minn = 0x3f3f3f3f3f3f3f3f;int cnt = 0;for (int i = 0; i < n; i ++ ) cin >> a[i];int tmp = 0;int ans = 0;sort(a.begin(), a.end(), greater<int>());for (int i = 0; i < n; i ++ ) ans += (n - tmp - 1) * 4 * a[i], tmp ++ ;cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

牛客 寒假集训2J Tokitsukaze and Short Path (minus)

题目链接

小点的先算

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;void solve()
{int n;cin >> n;vector<int> a(n);int minn = 0x3f3f3f3f3f3f3f3f;int cnt = 0;for (int i = 0; i < n; i ++ ) cin >> a[i];sort(a.begin(), a.end());int ans = 0;for (int i = 0; i < n; i ++ ){if (a[i] * 2 <= a[0] * 4) ans += (n - 1 - i) * a[i] * 2 * 2;else ans += (n - 1 - i) * a[0] * 4 * 2;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

牛客 寒假集训2K Tokitsukaze and Password (easy)

题目链接

直接dfs

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;
const int mod = 1e9 + 7;void solve()
{int n;cin >> n;string s;int y;cin >> s >> y;if (s.size() == 1 && s[0] == '0'){cout << 1 << '\n';return;}if (s[0] == '0'){cout << 0 << '\n';return;}vector<vector<int>> mp(5);for (int i = 0; i < n; i ++ ){if ((s[i] >= 'a' && s[i] <= 'd') || s[i] == '_'){if (s[i] != '_') mp[s[i] - 'a'].push_back(i);else mp[4].push_back(i);}}int ans = 0;auto get = [&](string x){int res = 0;for (int i = 0; i < x.size(); i ++ ){res += pow(10, (x.size() - i - 1)) * (x[i] - '0');}return res;};vector<bool> st(11);function<void(int, string)> dfs = [&](int u, string ss){if (u == 5){int res = get(ss);if (ss[0] == '0' && ss.size() != 1) return;if (res % 8 == 0 && res <= y) ans = (ans + 1) % mod;return;}if (mp[u].size() == 0) dfs(u + 1, ss);else{string tmp = ss;for (int i = 0; i < 10; i ++ ){// if (mp[u][0] == 0 && i == 0) continue;if (u != 4 && st[i]) continue;if (u != 4) st[i] = true;for (auto t : mp[u]){tmp[t] = '0' + i;}dfs(u + 1, tmp);if (u != 4) st[i] = false;}}};dfs(0, s);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}