中文题面 题目链接 题意: 给你一个矩阵$M$,满足$M_{i,j}=M_{j,i}$，且$M_{i,j}>=0$。 让你构造一个矩阵$P$,满足： $P$是对称矩阵。 $P_{i,j}$要么等于零，要么等于$M_{i,j}$。 存在一个$S>0$,使得$P+P^2+…+P^S$中每个元素都是正数。 最小化$P$中元素和。 $M$是一个邻接矩阵，可以看成一个完全图。 我们知道$(M^k)_{i,j}$对应所有走$k$条边从$i$到$j$边权乘积的和。 满足第3个条件就需要所有点两两可达。 于是就是最小生成树了。 ...
设$f[i]$表示深度不超过i的严格n元树的数量。 有$f[i]=f[i-1]^n+1$。 $Ans=f[d]-f[d-1]$ 递推式很显然。 代码: n,d=map(int,raw_input().split()) f=[0]*17 f[0]=1 for i in range(1,d+1): f[i]=f[i-1]**n+1 print f[d]-f[d-1] 这个题目答案可能很大很大.. 所以最坏情况下是跑不出来的…
题意: 有一个字符串生成器，初始时生成的字符串为空串，它每次按照给定概率随机生成一个小写字母，加在当前已生成字符串的后面。 给定N个长度为L的字符串，每个字符串由小写字母组成。 如果在某个时候，发现每个给定字符串都在当前已生成的字符串中作为子串出现过，生成器就会停下来，将当前生成的字符串作为输出。 求输出字符串长度的期望值。 ...
给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数 强制在线。 设$p[i]$为$a[i]$上一次出现位置,$q[i]$为$a[i]$下一次出现位置。 每次查询的就是 $ max _{l<=i<=r} a[i] $ 且$q[i] >r$ , $p[i]< l $。 可以排序然后树套树做。 偷懒写了KD-TREE。。复杂度$O(n^{5/3})$，不强制在线的话可以做到$O(n^{3/2})$ 。 ...
给出一系列点p_1, p_2, … , p_n，将其分成不多余m个连续的段，第i段内求一个点q_i，使得q_i到这段内点的距离的最大值的最大值最小 最大值最小，先二分答案。 再从每个开始点二分，用随机增量法的最小圆覆盖判断最长能扩展长度，段数是不是$<=m$。 但是有个问题。 如果m=n的话，每段长度都是1。 这样做是$O(n^2lgn)$的。 ...
去年省选的题。 突然发现还没有A这个题。 就抽时间写了写。 询问的那个树形dp很好搞。 我们把原树中有用的点(被选的点，和他们之间的lca)拿出来，建一棵虚树。 在虚树上dp就行了。 类似"消耗战"(为啥听着像卡组名)。 ...
学习 http://www.docin.com/p-598829500.html 线段树合并中的一道例题。 详细见那个课件。 复杂度$O(nlgn)$. 需要注意下空间 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; int n; int LS[400005],RS[400005]; int cc; int Root; int w[400005]; int siz[400005]; int ls[15000500],rs[15000500],sum[15000500]; int num; int stk[15000500],top; int getnew(){ if(top>0){ ls[stk[top-1]]=rs[stk[top-1]]=sum[stk[top-1]]=0; return stk[--top]; } return ++num; } void add(int &o,int l,int r,int pos){ if(!o) o=getnew(); if(l==r){ sum[o]=1; }else{ int mid=(l+r)>>1; if(pos<=mid) add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos); sum[o]=1; } } int read(){ int x; scanf("%d",&x); int now=++cc; if(!x){ LS[now]=read(); RS[now]=read(); siz[now]=siz[LS[now]]+siz[RS[now]]+1; }else{ add(w[now],1,n,x); siz[now]=1; } return now; } LL ans; LL ans0,ans1; int merge(int a,int b,int l,int r){ if(!a) return b; if(!b) return a; int now=getnew(); int mid=(l+r)>>1; int lft=sum[ls[a]]+sum[ls[b]]; int rgt=sum[rs[a]]+sum[rs[b]]; ans0+=sum[rs[a]]*1LL*sum[ls[b]]; ans1+=sum[ls[a]]*1LL*sum[rs[b]]; if(lft<rgt){ rs[now]=merge(rs[a],rs[b],mid+1,r); ls[now]=merge(ls[a],ls[b],l,mid); }else{ ls[now]=merge(ls[a],ls[b],l,mid); rs[now]=merge(rs[a],rs[b],mid+1,r); } stk[top++]=a; stk[top++]=b; sum[now]=sum[ls[now]]+sum[rs[now]]; return now; } void dfs(int x){ if(!LS[x]) return; else{ if(siz[LS[x]]<siz[RS[x]]) dfs(RS[x]),dfs(LS[x]); else dfs(LS[x]),dfs(RS[x]); ans0=ans1=0; w[x]=merge(w[LS[x]],w[RS[x]],1,n); ans+=min(ans0,ans1); } } int main(){ http://www.docin.com/p-598829500.html scanf("%d",&n); Root=read(); dfs(1); printf("%lld\n",ans); return 0; }
题意: 给你n个不相交的凸多边形或圆，每个图形有一个权值。 询问m次，从一个点到另一个点，穿越过的图形的权值异或和。 题解: 扫描线+树链剖分。 这些图形的互相包含关系形成了一些树。 每次相当于求从树上一个点走到另一个点边上的权值异或和。 扫描线算法$O(nlgn)$求出这颗树，然后树链剖分维护下就好了。 ...
今天上午无聊写了这个。 BZOJ抽题助手。 估价函数综合 AC率，AC人数，提交人数，随机因素。 还能指定难度。 记录已A的题，跳过设置的黑名单。 计算出这道题与你输入的难度的差距难度系数。 ...
贪心一下。 接水的时候肯定是从小到大接。 好像没什么性质。莫队好了。 观察到奇怪的强制在线方法。。。 类似[糖果公园/苹果树]做法。 块大小没仔细算，直接$n^{0.5}$的，卡了70s评测姬 233。 复杂度不明。。 ...