在机房其它人都有许多的橙名小号后我终于大号上橙了（果然还是太菜了），写篇博客记录一下。
计数水平太弱，赛场最后 5 分钟乱糊了一个 F 的做法，后来发现其它人做法都短好多。
A & B & C
模拟即可。
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
void solve(){
ll w=read(),d=read(),h=read();
ll a=read(),b=read(),f=read(),g=read();
printf("%lld\n",h+min({abs(a-w)+abs(b-g)+abs(w-f),abs(a-0)+abs(b-g)+abs(f-0),abs(a-f)+abs(b-0)+abs(g-0),abs(a-f)+abs(b-d)+abs(g-d)}));
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=1000003;
int n;
int a[N];
void solve(){
n=read();
for(int i=0;i<=n;++i) a[i]=0;
for(int i=1;i<=n;++i) ++a[read()];
for(int i=1;i<=n;++i) a[i]+=a[i-1];
int res=0;
for(int x=0;x<=n;++x){
int t=a[max(x-1,0)];
if(t==x&&(!x||a[x]==a[x-1])) ++res;
}
printf("%d\n",res);
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=1000003;
int n;
char s[N];
void solve(){
scanf("%d%s",&n,s+1);
vector<int> c(26,0);
vector<pii> t(26);
for(int i=1;i<=n;++i) ++c[s[i]-97];
for(int i=0;i<26;++i) t[i]=pii(c[i],i);
sort(t.begin(),t.end(),greater<pii>());
ll res=1e18;
int pos=0;
for(int x=1;x<=26;++x){
if(n%x) continue;
ll ans=0;
for(int i=0;i<26;++i){
if(n/x<t[i].fi) ans+=t[i].fi-n/x;
}
for(int i=x;i<26;++i) ans+=t[i].fi;
if(ans<res) pos=x,res=ans;
}
vector<int> pp(26,0),stk;
for(int i=0;i<26;++i){
if(t[i].fi>n/pos)
pp[t[i].se]=t[i].fi-n/pos;
else if(i>=pos)
pp[t[i].se]=t[i].fi;
else{
int tt=n/pos-t[i].fi;
while(tt--) stk.emplace_back(t[i].se);
}
}
printf("%lld\n",res);
for(int i=1;i<=n;++i){
if(pp[s[i]-97]){
--pp[s[i]-97];
putchar(stk.back()+97);
stk.pop_back();
}
else putchar(s[i]);
}
putchar('\n');
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}
D
经典 +x 问题，考虑作差找不变量 \(a_i-a_j\)，分解之后解出所有可能的 \(x\) check 即可。
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
int A[103];
int n;
set<ll> s[103];
void proc(int x,int y){
int t=A[y]-A[x];
for(int i=1;i*i<=t;++i)
if(t%i==0){
int a=i,b=t/i;
if((a^b)&1) continue;
ll p=(b-a)/2;
ll q=(b+a)/2;
p*=p;q*=q;
if(q>=A[y]&&p>=A[x]){
s[y].emplace(q-A[y]);
s[x].emplace(p-A[x]);
}
}
}
map<ll,int> mp;
void solve(){
n=read();
for(int i=1;i<=n;++i) A[i]=read(),s[i].clear();
int res=1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j) proc(i,j);
mp.clear();
for(int i=1;i<=n;++i)
for(ll x:s[i]) ++mp[x];
for(pair<ll,int> cur:mp) res=max(res,cur.se);
printf("%d\n",res);
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}
E
猜测答案为矩形之并。
考虑一维也就是区间怎么做，如果是按左端点/右端点排序的话不好扩展，任意顺序考虑这样做：对左/右端点维护一个 set，每次加入一个区间删除被严格包含的所有区间，然后把区间设为前驱的右端点 +1 和后继的左端点 -1。
于是我们先对第二维为 \([1,2]\) 的区间跑一边上述做法，然后再对 \([1,1],[2,2]\) 与 \([1,2]\) 一起分别跑即可。
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=400003;
struct rect{
int u,d,l,r,id;
}s[N];
bool cmp(rect x,rect y){return x.r<y.r;}
bool cmpid(rect x,rect y){return x.id<y.id;}
set<pii> o;
void solve(){
int n=read();
for(int i=1;i<=n;++i){
s[i].u=read();
s[i].l=read();
s[i].d=read();
s[i].r=read();
s[i].id=i;
}
sort(s+1,s+n+1,cmp);
o.clear();
for(int i=1;i<=n;++i){
if(s[i].u==1&&s[i].d==2){
if(s[i].l<=s[i].r){
set<pii>::iterator it=o.lower_bound(pii(s[i].l,0));
while(it!=o.end()&&it->fi<=s[i].r){
if(s[it->se].r>s[i].r){s[i].r=it->fi-1;break;}
else{s[it->se].u=2;s[it->se].d=1;o.erase(it);}
it=o.lower_bound(pii(s[i].l,0));
}
it=o.lower_bound(pii(s[i].l,0));
if(it!=o.begin()) s[i].l=max(s[i].l,s[prev(it)->se].r+1);
}
if(s[i].l<=s[i].r) o.emplace(s[i].l,i);
}
}
o.clear();
for(int i=1;i<=n;++i) if(s[i].u==1&&s[i].d==2&&s[i].l<=s[i].r) o.emplace(s[i].l,i);
for(int i=1;i<=n;++i){
if(s[i].u==1&&s[i].d==1){
if(s[i].l<=s[i].r){
set<pii>::iterator it=o.lower_bound(pii(s[i].l,0));
while(it!=o.end()&&it->fi<=s[i].r){
if(s[it->se].r>s[i].r){s[i].r=it->fi-1;break;}
else{s[it->se].u=2;o.erase(it);}
it=o.lower_bound(pii(s[i].l,0));
}
it=o.lower_bound(pii(s[i].l,0));
if(it!=o.begin()) s[i].l=max(s[i].l,s[prev(it)->se].r+1);
}
if(s[i].l<=s[i].r) o.emplace(s[i].l,i);
}
}
o.clear();
for(int i=1;i<=n;++i) if(s[i].u==1&&s[i].d==2&&s[i].l<=s[i].r) o.emplace(s[i].l,i);
for(int i=1;i<=n;++i){
if(s[i].u==2&&s[i].d==2){
if(s[i].l<=s[i].r){
set<pii>::iterator it=o.lower_bound(pii(s[i].l,0));
while(it!=o.end()&&it->fi<=s[i].r){
if(s[it->se].r>s[i].r){s[i].r=it->fi-1;break;}
else{s[it->se].d=1;o.erase(it);}
it=o.lower_bound(pii(s[i].l,0));
}
it=o.lower_bound(pii(s[i].l,0));
if(it!=o.begin()) s[i].l=max(s[i].l,s[prev(it)->se].r+1);
}
if(s[i].l<=s[i].r) o.emplace(s[i].l,i);
}
}
sort(s+1,s+n+1,cmpid);
long long res=0;
for(int i=1;i<=n;++i){
if(s[i].u<=s[i].d&&s[i].l<=s[i].r)
res+=(s[i].d-s[i].u+1)*(s[i].r-s[i].l+1);
}
printf("%lld\n",res);
for(int i=1;i<=n;++i){
if(s[i].u<=s[i].d&&s[i].l<=s[i].r){
printf("%d %d %d %d\n",s[i].u,s[i].l,s[i].d,s[i].r);
}
else puts("0 0 0 0");
}
}
int main(){
int tc=read();
while(tc--) solve();
return 0;
}
拒绝当口胡型选手。
首先原题过程发现有点难以维护，考虑直接对最终的括号串进行 DP。
我们将同一次操作插入的两个字符串匹配，在最终的括号串中发现这也是一个”括号串“的结构。
假设对于一个最终串，我们同时 DP 出了它的字符状态和匹配状态，那么原问题的结果应当是插入这些匹配的顺序乘这种方案数。
注意这些匹配是不能随便插入的，如 \(\texttt{)()(}\)，第一个字符和第四个字符构成的匹配必须比中间的匹配先插入。
这些匹配是一个树形结构，那么插入顺序的方案数相当于树形拓扑序方案数 \(n!\prod_{i=1}^n \frac{1}{size_i}\)，将 \(\frac{1}{size_i}\) 放入 DP 中统计即可。
具体怎么 DP：考虑每次在首尾加入一对 \(\texttt{)(}\) 或 \(\texttt{()}\)，对于中间那段括号串的影响相当于将其前缀和折线整体上移/整体下移。
设 \(g_{i,j}\) 表示长度为 \(2i\) 的且首尾一定是一对匹配的括号串（不一定合法），其前缀和最小值为 \(j\) 的方案数。
\(f_{i,j}\) 表示若干个 \(g_{i,j}\) 中的串拼起来，长度为 \(2i\)，前缀和最小值为 \(j\) 的方案数。
前后加匹配：\(\frac{pf_{i,x}}{i+1}\to g_{i+1,x+1}\) 和 \(\frac{(1-p)f_{i,x}}{i+1}\to g_{i+1,x-1}\)
拼接两个串的转移： \(f_{i,x}g_{j,y}\to f_{i+j,\min(x,y)}\)，前缀和优化一下。
最后别忘了除以总方案变成概率以及乘上 \(n!\)。
总复杂度 \(O(n^3)\)。
#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=503,P=998244353;
typedef long long ll;
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
a=(ll)a*a%P;b>>=1;
}
return res;
}
int f[N][N],g[N][N],dp[N][N],h[N],inv[N];
int n,p;
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
int pref[N][N],preg[N][N],res[N];
void convol(int t){
for(int i=0;i<=t;++i)
for(int j=0;j<=t;++j){
pref[i][j]=f[i][j];
preg[i][j]=g[i][j];
if(j){
inc(pref[i][j],pref[i][j-1]);
inc(preg[i][j],preg[i][j-1]);
}
}
for(int i=0;i<t;++i)
for(int j=0;j<=t;++j){
inc(f[t][j],(ll)pref[i][j]*g[t-i][j]%P);
if(j) inc(f[t][j],(ll)preg[t-i][j-1]*f[i][j]%P);
}
}
int main(){
n=read();p=(ll)read()*qp(10000)%P;inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
int res=1;
f[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<i;++j){
inc(g[i][max(j-1,0)],(ll)f[i-1][j]*p%P*inv[i]%P);//()
inc(g[i][j+1],(ll)f[i-1][j]*(P+1-p)%P*inv[i]%P);//)(
}
convol(i);
res=(ll)res*i%P*qp(i+i-1)%P;
}
res=(ll)res*f[n][0]%P;
printf("%d\n",res);
return 0;
}
