题目链接在这里
A. Vasya and Socks
初始共有n个，之后每m天多一个，其中发的那个第二天才能用，每天消耗一个，问能维持多少天？
直接模拟就可以，不过能写出推导式子更好。
我是这么理解的，以第二个例子n = 9, m = 3为例:
○ ○ ● ○ ○ ● ○ ○ ● ○ ○ ● ○
空心○ 表示从一开始就有，实心● 表示后来发的。
假设最后共使用了s天，于是有
s / m + n = s
即最后的 = 后来发的 + 最开始的, 但是当天发的是没法当天用的，因此如果s是m的倍数，s需要减1。
注s的推导： 假设s = p * m + q，可以得到p = n / (m - 1), q = n % (m - 1)，所以s = n * m / (m - 1)
int main()
{
int n,m;
cin >> n >> m;
int s = n * m / (m - 1);
if (s % m == 0)
--s;
cout << s << endl;
return 0;
}
B. Little Dima and Equation
给定一个公式，x = b * s(x) ** a + c
a,b,c给定，s(x)表示x十进制的各位和，**表示求幂，注意x的范围： 0←x→1e9，1e9单循环都会比较耗时。
因此暴力是不行的。
那就再看s(x)的范围，x最多是9个9，可以得到:0←x→81，循环一边得到结果即可。
int main()
{
LL a,b,c;
vector<LL> ans;
cin >> a >> b >> c;
for (int i = 0; i <= 81; ++i)
{
LL x = 1;
for (int j = 0; j < a; ++j)
x *= i;
x = b * x + c;
LL y = x;
int j = 0;
while (y)
{
j += (y%10);
y /= 10;
}
if (i == j && x < 1e9 && x > 0)
ans.push_back(x);
}
cout << ans.size() << endl;
sort(ans.begin(), ans.end());
for (vector<LL>::iterator iter = ans.begin(); iter != ans.end(); ++iter)
{
cout << *iter << " ";
}
if (!ans.empty())
cout << endl;
return 0;
}
C. Present
有n朵花，每次浇连续的w朵，被浇的花会长高1，问m天后最低的那朵最高是多高？
注意范围：1 ≤ w ≤ n ≤ 1e5; 1 ≤ m ≤ 1e5
套两层循环，比如
for i : 1 to m
for j : 1 to n
就会超时，更直接的思路是直接二分求结果。
注意二分的结束条件，关于二分的一篇笔记
数组water_cnt记录对第i朵花实际浇了多少次可以到希望的高度。
scurr维护了浇到当前花的次数（包括之前和当前花的次数，即water_cnt[i - w + 1] + … + water_cnt[i])
对下朵花，只要减去water_cnt[i - w + 1]就可以了，计算完后加上water_cnt[i + 1]就可以更新scurr。
这样计算当前花在前面浇花过程中浇了多少次了,更简单一些。
int main()
{
LL n,m,w, ans = 0;
cin >> n >> m >> w;
LL a[100000] = {0};
LL water_cnt[100000] = {0};
for (int i = 0; i < n; ++i)
cin >> a[i];
LL low = 1, high = 1e10;
while (low < high) {
LL mid = (low + high + 1) >> 1;
LL scurr = 0;//记录前面有多少次浇到了当前花,即[current - w + 1，current]共浇了多少次。
LL x = 0;
//compute x,x是浇花要浇到至少mid高度，所需要的天数
//water_cnt记录实际浇的次数
for (int i = 0; i < n; ++i) {
water_cnt[i] = 0;
scurr -= i >= w ? water_cnt[i - w] : 0;//i - w的花浇不到当前花，去掉后就是前面浇花时，浇到了当前花的次数
LL water_needed = mid - a[i];//需要浇多少
if (scurr < water_needed) {
water_cnt[i] = water_needed - scurr;//相减实际浇多少就可以到mid高度了
scurr += water_cnt[i];//更新供下朵花使用该值
x += water_cnt[i];
if (x > m) {
break;
}
}
}
if (x <= m)
{
low = mid;
}
else
{
high = mid - 1;
}
}
cout << low << endl;
return 0;
}
D. Little Victor and Set
给定一个范围[l,r]，从其中选取数字，使得所有数字异或的值最小。数字的个数1 <= x <= k。
范围是：1 ≤ l ≤ r ≤ 1e12; 1 ≤ k ≤ min(1e6, r - l + 1)。
求解这道题目，关于异或，有几个知识点：
x ^ x = 0//异或自己为0
x ^ 0 = x//异或0为自己
(2 * x) & (2 * x + 1) = 1//对一个偶数，与+1后的奇数异或为1，以为对偶数+1，只会让最低位变1，其余位不变。
记c = r - l + 1， 可知k≤4不妨分以下几个情况讨论：
- c≤4 → 状态DP求解即可
- 如果c>4
2.1. k == 1 → 取l
2.2. k == 2 → ans = 1，按第三个条件取
2.3. k == 4 → ans = 0, 按第三个条件取，取两组，则结果为0。
2.4. k == 3 → 按第三个条件取，ans为1。然后就是看下有没有取到0的办法，比如
3^5^6=0, 2^4^6=0
观察可知这种数字很多，如果有我们只要构造一组即可，构造的思路如下：
如果三个数异或为0，那么每一位组合有4种情况:
1 0 1 0 1 1 0 0 0 1 1 0 假设我们得到三个数字x>y>z满足x^y^z=0,那么对于x最高的为1的那一位,只能是第一种情况，即这一位：
x为1，y为1，z为0。
比如z=101101，那么x,y的第7位应当均为1，于是有
x: 1 * * * * * *
y: 1 * * * * * *
z: 0 1 0 1 1 0 1
同时为了使得x>y,那么第6位应当x为1，y为0，注意也可以x为0，y为1，但如果是这样，就意味着更高位需要x为1，y为0才能保证x>y， 注意我们是在构造数据，因此应当x,y使得尽量小，而不是尽量大。于是有
x: 1 1 * * * * *
y: 1 0 * * * * *
z: 0 1 0 1 1 0 1
接下来的每一位，可以令x均为0，y与z相同，这样范围应该就是最小的了。于是有
x: 1 1 0 0 0 0 0
y: 1 0 0 1 1 0 1
z: 0 1 0 1 1 0 1
按照这个构造的思路，可知道z越大，则x,y越大，如果对于z=l，仍然无法找到这样的x，y那么结果为1，否则结果为0.
假设z的最高1位是j，则
x = 2 ^ (j + 1) | 2 ^ j
y = 2 ^ (j + 1) | (z & ~(2 ^ j))
关于第一种情况里的状态DP，正在整理一篇笔记，会逐步贴出。
同时1 << 34这种代码会超int，因此需要修改为LL b = 1; b << 34才能AC.
具体代码如下：
void solution_dp()
{
const int max_state = (1 << 4);
LL dp[max_state] = {0};
int state = -1;
for (int i = 0; i < max_state; ++i)
for (int j = 0; j < c; ++j) {
if (i & (1 << j))
continue;
int new_state = (1 << j) | i;
int number_one_cnt = 0;
int p = new_state;
while (p)
{
number_one_cnt++;
p = p & (p - 1);
}
dp[new_state] = dp[i] ^ (l + j);
if (ans == -1 || dp[new_state] < ans && number_one_cnt <= k) {
ans = dp[new_state];
state = new_state;
}
}
for (int i = 0; state; ++i) {
if (state & 1)
vec.push_back(l + i);
state >>= 1;
}
}
void solution_constructive()
{
if (k == 1) {
ans = l;
vec.push_back(ans);
}
else if (k == 2) {
ans = 1;
if (l & 1)
l++;
vec.push_back(l);
vec.push_back(l + 1);
}
else if (k == 3) {
LL z = l;
int max_sign = -1;
for (LL i = 0; z; ++i) {
max_sign = i;
z >>= 1;
}
LL b = 1;
LL x = (b << (max_sign + 1)) | (b << max_sign);//如果直接1<<max_sign会超int有可能，需要指定LL.
if (r >= x) {
z = l;
ans = 0;
LL y = (b << (max_sign + 1)) | (z & ~(b << max_sign));
vec.push_back(x);
vec.push_back(y);
vec.push_back(z);
}
else {
ans = 1;
if (l & 1)
l++;
vec.push_back(l);
vec.push_back(l + 1);
}
}
else if (k >= 4) {
ans = 0;
if (l & 1)
l++;
vec.push_back(l);
vec.push_back(l + 1);
vec.push_back(l + 2);
vec.push_back(l + 3);
}
}
int main()
{
cin >> l >> r >> k;
c = r - l + 1;
if (c <= 4) {
solution_dp();
}
else {
solution_constructive();
}
cout << ans << endl;
cout << vec.size() << endl;
for (vector<LL>::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
cout << *iter << " ";
}
cout << endl;
return 0;
}