ABC276
\(\color{Green}{★}\) 表示赛时做出。
\(\color{Yellow}{★}\) 表示赛后已补。
\(\color{Red}{★}\) 表示 \(\text{To be solved}\)。
Contest
rk：708th
perf:\(\color{Blue}{1615}\)
A,B,C \(\color{Green}{★}\)
A: for 循环跑一遍。
B: 全丢 std::vector 或者 std::set 里即可。
C: std::prev_permutation() 一次即可。
D \(\color{Green}{★}\)
\(\color{Tan}{645}\)
显然，最优情况下的输出是 \(\gcd \{ a_i \}_{i=1}^n\)。
直接按照题意分解 \(\dfrac{a_i}{\gcd \{ a_i \}_{i=1}^n}\)，累计答案即可。
无解情况就是分解无法最终得到 \(1\)。
时间复杂度：\(O(n \log_2 n)\)
很难理解某人为何赛时假了 3 发。
code
int n,ans,z;bool f=1;vector<int>a;
void check(int x){
int l=sqrt(x),g=x;
while(g%2==0) g/=2,ans++;
while(g%3==0) g/=3,ans++;
if(g!=1) f=0;
}signed main(){
FST;cin>>n;a.resize(n);for(int &i:a) cin>>i;
z=a[0];for(int i:a) z=__gcd(z,i);
for(int i:a) check(i/z);cout<<(f?ans:-1);
}
E \(\color{Green}{★}\)
\(\color{Green}{1058}\)
每个点向四联通建图。
从起点往四联通跑 dfs，记录路径长度，回到起点施判断就行了。
不经过相同点开个数组打标记即可。
时间复杂度：\(O(nm)\)
罚时是因为慌乱之中把 D 的代码交到了 E 上。
code
int n,m,st;vi g[N];bool vis[N],flag=0;vector<string>a;
bool check(int x,int y){return (x>=0&&y>=0&&x<n&&y<m&&(a[x][y]=='.'||a[x][y]=='S'));}
void dfs(int u,int l){
if(u==st&&l>=4) return flag=1,void();
if(vis[u]) return ;vis[u]=1;
for(int v:g[u]) dfs(v,l+1);
}signed main(){
FST;cin>>n>>m;a.resize(n);
for(auto &i:a) cin>>i;
L(i,0,n-1) L(j,0,m-1){
if(a[i][j]=='#') continue;
if(a[i][j]=='S') st=id(i,j);
if(check(i+1,j)) g[id(i,j)].pb(id(i+1,j));
if(check(i-1,j)) g[id(i,j)].pb(id(i-1,j));
if(check(i,j+1)) g[id(i,j)].pb(id(i,j+1));
if(check(i,j-1)) g[id(i,j)].pb(id(i,j-1));
}dfs(st,0);cout<<(flag?"Yes":"No");
}
F \(\color{Green}{★}\)
\(\color{Cyan}{1562}\)
Description
给定 \(n\) 个正整数 \(a_1,a_2,\dotsb,a_n\)。
对于 \(k \in [1,n]\)，进行操作：
- 两次从 \(a_1,a_2,\dotsb,a_k\) 中等概率选取一个数。
- 得分为两个数中的较大值。
对于每个 \(k\)，求得分的期望。
\(n,a_i \le 2\cdot 10^5\)
Solution
因为对于已知的 \(k\)，情况数量已知，即 \(k^2\)。
考虑直接拆出贡献。
就拿样例为例，手磨样例可以发现，对于一个数 \(x\)，如果其在当前数列中是第 \(k\) 小，那么其贡献就是 \(x \times (2\cdot k+1)\)。
加入一个数 \(x\)，比 \(x\) 小的数贡献不变，比 \(x\) 大的数贡献增加其本身两倍。
考虑用数据结构维护，开两个权值树状数组，分别维护排名和权值和。
然后直接套式子计算即可。
时间复杂度：\(O(n \log_2 n)\)
code
const int N=2e6+100,INF=1e18;
int n,a[N],sum;Z cnt;
struct BIT{
int c[N];void add(int x,int k){for(;x<=N-100;x+=lb(x)) c[x]+=k;}
int ask(int x){int s=0;for(;x;x-=lb(x)) s+=c[x];return s;}
}t1,t2;
signed main(){
FST;cin>>n;L(i,1,n) cin>>a[i];
cnt=sum=a[1];cout<<a[1]<<'\n';
t1.add(a[1],1);t2.add(a[1],a[1]);
L(i,2,n){
int c1=t1.ask(a[i]),c2=t2.ask(a[i]);
cnt+=(c1*2+1)*a[i]+(sum-c2)*2;
Z g=i*i;cout<<cnt/g<<'\n';
t1.add(a[i],1);t2.add(a[i],a[i]);sum+=a[i];
}
}//Z 是 modint 的封装
G \(\color{Yellow}{★}\)
\(\color{Yellow}{2278}\)
Description
构造一个长为 \(n\) 的数组 \(a\)，满足：
- \(0 \le a_1 \le a_2 \le \dotsb \le a_n \le m\)
- \(\forall i \in [1,n), a_i\not\equiv a_{i+1} \pmod 3\)
求构造方案数。
\(n,m \le 10^7\)
Solution 1
为了满足限制 1，考虑构造一个 \(a\) 的差分数组 \(b\)。
那么有 \(\sum_{i=1}^{m} b_i \le m\)。
然后考虑限制 2，不难想到，先用 \(1,2\) 填充数组，再把 \(3\) 用插板法加入即可。
考虑具体的实现：
直接枚举 \(2\) 的数量，假设其为 \(x\)，需要满足 \(2 \cdot x + (n-x)=x+n \le m\)
此时的方案数就是 $$\binom{n}{x} \times \sum_{i=0}^{\left \lfloor \frac{m-n-x}{3} \right \rfloor } \binom{n+i-1}{n-1}$$
但是这样会遗漏一部分情况，如果 \(b_1\) 也就是 \(a_1 \equiv 0 \pmod 3\)，
考虑直接钦定 \(b_1=0\)，然后处理 \(n-1\) 的情况，相加即可。
时间复杂度：\(O(n+m)\)
code
int n,m;Z p[4000100];
Z sol(int n,int x){
Z s=0;p[0]=1;L(i,1,m/3) p[i]=p[i-1]+C(x+i-1,x-1);
L(i,0,n) if(i+n<=m) s+=C(n,i)*p[(m-n-i)/3];return s;
}signed main(){
FST;cin>>n>>m;init(n+m);
cout<<sol(n,n)+sol(n-1,n);
}
solution 2
跟我的赛时想法不太一样，预先鸽一手。
code
namespace math{
Z jc[30001000],ijc[30001000];
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 n<m||m<0?0:jc[n]*ijc[n-m]*ijc[m];}
}using namespace math;
#define int long long
int n,m;Z ans;
signed main(){
FST;cin>>n>>m;init((int)3e7);
L(i,0,n-1) L(x,0,2) L(y,0,2) if((m+1-x-y)%3==(n+i)%3)
ans+=C(n-1,i)*C((m+1-x-y-n-i)/3+n,n);cout<<ans;
}
EX \(\color{Red}{★}\)
\(\color{Red}{3087}\)
标签：le,int,check,color,ABC276,Green,id From： https://www.cnblogs.com/AIskeleton/p/16862226.html