A

题意：

• 给出一个字符串S，求出字符串T的个数，使f(S,T)达到最大值

• f(S,T)=S中每个字符在T中出现的次数的和

• 字符串中只有"A","C","G","T"四种字符

做法：

• 其实这题不算难

• T中每一个字符对答案的贡献，等于S中此字符出现的次数

• 所以只要T中每一个字符都在S中出现得最多就可以啦

• 扫一遍S，计算出现最多的一个或多个字符总共出现了多少次,设其为cnt

• 然后快速幂(Power(cnt,n))一下就过了

hack有关：

• 这题...

• pretests够强

• 

B

题意：

• 给包含n个平面上的点的点集，定义一种性质K：对于此点集中的任意一个不在X轴上的点(x,y)，都满足(x-1,y-1)或(x,y-1)或(x+1,y-1)在此点集中

• （妈呀这性质好长

• 现有两个人，轮流取出标号最大和最小的点，且取后此点集仍满足性质K

• 求取法在n进制数下的hash值（应该叫hash值吧= =

做法：

• 怎么想都是个模拟题啊QAQ

• 用STL的set或手打平衡树维护一下，每次取走之后看一下对周围点的影响，处理一下可取性的变化就可以啦

• 这题在考试的时候过的人少主要是因为...

• 这题意太难懂了QAQ

hack有关：

• 想一想发现这题的pretests也够强

• 只要出题人不想给hack，谁都别想= =

C

题意：

• 给出一个长度为n的数串，要求加k个加号

• 求所有加加号方法算得结果的和

• （就是说每个加+的方案所得到的表达式都有一个ans，把所有ans加起来就行了

做法：

• 其实这题还是比较难想的

• 需要想到分位讨论

• 也就是算出每一个数字对答案的贡献

• 算的时候有一点技巧

• 首先考虑当一个数字num（当然，0$≤$num$≤$9）在所在的被+分开的子数串中，所处的是从右数第i+1位

• 那么如果此子数串右端有+，则对答案贡献为$num\times\binom{n-i-2}{k-1}\times10^i$，如果无+，则贡献为$num\times\binom{n-i-1}{k}\times10^i$

• 第一种情况用前缀和优化一下就可以过啦

hack相关：

• 同样不好hack

• 如果pretests够水应该可以hack掉一些时间复杂度不对混过的

D

题意：

• 给出一个包含k个数的数列s，以及n个操作

• 操作有三种

• 1:把$s_i$赋值为b

• 2:把$s_i$加上b

• 3:把$s_i$乘上b

• 现求选m次操作，使$s_1\times s_2\times...\times s_n$最大

做法：

• 首先，对于同一个$s_i$的第一种操作可以归为一个第二种操作

• 然后考虑每一个操作对答案的贡献

• 若改变第i个数，其值原来为$w_i$，第二种操作的贡献为$\frac{w_i+b}{w_i}$，第三种操作的贡献直接为$b$，因为$w_i$会变，所以要用优先队列维护一下，每次取贡献最大的

• 但问题就来了...

• 因为精度什么的原因，两个第二种操作的比较要交叉相乘，而最大会大到$10^{22}$

• 所以要把操作的贡献改为$\frac{b}{w_i}$和$b-1$

• 然后就不用担心精度啦（最大只有$10^{17}$

hack相关：

• hack个毛啊

• 这种变态题能fst的也就只有rng_58了（还是WA on teset 149

• 好吧，不黑岛国人了，其实这题还是很容易fst的

• 毕竟是贪心，谁知道会有什么奇奇怪怪的贪心方法

E

题意：

• 给出一个三无（无向，无重边，无自环）图，要求找出两个点S,T

• 满足S,T之间有三条简单路径相连，且三条路径点集（当然除S,T）不相交

• 求此三条路径

• 其实我很不解为什么没有中国人过掉这一题

• 这题很水啊QAQ（虽然我当时根本没想到

• 其实...

• 这三条路径存在说明有两个边集有交的环

• 所以...

• 如果这个图中的所有联通块都是仙人掌，那么就无解；如果有个联通块不是仙人掌，那么这个联通块上必有一组解

• 所以看见官方题解里没有仙人掌我就很不爽啊吼！！！

• 同时，vfk的仙人掌教学好评啊吼！！！

做法：

• 先丢链接 vfk的仙人掌教程

• 然后...= =我还是说一下怎么做吧

• 首先Dfs...

• 然后搜到一个环之后（假设是在a搜到b已经到过），那么把a到b的原来的路径全部标记，如果以前就标记过，那么就说明有两个边集有交的环

还是丢代码比较清楚

void up(int S,int T)
{
    int x=S;
    while (x!=T)
    {
        if (pre[x].first!=0)
            print();
        pre[x]=mp(S,T);
        x=fa[x];
    }
}

以及...

void dfs(int w,int Fa)
{
    vis[w]=++ti,fa[w]=Fa,dep[w]=dep[Fa]+1;
    for (int i=0;i<E[w].size();i++)
    if (E[w][i]!=Fa)
    {
        if (!vis[E[w][i]]) 
            dfs(E[w][i],w);
        else if (vis[E[w][i]]<vis[w]) 
            up(w,E[w][i]);
    }
}

hack相关：

• 卧槽，这真的能hack？

• （嗯？似乎没说连通性，但那pretests也很强啊