今晚ABC ABCDF 题解
2026-01-24 22:21:43
发布于：广东
42阅读
0回复
0点赞
沟槽的 NOIP2025 还在追我。G 建议改名 Sale Sale Sale。
A
我懒得打循环，然后盲猜 STL 有 count 函数，然后真就自己试出来了 std::count，绷。
namespace cjdst{
void solve(){
std::string s;
std::cin >> s;
std::cout << std::count(s.begin(), s.end(), 'i') + std::count(s.begin(), s.end(), 'j') << '\n';
}
}
时间复杂度：。
B
按题意模拟即可。
namespace cjdst{
void solve(){
int n, cur = 0, flag = 0;
std::cin >> n;
while(n--){
int tmp;
std::cin >> tmp;
if(tmp == 1) cur++;
else if(tmp == 2) cur = std::max(cur - 1, 0);
else flag ^= 1;
std::cout << (flag && cur >= 3 ? "Yes\n" : "No\n");
}
}
}
时间复杂度：。
C
何意味。
我们可以把它当完全图，然后加边看成删边。最后的答案就是与它相连的边任选三个，答案就是 。
只需要记录度。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <ll> deg(n + 5, n - 1);
for(int i = 1; i <= m; i++){
int x, y;
std::cin >> x >> y;
deg[x]--, deg[y]--;
}
for(int i = 1; i <= n; i++){
std::cout << deg[i] * (deg[i] - 1) * (deg[i] - 2) / 6 << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
D
这题小时候抱过我。
注意到交换 后，所有前缀和中只有 的前缀和会变。
所以直接更新即可。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <ll> a(n + 5), pre(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
pre[i] = a[i] + pre[i - 1];
}
while(m--){
int tmp;
std::cin >> tmp;
if(tmp == 1){
int idx;
std::cin >> idx;
pre[idx] += (a[idx + 1] - a[idx]);
std::swap(a[idx], a[idx + 1]);
}else{
int l, r;
std::cin >> l >> r;
std::cout << pre[r] - pre[l - 1] << '\n';
}
}
}
}
时间复杂度：。
F
题意解析：给定一个 的 .# 矩阵。你需要将它重新染色，使得每一行与每一列都是前面的 . 后面的 #。问最小修改格数。
不难发现这个的形状大概是这样的：
令 为第 行，前 个元素是 ，后面的是 的答案最小值， 为前面的 # 的个数， 为后面的 . 的个数。则有：
前缀和优化。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <std::string> a(n + 5);
std::vector <std::vector <int>> b(n + 5, std::vector <int>(n + 5)), c(n + 5, std::vector <int>(n + 5));
for(int i = 1; i <= n; i++){
std::cin >> a[i];
a[i] = " " + a[i] + " ";
for(int j = 1; j <= n; j++){
b[i][j] = b[i][j - 1] + (a[i][j] == '#');
}
for(int j = n; j; j--){
c[i][j] = c[i][j + 1] + (a[i][j] == '.');
}
}
std::vector <std::vector <int>> dp(n + 5, std::vector <int>(n + 5)), pre(n + 5, std::vector <int>(n + 5));
for(int i = 1; i <= n; i++){
for(int j = 0; j <= n; j++){
dp[i][j] = pre[i - 1][j] + b[i][j] + c[i][j + 1];
}
pre[i][n + 1] = 0x3f3f3f3f;
for(int j = n; j >= 0; j--){
pre[i][j] = std::min(pre[i][j + 1], dp[i][j]);
}
}
std::cout << pre[n][0] << '\n';
}
}
时间复杂度：。
有帮助，赞一个