CTSC2017 Day1
P3770 [CTSC2017]密钥
首先暴力做是 \(O(k^2)\) 的。
实际上就是让你维护一个全局加一减一,添加或删除一个数,问大于 \(0\) 的数的个数,维护一个桶即可。
#include
using namespace std;
const int Zero=1e7;
int p[Zero*2+1];
int seed,n,k,s;
int getrand(){
seed=((seed*12321)^9999)%32768;
return seed;
}
void generateData(){
scanf("%d%d%d",&k,&seed,&s);
int t=0;n=k*2+1;
memset(p,0,sizeof(p));
for(int i=1;i<=n;++i)
p[i]=(getrand()/128)%2,t+=p[i];
int i=1;
while(t>k){
while(p[i]==0) ++i;
p[i]=0,--t;
}
while(t0&&p[i]);
buc[tmp+Zero-tag]+=p[i];
}
if(!p[1]){
if(cnt==0) res1=1;
if(cnt==s) res2=1;
if(k-cnt==s) res3=1;
}
for(int i=2;i<=n;++i){
buc[Zero-tag]-=p[i-1];
if(p[i]){
cnt-=buc[1+Zero-tag];
tag--,buc[-2+Zero-tag]+=p[i-1];
}
else{
tag++,buc[Zero-tag]+=p[i-1];
cnt+=buc[1+Zero-tag];
}
if(p[i]) continue;
if(cnt==0) res1=i;
if(cnt==s) res2=i;
if(k-cnt==s) res3=i;
}
return printf("%d\n%d\n%d\n",res1,res2,res3),0;
}
int main() {
generateData();
return solve();
}
P3771 [CTSC2017]网络
最小化树连上一条边之后的构成的基环树的直径,\(n\le 10^5\) 。
那么必然就存在一个 \(O(n^3)\) 的暴力,具体就是枚举每一条边,然后暴力计算基环树直径(基环树直径应该可以 \(O(n)\) 求的吧。)
然后感觉是必然连接直径上的两点。
\[dis_i+dis_j+sum_i-sum_j\le \text{Mid}\\ dis_i+dis_j+|sum_i-sum_a|+|sum_j-sum_b|+k\le \text{Mid}\\ \]首先考虑第一个不等式,枚举右端点,我们可以利用单调队列找到最大的 \(dis_j-sum_j\) ,然后进行 \(\text{check}\) 。因为由于 \(i
这样我们就可以比较轻松的得到上面四个变量的最值。
\[tmp1 \le sum_a+sum_b\le -tmp4\\ tmp2 \le sum_a-sum_b\le -tmp3\\ \]考虑找到可行的 \(a,b\) 点对,还是一样的,我们考虑枚举一个端点,计算另一个的取值范围即可。
这道题目代码实现是个难点。
#include
using namespace std;
const int N=1e5+5;
const long long INF=1e18;
int n,m,k;
struct Edge{int nxt,to,val;}e[N<<1];int fir[N];
void add(int u,int v,int w,int i){e[i]=(Edge){fir[u],v,w},fir[u]=i;}
int rt1,rt2,fa[N];long long dis[N];
void dfs(int u,int &rt){
if(dis[u]>dis[rt]) rt=u;
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].to;if(v==e[fa[u]].to) continue;
dis[v]=dis[u]+e[i].val,fa[v]=(i^1),dfs(v,rt);
}
}
void DFS(int u,int fa1,int fa2){
dis[u]=0;
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fa1||v==fa2) continue;
DFS(v,u,0),dis[u]=max(dis[u],dis[v]+e[i].val);
}
}
vector bag;
vector sum;
bool check(long long Dis){
long long tmp1=-INF,tmp2=-INF,tmp3=-INF,tmp4=-INF;
long long mx1=-INF,mx2=-INF;deque q;
for(int i=0;iDis){
mx1=max(mx1,dis[bag[q.front()]]+sum[q.front()]);
mx2=max(mx2,dis[bag[q.front()]]-sum[q.front()]);
q.pop_front();
}
long long tmp=dis[bag[i]]+k-Dis;
tmp1=max(tmp1,sum[i]+mx1+tmp),tmp2=max(tmp2,-sum[i]+mx1+tmp);
tmp3=max(tmp3,sum[i]+mx2+tmp),tmp4=max(tmp4,-sum[i]+mx2+tmp);
while(!q.empty()&&dis[bag[i]]-sum[i]>dis[bag[q.back()]]-sum[q.back()]) q.pop_back();
q.push_back(i);
}
if(tmp2>-tmp3||tmp1>-tmp4) return false;
int L1=m-1,L2=m,R1=-1,R2=0;
while(R1+1=0&&-sum[L2-1]<=-tmp3) L2--;
for(int i=0;i=0&&sum[i]+sum[L1]>=tmp1) L1--;
while(R1>=0&&sum[i]+sum[R1]>-tmp4) R1--;
while(L2-tmp3) L2++;
while(R2=tmp2) R2++;
if(max(L1+1,L2)<=min(R1,R2-1)) return true;
}
return false;
}
int solve(){
scanf("%d%d",&n,&k);
if(!n&&!k) return 1;
for(int i=1;i<=n;++i) fir[i]=0;
for(int i=1;i=0)?bag[i-1]:0;
int R=(i+1>1;
if(check(Mid)) R=Mid-1,res=Mid;
else L=Mid+1;
}
return printf("%lld\n",res),0;
}
int main(){
while(1) if(solve()) break;
return 0;
}
P3772 [CTSC2017]游戏
研究了一通贝叶斯公式,感觉牛得不行。
题目相当于让我们求:
\[\text{res}=\sum_{i=1}^n p(x_i=1|\bigcap_{i=1}^kx_k=c_k)\\ =\sum_{i=1}^n\frac{p((x_i=1)\cap(\bigcap_{i=1}^kx_k=c_k))}{p(\bigcap_{i=1}^kx_k=c_k))}\\ \]推不动上面的式子(悲)。
存在一个很重要结论,即每相邻两个已知信息会将整个序列分段,段内的局的获胜概率与段外的概率是互相独立的。换句话说,一个段内部的局的概率只与其两端的已知信息有关。
我们令 \(x\in(l,r)\) ,事件 \(X\) 表示 \(x\) 获胜,事件 \(L,R\) 表示 \(l,r\) 符合已知信息。我们要求的即:
\[p(X|L\cap R)=\frac{p(X\cap L\cap R)}{p(L\cap R)}\\ =\frac{p(L\cap R|X)p(X)}{p(R|L)p(L)} =\frac{p(L|X)p(R|X)p(X)}{p(R|L)p(L)}\\ =\frac{p(L\cap X)p(R|X)}{p(R|L)p(L)} =\frac{p(X|L)p(R|X)}{p(R|L)}\\ \]那么对于一段区间的,实际上计算方式是类似的,即
\[\frac{\sum_{x\in (l,r)}p(X|L)p(R|X)}{p(R|L)}\\ \]上下两者都是可以利用线段树加矩阵乘法维护的。具体的,分母就利用一个 \(\text{set}\) 加线段树上查询即可,单个矩阵易得为
\[F_i=\begin{bmatrix} 1-q_i&q_i\\ 1-p_i&p_i \end{bmatrix} \]那么 \(p(R|L)\) 即为,这里以已知信息为 \(x_l=1,x_r=1\) 为例。
\[p(R|L)=\begin{bmatrix}0&1\end{bmatrix}\prod_{i=l+1}^rF_{i}\begin{bmatrix}0\\1\end{bmatrix} \]对于分子,实际上我们可以利用上面类似的方法来搞,这里我们将 \(p\) 看成为一个 \(1\times 1\) 的矩阵,即
\[p(X|L)p(R|X)=\begin{bmatrix}0&1\end{bmatrix}\prod_{i=l+1}^xF_{i}\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0&1\end{bmatrix}\prod_{i=x+1}^rF_{i}\begin{bmatrix}0\\1\end{bmatrix}\\ =\begin{bmatrix}0&1\end{bmatrix}\prod_{i=l+1}^xF_{i}\begin{bmatrix}0&0\\0&1\end{bmatrix}\prod_{i=x+1}^rF_{i}\begin{bmatrix}0\\1\end{bmatrix}\\ =\begin{bmatrix}0&1\end{bmatrix}\prod_{i=l+1}^{x-1}F_{i}\begin{bmatrix}0&q_x\\0&p_x\end{bmatrix}\prod_{i=x+1}^rF_{i}\begin{bmatrix}0\\1\end{bmatrix}\\ \]这个东西好像可以用类似于 \(\text{cdq}\) 分治来计算 \(x\in(l,r)\) 的和,但是我们需要多次询问,所以这里我们考虑线段树。
具体的用 \(G_{[l,r]}\) 表示 \(\sum_{x\in[l,r]}\prod_{i=l}^{x-1}F_{i}\begin{bmatrix}0&q_x\\0&p_x\end{bmatrix}\prod_{i=x+1}^rF_{i}\) (注意边界与前面的不一样),\(F_{[l,r]}\) 表示 \(\prod_{i=l}^rF_{i}\) 。那么转移就十分好写了。
\[G_{[l,r]}=G_{[l,mid]}F_{[mid+1,r]}+F_{[l,mid]}G_{[mid+1,r]}\\ F_{[l,r]}=F_{[l,mid]}F_{[mid+1,r]}\\ \]然后区间查询即可。
#include
using namespace std;
const int N=2e5+5;
int n,m;char type;
double p[N],q[N];int c[N];
struct Matrix{double f[2][2];};
Matrix operator * (Matrix a,Matrix b){
Matrix res=(Matrix){0,0,0,0};
for(int i=0;i<2;++i){
for(int j=0;j<2;++j){
for(int k=0;k<2;++k)
res.f[i][k]+=a.f[i][j]*b.f[j][k];
}
}
return res;
}
Matrix operator + (Matrix a,Matrix b){
Matrix res;
for(int i=0;i<2;++i){
for(int j=0;j<2;++j)
res.f[i][j]=a.f[i][j]+b.f[i][j];
}
return res;
}
struct Seg_Tree{
struct Node{Matrix f,g;}tr[N<<2];
void up(int u){
tr[u].f=tr[u<<1].f*tr[u<<1|1].f;
tr[u].g=tr[u<<1].g*tr[u<<1|1].f+tr[u<<1].f*tr[u<<1|1].g;
}
void modify(int u,int l,int r,int x,Matrix f){
if(l==r) return tr[u].f=tr[u].g=f,tr[u].g.f[0][0]=tr[u].g.f[1][0]=0,void();
int mid=(l+r)>>1;
if(x<=mid) return modify(u<<1,l,mid,x,f),up(u);
else return modify(u<<1|1,mid+1,r,x,f),up(u);
}
pair query(int u,int l,int r,int x,int y){
if(x<=l&&r<=y) return make_pair(tr[u].f,tr[u].g);
int mid=(l+r)>>1;pair res1,res2;
if(x<=mid) res1=query(u<<1,l,mid,x,y);
if(y>mid) res2=query(u<<1|1,mid+1,r,x,y);
if(x<=mid&&y>mid){
pair res;res.first=res1.first*res2.first;
res.second=res1.second*res2.first+res1.first*res2.second;
return res;
}
return x<=mid?res1:res2;
}
}t;
struct Inf{int pos,c;};
bool operator < (Inf a,Inf b){return a.pos bag;double res=0;int cnt=0;
double cal(Inf l,Inf r){
if(l.pos+1>r.pos-1) return 0;
Matrix L,R;
if(l.c) L=(Matrix){0,1,0,0};
else L=(Matrix){1,0,0,0};
if(r.c) R=(Matrix){q[r.pos],0,p[r.pos],0};
else R=(Matrix){1-q[r.pos],0,1-p[r.pos],0};
pair tmp=t.query(1,1,n,l.pos+1,r.pos-1);
return (L*tmp.second*R).f[0][0]/(L*tmp.first*R).f[0][0];
}
void ADD(Inf x){
set::iterator L=bag.lower_bound(x);L--;
set::iterator R=bag.upper_bound(x);
res-=cal(*L,*R),res+=cal(*L,x),res+=cal(x,*R),bag.insert(x);
}
void DEL(Inf x){
set::iterator L=bag.lower_bound(x);L--;
set::iterator R=bag.upper_bound(x);
res-=cal(*L,x),res-=cal(x,*R),res+=cal(*L,*R),bag.erase(x);
}
int main(){
cin>>n>>m>>type;
scanf("%lf",&p[1]),p[n+1]=1,q[n+1]=1;
t.modify(1,1,n,1,(Matrix){0,0,1-p[1],p[1]});
for(int i=2;i<=n;++i) scanf("%lf%lf",&p[i],&q[i]);
for(int i=2;i<=n;++i) t.modify(1,1,n,i,(Matrix){1-q[i],q[i],1-p[i],p[i]});
res=cal((Inf){0,1},(Inf){n+1,1});
bag.insert((Inf){0,1}),bag.insert((Inf){n+1,1});
for(int i=1;i<=m;++i){
string opt;int x;cin>>opt;scanf("%d",&x);
if(opt[0]=='d') DEL((Inf){x,c[x]}),cnt-=c[x];
else scanf("%d",&c[x]),ADD((Inf){x,c[x]}),cnt+=c[x];
printf("%lf\n",res+cnt);
}
return 0;
}