Preface
难得这么好时间的CF，我直接找来队友组队练题
当然比赛的过程没有三人三机，就跟平时训练一样搞了个新号三人一机的写
中间因为溜去先看F了导致E题留给徐神solo因此出的偏慢，不过后面一起讨论了一下还是出了
最后开F结果好家伙我和祁神双双看错题，对着假题意苦战1h最后无奈投降，今天去再看了眼题意真想抽自己两大耳刮子
A. Goals of Victory
签到，答案就是\(-\sum_{i=1}^{n-1} a_i\)，铸币闪总因为读入了\(n\)个数导致对着样例怀疑了3min的人生
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,a[N];
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; int sum=0; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d",&a[i]),sum+=a[i]; printf("%d\n",-sum);
}
return 0;
}
B. Helmets in Night Light
题目都没看，徐神写的，签到题就不管了
#include <bits/stdc++.h>
int t, n, k;
std::pair<int, int> ab[100001];
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> t;
while(t--) {
std::cin >> n >> k;
for(int i = 0; i < n; ++i) std::cin >> ab[i].second;
for(int i = 0; i < n; ++i) std::cin >> ab[i].first;
std::sort(ab, ab + n);
int64_t ans = k;
int l = 0;
for(int i = 1; i < n; ++i) {
while(ab[l].second == 0) l += 1;
if(ab[l].first < k) {
ab[l].second -= 1;
ans += ab[l].first;
} else {
ans += k;
}
// std::cerr << "t " << ans << char(10);
}
std::cout << ans << char(10);
}
return 0;
}
C. Joyboard
差点又读假题了……
稍微手玩一下可以发现其实最后序列中的数最多只有三种，因此可以特判掉\(k>3\)的情形，同时\(k=1\)的情形也可以特判
考虑序列中的数什么时候能有两种，第一种情况是\(a_{n+1}< n\)，这种的到了前面的某个时候其中的数就会直接变成\(0\)
而另一种情况就是\(a_{n+1}\bmod n=0\)，这种的就是一步变成\(0\)，因此简单讨论一下即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,m,k;
int main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d%d",&n,&m,&k);
if (k>3) { puts("0"); continue; }
if (k==1) { puts("1"); continue; }
int c2; if (m>n) c2=m/n-1+n; else c2=m;
printf("%d\n",k==2?c2:m-c2);
}
return 0;
}
D. Effects of Anti Pimples
首先不妨令\(b_i=\max_\limits{j\bmod i=0} a_j\)，表示将\(j\)涂黑带来的最大值，计算\(b_i\)的复杂度就是调和级数的\(O(n\ln n)\)
得到\(b_i\)后不妨将其从大到小排序，考虑如果最后的方案中\(b_1\)被涂黑了那么最后的贡献就确定为\(b_1\)了，而这样的方案共有\(2^{n-1}\)种
同理对于\(b_2\)，如果它要产生贡献就要满足\(b_1\)不被涂黑且它自己要被涂黑，因此方案数就是\(2^{n-2}\)种
依此类推最后\(b_i\)的贡献就是\(2^{n-i}\)，累加起来即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int n,a[N],b[N],pw[N];
int main()
{
//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) for (j=i;j<=n;j+=i) b[i]=max(b[i],a[j]);
for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
sort(b+1,b+n+1,greater <int>()); int ans=0;
for (i=1;i<=n;++i) (ans+=1LL*b[i]*pw[n-i]%mod)%=mod;
return printf("%d",ans),0;
}
E. Autosynthesis
这种题目虽然给的不是排列，但处理方法其实都大同小异，我们可以将每个\(i\)向\(a_i\)连一条有向边
首先不妨考虑所有的入度为\(0\)的点，这些点最后一定不能被删去，我们把这些不能被删的点称为黑点
那么不难发现黑点的出点（一定唯一）一定要被删去，我们不妨将要被删去的点称为白点
同时由于白点不在最后的序列中，因此它的所有出点中一定要有至少一个黑点，要构造这些性质的话我们可以利用拓扑排序
在拓扑排序的过程中，如果当前点是黑点，就把它的出点赋值成白点并入队；而如果当前点是白点，就直接把它在图中删去
不难发现这样操作过后图中可能会剩下的只有一些环了，稍加讨论我们会发现如果环大小是奇数那么一定无解，否则可以相邻的黑板染色得到一组解
最后得到每个点的颜色后输出方案就很简单了，按序遍历每个点，如果它是黑点就输出其出点即可
#include <bits/stdc++.h>
constexpr int $n = 1000010;
int n;
int a[$n], co[$n], vi[$n], indu[$n], qu[$n];
enum {
WHITE = 0,
BLACK = 1,
};
//void dfs(int now) {
// vi[now] = 1;
// if(!vi[a[now]]) co[a[now]] = !co[now], dfs(a[now]);
// if(co[a[now]] == co[now]) {
// std::cout << "-1\n";
// exit(0);
// }
// return ;
//}
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> n;
for(int i = 1; i <= n; ++i) std::cin >> a[i], indu[a[i]] += 1;
memset(co, -1, sizeof co);
int ql = 0, qr = -1;
for(int i = 1; i <= n; ++i) if(indu[i] == 0) qu[++qr] = i, vi[i] = 1;
while(ql <= qr) {
int now = qu[ql++];
// std::cerr << "now = " << now << char(10);
if(co[now] < 0) co[now] = BLACK;
if(co[now] == BLACK) co[a[now]] = WHITE;
indu[a[now]] -= 1;
if((!indu[a[now]] || co[a[now]] == WHITE) && !vi[a[now]])
vi[a[now]] = 1, qu[++qr] = a[now];
}
int c = 0;
for(int i = 1, j; i <= n; ++i) if(indu[i]) {
co[i] = BLACK;
indu[i] = 0;
for(j = i; a[j] != i; j = a[j]) co[a[j]] = !co[j], indu[j] = 0;
indu[j] = 0;
if(co[j] == co[i]) {
std::cout << "-1\n";
return 0;
}
}
for(int i = 1; i <= n; ++i) c += co[i];
std::cout << c << '\n';
for(int i = 1; i <= n; ++i) if(co[i]) std::cout << a[i] << char(i == n ? 10 : 32);
return 0;
}
F. Lexichromatography
首先我们要发现由于题目要求对于任意一个子数组都要满足平衡性，因此值相同的数一定轮流地涂上两种颜色
因此不妨设颜色的种类数为\(tot\)，则仅考虑平衡的限制时方案数就是\(O(2^{tot})\)
那么加上第一条限制后有一种很经典地考虑方式，对于任意一种满足平衡的方案，如果它得到的两个串的字典序不同，那么我们总是将字典序较小的那个涂成蓝色
因此现在题目被我们转换成统计字典序相同的方案数了，设其为\(ret\)，则最后的答案就是\(\frac{2^{tot}-ret}{2}\)
首先可以发现当某种数出现次数为奇数时此时必然不存在相等的情况，因此接下来只考虑所有数出现次数均为偶数的情况
我们可以从左到右扫描整个序列，如果某个时刻当前两个串相等时，那么选任意一种颜色放这个字符都是可以的
否则考虑这个数能否放在较短的那个串的后面从而完成匹配，如果不能的话就只能接在较长的那个串后面了
当然还需要特判一下如果某个时刻某种数已经出现偶数次了但却没法正常匹配，这种情况也是无解的
但如果只按照这个思路去写是有点问题的，因为即使是前面已经通过一些操作使得两个串长度相同了，但由于同种数涂色一定是交替的，因此这些数的方案数其实也已经确定了
举个例子（校队群里大佬讨论了，一看就顿悟了），对于11221212这组数据，前面的1122虽然可以得到两个完全相同的串，但后面的1212哪个数跟哪个串其实也已经被唯一确定了，因此方案数是\(2\)而不是\(4\)
要解决这个问题也很简单，我们把在同一个串中的数字间连一条边，最后数一下连通块数量\(ret\)即可，字典序相同的方案数就是\(2^{ret}\)
#include<cstdio>
#include<iostream>
#include<deque>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=998244353,inv2=(mod+1)/2;
int n,m,a[N],c[N],pw[N],fa[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i)
scanf("%d",&a[i]),++c[a[i]],m=max(m,a[i]);
for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
bool flag=1; int tot=0;
for (i=1;i<=m;++i)
{
if (c[i]) ++tot;
if (c[i]&1) flag=0;
}
if (!flag) return printf("%d",pw[tot-1]),0;
deque <int> dq; memset(c,0,sizeof(c));
for (i=1;i<=m;++i) fa[i]=i;
for (i=1;i<=n;++i)
{
if (++c[a[i]],c[a[i]]%2==0&&a[i]!=dq.front())
return printf("%d",pw[tot-1]),0;
if (!dq.empty()&&dq.front()==a[i]) dq.pop_front(); else
{
if (!dq.empty()) fa[getfa(dq.front())]=getfa(a[i]);
dq.push_back(a[i]);
}
}
int ret=0; for (i=1;i<=m;++i) if (c[i]&&getfa(i)==i) ++ret;
return printf("%d",1LL*(pw[tot]-pw[ret]+mod)*inv2%mod),0;
}
Postscript
还是队里一起打比赛压力小啊，希望这种时间的CF摩多摩多
标签：902,std,now,ab,based,int,freopen,include,Round From： https://www.cnblogs.com/cjjsb/p/17751471.html