[考试反思]1112csp-s模拟测试111：二重

还是AK场。考前信心赛？

而且T3的部分分还放反了所有80的都其实只有50。

总算在AK场真正AK了一次。。。

手感好，整场考试很顺利。要不是因为T3是原题可能就没这么好看了。

20minT1，50minT2，去趟厕所回来70min想到T3，110min写完调完对拍完，然后去学skyh写平衡树了。

然后我发现我不会写平衡树了。

两场一计分：600//585/580/535/515/515/500///

Day1考得不够好，Day2就还是反超不了啊。。。

没关系这两个600的过两天直接联赛进营进队拿最优惠不是竞争对手挺过联赛我就是rank1了

T1：物理课

迭代都能A那就没得说了。。。等比数列求和还是会的

 #include<cstdio>

 #include<cmath>

 using namespace std;

 long double theta,d,v,g;

 int main(){

     freopen("physics.in","r",stdin);freopen("physics.out","w",stdout);

     int t;scanf("%d",&t);

     while(t--){

         scanf("%Lf%Lf%Lf%Lf",&theta,&v,&d,&g);theta/=;theta*=3.141592653589793238;

         printf("%.5Lf\n",*sin(theta)*v*cos(theta)*v/g/(-d*d));

     }

 }

T2：数学课

可以打表（超可怜的说）。但是从含义出发比较简单。

确定一个奇数的状态，那么它的任意偶数倍就都确定了，交替出现在AB集合中。

然后区别就是你把多的和少的分别放在A里还是B里。

如果多的和少的一样那么就不必考虑。设有pair0个，怎么放都一样所以方案数是$2^{pair0}$

接下来是多的比少的多一个。设有pair1个。

首先我们要知道这些选择的最小值是多少，设为Base。（在求出pair1和pair0的顺便弄一下就行，log的）

那么多的比少的的贡献就是：因为要从pair1个里选出m-Base个，所以就是$C_{pair1}^{m-Base}$

一个Lucas一个快速幂

 #include<cstdio>

 #define int long long

 #define mod 10000019

 int fac[],inv[];

 int C(int b,int t){return <=t&&t<=b?fac[b]*inv[t]%mod*inv[b-t]%mod:;}

 int Lucas(int b,int t){return b<mod&&t<mod?C(b,t):Lucas(b/mod,t/mod)*C(b%mod,t%mod)%mod;}

 int qpow(int b,int t,int a=){for(;t;b=b*b%mod,t>>=)if(t&)a=a*b%mod;return a;}

 main(){

     freopen("math.in","r",stdin);freopen("math.out","w",stdout);

     fac[]=;

     for(int i=;i<mod;++i)fac[i]=fac[i-]*i%mod;

     inv[mod-]=qpow(fac[mod-],mod-);

     for(int i=mod-;~i;--i)inv[i]=inv[i+]*(i+)%mod;

     int n,q,m,lst=,p2=1ll<<,pair1=,pair0=,Base=;

     scanf("%lld%lld",&n,&q);

     for(int i=;i;--i,p2>>=){

         int num=n/p2,cnt;num=(num>>)+(num&);cnt=num-lst;lst=num;Base+=cnt*(i>>);

         if(i&)pair1+=cnt;else pair0+=cnt;

     }

     while(q--)scanf("%lld",&m),printf("%lld\n",Lucas(pair1,m-Base)*qpow(,pair0)%mod);

 }

T3：地理课

第一反应：LCT。不会。

后来一想，改变一下题意就是原题了。

可以离线，所以只要把加边和删边的含义改变为“每条边只在一段时间内出现，其它时间消失”

然后就可以当作《Dash Speed》做了。线段树分治+按秩合并并查集板子。（给自己之前的博客打广告2333）

 #include<cstdio>

 #include<vector>

 #include<map>

 using namespace std;

 #define mod 1000000007

 vector<pair<int,int> >v[];

 map<pair<int,int>,int>M;

 int opt[],a[],b[],edt[],n,m,ans=,inv[],sz[];

 int stf[],stp[],strk[],rans[],top,f[],rk[],stsz[];

 pair<int,int>Pair(int a,int b){return a>b?make_pair(b,a):make_pair(a,b);}

 int find(int p){return f[p]==p?p:find(f[p]);}

 void merge(pair<int,int>P){

     int a=find(P.first),b=find(P.second);

     if(a==b)return;

     stp[++top]=a;stf[top]=f[a];stsz[top]=sz[a];strk[top]=rk[a];rans[top]=ans;

     stp[++top]=b;stf[top]=f[b];stsz[top]=sz[b];strk[top]=rk[b];rans[top]=ans;

     ans=1ll*ans*inv[sz[a]]%mod*inv[sz[b]]%mod*(sz[a]+sz[b])%mod;

     if(rk[a]<rk[b])f[a]=b,sz[b]+=sz[a],rk[b]+=rk[a]==rk[b];

     else f[b]=a,sz[a]+=sz[b],rk[a]+=rk[a]==rk[b];

 }

 void add(pair<int,int>P,int p,int l,int r,int cl=,int cr=m){

     if(l<=cl&&cr<=r){v[p].push_back(P);return;}

     if(l<=cl+cr>>)add(P,p<<,l,r,cl,cl+cr>>);

     if(r>cl+cr>>)add(P,p<<|,l,r,(cl+cr>>)+,cr);

 }

 void Divide_and_Conquer(int p,int l,int r){

     int tp=top;

     for(int i=;i<v[p].size();++i)merge(v[p][i]);

     if(l==r)printf("%d\n",ans);

     else Divide_and_Conquer(p<<,l,l+r>>),Divide_and_Conquer(p<<|,(l+r>>)+,r);

     while(top>tp){

         int x=stp[top];

         sz[x]=stsz[top];rk[x]=strk[top];f[x]=stf[top];ans=rans[top];top--;

     }

 }

 int main(){freopen("geography.in","r",stdin);freopen("geography.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;++i)scanf("%d%d%d",&opt[i],&a[i],&b[i]);

     inv[]=;

     for(int i=;i<=n;++i)inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;

     for(int i=;i<=n;++i)f[i]=i,rk[i]=sz[i]=;

     for(int i=m;i;--i)if(opt[i]==)M[Pair(a[i],b[i])]=i;

         else edt[i]=M[Pair(a[i],b[i])];

     for(int i=;i<=m;++i)if(opt[i]==)add(Pair(a[i],b[i]),,i,edt[i]?edt[i]-:m);

     Divide_and_Conquer(,,m);

 }

T4：普通平衡树

没调出来。爆零了。

巴特西

[考试反思]1112csp-s模拟测试111：二重

最新文章

热门文章