A 三连-签到!
using namespace std; using i64 = longlong; #define all(t) t.begin(), t.end() voidsolve() { intn; cin >> n; intans = 0; map<int, int> cnt; for (inti = 0; i < n; i++) { intx; cin >> x; cnt[x]++; } for (auto [k, v] : cnt) { ans += v / 3; } cout << ans; } signed main() { std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr); int_ = 1; // std::cin >> _; while (_--) solve(); return0; }
B 会长的牌子呢?
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m; string s; voidsolve() { intx1, x2, x3, y1, y2, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; intxx1 = x2 - x1, yy1 = y2 - y1, xx2 = x3 - x1, yy2 = y3 - y1; cout << fixed << setprecision(1) << abs(1.0 * (xx1 * yy2 - xx2 * yy1)) / 2; } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
C 走迷宫
#include <bits/stdc++.h> using namespace std; using i64 = longlong; #define all(t) t.begin(), t.end() using PII = pair<int, int>; constintINF = 0x3f3f3f3f; voidsolve() { intn, m; cin >> n >> m; vector<string> s(n + 1); vector<vector<int>> dis(n + 1, vector<int>(m + 1, 0x3f3f3f3f)); for (inti = 1; i <= n; i++) { cin >> s[i]; s[i] = ' ' + s[i]; } PII S, T; for (inti = 1; i <= n; i++) for (intj = 1; j <= m; j++) { if (s[i][j] == 'S') S = {i, j}; if (s[i][j] == 'E') T = {i, j}; } dis[S.first][S.second] = 0; queue<PII> q; q.push(S); while (q.size()) { auto [x, y] = q.front(); q.pop(); intdx[] = {0, 1, 0, -1}; intdy[] = {1, 0, -1, 0}; for (inti = 0; i < 4; i++) { inttx = x + dx[i], ty = y + dy[i]; if (tx < 1 || tx > n || ty < 1 || ty > m) continue; if (s[tx][ty] == '@') continue; if (dis[tx][ty] != INF) continue; dis[tx][ty] = dis[x][y] + 1; q.push({tx, ty}); } } cout << (dis[T.first][T.second] == INF ? -1 : dis[T.first][T.second]); } signed main() { // std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr); int_ = 1; // std::cin >> _; while (_--) solve(); return0; }
D 顺时针的正方形
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m; string s[1005]; voidsolve() { cin >> n; ll ans = 0; for (inti = 1; i <= n; i++) cin >> s[i], s[i] = ' ' + s[i]; for (inti = 1; i <= n / 2; i++) { for (intk = 1; k <= n / 2; k++) { intx1 = i, y1 = k; intx2 = k, y2 = n - i + 1; intx3 = n - i + 1, y3 = n - k + 1; intx4 = n - k + 1, y4 = i; intmxch = max(s[x1][y1], max(s[x2][y2], max(s[x3][y3], s[x4][y4]))); ans += mxch * 4 - s[x1][y1] - s[x2][y2] - s[x3][y3] - s[x4][y4]; } } cout << ans << '\n'; } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // tt=1; cin >> tt; while (tt--) solve(); }
E 据说XCPC每题首杀的气球不一样哦
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, t1[200005], t2[200005]; string s; bool ck(intt) { intsm = 0; for (inti = 1; i <= n; i++) { intns = t / (t1[i] + t2[i]); if (t - ns * (t1[i] + t2[i]) >= t1[i]) ns++; sm += ns; } returnsm >= m; } voidsolve() { cin >> n >> m; for (inti = 1; i <= n; i++) { cin >> t1[i] >> t2[i]; } intl = 0, r = mod, mid, ans = mod; while (l <= r) { mid = l + r >> 1; if (ck(mid)) ans = mid, r = mid - 1; else l = mid + 1; } cout << ans; /*intsm=0; for(inti=1;i<=n;i++){ intns=ans/(t1[i]+t2[i]); if(ans-ns*(t1[i]+t2[i])>=t1[i])ns++; cout<<ns<<' ';sm+=ns; } cout<<sm;*/ } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
F 最大子区间
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, a[200005], b[200005]; string s; voidsolve() { cin >> n >> m; intmx = 0; for (inti = 1; i <= n; i++) { cin >> a[i]; b[i] = b[i - 1] + a[i] - a[max(0, i - m)]; if (b[i] > mx) { mx = b[i]; } } // for (int i = 1; i <= 100; i++)cout << b[i] << ' '; // cout << '\n'; // cout<<mx<<'\n'; for (inti = 1; i <= n; i++) { if (b[i] == mx) { intr = i, l = max(1, i - m + 1); cout << l << ' ' << r << '\n'; while (a[l] == 0 && l + 1 <= r) { cout << ++l << ' ' << r << '\n'; } } } } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
G 最大最长子区间
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, a[200005], dp[200005], l[200005]; string s; vector<pair<int, int>> vt; voidsolve() { cin >> n; intmx = 0, mx_len = 0; l[0] = 1; for (inti = 1; i <= n; i++) { cin >> a[i]; if (dp[i - 1] + a[i] >= 0) { dp[i] = dp[i - 1] + a[i]; l[i] = l[i - 1]; } else { dp[i] = 0; l[i] = i + 1; } mx = max(mx, dp[i]); } // for(int i=1;i<=n;i++)cout<<dp[i]<<' ';cout<<'\n'; // for(int i=1;i<=n;i++)cout<<l[i]<<' ';cout<<'\n'; for (inti = 1; i <= n; i++) { if (dp[i] == mx) { intlen = i - l[i] + 1; if (len > mx_len) { vt.clear(); mx_len = len; } if (mx_len == len) vt.push_back({l[i], i}); } } for (auto it : vt) cout << it.first << ' ' << it.second << '\n'; } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
H 团建前的准备
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m; string s; map<int, map<int, int>> mp; set<int> st[200005]; priority_queue<pair<int, int>> q; priority_queue<pair<double, int>> q2; voidsolve() { cin >> n >> m; intx, y, z; for (inti = 1; i <= m; i++) { cin >> x >> y >> z; mp[x][y] = max(mp[x][y], z); st[x].insert(y); } for (inti = 1; i <= n; i++) { intw = 0; for (auto it : st[i]) w += mp[i][it]; q.push({w, i}); if (w) q2.push({1.0 * w / st[i].size(), i}); } cout << q.top().second << ' '; // 总评分最高 cout << q2.top().second << '\n'; // 防止踩雷 } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
I 赶不上团建啦
这里我用的是深搜回去找状态的方法 因为一开始是想把每条最短路径详细输出的 后来还是降低了点难度 不过没人在比赛的时候做出来 也许不该减的?
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, dis[200005], ans, cnt, lu[200005]; string s; struct node { intv, w; }; vector<node> vt[200005]; set<int> e[200005]; queue<int> q; voiddfs(intu) { if (u == 1) { // for(int i=cnt;i;i--)cout<<lu[i]<<' ';cout<<'\n'; ans++; return; } for (auto it : e[u]) { lu[++cnt] = it; dfs(it); cnt--; } } voidsolve() { cin >> n >> m; intu, v, w; memset(dis, 0x7f, sizeof(dis)); dis[1] = 0; for (inti = 1; i <= m; i++) { cin >> u >> v >> w; vt[u].push_back({v, w}); vt[v].push_back({u, w}); } q.push(1); while (!q.empty()) { intu = q.front(); q.pop(); for (auto it : vt[u]) { intv = it.v, w = it.w + dis[u]; if (w < dis[v]) { dis[v] = w; q.push(v); e[v].clear(); e[v].insert(u); } elseif(w == dis[v]) { e[v].insert(u); } } } if (dis[n] == int(0x7f7f7f7f)) cout << "-1\n"; else cout << dis[n] << '\n'; lu[++cnt] = n; dfs(n); cout << ans << '\n'; // for(int i=1;i<=n;i++)cout<<dis[i]<<' '; } intmain() { // ios::sync_with_stdio(false); // cin.tie(0);cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
J 终于团建上了
这个题本意是想让挑战者用线段树做的,但其实通过前缀差分的方法也可以 不过数据当时没捏好,有人偷偷蒙混过关了!现在数据已修正
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, a[150000], k; // 10Ěě144000ˇÖÖÓ intlowbit(intx) { returnx & -x; } voidadd(intid, intx) { for (inti = id; i <= 144000; i += lowbit(i)) a[i] += x; } inttk(intid) { intans = 0; for (inti = id; i; i -= lowbit(i)) ans += a[i]; returnans; } voidsolve() { cin >> n >> m >> k; intid, l, r; for (inti = 1; i <= k; i++) { cin >> id >> l >> r; add(l, 1); add(r + 1, -1); // for(int i=1;i<=10;i++)cout<<tk(i)<<' ';cout<<'\n'; } for (inti = 1; i <= 144000; i++) { if (n <= m - tk(i)) { cout << i; return; } } cout << "-1"; } intmain() { // ios::sync_with_stdio(false); // cin.tie(0);cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
K 最简数
应该是很简单的一个模拟 每次压缩一下再回退一下就ok了 再考虑“22”的情况,会不会一直陷入死循环
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, a[200005], b[200005]; string s; voidsolve() { cin >> n >> s; for (inti = 0; i < n; i++) { intns = 1; while (i < n - 1 && s[i] == s[i + 1]) i++, ns++; if (ns == 1) { continue; } if (ns == 2 && s[i] == '2') continue; string sr = s[i] + to_string(ns); n = n - (ns - sr.size()); i = i - ns; s.replace(i + 1, ns, sr); // cout<<s<<'\n'; } cout << s; } intmain() { // ios::sync_with_stdio(false); // cin.tie(0);cout.tie(0); tt = 1; // cin>>tt; while (tt--) solve(); }
但是每次通过replace()操作时间复杂度最坏为O(n^2),在数据足够强的话也会被卡掉 加上很多人喜欢在for(inti=0;i<s.size();i++)里面使用replace(),去看看c++的书,想想为什么不能这么干 下面是O(n)的做法
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 998244353 inttt, n, m, ns; string s, ss; voidsolve() { cin >> n >> s; for (inti = 0; i < n; i++) { if (i == n - 1 || s[i] != s[i + 1]) { cout << s[i]; continue; } // ns = 1; while (s[i] == s[i + 1]) i++, ns++; ss = s[i] + to_string(ns); if (ss == "22") { cout << "22"; continue; } for (intk = ss.size() - 1; k >= 0; k--, i--) s[i] = ss[k]; } } intmain() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); // cin>>tt; tt = 1; while (tt--) solve(); return0; }
L 梦不可及的ak
这个题就非常有意思了 总体考虑三种情况,答案分别为n,2~n-1,1 其中n的情况只有在所有数字相同的情况下得到 1的话是万能答案,但是我们求得是最大值,答案可能不是1 那么我们在排除n的情况下,只需要考虑2~n-1的情况,最后无脑输出1即可 我们从答案出发,假设n个数不断选取m个数-1,剩下的数都为x,一共选取了y次,可以发现x*n+y*m=sm,其中sm为原数组的总和 限制条件为 0<=x<=mi(mi为原数组的最小值),y>=0(非负即可)
#include <bits/stdc++.h> using namespace std; #define ll longlong #define mod 1000000007 inttt, n, m, a[200005]; string s; voidexgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return; } exgcd(b, a % b, y, x); y -= (a / b) * x; } voidsolve() { cin >> n; intmi = mod, sm = 0, mx = 0; for (inti = 1; i <= n; i++) { cin >> a[i]; mi = min(mi, a[i]); mx = max(mx, a[i]); sm = sm + a[i]; } if (mi == mx) { cout << n << '\n'; return; } for (inti = n - 1; i > 1; i--) { ll x, y, aa = n, bb = i, c = sm, gd = __gcd(aa, bb); if (sm % gd != 0) continue; aa /= gd; bb /= gd; c /= gd; exgcd(aa, bb, x, y); ll xx = x * sm, yy = y * sm; intns = xx / bb; xx -= ns * bb, yy += ns * aa; if (x < 0) xx += bb, yy -= aa; if (xx > mi || yy < 0) continue; cout << i << '\n'; return; } cout << "1\n"; } intmain() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // tt=1; cin >> tt; while (tt--) solve(); }
全部评论
(0) 回帖