真欢乐吗， 不过 mission accomplished.
Rank
A. Sakurako and Water
CF2033B *900
byd 还懂难易搭配，不过这个 b 翻译甚至不着重以下主对角线差评，被硬控半个小时，直到手模样例才发觉不对。
读懂题就很简单了，最优一定是找最长的对角线每次加，一共只有 \(2n-1\) 条线，枚举一下求出每条线上的最大值之和即可。复杂度 \(\mathcal{O(n^2)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 500 + 5;
const int mod = 998244353;
int n;
int a[N][N];
namespace Wisadel
{
short main()
{
int T = qr;
while(T--)
{
n = qr; ll ans = 0;
fo(i, 1, n) fo(j, 1, n) a[i][j] = qr;
fo(j, 1, n)
{
int x = 1, y = j;
int maxx = 0;
while(x <=n && y <= n)
{
if(a[x][y] < 0) maxx = max(maxx, -a[x][y]);
x++, y++;
}
ans += maxx;
}
fo(i, 2, n)
{
int x = i, y = 1;
int maxx = 0;
while(x <= n && y <= n)
{
if(a[x][y] < 0) maxx = max(maxx, -a[x][y]);
x++, y++;
}
ans += maxx;
}
printf("%lld\n", ans);
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞
B. Binomial Coefficients, Kind Of
CF2025B *1100
这位更是唐氏。翻译没写 akshiM 求得是错误的组合数差评，被硬控 20min，直到手模才发觉不对。
读懂题就很简单了，手模容易发现 akshiM 求的是：
\[ans=\begin{cases}2^k\quad n\neq k\\ 1\quad\,\, n = k \end{cases} \]然后写个快速幂或者预处理二的幂就做完了，前者 \(\mathcal{O(T\log k)}\) 后者 \(\mathcal{O(k)}\)，不知道哪个快。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5, M = 1e6;
const int mod = 1e9 + 7;
int n[N];
namespace Wisadel
{
ll Wqp(ll x, int y)
{
ll res = 1;
while (y){if (y & 1)res = res * x % mod; x = x * x % mod; y >>= 1;}
return res;
}
short main()
{
int T = qr;
fo(i, 1, T) n[i] = qr;
fo(i, 1, T)
{
int k = qr;
printf("%lld\n", Wqp(2, n[i] == k ? 0 : k));
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞
C. QED's Favorite Permutation
CF2030D *1700
这位更是唐氏，想了半天的可持久化并查集怎么做，愣了一大圈才回头想起来可以换角度先预处理出需要的边然后做，被硬控 1.4h。
如果某个点不在自己该在的位置上那么一定需要向本来的位置移动，即当前位置到原本位置都要有边。边读入边做，好像暴力处理就行，不过我上了线段树，相当于做区间赋值操作，由于只会赋值一次所以复杂度大概处于 \(\mathcal{O(n)}\) 到 \(\mathcal{O(n\log n)}\) 之间。
然后计数当前的边，按位置记，并记录有多少该有的边没有，翻转很简单，左右做一遍就完了，同时维护上面要记的，询问只有当所有需要的边都有的时候为 YES，否则为 NO。
时间复杂度 \(\mathcal{O(n)}\) 到 \(\mathcal{O(n\log n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m;
string s;
int a[N], e[N], ned[N];
int al[N << 2];
namespace Wisadel
{
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)
inline void Wpushup(int rt)
{
al[rt] = al[ls] && al[rs];
}
inline void Wupd(int rt, int l, int r, int x, int y)
{
if(al[rt]) return ;
if(x <= l && r <= y)
{
al[rt] = 1;
return ;
}
if(al[rt]) al[ls] = al[rs] = 1;
if(x <= mid) Wupd(ls, l, mid, x, y);
if(y > mid) Wupd(rs, mid + 1, r, x, y);
Wpushup(rt);
}
inline int Wq(int rt, int l, int r, int x)
{
if(al[rt]) return 1;
if(l == r) return al[rt];
if(x <= mid) return Wq(ls, l, mid, x);
else return Wq(rs, mid + 1, r, x);
}
short main()
{
int T = qr;
while(T--)
{
n = qr, m = qr;
fill(al + 1, al + 1 + (n << 2), 0);
fill(e + 1, e + 1 + n, 0);
fo(i, 1, n)
{
a[i] = qr;
if(a[i] > i) Wupd(1, 1, n, i, a[i] - 1);
if(a[i] < i - 1) Wupd(1, 1, n, a[i], i - 1);
}
cin >> s;
s = " " + s;
fo(i, 1, n) if(s[i] == 'L') e[i - 1]++;
else e[i]++;
int lan = 0;
fo(i, 1, n - 1)
{
ned[i] = Wq(1, 1, n, i);
if(e[i] < ned[i]) lan++;
}
fo(i, 1, m)
{
int x = qr;
if(s[x] == 'L')
{
e[x - 1]--;
if(e[x - 1] < ned[x - 1]) lan++;
if(e[x] < ned[x]) lan--;
e[x]++;
s[x] = 'R';
}
else
{
e[x]--;
if(e[x] < ned[x]) lan++;
if(e[x - 1] < ned[x - 1]) lan--;
e[x - 1]++;
s[x] = 'L';
}
puts(lan == 0 ? "YES" : "NO");
}
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞
剩下的吃完饭再写。
标签：ch,int,ll,long,欢乐,加赛,fo,NOIP2024,define From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18538273