T1-Table
简单模拟题啊
然而我各种打挂，只剩下了50分
mo得订正，毕竟是人都A了
/***50pts****/
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"
"
#define dbg3(x) cerr<<#x<<"
"
using namespace std;
#define reg register
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MN=10000;
int N,M;
char a[MN],s[105][MN];
int sz[105],len[105];
int blank(int n){while(n--) printf(" ");}
int line(int n){while(n--) printf("-");}
#define Enter puts("")
void put1()
{
printf("+");
for(int i=1;i<=M;++i)line(len[i]),printf("+");Enter;
}
void put2(int x,int l,int r)
{
for(int i=l;i<=r;++i) printf("%c",s[x][i]);
}
int main()
{
freopen("table.in","r",stdin);
freopen("table.out","w",stdout);
N=read(),M=read();
scanf("%s",a+1);
reg int i,j;
for(i=1;i<=N;++i)
{
scanf("%s",s[i]+1);
sz[i]=strlen(s[i]+1);
int la=0,nm=0;
for(j=1;j<=sz[i];++j)
if(j+1>sz[i]||s[i][j+1]==',')
len[++nm]=max(len[nm],j-la),la=j+1;
}
put1();
for(i=1;i<=N;++i)
{
printf("|");
int la=0,nm=0;
for(j=1;j<=sz[i];++j)
if(j+1>sz[i]||s[i][j+1]==',')
{
++nm;int siz=j-la;
if(a[nm]=='L') put2(i,la+1,j),blank(len[nm]-siz);
if(a[nm]=='C') blank((len[nm]-siz)/2),put2(i,la+1,j),blank((len[nm]-siz+1)/2);
if(a[nm]=='R') blank(len[nm]-siz),put2(i,la+1,j);
printf("|");la=j+1;
}
Enter;
put1();
}
}
T2-paradox
题意：求有(N)个人存在两个相同生日是一个(K)位二进制数的人的概率，要求所得分数约分后分子分母分别对(1e6+3)取模，(N,Kleq 10^9)
可以求没有人同一天生日的概率
发现答案是
[ans=frac{(2^{NK})^{underline N}}{2^{NK}}
]
约分就是(O(log N))求出分子所含的(2)的次幂，把它的逆元算出来最后分别乘就行
快速幂两次算分母，分子如果(N>1e6+3)，则一定会是(0)，否则暴力算阶乘
最后答案是(1-ans)
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"
"
#define dbg3(x) cerr<<#x<<"
"
using namespace std;
#define reg register
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
ll N,K;
int _1,_2;
const int M=1e6+3,inv2=5e5+2;
ll Mul(ll x,ll y){return (1ll*x*y)%M;}
ll Add(ll x,ll y){return (x+y)%M;}
ll fpow(ll x,ll y){ll r=1;for(;y;y>>=1,x=Mul(x,x))if(y&1)r=Mul(r,x);return r;}
int main()
{
freopen("paradox.in","r",stdin);
freopen("paradox.out","w",stdout);
N=read(),K=read();
ll i,j;
for(i=1,j=0;i<(K+1)/2;i<<=1,++j);
if(j>=N) return 0*puts("1 1");
ll sum=N;
for(i=1;i<=K/2;i<<=1)sum+=(K-1)/(i<<1);
sum=fpow(inv2,sum);
_2=fpow(2,N);_2=fpow(_2,K);_2=Mul(_2,sum);
if(K<M)
{
ll x=fpow(2,N);_1=1;
for(i=0;i<K;++i) _1=Mul(_1,Add(x,M-i));
_1=Mul(_1,sum);
}
_1=Add(_2,M-_1);
printf("%lld %lld
",_1,_2);
return 0;
}
T3-treemutaion
题意：更改树上节点的权值，询问链上权值是否构成一个排列
我RE了啊。。。菜
其实，不需要在意排列的问题，可以先给每个数附加一个值
我的做法是(Val(x)=x^4) mod (P_1+x^3) mod (P_2+x^2) mod (P_1+x)
然后树剖后线段树维护链上权值和即可，每次把询问的链的和求出来看是否等于一个排列的权值和
为了保险起见，我还顺带维护了一下链上的最大值和最小值
因为每次只有不超过(3)个段的询问不是整个链的，所以复杂度仍然是(O(nlog n))
实现时应当是对每个重链分别开线段树
（是的，我就是这么想的，然后，我对每个链头的子树都开了一棵线段树，并成功RE到只剩下(50)分）
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"
"
#define dbg3(x) cerr<<#x<<"
"
using namespace std;
#define reg register
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MN=5e5+5;
int N,Q,A[MN];
ll Sum[MN];
struct ed{int to,nex;}e[MN];int hr[MN],en;
void ins(int x,int y)
{
e[++en]=(ed){y,hr[x]};hr[x]=en;
e[++en]=(ed){x,hr[y]};hr[y]=en;
}
int dep[MN],fa[MN],top[MN],l[MN],r[MN],id[MN],siz[MN],mx[MN],dind;
void dfs1(int x,int f)
{
siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
reg int i;
for(i=hr[x];i;i=e[i].nex)if(e[i].to^f)
dfs1(e[i].to,x),siz[x]+=siz[e[i].to],
(siz[e[i].to]>siz[mx[x]])?mx[x]=e[i].to:0;
}
void dfs2(int x,int tp)
{
id[l[x]=++dind]=x;top[x]=tp;
if(mx[x]) dfs2(mx[x],tp);
reg int i;
for(i=hr[x];i;i=e[i].nex)
if(e[i].to!=fa[x]&&e[i].to!=mx[x])
dfs2(e[i].to,e[i].to);
if(!mx[x]) r[top[x]]=l[x];
}
int lca(int x,int y)
{
while(top[x]^top[y])
dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
return dep[x]>dep[y]?y:x;
}
const ll P1=1e12-7,P2=1e12+37,P3=1e12+9;
struct node{pii p;ll sm;}T[MN<<1];
int ls[MN<<1],rs[MN<<1],rt[MN],tot;
pii Mge(pii x,pii y)
{
pii tmp;
tmp.fi=min(x.fi,y.fi);
tmp.se=max(x.se,y.se);
return tmp;
}
ll Val(int x){return (1ll*x*x%P1*x%P1*x%P1)+(2ll*x*x%P2*x%P2)+(3ll*x*x%P3)+x;}
node mge(node x,node y){return (node){Mge(x.p,y.p),x.sm+y.sm};}
int bld(int l,int r)
{
int x=++tot;
if(l==r){T[x]=(node){mp(A[id[l]],A[id[l]]),Val(A[id[l]])};}
else
{
int mid=(l+r)>>1;
ls[x]=bld(l,mid);
rs[x]=bld(mid+1,r);
T[x]=mge(T[ls[x]],T[rs[x]]);
}
return x;
}
void mdf(int x,int l,int r,int k,int v)
{
if(l==r){T[x]=(node){mp(v,v),Val(v)};return;}
int mid=(l+r)>>1;
if(k<=mid)mdf(ls[x],l,mid,k,v);
else mdf(rs[x],mid+1,r,k,v);
T[x]=mge(T[ls[x]],T[rs[x]]);
}
node qry(int x,int l,int r,int a,int b)
{
if(l==a&&r==b){return T[x];}
int mid=(l+r)>>1;
if(b<=mid)return qry(ls[x],l,mid,a,b);
if(a>mid)return qry(rs[x],mid+1,r,a,b);
return mge(qry(ls[x],l,mid,a,mid),qry(rs[x],mid+1,r,mid+1,b));
}
void empty()
{
en=dind=tot=0;
for(int i=1;i<=N;++i)A[i]=hr[i]=rt[i]=mx[i]=0;
}
int main()
{
freopen("treemutaion.in","r",stdin);
freopen("treemutaion.out","w",stdout);
int cas=read();
reg int i,j;
for(i=1;i<=300000;++i)Sum[i]=Sum[i-1]+Val(i);
while(cas--)
{
N=read(),Q=read();
for(i=1;i<=N;++i) A[i]=read();
for(i=1;i<N;++i) j=read(),ins(j,read());
dfs1(1,0);dfs2(1,1);
for(i=1;i<=N;++i)if(top[i]==i)rt[i]=bld(l[i],r[i]);
while(Q--)
{
int ty,x,y;
ty=read(),x=read(),y=read();
if(ty==1)
{
int len=dep[x]+dep[y]-dep[lca(x,y)]*2+1;
int mi=1e7,ma=-1e7;ll sum=0;
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
node P=qry(rt[top[x]],l[top[x]],r[top[x]],l[top[x]],l[x]);
mi=min(P.p.fi,mi);ma=max(P.p.se,ma);sum+=P.sm;x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
node P=qry(rt[top[x]],l[top[x]],r[top[x]],l[x],l[y]);
mi=min(P.p.fi,mi);ma=max(P.p.se,ma);sum+=P.sm;
puts((mi==1&&ma==len&&sum==Sum[len])?"Yes":"No");
}
else mdf(rt[top[x]],l[top[x]],r[top[x]],l[x],y);
}
empty();
}
return 0;
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！