A 体育打卡
签到模拟题。
B 时间管理
由
设
于是由
得
于是直接输出 $\dfrac{t-1}{5}$ 即可。
时间复杂度 $O(T)$ 。
C 贪吃蛇
模拟题。
考虑贪吃蛇的移动方式，由于本题的贪吃蛇长度不会变化，所以移动可以看成是蛇尾移动到蛇头。
所以很容易想到用双端队列来维护整个蛇身，每次从队尾取出蛇尾，判断下一个蛇头的位置是否是目前蛇身的位置（开二维数组或者 map 标记），若是则说明 game over，输出时间；否则从将新蛇头的位置加入队头。
D 佑香跑步
最多和最少的做法其实是一致的。
记 $f(x)$ 表示到第 $x$ 格时投掷骰子的最少次数。
于是显然有
对于前面的 $\min\{f(i)\}$ ，直接开 vector 将所有的 $i$ 存入到第 $x$ 个 vector 里，直接转移即可。
对于后面的，可以用数据结构优化到 $\log $ 或者用单调队列。
我写的单调队列，时间复杂度 $O(n)$ 。
E 简单染色
第一次看被数据范围吓到了，跳去看了 F 题。
F 题想半天感觉不对劲，又回来看了这题。
才注意到 $q$ 最大才 1e3 ，这说明区间端点不过最多才 $2000$ 个。
于是自然而然想到了将区间端点离散化，然后每次对操作序列里面的每小段进行修改。
但是这样无法处理 [10,20],[20,30],[30,40] 这样的操作，因为每小段的区间端点与区间内部的颜色不同。
所以想到了将每个端点的后一位也进行离散化，这样便可以代表区间内部的节点。
于是开个 map 存各颜色的节点个数，依次计数即可。
讲的有点混乱，贴个代码（
时间复杂度大约是 $O(q^2\log n)$ ？
#include<bits/stdc++.h>
#define N 4010
#define ll long long
using namespace std;
inline ll read() {
ll w=1,x=0;
char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return w*x;
}
ll n,q,k,l[N],r[N],x[N],c[N],v[N];
map<ll,ll> cnt;
ll raw[N],t;
map<ll,ll> val;
vector<ll> tmp;
void discrete() {
sort(tmp.begin(),tmp.end());
t=unique(tmp.begin(),tmp.end())-tmp.begin();
for(int i=0;i<t;i++) {
val[tmp[i]]=i+1;
raw[i+1]=tmp[i];
}
}
int main() {
n=read(),q=read(),k=read();
for(int i=1;i<=q;i++) {
l[i]=read(),r[i]=read(),x[i]=read(),c[i]=read();
tmp.push_back(l[i]),tmp.push_back(r[i]);
tmp.push_back(l[i]+1);
tmp.push_back(r[i]+1);
}
discrete();
cnt[1]=n;
for(int i=1;i<=t;i++) v[i]=1;
for(int i=1;i<=q;i++) {
for(int j=val[l[i]];j<val[r[i]];j++) {
cnt[v[j]]-=raw[j+1]-raw[j];
v[j]=((v[j]^x[i])%k)+1;
cnt[v[j]]+=raw[j+1]-raw[j];
}
cnt[v[val[r[i]]]]--;
v[val[r[i]]]=((v[val[r[i]]]^x[i])%k)+1;
cnt[v[val[r[i]]]]++;
printf("%lld\n",cnt[c[i]]);
}
system("pause");
return 0;
}- UPD：官方题解出辣，贴个官方题解。
F eyes
第一眼：这不是个裸的分组背包吗
再深入一想：不行啊，如果出现一个物品和多个物品有限制关系就不行了。
首先可以想到的是，没有限制关系的物品可以直接对其进行背包。
主要就是有限制关系的物品的处理。
于是想了接近两天的傻逼暴力。
第一回，想了个暴搜每个限制选取的宝物，每次选取对该物品做一次背包，时间复杂度 $O\Big(q3^qV\Big)$ ，妥妥滴超时辣
第二回，想到可以暴搜选取的宝物集合，每次搜完对集合做一次背包，显然这是和上面一样的，也超时辣。
第三回，在比赛结束的前一天晚上，突然意识到了，为什么我要干暴搜里面 DP 这种傻逼事情，直接以剩余体积为状态搜不就行了吗，开个数组记录每个体积状态时的最大值，这样搜索的时间复杂度就是 $O(q3^q)$ ，再加上背包，总时间复杂度为 $O(q3^q+nV)$ ，可以通过本题。
我太飞舞辣。
G 浮点运算
大模拟，不可做（bushi
