先给出ydc的题解地址:
http://ydc.blog.uoj.ac/blog/336
T1(树上染色):
题目地址:
首先有一个基础的想法是DP:令f[i][j]代表以i为根的子树中选了j个黑色点的最小代价(代价指该子树中所有边对答案的贡献之和)。在转移时,只需要枚举在当前儿子中放几个黑色点,计算这条父子边对答案的贡献。
代码:
#include#include #include #include #include using namespace std; typedef long long LL; const LL INF=1e16; const int SIZEN=2010; int N,K; LL F[SIZEN][SIZEN]; vector > c[SIZEN]; int subsz[SIZEN]; void DFS(int x,int fa){ F[x][0]=F[x][1]=0; subsz[x]=1; for(int i=0;i =0;j--){ for(int k=0;k<=subsz[u]&&k<=j;k++){ LL add=(LL)k*(K-k)+(LL)(subsz[u]-k)*(N-K-(subsz[u]-k)); add*=c[x][i].second; add+=F[u][k]; F[x][j]=max(F[x][j],F[x][j-k]+add); } } } } void read(void){ scanf("%d%d",&N,&K); int a,b,w; for(int i=1;i
这份代码的时间复杂度初看上去是O(NK^2)的,但实际上是O(N^2),因为在黑点个数的枚举范围并不是0~K,而是0~子树大小。这就相当于枚举点对,而每两点只会在其LCA处被枚举到,因此时间复杂度是O(N^2)的。
考试时我是拿这个当50分暴力写的,结果就这么玄学的A掉了……
T2(树上操作):
题目地址:
这道题我在考场上写了一个分块,思路如下:
首先建出树的DFS序列,那么每个点到根的路径也就是从DFS序列中该点开始,不断向前跳跃的一条链。两个修改操作都是DFS序列的区间修改,而查询操作就是查询该链上的点权之和。
将DFS序列分块。对每个点,记录它的对应链在本块中的最前点,以及该点到这个最前点需要跳跃几次、经过的点权和。
显然两个修改操作都是DFS序列的区间修改,那么对中间的整块修改lazy标记,暴力修改并重新DP两端部分。
查询操作时,只需要根据我们已有的DP信息,不断地向前跳跃,经过sqrt(N)个块就能到达根。
这样的时间复杂度就是O(Msqrt(N))的。
代码:
#include#include #include #include #include #include #include #include using namespace std; typedef long long LL; const int SIZEN=100010,SIZEM=200010; int N,M; class Edge{ public: int to; int nxt; }; Edge edges[SIZEM]; int tot=0; int head[SIZEN]; LL val[SIZEN]; LL lis_val[SIZEN]; int father[SIZEN]; int lis_fa[SIZEN]; int subsz[SIZEN]; int dfn[SIZEN]; int dfslis[SIZEN]; int timer=0; int BN,Bsize; int start[SIZEN],end[SIZEN]; int belong[SIZEN]; LL badd[SIZEN];//整个区间被加了多少 LL cgoal[SIZEN];//跳出块之前最后跳到哪里 LL cnum[SIZEN];//跳出块之前有多少个 LL csum[SIZEN];//跳出块之前的和(不计badd) void calc_block(int k){ for(int i=start[k];i<=end[k];i++) lis_val[i]+=badd[k]; badd[k]=0; for(int i=start[k];i<=end[k];i++){ int j=lis_fa[i]; if(belong[j]!=k){ cgoal[i]=i; cnum[i]=1; csum[i]=lis_val[i]; } else{ cgoal[i]=cgoal[j]; cnum[i]=cnum[j]+1; csum[i]=csum[j]+lis_val[i]; } } } void seg_add(int l,int r,LL w){ if(belong[l]==belong[r]){ for(int i=l;i<=r;i++){ lis_val[i]+=w; } calc_block(belong[l]); } else{ for(int k=belong[l]+1;k =Bsize||i==N){ BN++; start[BN]=i+1; tot=0; } } for(int i=1;i<=BN;i++) calc_block(i); } void DFS(int x){ dfn[x]=++timer; dfslis[timer]=x; subsz[x]=1; for(int i=head[x];i!=-1;i=edges[i].nxt){ Edge &e=edges[i]; int u=e.to; if(u==father[x]) continue; father[u]=x; DFS(u); subsz[x]+=subsz[u]; } } void addedge(int from,int to){ edges[tot]=(Edge){to,head[from]}; head[from]=tot; tot++; } void read(void){ scanf("%d%d",&N,&M); int x; for(int i=1;i<=N;i++){ scanf("%d",&x); val[i]=x; } int a,b; for(int i=1;i
还有一个O(MlogN)的做法,就是预处理出每个点的深度up[i],然后建出DFS序列,用线段树维护每个点的两个值a[i]和b[i],使得该点的答案就是a[i]*up[i]+b[i]。
不过还有个问题:在10^5的规模下系统栈会爆掉。所以需要手写栈。我没用手写栈,所以只得了50分。
T3(数组游戏):
题目地址:
这道题首先要想明白一点:一个状态的SG函数等于其所有白格的SG函数的异或和。
打个比方:如果某个状态是仅有1,4,7三个白格,那么其SG值等于(仅有1这一白格的SG值) xor (仅有4这一白格的SG值)xor(仅有7这一白格的SG值)。
为什么呢?前面的白格不是会把后面的白格翻成黑的,于是就不再是独立的子游戏了吗?其实如果选了1,在操作中把4翻过来,我们大可以视作“4处是两个白格”,而这会导致4带来的SG值和自己异或抵消掉,也就和“4是黑格”一样了。
然后就顺理成章了:可以证明,SG函数是分段的,而且段数非常少。这样一段一段地来就行了。
代码:
#include#include #include #include #include #include using namespace std; const int SIZE=100010; class Seg{ public: int l,r; int sg; }; bool operator < (const Seg &s,int a){ return s.l>a; } vector segs; int find_sg(int a){ int k=lower_bound(segs.begin(),segs.end(),a)-segs.begin(); return segs[k].sg; } int cur_cnt(int l,int r,int a){ return r/a-(l-1)/a; } int cur_cnt(const Seg &s,int a){ return cur_cnt(s.l,s.r,a); } Seg merge(Seg a,const Seg &b){ a.l=min(a.l,b.l); a.r=max(a.r,b.r); return a; } int vis[SIZE]={0}; int timer=0; void calc_seg(int L,int R){//保证L~R的SG值一样 //以R为例 timer++; int now=0; vis[now]=timer; for(int i=segs.size()-1;i>=0;i--){ Seg &s=segs[i]; int t=cur_cnt(s,R); if(t>=1) vis[now^s.sg]=timer; if(t&1) now^=s.sg; } int f; for(f=0;;f++){ if(vis[f]!=timer) break; } Seg s;s=(Seg){L,R,f}; if(!segs.empty()&&f==segs.back().sg) segs.back()=merge(segs.back(),s); else segs.push_back(s); } int N,K; void work(void){ int w,x,f=0; scanf("%d",&w); for(int i=1;i<=w;i++){ scanf("%d",&x); f^=find_sg(x); } if(f==0) printf("No\n"); else printf("Yes\n"); } void prepare(void){ int B=sqrt(N+0.5); for(int i=1;i=1;i--) calc_seg(i,i); } int main(){ freopen("haoi2015_t3.in","r",stdin); freopen("haoi2015_t3.out","w",stdout); scanf("%d%d",&N,&K); prepare(); for(int i=1;i<=K;i++) work(); return 0; }
ps:题解中说N=10^9时SG函数的段数不超过2000,但实际应为9000多……不过并没有这样的极限数据,所以也能过……
这道题我在考场上写的是30分的暴力状压DP。
set(按位或):
题目地址:
我们要求的期望也就是:操作0次没变成目标的概率+操作1次没变成目标的概率+操作2次没变成目标的概率……
而“操作k次没变成目标的概率”是什么呢?有1个0没变成1的概率-有2个0没变成1的概率+有3个0没变成1的概率……这是一个容斥。
可以注意到,容斥的每一项在总的答案中以几何级数的形式出现。例如,当N=4时,假设每次操作,“0011”中的“00”仍然保持的概率是0.5,那么它对总的答案的贡献是:-(1+0.5+0.5^2+0.5^3)……负号是因为有两个0,而第一项1是操作0次没变成目标的概率中的。
因此我们得出了一个算法:枚举s,计算s中那些0在一次操作中仍然全部保持为零的概率p,然后根据s中0的个数,将答案加上或减去1+p+p^2+...,也就是1/(1-p)。当然,如果1-p为零,答案就是INF了。
那么对于s,p究竟是什么呢?就“0011”而言,显然这个数是:选中0011的概率+选中0001的概率+选中0010的概率+选中0000的概率。换言之,选中0011的所有子集的概率之和。
三个不同的分值就对应了三种计算子集和的方法。2^2N暴力遍历这是N<=10的30分算法,而3^N枚举子集就是N<=15的50分算法。至于100分算法,需要用到一种特殊的技巧:
for(int i=0;i>i)&1) P[s]+=P[s^(1< 假设P数组一开始是读进来的概率数组(P[i]代表选择i的概率),那么在进行这一操作后,P[i]就成为了选择i的所有子集的概率之和。
为什么这样是对的呢?我们可以感性地理解一下,看看P[0000]是怎么加到P[0011]上的(这都是二进制……):在i=0时,P[0000]加到了P[0001]上,而在P=1时,P[0001]带着其中的P[0000]加到了P[0011]上。可以发现,每个子集的这种“加法路径”是唯一的。
代码:
#include#include #include #include using namespace std; const double eps=1e-10; int N; double P[1<<20]; double F[1<<20]; int cnt[1<<20]; int getdig(int s,int i){return (s>>i)&1;} void work(void){ cnt[0]=0; for(int s=1;s<(1< >1]+(s&1); } memcpy(F,P,sizeof(F)); for(int i=0;i
这题我在考场上写的是60分算法。
str(数字串拆分):
题目地址:
首先我们考虑一下f值的求法:有转移方程f(i)=f(i-1)+f(i-2)+...+f(i-M),显然这是可以写成矩阵的。即,假设f(0)~f(M-1)组成一个列向量D0,那么存在某个M*M的转移矩阵A,使得f(n)=(A^n*D0)[1][1](这个记号代表矩阵A^n*D0的(1,1)位置的元素)。
我们不妨以123为例:f(123)=(A^123*D0)[1][1],f(24)=(A^24*D0)[1][1],那么f(123+24)=(A^123*D0)[1][1] +(A^24*D0)[1][1] = ((A^123+A^24)*D0)[1][1]。
换言之,为了求g(123)=f(123)+f(1+23)+f(12+3)+f(1+2+3),我们只需要求B=A^123+A^(1+23)+A^(12+3)+A^(1+2+3),然后计算B*D即可。
具体做法就是:先用类似高精度的方法(有点像NOI2013 矩阵游戏)预处理出seq数组:seq[i][j]代表A^S[i~j]。然后进行DP:dp[i]表示以i结尾的和,有转移dp[i]=∑dp[j]*seq[j+1][i],其中j
这道题卡常数,需要一些技巧,比如计算矩阵乘法时,用一个long long先存下所有a[i][k]*b[k][j]之和,最后再取模。事实上,对于极限数据,矩阵乘法的内层循环大致需要运行1.25亿次,也就是说,在较慢的机器上可能没有任何人能通过这道题。
代码:
#include#include #include #include #include using namespace std; typedef long long LL; const int SIZEN=510; const int MOD=998244353; int timer=0; class Matrix{ public: int n,m; int s[5][5]; inline void clear(int n_,int m_){ n=n_; m=m_; memset(s,0,sizeof(s)); } inline void unit(int x){ n=m=x; memset(s,0,sizeof(s)); for(int i=0;i >=1; } return ans; } char S[510]; int L,M; Matrix step; Matrix seq[SIZEN][SIZEN]; Matrix DP[SIZEN]; int F[SIZEN]={0}; void work(void){ DP[0].unit(M); for(int i=1;i<=L;i++){ DP[i].clear(M,M); for(int k=1;k<=i;k++){ DP[i]=DP[i]+DP[i-k]*seq[i-k+1][i]; } } F[0]=1; for(int i=1;i<=M;i++){ for(int k=1;k<=M;k++){ if(i-k<0) continue; F[i]=(F[i]+F[i-k])%MOD; } } Matrix ori; ori.clear(M,1); for(int i=0;i
总结
考试中我算法A了三道题:上午的T1,T2和下午的str。不过实际结果是上午180分,下午70分。上午的180分可能是100+50+30,即T2未写手工栈导致只有50分。下午70分可能是10+60,第一题我输出了8位而非答案中的10位小数,因此若cena评测时采用了简单对比而非special judge,那么我的第一题就只得10分,而不是应有的60分。第二题可能是由于卡常数的关系,只得到了60分(后四个点全部是极限数据)。