集训没打，F 提前做了，今晚 20min 干掉了前五题，确为水题场啊，但是题目似乎不利于 CN 选手发挥（
F（绿）
E（黄/绿）
题意
你有 N 个任务和 X 日元，完成任务的方式是进行提交。第 i 个任务完成的收益是 S_i 个点数（每个任务只能完成一遍，完成后将不能再提交），对这个任务进行提交的花费是 C_i 日元，这次提交有 P_i\% 的概率完成任务，其余 1-P_i\% 的情况将失败，没有收益。
求用最佳策略使用这 X 日元时获得点数的期望，浮点数输出。
1\le N\le 8,1\le S_i\le 2718,1\le C_i\le X\le 5000,1\le P_i\le100，2s，1024MB。
题解
这道题偏理解。对期望概念不熟悉的话会被这道题的题意困很久。
观察到 N\le 8，考虑状态压缩动态规划，用 f_{i,j} 表示拥有 i 元，剩余未做问题表示为 j 时，可以获得的最大点数，j 的最低位表示 1 号任务是否未做，第二位表示 2 号任务是否未做，以此类推。例如：j=(110)_2 表示 2,3 任务未做，1 任务已完成。
每一个 f_{i,j} 从当前状态下“去做一次提交尝试”的期望最大值转移过来。具体地：
对于 j 情况下的每一个未被做的任务 k，尝试提交这个任务，在这一步选择这个任务的情况下，期望是“（这次提交成功可以获得的点数+这个任务完成后的情况的期望）*成功的概率+这个任务失败后的情况的期望*失败的概率”。形式化地：
在我们采用的二进制表示 j 的方案中，用 j_k 表示 j 二进制下的第 k 位，这个式子是：
递推即可，状态数 O(X2^N)，每个状态从 O(N) 个未完成的任务转移，因此总时间复杂度是 O(NX2^N)。
代码
scanf("%d%d",&n,&x);
for(int i = 1;i <= n;i ++) scanf("%d%d%d",&s[i],&c[i],&p[i]);
for(int i = 1;i <= x;i ++)
for(int j = 0;j < (1 << n);j ++)//计算每个 f[i][j]
for(int k = 1;k <= n;k ++)
if((j & (1 << k - 1)) && i >= c[k]) //如果情况 j 里任务 k 还没做，并且当前考虑的金钱 i 足够做这个任务
f[i][j] = max(f[i][j],
p[k] / 100.0 * (f[i - c[k]][j - (1 << k - 1)] + s[k]) + //这部分是成功的期望
(100 - p[k]) / 100.0 * f[i - c[k]][j]);//这部分是这次提交失败后的期望
printf("%.20lf",f[x][(1 << n) - 1]);//输出最终状态，有 x 的钱并且所有任务都未做
D（橙/黄）
题意
给定一个圆，圆上均匀分布着 N 个点，顺时针依次编号。接下来给定 M 条直线，每条直线经过圆上的两个点 (A_i,B_i)，求有多少对直线相交。
2\le N\le 10^6,1\le M\le3\times10^5，2s，1024MB。
题解
几何题，不妨改成求每条线加入之前，图上已有多少条线和它平行。
我们知道平行就是斜率相同，但是这张图很难表示斜率。考虑换种方式表示斜率。
我们发现：每一条直线都和圆的某条半径相垂直，这条半径经过点 \frac{A_i+B_i}{2} 的位置（即直线截出的弧的中点）。分数不好表示，考虑把它乘以二，这样它的范围是 [1,2N]，显然一条半径是经过两个圆上的点的，对应一个 x(x\in[1,N]) 和 x+N，把它们对 N 取模，这样半径就和这个数字唯一对应了。
结论：(A_i+B_i)\bmod N 可以准确映射直线的斜率。有多少条直线平行于它，就是在问有多少条直线 j 满足 (A_i+B_i)\bmod N=(A_j+B_j)\bmod N。
用桶实现，时间复杂度 O(M)。
代码超短。
代码
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++){
scanf("%d%d",&a,&b);
x = (a + b) % n;//斜率的唯一映射表示
cnt[x] ++;//同斜率的线，都是平行的
ans += i - cnt[x];//题目要求统计不平行的直线对
}
printf("%lld\n",ans);
C（橙）
题意
有 N 种食材，M 种料理，第 i 种料理有 K_i 种组成的食材，为 A_{i,1\cdots K_i}。你喜欢一种料理，当且仅当你喜欢组成这种料理的所有食材。
初始的时候，你不喜欢所有食材。从第 i 天开始，你对 B_i 食材的态度会由不喜欢转变为喜欢。求 N 天里每一天你喜欢多少种料理。
1\le N,M,\sum K_i\le 3\times 10^5。2s，1024MB。
题解
考虑维护每一种料理有多少种食材被你“不喜欢”，记为“讨厌度” D_i。初始时 D_i=K_i。
当你开始喜欢一种食材时，它构成的所有料理的“讨厌度”都会减一。当一个料理的讨厌度降为 0，你就会开始喜欢这个料理。
我们可以考虑用邻接表/vector 存储每一种食材构成了哪些料理，每一天遍历检查所有 B_i 构成的料理即可。时间复杂度 O(N+M+\sum K_i)。
代码
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++){
scanf("%d",&k[i]);
for(int j = 1;j <= k[i];j ++){
scanf("%d",&a);
d[a].push_back(i);//食材 a 组成了料理 i
}
}
for(int i = 1;i <= n;i ++){
scanf("%d",&b);
for(auto j : d[b]) if(!-- k[j]) ans ++;//如果料理 j 讨厌度降为了 0，那么喜欢的料理数 +1
printf("%d\n",ans);
}
B（红）
题意
餐厅门口有一个排队队列，初始没有人。接下来 Q 个时刻，每个时刻会发生一件事情：
- 有一个人拿着号码牌 X 去到队尾排队。
- 队首的一个人进店用餐，你需要报出他的号码 X。
1\le Q\le100，2s，1024MB。
题解
考虑使用 queue 进行模拟。时间复杂度 O(Q)。
代码
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
scanf("%d",&op);
if(op == 1){//这是入队操作
scanf("%d",&x);
q.push(x);//入队
}
else{//这是出队操作
printf("%d\n",q.front());//报出队首号码
q.pop();//队首出队进店
}
}
A（红）
题意
给你一个字符串 S。你需要输出 S 中大写字母构成的字符串。
1\le \vert S\vert\le 100，2s，1024MB。
题解
我们可以通过 c >= 'A' && c <= 'Z' 判断 c 是否是大写字母。
按照题意模拟即可，时间复杂度 O(\vert S\vert)。
代码
scanf("%s",s + 1);
n = strlen(s + 1);
for(int i = 1;i <= n;i ++) if(s[i] >= 'A' && s[i] <= 'Z') printf("%c",s[i]);