目录
写在前面
比赛地址:https://codeforces.com/contest/1877。
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1423038384&auto=0&height=66" width="330"></iframe>呜呜铃果唱歌太好听了、、、
我宣布是第二喜欢的声线,第三喜欢是东北切蒲英,第一喜欢绝赞招募中。
这下不得不成为数码推了、、、
A
答案为 \(-\sum a_i\)。
懒得写代数式子推了,赛时看完题直接去手摸样例了,打 ACM 打的。
B
首先进行一次代价为 \(p\) 的通知,然后可以将村长看做一个 \(a = \infin, b = p\) 的人。
发现代价 \(b\) 均为通知一个人的代价,于是显然再选择前 \(n-1\) 小的代价即可。
排个序即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, p;
struct AdmireVega {
int a, b;
} a[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool cmp(AdmireVega fir_, AdmireVega sec_) {
return fir_.b < sec_.b;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
LL ans = 0;
n = read(), p = read();
a[0].a = n, a[0].b = p;
ans = p;
for (int i = 1; i <= n; ++ i) a[i].a = read();
for (int i = 1; i <= n; ++ i) a[i].b = read();
std::sort(a, a + n + 1, cmp);
for (int i = 1, j = 0; i < n; ++ i) {
while (a[j].a <= 0) ++ j;
ans += a[j].b;
-- a[j].a;
}
printf("%lld\n", ans);
}
return 0;
}
C
呃呃题。
因为是连续地 \(\bmod n\sim 1\),发现颜色最多只有三段:\(a_{n+1}, a_{n+1}\bmod n, 0\)。
然后手玩下规则,大力特判就行了。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, m, k;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
int Solve() {
if (k == 1) return 1;
int c = m / n;
if (k == 2) return std::min(n - 1 + c, m);
if (k == 3) return std::max(0, m - n + 1 - c);
return 0;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), m = read(), k = read();
printf("%d\n", Solve());
}
return 0;
}
D
发现这个先涂黑再涂绿的题面就是劝退的。一种涂黑的方案的贡献,实质上就是所有位于涂黑位置倍数的最大值,则选择 \(a_i\) 涂黑对于某种方案的贡献,即为 \(\max_{i | j} a_j\),这玩意可以调和级数地预处理,记为 \(f_{i}\)。
以下给出两种做法。
首先是傻逼赛时做法,考虑枚举选数方案中位置最靠后的数 \(a_i\),在此过程中维护使得贡献为 \(j\) 的方案数 \(g_j\),考虑在方案中加入了 \(a_i\) 之后对 \(g\) 的影响,显然加入后只会影响 \(j\ge f_i\) 的方案数 \(g_j\),对于 \(j=f_i\),有 \(g_{j}\leftarrow \sum_{k\le j} g_{k}\),对于 \(j>f_i\) 有 \(g_j\leftarrow 2\times g_{j}\)。
于是考虑使用权值线段树维护 \(g\),支持区间求和、区间加和区间乘即可,总时间复杂度为常数略大的 \(O(n\log n)\) 级别。
特别地,注意需要记 \(g_0 = 1\)。
然后是赛后学习的大神做法,考虑升序枚举以 \(a_i\) 的贡献 \(f_i\),考虑钦定选择 \(a_i\),并使 \(f_i\) 为总贡献的方案数。显然对于 \(f_{j} < f_i\) 的 \(a_j\) 可以任意出现在方案中,否则不能出现在方案中,记满足 \(f_j<f_i\) 的数量为 \(c\),则这样的方案数为 \(2^c\)。
预处理 \(f\) 后排序记录贡献即可,总时间复杂度是超快的 \(O(n\log n)\) 级别。
赛时,295ms:
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define ls (now<<1)
#define rs (now<<1|1)
const int kN = 1e5 + 10;
const LL p = 998244353;
//=============================================================
int n, a[kN];
int datanum, data[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
struct Node {
int L, R;
LL sum, plustag, prodtag;
}tree[kN << 2];
void Pushup(int now) {tree[now].sum = (tree[ls].sum + tree[rs].sum) % p;}//子区间合并
void Pushdown(int now)//下传 懒标记
{
LL plustag = tree[now].plustag, prodtag = tree[now].prodtag;
tree[now].plustag = 0, tree[now].prodtag = 1;
tree[ls].sum = (tree[ls].sum * prodtag % p + plustag * (tree[ls].R - tree[ls].L + 1) % p) % p;
tree[rs].sum = (tree[rs].sum * prodtag % p + plustag * (tree[rs].R - tree[rs].L + 1) % p) % p;
tree[ls].prodtag = tree[ls].prodtag * prodtag % p, tree[ls].plustag = (tree[ls].plustag * prodtag % p + plustag) % p;
tree[rs].prodtag = tree[rs].prodtag * prodtag % p, tree[rs].plustag = (tree[rs].plustag * prodtag % p + plustag) % p;
}
void Build(int now, int L, int R)//建树
{
tree[now].L = L, tree[now].R = R, tree[now].prodtag = 1;
if(L == R) {tree[now].sum = 0; return ;}
int mid = (L + R) >> 1;
Build(ls, L, mid), Build(rs, mid + 1, R);
Pushup(now);
}
void Change(int now, int L, int R, int type, LL add)
{
if(L <= tree[now].L && tree[now].R <= R) //修改 被覆盖的区间
{
if(type == 1)
tree[now].sum = (tree[now].sum * add) % p,
tree[now].prodtag = tree[now].prodtag * add % p,
tree[now].plustag = tree[now].plustag * add % p;
else
tree[now].sum = (tree[now].sum + (tree[now].R - tree[now].L + 1) * add) % p,
tree[now].plustag = (tree[now].plustag + add) % p;
return ;
}
if(tree[now].plustag || tree[now].prodtag != 1) Pushdown(now);
int mid = (tree[now].L + tree[now].R) >> 1;
if(L <= mid) Change(ls, L, R, type, add);//修改左右子区间
if(R > mid) Change(rs, L, R, type, add);
Pushup(now);//左右区间合并
}
LL Query(int now, int L, int R)
{
if(L <= tree[now].L && tree[now].R <= R) return tree[now].sum % p;//查询 被覆盖区间
if(tree[now].plustag || tree[now].prodtag != 1) Pushdown(now);
int mid = (tree[now].L + tree[now].R) >> 1;
LL ret = 0;
if(L <= mid) ret = (ret + Query(ls, L, R)) % p;//查询 左右子区间
if(R > mid) ret = (ret + Query(rs, L, R)) % p;
return ret;
}
LL Getans(int now, int L, int R) {
if (L == R) {
return 1ll * data[L] * tree[now].sum % p;
}
if(tree[now].plustag || tree[now].prodtag != 1) Pushdown(now);
int mid = (L + R) >> 1;
return (Getans(ls, L, mid) + Getans(rs, mid + 1, R)) % p;
}
void Init() {
n = read();
for (int i = 1; i <= n; ++ i) a[i] = data[i + 1] = read();
std::sort(data + 1, data + n + 1 + 1);
datanum = std::unique(data + 1, data + n + 1 + 1) - data - 1;
for (int i = 1; i <= n; ++ i) {
a[i] = std::lower_bound(data + 1, data + datanum + 1, a[i]) - data;
}
Build(1, 1, datanum);
Change(1, 1, 1, 0, 1);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
Init();
for (int i = 1; i <= n; ++ i) {
int maxa = a[i];
for (int j = i; j <= n; j += i) maxa = std::max(maxa, a[j]);
LL sum = Query(1, 1, maxa);
Change(1, maxa, maxa, 0, sum);
if (maxa < datanum) Change(1, maxa + 1, datanum, 1, 2);
}
printf("%lld\n", Getans(1, 1, datanum));
return 0;
}
大神, 46ms:
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 998244353;
//=============================================================
int n, a[kN], f[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= n; ++ i) {
for (int j = i; j <= n; j += i) {
f[i] = std::max(f[i], a[j]);
}
}
std::sort(f + 1, f + n + 1);
LL ans = 0, pow2 = 1;
for (int i = 1; i <= n; ++ i) {
ans += f[i] * pow2 % p, ans %= p;
pow2 = 2 * pow2 % p;
}
printf("%lld\n", ans);
return 0;
}
E
懂了,但不好描述。
咕咕先。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], fa[kN], into[kN];
int color[kN];
// bool vis[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
int Dfs(int u_, int now_) {
if (color[u_]) return 0;
color[u_] = now_;
return Dfs(fa[u_], (now_ == 1) ? 2 : 1) + 1;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
fa[i] = a[i], into[a[i]] ++;
}
std::queue <int> q;
for (int i = 1; i <= n; ++ i) {
if (into[i] == 0) q.push(i), color[i] = 1;
}
while (!q.empty()) {
int u_ = q.front(); q.pop();
-- into[fa[u_]];
if (color[u_] == 1 && !color[fa[u_]]) {
color[fa[u_]] = 2;
q.push(fa[u_]);
}
if (!into[fa[u_]] && !color[fa[u_]]) {
color[fa[u_]] = 1;
q.push(fa[u_]);
}
}
for (int i = 1; i <= n; ++ i) {
if (color[i]) continue;
if (Dfs(i, 2) % 2 == 1) {
printf("-1\n");
return 0;
}
}
int ans = 0;
for (int i = 1; i <= n; ++ i) {
if (color[i] == 1) ++ ans;
}
printf("%d\n", ans);
for (int i = 1; i <= n; ++ i) {
if (color[i] == 1) printf("%d ", a[i]);
}
return 0;
}
写在最后
学到了什么:
- D:枚举对象。