T1 茵蒂克丝
模拟题，用一个栈模拟就完了，挺简单的有人没看见是非负数
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define N 1000010
using namespace std;
int n,k,a[N],ans[N],cnt,top,tot;
pii stk[N],b[N];
bool cmp(pii x,pii y){
return x.se==y.se?x.fi<y.fi:x.se<y.se;
}
void del(){
while(top>1&&stk[top-1].fi==stk[top].fi){
stk[top-1] = {stk[top-1].fi+1,stk[top].se};
top--;
}
}
int main(){
freopen("index.in","r",stdin);
freopen("index.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i = 1;i<=n;i++){
cin>>a[i];
while(top>0&&stk[top].fi<a[i]){
b[++tot] = stk[top];
stk[top].fi++;
del();
}
stk[++top] = {a[i],i};
del();
}
while(1){
if(top==1&&stk[top].fi==30) break;
b[++tot] = stk[top];
stk[top].fi++;
del();
if(top==1&&stk[top].fi==30) break;
}
/*cerr<<tot<<"\n";
for(int i = 1;i<=tot;i++)
cerr<<b[i].fi<<" "<<b[i].se<<"\n";*/
int tmp = 1;
while(tot<k){
while(b[tmp].fi==0) tmp++;
b[tmp].fi--;
b[++tot] = b[tmp];
}
sort(b+1,b+tot+1,cmp);
/*cerr<<tot<<"\n";
for(int i = 1;i<=tot;i++)
cerr<<b[i].fi<<" "<<b[i].se<<"\n";*/
tot = 1;
for(int i = 1;i<=n;i++){
ans[++cnt] = a[i];
while(b[tot].se==i){
ans[++cnt] = b[tot].fi;
tot++;
}
}
for(int i = 1;i<=cnt;i++)
cout<<ans[i]<<" ";
return 0;
}
T2 初春饰利
\(\mathcal O(nq\log n)\) 飞过去了？
就是每一行预处理当前行排列之后的答案
具体做法就是先把当前行踢出矩阵找每一列最大值，再用当前行更新找到最佳答案
每一次 \(n\) 行分别二分查找答案，输出最大的那个
优化掉一个 \(n\) 也是十分简单
预处理多处理一个每个答案的最大要求是多少
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int n,q,b[N][N],a[N][N];
struct stlist{
int st[N][20];
inline int query(int l,int r){
if(l>r) return 0;
int k = log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
inline void pre(){
for(int i = 1;(1<<i)<=n;i++)
for(int j = 0;j+(1<<(i-1))<=n;j++)
st[j][i] = max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}T[N];
int main(){
freopen("uiharu.in","r",stdin);
freopen("uiharu.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++){
cin>>T[j].st[i][0];
a[i][j] = T[j].st[i][0];
}
for(int i = 1;i<=n;i++)
T[i].pre();
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++)
b[i][j] = max(T[j].query(1,i-1),T[j].query(i+1,n));
sort(a[i]+1,a[i]+n+1);
sort(b[i]+1,b[i]+n+1);
int cnt = n;
for(int j = 1;j<=n;j++)
if(b[i][j]<a[i][cnt]){
b[i][j] = a[i][cnt];
cnt--;
}
sort(b[i]+1,b[i]+n+1);
}
while(q--){
int x,ans = 0;cin>>x;
for(int i = 1;i<=n;i++){
int tmp = lower_bound(b[i]+1,b[i]+n+1,x)-b[i];
ans = max(ans,n-tmp+1);
if(ans==n) break;
}
cout<<ans<<"\n";
}
return 0;
}
T3 御坂美琴
麻烦的很，看懂了题解但是自己说不出来系列
首先定义 \(s_i\) 表示 \(\sum \limits_{j=1}^{i} j\) ，再定义 \(sq_i\) 表示 \(\sum \limits_{j = 1}^{i} j^2\)
为了方便假设 \(a_i\) 互不相同，显然每一个数都是答案独立的
设 \(F(P_2,S_2)\) 为 \(i \in P_2,a_i \in S_2\) 的方案总数，\(f_2(i)\) 表示 \(i\in P_2\) 的方案数，\(g_2(i)\) 表示 \(i\in S_2\) 的方案数
因为对于 \(i,a_i\) 的限制是独立的，所以可以写为 \(f_2(i) \times g_2(i)\)
但是又因为对于 \(i,a_i\) 的限制是独立的，所以 \(f_2=g_2\)
根据定义 \(f_2(i)\) 表示 \(i\in P_2 \subseteq P_1 \subseteq [1,n]\) ，不妨反过来考虑，将其定义为在位置 \(i\) 两侧嵌套两层括号的总方案数
对于左右括号来说也是相互独立的，先考虑左括号：第一层左括号在 \(j\) 的两侧时，第二层只能在套在 \([1,j]\) ，即 \(s_j\) 种，同理右括号方案数为 \(s_{n-j+1}\)
所以 \(f_2(i) = s_i\times s_{n-i+1}\) 由此推出 \(a_i\) 对 \(F(P_2,S_2)\) 的贡献为 \(f_2(i)\times g_2(i) = s_i\times s_{n-i+1} \times s_{a_i} \times s_{n-a_i+1}\)
再求 \(a_i\) 对于 \(F(P_1,S_1)\) 的贡献，即所有 \(i\in P_1,a_i \in S_1\) 的方案数
注意此时每一个区间 \(P_1(S_1)\) 并不是只计算一次，还要考虑子区间 \(P_2(S_2)\) 的个数
我们可以如法炮制设 \(f_1(i),g_1(i),F(P_1,S_1) = f_1(i) \times g_1(i)\) ，同理可得 \(f_1 = g_1\)
枚举 \(P_1\) 左右端点 \(l,r(l\le i,i\le r)\) 再乘上子区间个数，可以得：
\[f(i) = \sum\limits_{l = 1}^i\sum\limits_{r = i}^n\binom {r-l+2} 2 \]注意此处 \(r-l+2\) 是因为区间长度 \(P_1\) 为 \(r-l+1\) ，而长度为 \(len\) 的区间有 \(\binom {len+1} 2\) 个子区间
上式可化为
\[\frac 1 2\sum\limits_{l = 1}^i\sum\limits_{r = i}^n (r-l+2)(r-l+1) \]拆开可以得到
\[ \frac 1 2\sum\limits_{l = 1}^i\sum\limits_{r = i}^n r^2+l^2-2lr+3r-3l+2 \]上面可以 \(\mathcal O(n)\) 预处理 \(\mathcal O(1)\) 求
化简一下其实并不简
我们一开始假设都不相同
但是实际上只有对位置上限制的情况需要重新计算，对数值上的并不需要重算
根据上述假设，显然有 \(a_i = a_j(i<j)\) ，对于 \(a_j\) 来说，所有左端点在 \(i\) 左边的 \(P_1(P_2)\) 都没有贡献
因此假设 \(f'_1(pre,i)\) 表示 \(P_1\) 左端点在 \(pre\) 右侧的总情况数，表达式如下
\[f'_1(pre,i) = \sum\limits_{l = pre+1}^i \sum\limits_{r = i}^n \binom {r-l+2} 2 \]对比 \(f_1(i)\) ，可以发现 \(f'_1\) 相比较于 \(f_1\) 只有左端点 \(l\) 下界改变，即 \(f_1(i) = f'_1(1,i)\)
因此，\(a_i\) 对 \(F(P_1,S_1)\) 的贡献等于 \(f'_1(pre,i)\times f_1(a_i)\) ，其中 \(pre_i\) 定义为在 \(a_i\) 之前与 \(a_i\) 相等的最右边的数的位置，没有则为 \(0\)
同理，可以推出 \(f'_2(pre,i) = \sum\limits_{j = pre+1}^i j\) 因为嵌套的第一层左括号只能在 \(pre\) 右边，\(i\) 左边
对于 \(f'_2,f_2\) 来说，同样只有左端点 \(l\) 的下界改变，即 \(f_2(i) = f'_2(1,i)\)
那么 \(a_i\) 对答案的贡献即为 \(f'_1(pre,i)\times f_1(a_i) - f'_2(pre,i)\times f_2(a_i)\)
距离解出这道题还差一个总方案数，因为 \(P_1,P_2\) 与 \(S_1,S_2\) 等价，所以可由一边的数量平方得到
不妨枚举 \(P_1\) 区间长度 \(len\) ，那么就有 \(n-len+1\) 种情况，此时其子区间 \(P_2\) 有 \(\binom {len+1} 2\) 种情况
不难发现 \(s_i = \binom {i+1} 2\) 所以：
\[cnt = \sum\limits_{i = 1}^n (n-i+1)s_i \]至此，本题就解决了，时间复杂度 \(\mathcal O(n)\)抄袭题解讲解完毕
#include<bits/stdc++.h>
#define N 500010
#define mod ((int)1e9+7)
#define int long long
using namespace std;
int n,ans,cnt,s[N],sq[N],t[N];
int ksm(int x,int y){
int res = 1;
while(y){
if(y&1) res = 1ll*res*x%mod;
x = 1ll*x*x%mod;
y>>=1;
}
return res;
}
int inv(int x){
return ksm(x,mod-2);
}
int calcs(int l,int r){
return (s[r]-s[l-1]+mod)%mod;
}
int calcsq(int l,int r){
return (sq[r]-sq[l-1]+mod)%mod;
}
int f1(int l,int r){
return (calcsq(l,r)*(n-r+1)%mod+calcsq(r,n)*(r-l+1)%mod-
2*calcs(l,r)*calcs(r,n)%mod-3*calcs(l,r)*(n-r+1)%mod+
3*calcs(r,n)*(r-l+1)%mod+2*(n-r+1)*(r-l+1)%mod+mod)*(mod+1)/2%mod;
}
int f2(int l,int r){
return calcs(l,r)*s[n-r+1]%mod;
}
signed main(){
freopen("misaka.in","r",stdin);
freopen("misaka.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++){
s[i] = (s[i-1]+i)%mod;
sq[i] = (sq[i-1]+i*i)%mod;
}
int pre;
for(int i = 1;i<=n;i++){
int x;cin>>x;
pre = t[x]+1;t[x] = i;
ans = (ans+f1(pre,i)*f1(1,x)-f2(pre,i)*f2(1,x)%mod+mod)%mod;
cnt = (cnt+(n-i+1)*s[i])%mod;
}
cout<<ans*inv(cnt*cnt%mod)%mod;
return 0;
}