(Rating)上涨了，真开心
A - Red-Blue Shuffle
给你(n)张牌，每张牌上有一个红色的数字和一个蓝色的数字，你可以将牌随便排序，问你是红色组成的数字大于蓝色的概率大，还是蓝色组成的数字大于红色的概率大，还是两者相等。
哪种颜色的数字大的数量多，哪种颜色概率就大，签到题
B - Move and Turn
找规律+结论题
有一个无限展的二维平面，一个机器人每秒可以前进一个单位，但是每一秒之后，机器人必须向左转或者向右转。问你(n)秒之后机器人可能出现的坐标的数量。
找规律的话，就先用(bfs)打表(注意(bfs)会爆内存)，然后就能发现规律：
-
若(n)是偶数，则答案为((n / 2 + 1)^2)
-
若(n)是奇数，则答案为(k=frac{n}{2},2*(k+1)(k+2))
考虑(n)为偶数时的情况。无论初始方向如何，我们将进行(n/2)个水平步和(n/2)个垂直步。此外，水平和垂直步数的方向可以单独决定。
比如有(k)个水平方向的选择，那么最后的落点横坐标就是([-k,-k+2,.....k])
则偶数答案为((n/2+1)^2)
奇数的情况需要考虑第一步是水平的还是垂直的，这里首先说明一个结论
最终的水平位置x的奇偶性与水平步数相同
由此得出：从垂直和水平步数开始都不可能到达相同的位置
(n=2k+1)是奇数。如果我们从水平步开始，那么总共将进行(k+1)个水平步和(k)个垂直步，那么最后到达点数是((k+1)*(k+2))（可以参考偶数情况理解）
最后答案就是(2*(k+1)*(k+2)，k=n/2)
本题告诉我们，像这类在二维坐标系上移动的题目：
-
可以单独分离出横纵坐标，然后利用简单计数原理进行求解
-
从奇偶数角度考虑
C - Row GCD
数论+思维+差分
给定数组(a[n],b[m])，对于每个(b_i,ile m)，求(gcd(a_1+b_i,a_2+b_i.....))
很妙的题目，平时(gcd)的题目很少用的(gcd(a,b)=gcd(a-b,b))这个性质，本题就是利用这个性质来求解
同理(gcd(x,y,z)=gcd(x-y,y,z))依然成立，那么求解(gcd(a_1 + b_j, ldots, a_n + b_j))时，可以把第二项往后减去第一项，即(gcd(a_1 + b_j, ldots, a_n + b_j) = gcd(a_1 + b_j, a_2 - a_1, ldots, a_n - a_1))
这时候我们可以发现(gcd)式子里面除去第一项外都是定值了，这时候可以分离一下
(X=gcd(a_2-a_1,...,a_n-a_1))，题目变成了求解(gcd(a_1+b_j,X))
D - Glass Half Spilled
(DP)
桌子上有(n)个玻璃杯，编号为(1，...，n)。第(i)个玻璃杯最多可以装(a_i)单位的水，目前装的是(b_i)单位的水。
选择(k)个玻璃杯，可以把(x)（不超过(c_i)，可以是实数）单位水从(i)杯转移到(j)杯,水会撒一半（(j)杯超出部分也会溢出），问最后(k)个玻璃杯最大水量为多少(误差不超过(10^{-9}))
设最初所有杯子水的和是(s_1),最后选择的(k)杯水和是(s_2),容量是(s_3)
显然，其他杯子最多能给我们选择的倒出((s_1-s_2)/2)
答案就是(max(s_3,s_2+(s_1-s_2)/2)=max(s_3,(s_1+s_2)/2))
现在未知数就是(s_2,s_3)
(f[i][j][k])表示前(i)个水杯，选了(j)个，容量(s_3=k)时最多能放的水量，这样就成功联系起来了(s_2,s_3)
现在问题变为：有一个背包，容积为(k)，能拿(j)个物品，问最大价值。
思路源自大神qscqesze
const int N = 220, M = 1e4 + 2020;
int n, dp[N][M], a[N], b[N], suma, sumb;
int main()
{
n = read();
for(int i = 1; i <= n; ++i){
a[i] = read(), b[i] = read();
suma += a[i], sumb += b[i];
}
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= M; ++j)
dp[i][j] = - 1e9;
dp[0][0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = n; j >= 1; --j)//???为什么正序不行呀
for(int k = suma; k >= a[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - 1][k - a[i]] + b[i]);
for(int i = 1; i <= n; ++i){
double ans = 0.0;
for(int k = 0; k <= suma; ++k){
ans = max(ans, min( (dp[i][k] * 1.0 + sumb ) / 2.0, k * 1.0 ) );
}
printf("%.10lf ", ans);
}
return 0;
}
(DP)还是弱，经典(DP)问题不会处理