仮面の街
今天是 bct Day 3，賽時 \(100+20+15+50=185\)，rk.11。
沒有掛分很舒適。
評價是 ok 場，複習（？）了下期望這一塊。寫了 T1,T4 的拍子。
T1
考慮從小到大填數，這樣這個數的排名就是後面空位的數量，填到對應位置即可。
使用二分+樹狀數組，有兩個 log。
code
Show me the code
#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
i64 x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
const int N=2e5+5;
int pin[N];
int c[N];
int n;
void add(int p){
for(;p<=n;p+=(p&(-p))){
c[p]++;
}
return ;
}
int pf(int p){
int res=0;
for(;p>0;p-=(p&(-p))){
res+=c[p];
}
return res;
}
int aac(int p,int r){
return (n-p)-(r-pf(p));
}
int main(){
freopen("contest.in","r",stdin);
freopen("contest.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
int pos;
cin>>pos;
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(aac(mid,i-1)>pos)l=mid+1;
else r=mid;
}
add(l);
pin[l]=i;
}
for(int i=1;i<=n;i++){
cout<<pin[i]<<' ';
}
return 0;
}T2
沒做過期望題，但是人家出了咱就要想對吧。
考慮期望的一般步驟就是從終態往回推。於是設 \(dp_{i,j}\) 表示選了 \(i\) 個單獨的原來成對的襪子和 \(j\)
對於任意一個 \(dp_{i,j},i\ne 0\) 都可以導出一個終態 \(e_{i+1,j}=i+1+j\)，概率是 \(\dfrac{i}{2n+m-i-j}\)，也就是：
\[dp_{i,j}\leftarrow dp_{i,j}+e_{i+1,j}\times \frac{i}{2n+m-i-j} \]
接下來是正常的轉移：
\[dp_{i-1,j} \leftarrow dp_{i-1,j}+dp_{i,j} \times \frac{2n-2(i-1)}{2n+m-(i-1)-j} ,i\ne 0 \]
\[dp_{i,j-1} \leftarrow dp_{i,j-1}+dp_{i,j} \times \frac{m-(j-1)}{2n+m-i-(j-1)} ,j\ne 0 \]
答案取 \(dp_{0,0}\)，時間複雜度 \(O(nmT)\)。
關於輸出有理數，把除法換成乘法逆即可。
賽時想到這裏，20pts。
code
Show me the code
#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
i64 x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
struct que{
int n,m;
}q[20000];
i64 dp[2000][2000];
i64 e[2000][2000];
i64 poww[200000];
const int mod=1e9+7;
i64 ksm(i64 a,i64 b){
i64 res=1,k=a;
while(b){
if(b&1){
res=res*k%mod;
}
k=k*k%mod;
b>>=1;
}
return res;
}
int main(){
int T;cin>>T;
int T1=T;
int cnt=0;
bool le20=1;
poww[0]=0;
for(int i=1;i<=100000;i++){
poww[i]=ksm(i,mod-2)%mod;
}
while(T--){
cnt++;
cin>>q[cnt].n>>q[cnt].m;
if(q[cnt].n>20&&q[cnt].m>20)le20=0;
}
cnt=0;
while(T1--){
cnt++;
int n,m;
n=q[cnt].n;m=q[cnt].m;
for(int i=2;i<=n+1;i++){
for(int j=0;j<=m;j++){
e[i][j]=i+j;
}
}
for(int i=n;i>=0;i--){
for(int j=m;j>=0;j--){
dp[i][j]=(dp[i][j]%mod+(i)*poww[2*n+m-i-j]%mod*e[i+1][j]%mod)%mod;
if(i>0){
dp[i-1][j]=(dp[i-1][j]%mod+(2*n-2*(i-1))*poww[2*n+m-(i-1)-j]%mod*dp[i][j]%mod)%mod;
}
if(j>0){
dp[i][j-1]=(dp[i][j-1]%mod+(m-(j-1))*poww[2*n+m-i-(j-1)]%mod*dp[i][j]%mod)%mod;
}
}
}
cout<<dp[0][0]<<'\n';
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
dp[i][j]=0;
}
}
}
return 0;
}我們看看能不能扔掉一個 \(n\) 或者 \(m\)
我們改變定義，直接正向求解，\(dp_{i,j}\) 表示選了 \(i\) 雙襪子，\(j\)
\[dp_{i,j}=dp_{i,j-1}\times \frac{2i+j+1}{2i+j} \]
證明就是考慮展開直接使用期望的定義，也就是某個選襪子序列乘上這個序列被選到的概率。
假設我們選出的這個有 \(2i+j-1\) 個襪子在 \(k\) 位置出現了一個襪子和前面選過的襪子配上對了。那麼現在接着放入一個單襪子。這個襪子可以放在 \(2i+j\)
分襪子放在 \(k\) 前或者 \(k\) 後的情況，放 \(k\) 前有 \(k\) 個位置，也就是有 \(\dfrac{k}{2i+j}\) 的可能，還讓這個序列的答案變成了 \(k+1\)。於是期望就變成了 \((k+1)\dfrac{k}{2i+j}\)。
如果放在後面，答案不變，期望變成 \(\dfrac{2i+j-k}{2i+j}\)。
通個分就可以得到 \(dp_{i,j}=k\times \dfrac{2i+j+1}{2i+j}\)，這個 \(k\) 其實就是 \(dp_{i,j-1}\)。既然我們用 \(k\)
還有一個性質是：
\[dp_{i,0}=dp_{i-1,1}，i\ge 2 \]
這個比較好理解，因為 \(i\ge 2\)
於是，用第一個式子，我們能把 \(dp_{i,j}\) 一路展開到 \(dp_{i,0}\)，就是：
\[dp_{i,j}=dp_{i,0}\times \frac{2i+j+1}{2i+1} \]
然後你能用第二個式子把所有的 \(dp_{i,0}\)
於是你可以遞推並 \(O(1)\) 求出所有 \(dp_{i,j}\)。時間複雜度 \(O(nT)\)。
然後接下來再推式子就要科技了。放了。
T3
賽時只寫了 \(O(n!m)\)
code
Show me the code
#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
i64 x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
string s[10000];
int main(){
freopen("iqtest.in","r",stdin);
freopen("iqtest.out","w",stdout);
//
int n,m;cin>>n>>m;
vector<int> pm;
int es=1;
for(int i=1;i<=n;i++){
cin>>s[i];
pm.push_back(i);
es=es*i;
}
double eps=1.0/es;
double ans=0;
do{
int exs=(1<<m)-1;
bool fil=0;
for(int t:pm){
bool win=0,los=0;
for(int j=0;j<s[t].size();j++){
if(!((exs>>j)&1))continue;
if(s[t][j]=='1')win=1;
if(s[t][j]=='0')los=1;
}
if(win&&los){
for(int j=0;j<s[t].size();j++){
if(!((exs>>j)&1))continue;
if(s[t][j]=='0')exs^=(1<<j);
}
}
if(!(exs&1)){fil=1;break;}
}
if(fil)continue;
else ans+=eps;
}while(next_permutation(pm.begin(),pm.end()));
cout<<fixed<<setprecision(16)<<ans;
return 0;
}發現題目很多人很少，於是複雜度主體不能是題目數量。
我們考慮狀壓枚舉人的存活情況，對於每一種存活情況，可以處理出能改變這種存活情況的題目。
然後有個重要的性質是：存活的人越少，能改變存活情況的題目也越少，且改變後的狀態的題目是之前的子集。
這樣 DP 就是沒有後效性的了。於是設 \(f_s\) 表示存活的人狀態為 \(s\)，枚舉能改變狀態的題目集合 \(a_s\)，大小為 \(k\)：
\[f_s=\frac{1}{k}\sum_{i=1}^{k}f_{s \And a_i} \]
之後又要用高科技了，放。
T4
貪心是對的，於是數據點分治+線段樹有 \(50\)
後面維護置換環就要用平衡樹了，放了。
code
Show me the code
#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
i64 x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
const int N=5e5+5555;
i64 c[N];
int p[N];
int cpy[N];
int pos[N];
int n,m;
i64 endcst;
i64 calc(){
for(int i=1;i<=n;i++)p[i]=cpy[i],pos[p[i]]=i;
i64 ans=c[n];
i64 cst=0;
for(int i=n;i>=1;i--){
if(pos[i]!=i){
int l=pos[i];
pos[p[i]]=pos[i];
pos[i]=i;
swap(p[l],p[i]);
cst++;
}
ans=min(ans,cst+c[i-1]);
}
ans=min(ans,cst);
return ans;
}
i64 bpm[N];
i64 calc1(){
for(int i=1;i<=n;i++)p[i]=cpy[i],pos[p[i]]=i;
i64 ans=c[n];
bpm[n]=c[n];
i64 cst=0;
for(int i=n;i>=1;i--){
if(pos[i]!=i){
int l=pos[i];
pos[p[i]]=pos[i];
pos[i]=i;
swap(p[l],p[i]);
cst++;
}
ans=min(ans,cst+c[i-1]);
bpm[i-1]=cst+c[i-1];
}
ans=min(ans,cst);
endcst=cst;
return ans;
}
struct qur{
int op;
int x;int y;
i64 c1;
}q[N];
struct seg{
int l;int r;
i64 v;
i64 lzt;
}t[N<<2];
void b(int p,int l,int r){
t[p].l=l;t[p].r=r;
t[p].v=bpm[l];
t[p].lzt=0;
if(l==r){
return ;
}
int mid=l+r>>1;
b(ls,l,mid);b(rs,mid+1,r);
t[p].v=min(t[ls].v,t[rs].v);
return ;
}
void pushdown(int p){
if(!t[p].lzt)return ;
t[ls].v+=t[p].lzt;
t[rs].v+=t[p].lzt;
t[ls].lzt+=t[p].lzt;
t[rs].lzt+=t[p].lzt;
t[p].lzt=0;
return ;
}
void add(int p,int l,int r,int c1){
if(l<=t[p].l&&t[p].r<=r){
t[p].v+=c1;
t[p].lzt+=c1;
return ;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid)add(ls,l,r,c1);
if(mid<r) add(rs,l,r,c1);
t[p].v=min(t[ls].v,t[rs].v);
return ;
}
i64 qu(){return t[1].v;}
int main(){
//
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++){cin>>p[i];cpy[i]=p[i];}
if(n<=2000&&m<=2000){
cout<<calc()<<'\n';
for(int i=1;i<=m;i++){
int op;cin>>op;
if(op==1){
int x,y;cin>>x>>y;
swap(cpy[x],cpy[y]);
}
if(op==2){
int l,r,ci;cin>>l>>r>>ci;
for(int i=l;i<=r;i++){
c[i]+=ci;
}
}
cout<<calc()<<'\n';
}
return 0;
}
bool no1=1,no2=1;
for(int i=1;i<=m;i++){
int op;cin>>op;
if(op==1){
no1=0;
int x,y;cin>>x>>y;
q[i].op=op;
q[i].x=x;q[i].y=y;
}
if(op==2){
int l,r,c1;cin>>l>>r>>c1;
no2=0;
q[i].op=op;
q[i].x=l;q[i].y=r;
q[i].c1=c1;
}
}
if(no1){
cout<<calc1()<<'\n';
b(1,1,n);
for(int i=1;i<=n;i++){
int op=q[i].op;
if(op==1){
}
else{
int l=q[i].x,r=q[i].y,c1=q[i].c1;
add(1,l,r,c1);
}
cout<<min(qu(),endcst)<<'\n';
}
}
return 0;
}