20250805

Problem - 2093D - Codeforces

/*
能很明显的知道这个肯定是要用dfs的，并且需要分块做，但是对于自己来说最初就是不会写，看了题解的
我们将这个矩形分成2 x 2的四宫格，然后依次类推。那么我们就能根据边长len算出每一个四宫格的范围，然后递归的时候就要加上这个范围值
对于op1 -> 查询(x, y)对应的值：因为我们有了这个横纵坐标，那么我们就能直接判断这个坐标在整个大矩形里的哪一个矩形中，如果在左上，那么就要加上左上的偏移量LU, 右下就要加上右下的偏移量RD以此类推。然后递归的时候，要注意对[x, y]的操作，如果在左上的话，下一步的递归对于[x, y]来说是没有变化的，但是如果是右下，那么就要变成[x - len, y - len]，因为我们最后是对递归后的小矩形做判断的，即每一步的n都要减一。
对于op2 -> 查询d所在的坐标：和上述一样，判断d所在的是哪一个小矩形里，然后加上对应的偏移量即可。这里要注意的是，每一次dfs要对d进行减的操作。
最后要注意的就是在递归到最后的时候要做返回条件的特判
*/

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 2e5 + 10, INF = 0x3f3f3f3f;#define LU 0
#define RD ((1ll << (2 * n - 2)))
#define LD ((1ll << (2 * n - 2)) * 2)
#define RU ((1ll << (2 * n - 2)) * 3)
#define len (1ll << (n - 1))int dfs1(int x, int y, int n)
{if(n == 0) return 1;if(x > len)if(y > len) return dfs1(x - len, y - len, n - 1) + RD;else return dfs1(x - len, y, n - 1) + LD;elseif(y > len) return dfs1(x, y - len, n - 1) + RU;elsereturn dfs1(x, y, n - 1) + LU;
}PII dfs2(int d, int n)
{if(n == 0)return make_pair(1, 1);if(d > LU && d <= RD) return dfs2(d - LU, n - 1);if(d > RD && d <= LD){auto [x, y] = dfs2(d - RD, n - 1);return make_pair(x + len, y + len);}if(d > LD && d <= RU){auto [x, y] = dfs2(d - LD, n - 1);return make_pair(x + len, y);}auto [x, y] = dfs2(d - RU, n - 1);return make_pair(x, y + len);
}void solve()
{int n, q;cin >> n >> q;while(q--){string op;cin >> op;if(op == "->"){int x, y;cin >> x >> y;cout << dfs1(x, y, n) << '\n';}else{int d;cin >> d;auto [x, y] = dfs2(d, n);cout << x << ' ' << y << '\n';}}return;
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

Problem - 2091E - Codeforces

/*
这个题的思路很好想，个数一定是质数的个数和1搭配，以及合数和其所有的质数搭配
问题就是控制时间复杂度，在筛合数的质数的个数的时候，如果用set来去去重的话会多一个log那么在1e7的条件下会超时，所有我们直接用last来保证上一次筛的质数和这一次的不同时再将ans++,用last可以保证去重的效果
*/

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 1e7 + 10, INF = 0x3f3f3f3f;
int primes[N], cnt, pri[N];
bool st[N];void init()
{for(int i = 2; i <= 1e7; i++){if(!st[i])primes[cnt++] = i, pri[i] = i;for(int j = 0; primes[j] <= (int)(1e7 / i); j++){st[primes[j] * i] = true;pri[primes[j] * i] = primes[j];if(i % primes[j] == 0) break;}}
}void solve()
{int n;cin >> n;int ans = 0;rep(i, 2, n){int val = i, last = -1;while(val != 1){if(pri[val] != last){ans++;last = pri[val];}val /= pri[val];}}cout << ans << '\n';
}signed main()
{IOS;int T = 1;cin >> T;init();while(T --)solve();return 0;
}

Problem - 2086C - Codeforces

/*
很明显的并查集做
因为分析样例我们可以得到的是，对于每一个改变都会影响一个圈内的数，那么我们可以直接统计出这个圈内有多少个数，然后用并查集动态维护即可

用set动态维护圈的大小也可以，代码会稍微短一些
*/

#include <bits/stdc++.h>
using namespace std;#define IOS                           \ios_base::sync_with_stdio(false); \cin.tie(0);                       \cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, p[N], d[N];struct DSU
{vector<int> p, siz;DSU(int n) : p(n + 10), siz(n + 10, 1){iota(p.begin(), p.end(), 0);}int find(int x){if (x != p[x])p[x] = find(p[x]);return p[x];}bool same(int u, int v){return find(u) == find(v);}bool merge(int x, int y){x = find(x), y = find(y);if (x == y)return false;if (siz[x] < siz[y])swap(x, y);siz[x] += siz[y];p[y] = x;return true;}
};void solve()
{cin >> n;rep(i, 1, n) cin >> p[i];rep(i, 1, n) cin >> d[i];DSU dsu(n);vector<bool> st(n + 10, false);function<void(int, int)> dfs = [&](int x, int f) -> void{if (st[x])return;st[x] = true;dsu.merge(x, f);dfs(p[x], f);};rep(i, 1, n) if (!st[i]) dfs(i, i);// rep(i, 1, n) cout << dsu.find(i) << ' ';// cout << '\n';st.assign(n + 10, false);rep(i, 1, n){int poi = d[i];int fa = dsu.find(poi);if(i == 1){cout << dsu.siz[fa] << ' ';continue;}int ffa = dsu.find(d[i - 1]);if(fa == ffa) cout << dsu.siz[fa] << ' ';else{cout << dsu.siz[fa] + dsu.siz[ffa] << ' ';dsu.merge(fa, ffa);}}cout << '\n';
}signed main()
{IOS;int T = 1;cin >> T;while (T--)solve();return 0;
}

牛客网-该题目为付费比赛题目，请购买后查看

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n;void solve()
{cin >> n;vector<int> a(n + 10);rep(i, 1, n) cin >> a[i];int now = a[n], ans = 0;for(int i = n - 1; i >= 1; i--){if(a[i] > now) ans = max(ans, a[i] - now);else now = a[i];}cout << ans << '\n';
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

牛客网-该题目为付费比赛题目，请购买后查看

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 2e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;
int n, a[N];void solve()
{cin >>n;int sum = 0;int cnt1 = 0, cnt2 = 0;rep(i, 1, n) cin >> a[i];rep(i, 1, n) if(a[i] % 2) cnt1++; else cnt2++;cout << cnt1 * cnt2 % mod << '\n';
}signed main()
{IOS;int T = 1;// cin >> T;while(T --)solve();return 0;
}

牛客网-该题目为付费比赛题目，请购买后查看

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
int primes[N], cnt, pri[N];
bool st[N];void init()
{for(int i = 2; i <= 1e6; i++){if(!st[i])primes[cnt++] = i,pri[i] = i;for(int j = 0; primes[j] <= (int)(1e6 / i); j++){st[primes[j] * i] = true;pri[primes[j] * i] = primes[j];if(i % primes[j] == 0)break;}}
}void solve()
{cin >> n;vector<int> vec;// cout << pri[6] << ' ';rep(i, 2, n){if(vec.size() == n / 2) break;if(!st[i]){vec.pb(i);continue;}int cnt = 0;int val = i;while(val != 1){cnt++;val /= pri[val];}if(cnt % 2 != 0 && (int)sqrt(i) * (int)sqrt(i) != i)vec.pb(i);}for(auto it : vec) cout << it << ' ';cout << '\n';
}signed main()
{IOS;int T = 1;cin >> T;init();while(T --)solve();return 0;
}

Problem - 2075B - Codeforces 

/*
最初的思路是对的，只不过需要分类讨论k是否等于1，因为1的时候最大值和次大值得位置和答案有关系
*/ 

#include <bits/stdc++.h>
using namespace std;#define IOS                           \ios_base::sync_with_stdio(false); \cin.tie(0);                       \cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 5e3 + 10, INF = 0x3f3f3f3f;
int n, k, a[N];void solve()
{cin >> n >> k;rep(i, 1, n) cin >> a[i];if (k != 1){sort(a + 1, a + 1 + n, greater<int>());int sum = 0;rep(i, 1, min(k + 1, n)) sum += a[i];cout << sum << '\n';return;}int maxx = 0;for (int i = 2; i <= n - 1; i++){maxx = max(maxx, a[i]);}cout << max(maxx + max(a[1], a[n]), a[1] + a[n]) << '\n';
}signed main()
{IOS;int T = 1;cin >> T;while (T--)solve();return 0;
}

Problem - 2074D - Codeforces 

/*
题目因为m的总和不超过2e5,那么有效的横坐标肯定就不超过4e5
就可以用map来做到不重不漏，用横坐标存储有效的最大的y即可
*/ 

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int x[N], r[N];
map<int, int> mp;void solve()
{cin >> n >> m;rep(i, 1, n) cin >> x[i];rep(i, 1, n) cin >> r[i];mp.clear();rep(i, 1, n){rep(j, x[i] - r[i], x[i] + r[i])mp[j] = max(mp[j], (int)sqrt(r[i] * r[i] - (j - x[i]) * (j - x[i])));}int ans = 0;for(auto [l, r] : mp)ans += r * 2 + 1;cout << ans << '\n';
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

J-Ivory_"现代汽车前瞻杯"2025牛客暑期多校训练营7 

/*
对于求 gcd(a^b, c^d), 四个数都是1e18级别的，但是可以在log^2内做完

1。设 g = gcd(a, c) 那么式子就可以写为 gcd((A*g)^b，(C*g)^d)。
    对于这里的A C，一定满足gcd(A, C) = 1。如果 gcd(A, C) = k，那么 gcd(a, c)应该等于g * k才对
2.我们每次都令b < d， 那么就可以提出公因式出来，式子变为 g^b * gcd(A^b, C^d*g^(d - b))
    更形象的可以写为 g^b * gcd(A^b, c^(d - b) * C^b), 但是因为这里的A和C是互质的，所以多乘一个C
    不会影响最后的答案，那么就可以更精简为 g^b * gcd(A^b, c^(d - b))
3.一定能在log * log的时间内完成
*/

 

#include <bits/stdc++.h>
using namespace std;#define IOS                           \ios_base::sync_with_stdio(false); \cin.tie(0);                       \cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 2e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;int qpow(int a, int k)
{int ans = 1;a %= mod; // 一定要注意防止a太大了，避免第一次乘就爆炸了while (k){if (k & 1)ans = ans * a % mod;k >>= 1;a = a * a % mod;}return ans;
}int dfs(int a, int b, int c, int d)
{if (b == 0 || d == 0)return 1;if (b > d)swap(b, d), swap(a, c);int g = __gcd(a, c);if (g == 1)return 1;return qpow(g, b) % mod * dfs(a / g, b, c, d - b) % mod;
}void solve()
{int a, b, c, d;cin >> a >> b >> c >> d;cout << dfs(a, b, c, d) << '\n';return;
}signed main()
{IOS;int T = 1;cin >> T;while (T--)solve();return 0;
}

Problem - 2055C - Codeforces

构造即可

#include<bits/stdc++.h>
using namespace std;#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;
typedef array<int, 3> ARR;const int N = 1e3 + 10, INF = 0x3f3f3f3f;
int n, m;
string s;
int a[N][N];
bool st[N][N];void solve()
{cin >> n >> m;cin >> s;rep(i, 0, n - 1) rep(j, 0, m - 1) cin >> a[i][j];PII poi = {0, 0};auto ch1 = [&]() -> void {int sum = 0;rep(i, 0, m - 1) sum += a[poi.first][i];a[poi.first][poi.second] = -sum;};auto ch2 = [&]() -> void {int sum = 0;rep(i, 0, n - 1) sum += a[i][poi.second];a[poi.first][poi.second] = -sum;};for(auto it : s)if(it == 'D'){ch1();poi.first++;}else{ch2();poi.second++;}int sum = 0;rep(i, 0, m - 1) sum += a[n - 1][i];a[n - 1][m - 1] = -sum;rep(i, 0, n - 1) rep(j, 0, m - 1) cout << a[i][j] << " \n"[j == m - 1];
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}