初来乍到，用刚刚结束的div4试试编辑器代码大部分都是给出的答案原题题解：[1692 Editorial](https://codeforces.com/blog/entry/103883) # A 马拉松 [A:Marathon](https://codeforces.com/contest/1692/problem/A) ## 题目描述考察单条件判断给定四个代表马拉松距离的值，比对比第一个大的人数 ## 解题思路 a和所有人比较，比较得出的结果直接代表了答案 ## 题解 ```c++ #include using namespace std; int t; int a,b,c,d; int n; int main(){ cin >> t; while( t-- ) { n = 0; cin >> a >> b >> c >> d; if (b > a) n++; if (c > a) n++; if (d > a) n++; cout << n << endl; } return 0; } ``` # B 不重复值 [B All Distinct](https://codeforces.com/contest/1692/problem/B) ## 题目描述考察数据结构给定一个数列，在数列中删除一个数对，保证正序的不重复且每次删除后数组长度最大 ## 解题思路先排序，再去重，如果剩下的元素和原来的数组奇偶性相同，两个两个减就不会有冲突，如果奇偶性不同，就说明有一组冲突，减去1。 ## 题解 ```c++ #include typedef long long ll; using namespace std; void solve() { int n, x; cin >> n; set a; for(int i = 0; i < n; i++) { cin >> x; a.insert(x); } if((n-a.size())%2 == 0) { cout << a.size() << endl; } else { cout << a.size()-1 << endl; } } int32_t main(){ int t = 1; cin >> t; while (t--) { solve(); } } ``` # C 象棋找象（主教） [C:Where's the Bishop?](https://codeforces.com/contest/1692/problem/C) ## 题目描述考察广度优先搜索给定一个棋盘和象的轨迹，找交叉点（也就是象所在的位置） ## 题目思路宽搜找匹配模式 ## 题解 ```c++ #include #include #include #include using namespace std; char map[8][8]; int dis[8][8]; int t; int dx[] = {1,1,-1,-1}; int dy[] = {-1,1,-1,1}; struct p{int x;int y;}; bool judge(struct p t){ struct p f[4]; int d = 4; for(int i = 0;i < 4;i++) if(map[t.x + dx[i]][ t.y + dy[i]] == '#') --d; if(d == 0) return true; else return false; } void dfs() { queue q; for(int i = 0;i < 8;i++) for(int j = 0;j < 8;j++) if(map[i][j] == '#') { q.push({i,j}); dis[i][j] = 1; } while(q.size()) { auto head = q.front(); q.pop(); if(judge(head) == true) { printf("%d %d\n",head.x + 1,head.y + 1); return; } for(int i = 0;i < 4;i++) { int x = head.x + dx[i]; int y = head.y + dy[i]; if(x>=0 && x < 8 && y >= 0 && y < 8 && dis[x][y] == 0 && map[x][y] == '#') { dis[x][y] == 1; q.push({x,y}); } } } } int main() { cin >> t; while(t--) { for(int i = 0;i < 8;i++) for(int j = 0;j < 8;j++) cin >> map[i][j]; dfs(); memset(map,0,sizeof(map)); } } ``` # D 回文钟表 [D:The Clock](https://codeforces.com/contest/1692/problem/D) ## 题目描述考察模运算给定一个时间区间，再该区间中找到回文时间 ## 解题思路一天1440分钟，符合条件的没几个，转换成数列然后直接匹配查找 ## 题解 ```c++ #include using namespace std; int a[5] = {600, 60, 0, 10, 1}; int good[16] = {0, 70, 140, 210, 280, 350, 601, 671, 741, 811, 881, 951, 1202, 1272, 1342, 1412}; void solve() { string s; cin >> s; int x; cin >> x; int tot = 0; for (int i = 0; i < 5; i++) { tot += (int)(s[i] - '0') * a[i]; } set t; for (int i = 0; i < 2022; i++) { t.insert(tot); tot += x; tot %= 1440; } int res = 0; for (int i : t) { for (int j = 0; j < 16; j++) { if (good[j] == i) {res++;} } } cout << res << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} // solve(); } ``` # E 二进制队列 [E. Binary Deque](https://codeforces.com/contest/1692/problem/E) ## 题目描述考察前缀和给定一个二进制队列，通过多少次队列操作让队列里面的数目达到给定目标 ## 解题思路求前缀和，然后再数组中单调保存最小值，然后二分找到目标值 ## 题解 ```c++ #include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i& p) { return p[r] - (l ? p[l - 1] : 0); } void solve() { int n, s; cin >> n >> s; vector a(n), p(n); forn(i, n) { cin >> a[i]; p[i] = a[i]; if(i) p[i] += p[i - 1]; } int ans = INT_MAX; for(int i = 0; i < n; ++i) { int l = i, r = n - 1, pos = -1; while(l <= r) { int mid = l + r >> 1; if(query(i, mid, p) <= s) { pos = mid; l = mid + 1; } else r = mid - 1; } if(pos == -1 || query(i, pos, p) != s) continue; ans = min(ans, n - (pos - i + 1)); } cout << (ans == INT_MAX ? -1 : ans) << "\n"; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; cin >> t; while(t--) { solve(); } } ``` # F 三数相加 [F. 3SUM](https://codeforces.com/contest/1692/problem/F) ## 题目描述考察优化给定一个数列，找出数列中三个数相加个位是3的三个数。 ## 解题思路判断个位可以把其它位抛弃，多次出现重复数字可只取三个，0-9每个数字最多出现三次，因此再长的数列都可以用三十个以内的数组表示，此时再暴查 ## 题解 ```c++ #include using namespace std; void solve() { int n; cin >> n; int cnt[10] = {}; for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x % 10]++; } vector v; for (int i = 0; i < 10; i++) { for (int j = 0; j < min(cnt[i], 3); j++) { v.push_back(i); } } int m = v.size(); for (int i = 0; i < m; i++) { for (int j = i + 1; j < m; j++) { for (int k = j + 1; k < m; k++) { if ((v[i] + v[j] + v[k]) % 10 == 3) {cout << "YES\n"; return;} } } } cout << "NO\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} // solve(); } ``` # G 指数权重 [G. 2^Sort](https://codeforces.com/contest/1692/problem/G) ## 题目描述考察对数运算和序列化、前缀和、滑动窗口或者DP 在给定的数组中，找出加权之后还满足升序要求的字串个数 ## 解题思路对于任意合法排序： $$ \begin{align} & G = 2^x*a_i<2^{x+1}*a_{i-1}\\ & \frac{G}{2^x} = a_i<2^x*a_{i-1} \end{align} $$ 上式都满足，这样就可以将指数问题转为差分问题，按先后来对比对结果进行序列化，转为顺序对和顺序错两个状态，然后再用状态数组的操作求得不同情况的最长子序列 ## 题解 ```c++ #include using namespace std; const int MAX = 200007; const int MOD = 1000000007; void solve() { int n, k; cin >> n >> k; int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } int ok[n]; for (int i = 0; i < n - 1; i++) { ok[i] = (a[i] < 2 * a[i + 1]); } int tot = 0; for (int i = 0; i < k; i++) { tot += ok[i]; } int res = 0; if (tot == k) {res++;} for (int i = k; i < n - 1; i++) { tot += ok[i]; tot -= ok[i - k]; if (tot == k) {res++;} } cout << res << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} // solve(); } ``` # H [H. Gambling](https://codeforces.com/contest/1692/problem/H) ## 题目简介考察线段数给定数组，通过设定数组边界和初值的方法，来确定带有单调权重的数组的最大和值 ## 解题思路由于题目特殊的减半和增倍，可以将猜中和猜不中转为指数运算，然后只在指数上做运算 ## 题解 ```c++ #include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i t; DynamicMaxSubarraySum(int _N, ll assign_value) { neutral = assign_value; N = _N; t.resize(4 * N); forn(i, 4 * N) t[i] = {0, 0, 0, 0}; build(1, 0, N - 1); } void build(int i, int l, int r) { if(l == r) { t[i].pref = t[i].suf = t[i].val = t[i].sum = neutral; return; } int mid = (l + r) >> 1; build(2 * i, l, mid); build(2 * i + 1, mid + 1, r); t[i] = merge(t[2 * i], t[2 * i + 1]); } node merge(node a, node b) { node c; c.pref = max(a.pref, a.sum + b.pref); c.suf = max(b.suf, b.sum + a.suf); c.val = max({a.val, b.val, a.suf + b.pref}); c.sum = a.sum + b.sum; return c; } void modif(int i, int l, int r, int pos, ll val) { if(l > pos || r < pos) return; if(l == pos && r == pos) { t[i].pref = t[i].suf = t[i].val = t[i].sum = val; return; } int mid = (l + r) >> 1; modif(2 * i, l, mid, pos, val); modif(2 * i + 1, mid + 1, r, pos, val); t[i] = merge(t[2 * i], t[2 * i + 1]); } node query(int i, int l, int r, int tl, int tr) { if(l > tr || r < tl) return {0, 0, 0, 0}; if(l >= tl && r <= tr) return t[i]; int mid = (l + r) >> 1; return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr)); } void modif(int pos, int val) { modif(1, 0, N - 1, pos, val); } node query(int l, int r) { return query(1, 0, N - 1, l, r); } node query(int pos) { return query(1, 0, N - 1, pos, pos); } }; void solve() { int n; cin >> n; vector a(n); forn(i, n) cin >> a[i]; map> vv; forn(i, n) { vv[a[i]].pb(i); } DynamicMaxSubarraySum st(n, -1); ll mx = 0, ans = -1; for(auto i: vv) { vector v = i.second; for(auto x: v) st.modif(x, 1); if(mx < st.query(0, n - 1).val) { ans = i.first; mx = st.query(0, n - 1).val; } for(auto x: v) st.modif(x, -1); } int ansl = -1, ansr = -1; for(int i = 0; i < n; ++i) { if(a[i] == ans) a[i] = 1; else a[i] = -1; } ll sum = 0, lastl = 0; mx = 0; for(int i = 0; i < n; ++i) { sum += a[i]; if(sum > mx) { mx = sum; ansr = i; ansl = lastl; } if(sum <= 0) { lastl = i + 1; sum = 0; } } cout << ans << " " << ansl + 1 << " " << ansr + 1 << "\n"; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; cin >> t; while(t--) { solve(); } } ```