\(\mathcal{ARC} \mathsf{145}\)
$\color{Green}{★}\ \ $ 表示赛时做出。
$\color{Yellow}{★}\ \ $ 表示赛后已补。
$\color{Red}{★}\ \ $ 表示 \(\mathcal{To\ be\ solved}\)。
\(\mathcal{VP}\)
| score | A | B | C |
|---|---|---|---|
| 72:49 | 10:45 | 28:04 | 62:49 |
| +2 | +2 |
\(\mathcal{rk:} \mathsf{342} \mathcal{ed}\)
\(\mathcal{perf:} \color{Gold}{\mathsf{2075}}\)
\(\mathcal{A}\)
\(\color{Green}{★}\)
\(\mathcal{*Difficulty} : \color{Brown}{\mathsf{596}}\)
\(\mathcal{Description}\)
给定长为 \(n\)，由 A 和 B 组成的字符串，每次可以选择相邻两位替换成 AB。
询问原字符串是否能通过若干次操作变成回文字符串。
\(\mathcal{Solution}\)
可以发现，如果最后一个字符是 A，就可以从头开始覆盖到最后一位前，即结果为 ABB……BBA 的情况。
同理，如果开头字符为 B，就从后往前覆盖，形如 BAA……AAB。
长度为 \(2\) 的字符串要特判。
$\mathcal{code}$
/*******************************
| Author: A.I.skeleton
| Problem: A - AB Palindrome
| Contest: AtCoder - AtCoder Regular Contest 145
| URL: https://atcoder.jp/contests/arc145/tasks/arc145_a
| When: 2022-10-20 08:58:11
|
| Memory: 1024 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
#define FST ios::sync_with_stdio(0);cin.tie(0);
#define int long long
const int N=2e6+100,INF=1e18;
char s[N];int n;
signed main(){
FST;cin>>n>>(s+1);
if(n==2) return cout<<(s[1]^s[2]?"No":"Yes"),0;
cout<<((s[n]=='A'||s[1]=='B')?"Yes":"No");
}
\(\mathcal{B}\)
\(\color{Green}{★}\)
\(\mathcal{*Difficulty} : \color{Brown}{\mathsf{767}}\)
\(\mathcal{Description}\)
取石子游戏，先手每次取 \(A\) 的倍数块，后手每次取 \(B\) 的倍数块，求问先手胜利数。
\(\mathcal{Solution}\)
先考虑几个特殊情况：
- 如果 \(a > n\)，显然答案为 \(0\)。
- 如果 \(a \le b\)，此时答案为 \(\max(n-a+1,0)\)，因为 \(a>n\) 是必败态。
在此基础上，尝试证明：先手尽可能多的取走石子是最优策略。
proof
因为已经排除了 \(a \le b\) 的情况，所以此时 \(b<a\)，假设先手没有尽可能多取石子，那么剩下的石子数会 \(\ge a > b\)。
后手显然可以尽可能多的取走石子，使得剩下石子数 \(<b\)，此时为先手必败态。
所以，先手应尽量多的取走石子，否则必然为必败态。
然后不难得到，计算式为 $$\sum_{i=1}^n \left[ i \bmod a < b \right]$$
$\mathcal{code}$
/*******************************
| Author: A.I.skeleton
| Problem: B - AB Game
| Contest: AtCoder - AtCoder Regular Contest 145
| URL: https://atcoder.jp/contests/arc145/tasks/arc145_b
| When: 2022-10-20 09:08:27
|
| Memory: 1024 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FST ios::sync_with_stdio(0);cin.tie(0);
#define int long long
int n,a,b,ans;
signed main(){
FST;cin>>n>>a>>b;if(n<a) return cout<<0,0;
if(a<=b) return cout<<max(n-a+1,0ll),0;n++;
ans=max(n/a-1,0ll)*b+min(b,n%a);cout<<ans;
}
\(\mathcal{C}\)
\(\color{Green}{★}\)
\(\mathcal{*Difficulty} : \color{Blue}{\mathsf{1697}}\)
\(\mathcal{Description}\)
给定 \(n\)，输 \(2\cdot n\) 的所有排列中，将其分成两个大小为 \(n\) 的子序列 \(A,B\)，使得 \(\sum_{i=1}^n A_i \cdot B_i\) 为最大值的方案数。
\(\mathcal{Solution}\)
首先，显然最优的构造方案只有可能形如：\((1,2),(3,4),\dots,(2\cdot n-1,2\cdot n)\)。
即：对于 \(i \in \left[ 1,n \right]\)，\(2\cdot i-1\) 必须与 \(2\cdot i\) 配对。
如果把所有奇数看做左括号，偶数看做右括号，某个序列可能产生构造方案就是此序列转化的括号序列合法，也就是卡特兰数：\(\dfrac{1}{n+1} \dbinom{2 \cdot n}{n}\)
因为左括号可以随意排列，所以乘上 \(n!\)。
因为不一定所有奇数看成左括号，同理会产生 \(2^n\) 种不同的情况。
所以最后的总方案数是： $$2^n \cdot n! \cdot \dfrac{1}{n+1} \dbinom{2 \cdot n}{n} = 2^n \cdot A_{n-1}^{2\cdot n}$$
$\mathcal{code}$
/*******************************
| Author: A.I.skeleton
| Problem: C - Split and Maximize
| Contest: AtCoder - AtCoder Regular Contest 145
| URL: https://atcoder.jp/contests/arc145/tasks/arc145_c
| When: 2022-10-20 09:23:49
|
| Memory: 1024 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define R(i,j,k) for(int (i)=(j);i>=(k);(i)--)
#define FST ios::sync_with_stdio(0);cin.tie(0);
const int P=998244353;
int O(int x){return x<0?(x+=P):x<P?x:(x-=P);}
template<class T>
T ksm(T a,ll b){T s=1;for(;b;b>>=1,a*=a) if(b&1) s*=a;return s;}
struct Z{
int x;Z(int x=0):x(O(x)){}Z(ll x):x(O(x%P)){}
int val()const{return x;}Z operator-()const{return Z(O(P-x));}
Z inv()const{assert(x!=0);return ksm(*this,P-2);}
Z&operator/=(const Z&r){return*this*=r.inv();}
Z&operator+=(const Z&r){x=O(x+r.x);return*this;}
Z&operator-=(const Z&r){x=O(x-r.x);return*this;}
Z&operator*=(const Z&r){x=(ll)(x)*r.x%P;return*this;}
friend Z operator*(const Z&l,const Z&r){Z s=l;s*=r;return s;}
friend Z operator+(const Z&l,const Z&r){Z s=l;s+=r;return s;}
friend Z operator-(const Z&l,const Z&r){Z s=l;s-=r;return s;}
friend Z operator/(const Z&l,const Z&r){Z s=l;s/=r;return s;}
friend ostream&operator<<(ostream&os,const Z&a){return os<<a.val();}
friend istream&operator>>(istream&is,Z&a){ll v;is>>v;a=Z(v);return is;}
};namespace math{
Z jc[1000100],ijc[1000100];
void init(int x){
jc[0]=1;L(i,1,x) jc[i]=jc[i-1]*i;
ijc[x]=jc[x].inv();R(i,x,1) ijc[i-1]=ijc[i]*i;
}Z C(int n,int m){return jc[n]*ijc[n-m]*ijc[m];}
Z A(int n,int m){/*cout<<ijc[n-m]<<endl;*/return jc[n]*ijc[n-m];}
}using namespace math;
ll qmul(ll a,ll b,ll p){
ll c=(ld)a/p*b;
ll res=(ull)a*b-(ull)c*p;
return (res+p)%p;
}ll power(ll a,ll b,ll p){
ll s=1;while(b){
if(b&1) s=qmul(s,a,p);
a=qmul(a,a,p);b>>=1;
}return s;
}
#define int long long
signed main(){
FST;int n;Z ans;cin>>n;init(n*2);
cout<<(ans=power(2,n,P)*A(n*2,n-1));
}
当然，在赛时，完全可以先写个爆搜把前几个答案打出来，然后丢到 OEIS 上。
然后把 A152029 的通项公式套回来，就能直接无脑解决这个问题。
\(\mathcal{D}\)
人类智慧题。
\(\color{Yellow}{★}\)
\(\mathcal{*Difficulty} : \color{Gold}{\mathsf{2297}}\)
\(\mathcal{Description}\)
给定 \(n,m\)，构造一个 \(n\) 个数组成的集合，其 \(\sum_{i \in S} = m\)，对于集合内任意递增的数 \(x,y,z\)，有 \(y-x \ne z-y\)。
\(\mathcal{Solution}\ \mathsf{1}\)
首先只关注最后一个限制条件。
\(y-x \ne z-y \Longrightarrow 2 \cdot \ne x+y\)。
考虑三进制下的数。
让集合 \(S\) 中所有数在三进制下的最后一位都为 \(0/1\)。
这样因为 $ x < z $ 那么 \((x+z)_{(3)}\) 中必然有一位是 \(1\)。
而 \((2\cdot y)_{(3)}\) 的每一位都只能是 \(0/2\)，这样就保证了该限制条件。
继续看 \(\sum_{i \in S} = m\) 的限制条件。
先建立一个满足上述条件的集合 \(S'\)，设 \(\sum_{i \in S'} =x\)。
集合中总共有 \(n\) 个数，所有数减去某个数相当于减去这个数乘 \(n\)。
所以要把 \(\left| m-x \right|\) 变成 \(n\) 的倍数。
因为 \(\left| m-x \right|\) 与最近的 \(n\) 的倍数的差值不会超过 \(n\)，考虑将 \(S'\) 中所有数的三进制下最后一位都设为 \(0\)，在调整时改变某一些部分，使得其最后一位变为 \(1\)，这样就同时满足了两个性质。
按照上述过程模拟即可，代码难度不大，主要偏思维。
$\mathcal{code}$
/*******************************
| Author: A.I.skeleton
| Problem: D - Non Arithmetic Progression Set
| Contest: AtCoder - AtCoder Regular Contest 145
| URL: https://atcoder.jp/contests/arc145/tasks/arc145_d
| When: 2022-10-20 10:06:44
|
| Memory: 1024 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define FST ios::sync_with_stdio(0);cin.tie(0);
const int N=2e6+100;
int n,m,del,a[N];
signed main(){
FST;cin>>n>>m;
L(i,1,n){
int c=0,g=3;
for(int j=0;j<14;j++,g*=3)
if((i&(1<<j))) c+=g;
m-=(a[i]=c);
}del=(m<0?m%n+n:(m%n));
L(i,1,del) a[i]++;del=(m-del)/n;
L(i,1,n) cout<<a[i]+del<<' ';
}
\(\mathcal{Solution}\ \mathsf{2}\)
总体思路类似，也是先构造出满足最后一个限制条件的集合 \(S'\)，再修改其中某些值使得其 \(\sum\) 与 \(m\) 的差为 \(n\) 的倍数，然后修改整个数组，但是不依赖于三进制的人类智慧。
设 \(f_(i)\) 表示大小为 \(i\) 的满足最后一个限制条件的集合 \(S'\)。
保证： \(\begin{cases}f(1)= \{ 0 \}\\f(2\cdot n) = f(n) \cup \left( f(n) + 2 \max f(n) +1 \right)\end{cases}\)
可知这样的集合是满足限制的。
然后调整其中最大的那部分值(从后往前)，使差值为 \(n\) 的倍数。
修改整个数组，输出即可。
$\mathcal{code}$
/*******************************
| Author: A.I.skeleton
| Problem: D - Non Arithmetic Progression Set
| Contest: AtCoder - AtCoder Regular Contest 145
| URL: https://atcoder.jp/contests/arc145/tasks/arc145_d
| When: 2022-10-20 10:06:44
|
| Memory: 1024 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define FST ios::sync_with_stdio(0);cin.tie(0);
int n,m;
vi work(int x){
if(x==1) return {0};
int m=(x+1)/2;auto g=work(m);
L(i,0,m-1) g.pb(g[i]+g[m-1]*2+2);
g.resize(x);return g;
}signed main(){
FST;cin>>n>>m;auto a=work(n);
int cnt=accumulate(all(a),0ll);
m-=cnt;int t=m/n;m-=t*n;
if(m<0) t--,m+=n;
for(int &i:a) i+=t;
L(i,n-m,n-1) a[i]++;
for(int i:a) cout<<i<<' ';
}
\(\mathcal{E}\)
\(\color{Red}{★}\)
\(\mathcal{*Difficulty} :\color{Black}{\mathsf{3}} \color{Goldenrod}{\mathsf{581}}\)
\(\mathcal{F}\)
\(\color{Red}{★}\)
\(\mathcal{*Difficulty} :\color{Black}{\mathsf{3}} \color{CadetBlue}{\mathsf{943}}\)