NOIP 之后就写了这么个 simple 题

BZOJ 4589

题意

你有 $n$ 堆有序的石子，每堆的数量都是 $\le m$ 的一个质数

你要玩 Nim游戏，问有多少种方案先手必败

$n\le 10^9, m\le 5*10^4$

LOJ #2269

题意

你有一棵$n$个点的树，点$y$有一个$[0,m)$内的整数权值$a_u$

定义一棵树的权值是点权的异或和

有$q$次操作

• Change x y，表示把第$x$个点的权值改成$y$

• Query x，表示询问有多少个非空的联通子树的权值是$x$，模$10007$

$n,q\le30000,m\le128$

BZOJ 1023

题意

你有一棵$n$个点的仙人掌，边权为$1$

定义两点的距离是最短路的长度

定义仙人掌的直径是距离最远的两点的距离

求直径

$n\le5*10^4$

Luogu P3674

题意

你有一个长为$n$的数列$a$，$q$个询问，有三类，每次指定一个区间$[l,r]$和一个数$x$。

• 询问区间中是否存在两个数相加为$x$

• 询问区间中是否存在两个数相减为$x$

• 询问区间中是否存在两个数相乘为$x$

两个数可以在同一位置

$n,q\le10^5,0\le a_i\le10^5$

LOJ #2145

Zeit und Raum trennen dich und mich.

时空将你我分开。

题意

你有一排$n$个灯泡，有初始状态$0/1$，从$1$开始编号

一次操作可以选定一个整数$x\in[1,n]$，把$x$的所有约数号（含$1$和$x$）灯泡状态取反。

你要把所有灯泡变成$0$，给出$0\le k\le n$

1. 若剩余最小操作次数$\le k$，你会直接按照最小操作次数操作，并结束

2. 否则每次你会在$[1,n]$中等概率地选择一个整数进行操作，直到满足1的条件

求期望操作次数乘$n!$对$100003$取模的结果

$1\le n\le 10^5$

BZOJ 4316

题意

你有一棵边仙人掌，求最大点独立集

$n\le510^4,m\le610^4$

SPOJ QTREE

题意

你有一棵$n$个点的树，边有权，有两种操作

• CHANGE x y，表示修改第$x$条边的边权为$y$

• QUERY x y，表示询问点$x$到$y$路径上的边权最大值

BZOJ 2125

题意

给定 $n$个 点仙人掌（每条边只在不超过1个简单环中的无向连通图），$q$ 次询问两点间最短路

边带权

$n,q\le 10000$

LOJ #2585

题意

在数轴上有$n$家商店，第$i$个商店有坐标$x_i$，种类$t_i\in[1..k]$，出现时间$[a_i,b_i]$

有$q$组询问$l_i,y_i$，表示询问在时间$y_i$，离坐标$l_i$最远的商店类型到$l_i$的距离

类型$t$的商店到一个点的距离定义为所有存在的$t$类商店到这个点的距离的最大值

$1\le n,q\le 3*10^5,1\le k\le n$

$1\le x_i,a_i,b_i\le 10^9$

$1\le l_i,y_i\le 10^8$

LOJ #2127

题意

你有一个数字 $0$，每秒你会以 $p_i$ 的概率选择 $i$，$i\in[0,2^n-1]$，和自己的数进行按位或，问期望多少秒后数字变成 $2^n-1$

$n\le20,\sum p_i=1$