这次考试共得 573 分，排名第 3。
\color{red}{p.s：这里作者只会写自我感觉有意义得题目的题解。}
总体分析：
T1 到 T4 为签到题，其中 T1 难度为语法，T2 也为语法，T3 为普及，T4 为普及，其中 T4 为原题。
T1
这道题目一上来就秒掉了，就是每次判断这个孩子是不是男孩，然后判断这个孩子是不是他们家的第一个孩子即可，无需多讲。
T2
这道题目也秒了，每次循环把 x_i 放到数组前面，然后输出的时候判断这个数是否出现过，然后输出即可，无需多讲。
T3
我的方法是使用二分，正解为贪心。二分大概就是二分能取到的最大值，然后每次判断是都能有 m 组数的成绩大于等于当前二分的答案，然后就没有然后了，无需多讲。
T4
这里注意到容量很大，所以我们将正常的背包反过来思想，具体可以参见此文章：link 无需多讲。
T5
一分没得……
这道题目一开始以为是什么高级的 dp，其实不应该这么想，因为观察数据范围也不可能是 dp 除非利用高级算法优化，属于失误。
其实正解就是套 Dijkstra。像那些不能转弯的路口我们不需要多考虑，我们可以只考虑能转弯的路口和起点和终点。
T6
这道题目赛场上输出的数字是对的但是顺序不对，夺得了 \color{red}{W A46} 的成绩。
看完某位巨佬的题解以后豁然开朗！
给出巨佬的题解：link。
T7
想了大概一个半小时，赛场上搞出来了，其实想想题目难度还可以。
题解
首先需要使用贪心思想，考虑复习的顺序，顺序应该按照遗忘度 c_i 从大到小排序。如果很大的 c_i 与很大的 j 相乘，乘积会很大。
然后就用分治好了，注意到 n 大约是 40 直接枚举是不行的，因此考虑折半搜索的思想，我们把知识点分成两个部分，设前一半是 A 后一半是 B，分别枚举两个部分，然后把结果合并。
首先枚举前一半 A，我们对 A 的每个子集，记录选择元素个数 k_1、总时间 time 和总价值 value。
然后我们枚举后一半 B，对 B 的每个子集，记录选择元素个数 k_2、基础时间 time_2、遗忘度总和 sum 和总价值 value_2。合并结果的时候，B 的总时间为 time_2+(m-k_2)\times sum。
然后我们要来合并答案，对于每个可能的 k_2，我们计算 k_1=m-k_2。遍历 B 的所有子集，在 A 的对应状态中查找满足总时间要求的最大价值。
上个伪代码：
/*输入*/
sort(&item[0],&item[n],cmp);//按照遗忘度排序
int n1=n/2,n2=n-n1;//分成两段
vector<vector<pair<int,int> > >p(n1+5);//用来记录每种子集的状态
for(int mask=0;mask<(1<<n1);mask++){//生成这一段的所有子集
int k=__builtin_popcount(mask);//这是一个内置函数用于统计二进制码中 1 的个数，这里是记录下可能的 k 的值
int t_=0,v_=0,cnt=0;//初始化总时间，总价值，元素个数
for(int i=0;i<n1;i++){//枚举前半段的所有元素
if(mask&(1<<i)){//如果选择了第 i 个元素
//更新元素个数
//更新时间
//更新价值
}
}
// 记录下这个子集的状态
}
/*这里是枚举后半段和前面大致相同，自己试试看吧！*/
vector<vector<pair<int,int> > >list(n1+5);
for(int k=0;k<=n1;k++){
if(p[k].empty())continue;//如果没有这种状态跳过
/*对 p 进行排序*/
vector<pair<int,int>>v;
for(auto it:p[k])if(v.empty()||it.second>v.back().second)v.push_back(it);
list[k]=v;
}
int ans=-1;//答案
for(int k2=0;k2<=min(m,n2);k2++){
int k1=m-k2;//计算 k1
if(k1<0||k1>n1)continue;
if(list[k1].empty())continue;
for(auto it:p_[k2]){
//按照上面说的公式计算
if(t_>t)continue;
int t0=t-t_;
auto v=list[k1];
auto it_=upper_bound(v.begin(),v.end(),make_pair(t0,LLONG_MAX));
if(it_==v.begin())continue;
it_--;
int tot=it_->second+v_;
if(tot>ans)ans=tot;
}
}
/*输出*/
T8
这道题目坠机了，题目都没看多少，赛场上一直在搞前面 7 题，最后几分钟骗了 27 分。这道题目是考虑最小生成树，然后利用贝祖定理得到一些性质，然后得到一个非常简洁的结论。这道题目竟然是结论题，太不可思议了。
结论就是：
先将 C_i 升序排列，然后就开始套结论了：
- 若 \gcd(A_1,A_2,\dots,A_m,N)≠1 那么这个图不连通直接输出 -1 即可。
- 否则，答案就是 \sum_{i=1}^MC_i\times(\gcd(A_1,A_2,\dots,A_{i-1},N)-\gcd(A_1,A_2,\dots,A_i,N))。
大概的代码如下：
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>x[i].a>>x[i].c;
sort(&x[1],&x[m+1],cmp);
g[0]=n;
for(int i=1;i<=m;i++)g[i]=gcd(g[i-1],x[i].a);
if(g[m]!=1){
puts("-1");
i_ak ioi;
}
for(int i=1;i<=m;i++)ans+=x[i].c*(g[i-1]-g[i]);
cout<<ans;
反思
像 T5 这种题目观察数据范围就知道大概率不可能是 dp，应该把算法的适用条件搞清楚，然后时间分配并不合理，导致 T8 几乎都没想，相信即使想了估计也大概率想不出结论，还是太菜了思维有待提高……
比赛过程
首先打开 T1 秒了，然后打开 T2 秒了。
然后看了一眼 T3 又看了一眼 T4，发现 T4 为原，先把 T4 打完了，然后看 T3 利用二分 AC。
前 4 题，大概花费 20\sim 30 分钟。
然后看 T5 以为是 dp，看不出什么状态转移方程，先跳过看了 T6。
T6 花了 10\sim 20 分钟打了代码，发现输出的数正确但是顺序不对，提交上去 46 分，调了一下没有进展，于是看到 T7。
T7 大概花了 1 个多小时，注意到数据范围知道要折半搜索枚举子集，然后想了一下优化，打出了代码，提交上去 AC 了。
看了一眼 T8 感觉性价比不高，回去看了 T5、T6.
然后就没有然后了，很显然 T5、T6、T8 全军覆没，最后 T8 骗了 27 分，收场。