写在前面
菜菜，哭哭，大佬救救QaQ
理解大佬的代码并且整理成一篇博客真的很累...
C：Tokitsukaze and a+b=n (hard)
1.本蒟蒻的代码
个人感觉用前缀和更方便。
我最开始用的是线段树，但出了三次段错误，就干脆改成前缀和了。
枚举a所在区间，这样可以得出b的范围，直接用前缀和求出合法的b数量
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define p 998244353
int n,m;
int l[400100],r[400100];
ll sum[200100];
int mx=0,mn=1e7;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>l[i]>>r[i];
if (l[i] < mn) mn = l[i];
if (r[i] > mx) mx = r[i];//小小的优化
sum[l[i]]++;
sum[r[i]+1]--;//这个时候sum是差分数组
}
for(int i=1;i<=mx+1;i++){//转化为原数组
sum[i]=sum[i-1]+sum[i];
}
for(int i=1;i<=mx+1;i++){//转化为前缀和
sum[i]=sum[i-1]+sum[i];
}
ll ans=0;
for(int i=1;i<=m;i++){
if (l[i] + mn > n || r[i] + mx < n) continue;
int x = n - min(n - 1, r[i]);
int y = n - l[i];
x=max(x,mn);//不这样的话会数组越界，当然把数组开大些也可以
y=min(y,mx);
int d = max(0, min(y, r[i]) - max(x, l[i]) + 1);//因为a，b不能在用一区间所以要减去a区间与b区间相交范围
ans = (ans + sum[y]-sum[x-1]-d) % p;
}
cout<<ans;
}
2.STL
大家可能看了jiangly的struct Z，我觉得其就是基于int定义了结构体，支持求逆元，取模操作，同时重定义了大部分运算符方便了操作。线上比赛可以直接复制过来用，但不能ctrlcv的话没必要用。
struct Z的代码放在后面
jiangly的代码使用了离散化，所以看起来非常难受
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define endl '\n'
constexpr int P = 998244353;
int n,m;
int main() {
cin >> n >> m;
vector<int> l(m), r(m), v;//大佬怎么都喜欢用vector
ll ans = 0;
for (int i = 0; i < m; i++) {
cin >> l[i] >> r[i];
v.push_back(l[i]);
v.push_back(r[i] + 1);
v.push_back(n - r[i]);
v.push_back(n - l[i] + 1);
ans -= max(min(r[i] + 1, n - l[i] + 1) - max(l[i], n - r[i]), 0);///因为a，b不能在用一区间所以要减去a区间与b区间相交范围
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
//unique是去重函数，返回一个迭代器指向去重后容器中不重复序列的最后一个元素的下一个元素
//unique函数的去重过程实际上就是不停的把后面不重复的元素移到前面来，也可以说是用不重复的元素占领重复元素的位置。
//int cnt=unique(a+1,a+1+cnt)-(a+1);
//这样可以得到元素种类数，即去重后元素个数，一般用于离散化
//如上配合erase函数可以真正删除重复元素
int cnt = v.size();
vector<int> d1(cnt), d2(cnt);
for (int i = 0; i < m; i++) {
int a = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
int b = lower_bound(v.begin(), v.end(), r[i] + 1) - v.begin();
d1[a]++;
d1[b]--;
a = lower_bound(v.begin(), v.end(), n - r[i]) - v.begin();
b = lower_bound(v.begin(), v.end(), n - l[i] + 1) - v.begin();
d2[a]++;
d2[b]--;
}
for (int i = 1; i < cnt; i++) {
d1[i] = (d1[i] + d1[i - 1]) % P;
d2[i] = (d2[i] + d2[i - 1]) % P;
}
for (int i = 0; i < cnt - 1; i++) {
ans = (ans + (ll)(d1[i]) * d2[i] % P * (v[i + 1] - v[i]) % P) % P;
}
cout << ans ;
}
struct Z的代码
constexpr int P = 998244353;
ll norm(ll x) {
return (x % P + P) % P;//浅改了一下
}
template<class T>
T power(T a, ll b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
ll x;
Z(int x = 0) : x(norm(x)) {}
Z(ll x) : x(norm(x% P)) {}
ll val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
if (x<=0) return 0;
else return power(*this, P - 2);
}
Z& operator*=(const Z& rhs) {
x = (ll)x * rhs.x % P;
return *this;
}
Z& operator+=(const Z& rhs) {
x = norm(x + rhs.x);
return *this;
}
Z& operator-=(const Z& rhs) {
x = norm(x - rhs.x);
return *this;
}
Z& operator/=(const Z& rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z& lhs, const Z& rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z& lhs, const Z& rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z& lhs, const Z& rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z& lhs, const Z& rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream& operator>>(std::istream& is, Z& a) {//可以直接>>读入<<输出
ll v;
is >> v;
a = Z(v);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Z& a) {
return os << a.val();
}
};
D：Tokitsukaze and Energy Tree
贪心，可以发现每个节点会被加Rank次，Rank为点的深度
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define endl '\n'
int n, m;
ll v[200100],Rank[200100];
vector<int> mp[200100];
void dfs(int u, int sum) {
Rank[u] = sum;
for (auto v : mp[u]) {
dfs(v, sum + 1);
}
}
int main() {
cin >> n;
Rank[1] = 1;
for (int i = 2,u; i <= n; i++) {
cin >> u;
mp[u].push_back(i);
}
dfs(1, 1);
sort(Rank + 1, Rank + 1 + n);
for (int i = 1; i <= n; i++) cin >> v[i];
sort(v + 1, v + 1 + n);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += Rank[i] * v[i];
}
cout << ans;
}
E：Tokitsukaze and Function
第一眼看过去以为是三分但在尝试各种三分后始终过不了
通过对勾函数性质可以知道x=sqrt(n)时取得极值
简单说一下为什么不能三分：
纵使我一身反骨，但加了条件的三分也没过，也可能是我太菜
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int T;
ll n,l,r;
inline ll f(ll x) { return n/x+x-1;}
int main() {
cin >> T;
while (T--) {
scanf("%lld%lld%lld",&n,&l,&r);
ll mn = f(l);
ll p = l;
if (f(r) < mn) {
mn = f(r);
p = r;
}
ll x = sqrt(n);
if (l <= x && x <= r && f(x) < mn) {
mn = f(x);
p = x;
}
x++;
if (l <= x && x <= r && f(x) < mn) {
mn = f(x);
p = x;
}
ll lo = l, hi = p;
while (lo < hi) {
ll x = (lo + hi) / 2;
if (f(x) == mn) hi = x;
else lo = x + 1;
}
cout << lo << endl;
}
}
F：Tokitsukaze and Gold Coins (easy)
k次变化后反向dp，再正向dp同时统计一下正反都能走到的点数
#include<iostream>
using namespace std;
#define endl '\n'
int T, n, k;
bool dp[500100][5], dp2[500100][5];
bool vis[500100][5];
int main() {
cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
dp[i][j] = 0;
dp2[i][j] = 0;
vis[i][j] = 0;
}
}
for (int i = 1, x, y; i <= k; i++) {
cin >> x >> y;
vis[x][y] ^= 1;
}
int ans = 0;
dp2[n][3] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 3; j >= 1; j--) {
if (j > 1 && !vis[i][j - 1]) {
dp2[i][j - 1] |= dp2[i][j];//注意一下转移的时候或一下就好了
}
if (i > 1 && !vis[i - 1][j]) {
dp2[i - 1][j] |= dp2[i][j];
}
}
}
dp[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
if (dp[i][j] && dp2[i][j] && (i != 1 || j != 1)) ans++;
if (j < 3 && !vis[i][j + 1]) {
dp[i][j + 1] |= dp[i][j];
}
if (i < n && !vis[i + 1][j]) {
dp[i + 1][j] |= dp[i][j];
}
}
}
cout << ans << endl;
}
}
G:Tokitsukaze and Gold Coins (hard)
1.空白菌的代码
空白菌也是博客园的博主，因为找题解的时候经常翻到他的博客，所以在牛客提交中一眼就看到了他的id，他的代码看起来非常舒服。
我晚点会更新更详细的注释
大体思路和czh发的题解一样
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
///线段树，建树O(nlogn)、修改查询O(logn)，单点修改、区间查询
//需要魔改内部，就把泛型删掉
template<class T, class F>
class SegmentTree {
const int n;
vector<T> node;
void update(int rt, int l, int r, int pos, F f) {
if (r < pos || l > pos) return;
if (l == r) {
node[rt] = f(node[rt]);
return;
}
int mid = l + r >> 1;
update(rt << 1, l, mid, pos, f);
update(rt << 1 | 1, mid + 1, r, pos, f);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
}
T query(int rt, int l, int r, int x, int y) {
if (l > y || r < x) return T::e();
if (x <= l && r <= y) return node[rt];
int mid = l + r >> 1;
return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
}
public:
SegmentTree(int _n):n(_n), node(_n << 2, T::e()) {}
SegmentTree(int _n, vector<T> &src):n(_n), node(_n << 2, T::e()) {
function<void(int, int, int)> build = [&](int rt, int l, int r) {
if (l == r) {
node[rt] = src[l];
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
};
build(1, 1, n);
}
void update(int pos, F f) { update(1, 1, n, pos, f); }
T query(int x, int y) { return query(1, 1, n, x, y); }
};
///节点元封装类，定义单位元"e"、合并"+"
struct T {
int val;
static T e() { return T{ 0 }; }
friend T operator+(const T &a, const T &b) { return { a.val + b.val }; }
};
///修改元封装类，定义映射"()"
struct F {
int diff;
T operator()(const T &x) { return T{ diff + x.val }; }
};
bool solve() {
int n, k;
cin >> n >> k;
set<int> st[4];
SegmentTree<T, F> sgt(n);
for (int i = 0;i <= n + 1;i++) st[0].insert(i);//中间有效区域
st[1].insert(n + 1);//左侧底部障碍物
st[3].insert(0);//右侧顶部障碍物
st[2].insert(0);
st[2].insert(n + 1);//中间障碍物
while (k--) {
int x, y;
cin >> x >> y;
if (auto it = st[y].find(x);it != st[y].end()) {
st[y].erase(it);
if (y == 2) sgt.update(x, { -1 }), st[0].insert(x);
}
else {
st[y].insert(x);
if (y == 2) sgt.update(x, { 1 }), st[0].erase(x);
}
int r = *st[1].begin() - 1;
int R = *prev(st[0].lower_bound(*st[2].lower_bound(r)));
int l = *prev(st[3].end()) + 1;
int L = *st[0].upper_bound(*prev(st[2].upper_bound(l)));
r = min(r, R);
l = max(l, L);
if (r < L || R < L || R < l) cout << 0 << '\n';
else cout << r + (n - l + 1) + (R - L + 1 - sgt.query(L, R).val) - 1 << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
H:Tokitsukaze and K-Sequence
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int T,n;
int a[100100];
int cnt[100100];
int pq[100100];
int sz=0;
int main(){
cin>>T;
while(T--){
cin>>n;
memset(cnt,0,sizeof(cnt));
sz=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
for(int i=1;i<=1e5+20;i++){
if(cnt[i]){
sz++;
pq[sz]=cnt[i];
}
}
sort(pq+1,pq+1+sz);
ll ans=0;
for(int i=1,j=1;i<=n;i++){
if(i>1)ans+=1ll*(sz-j+1);
while(pq[j]<=i&&j<=sz){
ans++;
j++;
}
cout<<ans<<endl;
}
}
}
I:Tokitsukaze and Musynx
emplace_back比push_back高效
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> x(n);
for (int i = 0; i < n; i++) {
std::cin >> x[i];
}
int a, b, c, d;
std::cin >> a >> b >> c >> d;
d++;
std::array<int, 5> v;
for (int i = 0; i < 5; i++) {
std::cin >> v[i];
}
i64 res = 0;
std::vector<std::pair<int, int>> events;
for (int i = 0; i < n; i++) {
res += v[0];
events.emplace_back(a - x[i], v[1] - v[0]);
events.emplace_back(b - x[i], v[2] - v[1]);
events.emplace_back(c - x[i], v[3] - v[2]);
events.emplace_back(d - x[i], v[4] - v[3]);
}
i64 ans = res;
std::sort(events.begin(), events.end());
for (auto [_, x] : events) {
res += x;
ans = std::max(ans, res);
}
std::cout << ans << "\n";
}
int main() {
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
J:Tokitsukaze and Sum of MxAb
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int T, n;
int a[100100];
ll sum = 0;
int main() {
cin >> T;
while (T--) {
scanf("%d", &n);
sum = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum += abs(a[i]);
}
sum = sum * n * 2;
cout << sum << endl;
}
}
K:Tokitsukaze and Synthesis and Traits
jiangly大佬原本用的是注释内的方式使用404kb
我改了一下发现区别不大使用740kb都是2ms
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define N 200000
#define B 400
int n, m, q;
int main() {
cin >> n >> m >> q;
vector<int> x(m), y(m), deg(n);
vector<vector<int>> adj(n);
vector<bitset<N>> bits(n);
//vector<bitset<N> *> bits(n);
for (int i = 0; i < m; i++) {
cin >> x[i] >> y[i];
x[i]--, y[i]--;
deg[x[i]]++, deg[y[i]]++;
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
for (int i = 0; i < n; i++) {
if (deg[i] >= B) {
for (auto j : adj[i]) bits[i][j] = 1;
//bits[i] = new bitset<N> {};
//for (auto j : adj[i]) (*bits[i])[j] = 1;
}
}
bitset<N> qry {};
while (q--) {
int k;
cin >> k;
vector<int> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i];
a[i]--;
qry[a[i]] = 1;
}
int ans = 0;
if (k >= B) {
for (int i = 0; i < m; i++) {
if (qry[x[i]] && qry[y[i]]) ans++;
}
} else {
for (auto x : a) {
if (deg[x] < B) {
for (auto y : adj[x]) {
ans += qry[y];
}
} else {
for (auto y : a) {
ans += bits[x][y];
//ans += (*bits[x])[y];
}
}
}
ans /= 2;
}
cout << ans << endl;
for (int i = 0; i < k; i++) {
qry[a[i]] = 0;
}
}
}
L:Tokitsukaze and Three Integers
蒟蒻代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int n,p;
ll dp[5010];
ll a[5010];
ll dp2[5010];
int main() {
cin >> n >> p;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
a[i]=a[i]%p;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) if(i!=j){
dp[a[i]*a[j]%p]++;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<p;j++){
dp2[(a[i]+j)%p]+=dp[j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) if(i!=j){
dp2[(a[i]*a[j]%p+a[j])%p]-=2;
}
}
for(int i=0;i<p;i++) cout<<dp2[i]<<" ";
}