over 1 year ago

真是呵呵呵呀。。
t1
题意:
有个数列,两个人在玩游戏。第一个人先把满足ai大于ai+1的某两数对调,第二个人50%概率对调ai大于ai+1两数,50%概率对调ai小于ai+1两数。问期望多少轮结束
题解:
发现只会把逆序对+1或-1,结束状态为逆序对0
随便推推就行了
p.s.多少轮看成多少次操作 推期望还没乘2。。发现我真的很搞笑。。
t2
题意:
有两个01串,长度小于4000。有些位置是?,选填01。最后代价就是两个串所有位置匹配不匹配的数个数。问最小代价,构造方案
题解:
最小割!!然而我不会找割边,然后就开始各种yy。。然后就跪在这题上了。。
割边找法:从st开始bfs,只经过残量网络大于0的边,把到的点标记。标完后看所有边,若他剩余流量为0,且一端被标另一端没被标就是割边
t3
题意:
给n(<=1000)个点,问把所有点移动到同一条直线上最小代价。移动代价就是移动距离
啊计算几何好难根本不会
t4
迷之题意:


答案对质数取mod
题解:
其实挺良心的一道数据结构。。我推出了每个果子对祖先的贡献就是果子的值连乘到祖先每个点的边数 但由于太多时间花在t2 而且题意太迷 我连样例都画不出来TAT 最后打了个wa暴力。。
说实话推出那东西后就区间乘除、单点改数,除用逆元就行了

include

include

include

include

include

define N 310000

define mmod 10000019

define LL long long

using namespace std;
struct node{LL o,x,d;}q[N];
struct node1{LL l,r,lc,rc,sum,d,lz;}lt[2*N];
struct node2{LL y,next;}a[2*N];
LL n,m,dfn[N],las[N],id,tl,fa[N],cnt[N],first[N],ltlen,ans,len;
LL qmod(LL a,LL b)
{
LL t=1;
while(b)
{
if(b&1) t=(t*a)%mmod;
a=(a*a)%mmod;
b>>=1;
}
return t;
}
void ins(LL x,LL y)
{
a[++len].y=y;a[len].next=first[x];first[x]=len;
}
void dfs(LL x,LL ff)
{
fa[x]=ff;
dfn[x]=++id;
for(LL k=first[x];k;k=a[k].next)
{
LL y=a[k].y;
if(y==ff) continue;
dfs(y,x);
}
las[x]=id;
}
void bt(LL l,LL r)
{
LL now=++ltlen;
lt[now].l=l;lt[now].r=r;
lt[now].lc=lt[now].rc=-1;
lt[now].sum=0;
lt[now].d=lt[now].lz=1;
if(l {
LL mid=(l+r)/2;
lt[now].lc=ltlen+1;bt(l,mid);
lt[now].rc=ltlen+1;bt(mid+1,r);
}
}
void down(LL now)
{
LL lc=lt[now].lc,rc=lt[now].rc;
if(lc!=-1) lt[lc].lz=(lt[lc].lz*lt[now].lz)%mmod;
if(rc!=-1) lt[rc].lz=(lt[rc].lz*lt[now].lz)%mmod;
lt[now].d=(lt[now].d*lt[now].lz)%mmod;
lt[now].sum=(lt[now].sum*lt[now].lz)%mmod;
lt[now].lz=1;
}
void upd(LL now)
{
LL lc=lt[now].lc,rc=lt[now].rc;
if(lt[lc].lz>1) down(lc);
if(lt[rc].lz>1) down(rc);
lt[now].sum=(lt[lc].sum+lt[rc].sum)%mmod;
}
void change(LL now,LL k,LL d)
{
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==lt[now].r) {lt[now].sum=(lt[now].d*d)%mmod;return;}
if(mid>=k) change(lc,k,d);
else change(rc,k,d);
upd(now);
}
void modify(LL now,LL l,LL r,LL d)
{
if(l>r) return;
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==l && lt[now].r==r)
{lt[now].lz=(lt[now].lz*d)%mmod;return;}
if(mid>=r) modify(lc,l,r,d);
else if(l>mid) modify(rc,l,r,d);
else modify(lc,l,mid,d),modify(rc,mid+1,r,d);
upd(now);
}
LL find(LL now,LL l,LL r)
{
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==l && lt[now].r==r) return lt[now].sum;
if(mid>=r) return find(lc,l,r);
else if(l>mid) return find(rc,l,r);
else return find(lc,l,mid)+find(rc,mid+1,r);
}
LL get_d(LL now,LL k)
{
if(k==0) return 1;
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==lt[now].r) return lt[now].d;
if(mid>=k) return get_d(lc,k);
else return get_d(rc,k);
}
int main()
{
LL tt;
scanf("%I64d%I64d",&tt,&m);
tl=1;
for(LL i=1;i<=m;i++)
{
scanf("%I64d",&q[i].o);
scanf("%I64d",&q[i].x);
if(q[i].o==1) {ins(q[i].x,++tl);q[i].x=tl;scanf("%I64d",&q[i].d);}
}
dfs(1,0);
ltlen=0;
bt(1,tl);
cnt[1]=1;
change(1,dfn[1],tt);
for(LL i=1;i<=m;i++)
{
LL x=q[i].x,ny;
if(q[i].o==1)
{
ny=qmod(cnt[fa[x]],mmod-2);
modify(1,dfn[fa[x]],las[fa[x]],ny);
cnt[fa[x]]++;
modify(1,dfn[fa[x]],las[fa[x]],cnt[fa[x]]);
cnt[x]++;
change(1,dfn[x],q[i].d);
}
else
{
ans=find(1,dfn[x],las[x]);
ny=get_d(1,dfn[fa[x]]);
ny=qmod(ny,mmod-2);
printf("%I64d\n",(ans*ny)%mmod);
}
}
return 0;
}

← 2016-4-2 CQOI2015 日常训练之图论 →