出题人好像鸽了

A. 超简单题 (普及组 T1 Only)

一个简单的贪心，我们知道n个线段一定要用全，否则一定不优
接下来我们就要判断一个边长为a,b,c的三角形能否被搞出来，c=总长-a-b
那么我们用布尔数组f[a][b]表示其中两边为a,b能否被表示出来（背包问题）
直接dp就可以过了
当然可以用bitset进行优化

B. 超级水题 (普及组 T2 Only)

我们可以从小到大枚举数字j出现的所有位置，那么对于以后出现的数字，一定会比j大，那么在j所在位置之前的数字就会对逆序对数有贡献，动态统计逆序对数，用树状数组即可

C. 大送分题 (提高组 T1 Only)

每次修改都是伪随机的。

修改到最小值的概率为 $1/n$，此时暴力扫一遍数列求出最小值即可。

期望时间复杂度 $O(m)$

D. 人口普查题 (普及组 T3 / 提高组 T2)

来自 QOJ Round #6 的 B 题

令f[i][j]表示将s的前i个字母修改为t的前i个字母的代价。
操作1：f[i][j]=f[i][j-1]+a
操作2：f[i][j]=f[i-1][j]+b
操作3：f[i][j]=f[i-1][j-1]+c
由于a+b<=2*d，因此每个数只会交换一次，并且交换后不会替换。
操作4：记k为s中上一个t[j]的位置，l为t中上一个s[i]的位置，f[i][j]=f[k-1][l-1]+d+(i-k-1)*b+(j-l-1)*a
时间复杂度O(|s||t|)

E. 打卡签到题 (普及组 T4 Only)

把n!末尾所有零都去掉，然后对10取模
对10取模不太好处理，我们从n!提一个2出来，先对5取模，然后再乘2
1/2在mod 5意义下等于3
两边对5取模，就是（5k)!/(10^k) = (1*2*3*4)^k*3^k*k!
设f(n)=n去掉末尾所有0
也就是f(5k!)=f(2^k*k!) (mod 10)
如果n=5k+t, 那么暴力乘上多的t个数

F. 最简单题 (提高组 T3 Only)

这是一道原创题，放最后讲jian，出题人拍脑袋的时候觉得很easy，但是实际情况确实挺难调的……
这是一道大模拟题，可以说不怎么考察算法水平，主要考察代码能力。
现在提供两种做法：
做法一：直接在展开图上进行操作，将18种转动情况分类讨论过去，部分类似的可以进行合并。
做法二：将展开图先转化成三维魔方，其中每个魔方的单元格子记下6面的颜色，没有颜色记为0，然后转动情况写起来会少很多，最后再将三位魔方转化成展开图输出。
做法一比做法二容易想，也不用进行输入输出的转化，就是细节偏多，做法二主要难度在于要将平面图转化成三维图。
出题人写了做法二。
欢迎提供更优秀的做法。

G. 白给题 (提高组 T4 / 省选组 T1)

令 $b_i$ 表示 $a_i$ 下一次出现的位置，那么询问等价于求 $b_l \sim b_r$ 中 $>r$ 的数的个数。

用树套树维护 $b$，并对每个值开一个 std::set 记录它出现的位置，每次修改时在 std::set 中查询它的前驱和后继并修改它们的b值。

区间修改后，可以把这个区间缩起来，只保留它的左端点。每个修改操作只会使段数+2，每次修改 $b$ 值会使段数-1。时间复杂度 $O((n+m)\log^2 n)$

H. 神秘题 (省选组 T2 Only)

对于 30%的数据
枚举一个子网格图的一个顶点，一边往下扫一边维护区域内的点数，统计答案。
时间复杂度：O(N^3)
对于 60%的数据：
我觉得这题可能有 N^2 的解法，但是我没想到。希望有想法的同学与我交流一下。
对于 100%的数据：
显然，题目可化简为：给定 N 个数的一个排列，问这个序列中有多少个子区间的数恰好是连续的。
进一步可以化为：有多少种情况使得，相邻的 k 个数中最大值和最小值的差小于等于 k-1。
大致有两种解法，一种是分治，一种是线段树。
这里主要讲一下分治的解法。
考虑分治，对于当前分治区间[L,R]，记区间中点为 mid。当前区间的答案就是Ans[L..mid]+Ans[mid+1..R]+跨过中点的合法区间数，然后就分为两种情况了：
1.最小值和最大值在同侧。
2.最小值和最大值在异侧。
下面只考虑最值同在左，和最小值在左，最大值在右的情况。其余两种是对称的。
对于最值同在左侧的情况，我们枚举左边界在哪，然后可以计算出右边界的位置，在判断是否合法，统计答案。时间复杂度：O(N).
对于最小值在左侧，最大值在右侧的情况，可以用单调栈+桶来完成这个任务。时间复杂度：O(N).
总的时间复杂度：O(NlogN)/O(NlogN^2)
简单提一下，线段树解法的思路大致也是维护一个单调栈，
然后进行区间修改和查询，统计答案。
时间复杂度：O(NlogN).

I. 大原题 (省选组 T3 Only)

• 测试点1~3：送分点，手玩。
• 测试点4：每种颜色的两个点分别出现在第1列和第m列，dp求带权最长上升子序列。
• 测试点5~6：有些颜色会出现在同一侧，加一个区间dp即可。
• 测试点7：每一圈有两种颜色，可以直接连起来。
• 测试点8：一些圈的两种颜色交替出现，但是上下两圈都是空的。
• 测试点9：每种颜色都可以直线连起来。
• 测试点10：把价值为0的颜色看做障碍，同上。

J. 思考题 (附加)

看不懂，可以参考 https://codeforces.com/blog/entry/62010?#comment-460369

30 分可以考虑直接暴力在自动机上跳，需要卡常

对不起~ 萌新选手第一次搬题, 出了好大的锅555

把题解搞过来了:

1

第 $x$ 条鱼的答案 =$\sum_{mx=1}^4\sum_{cx=1}^4w_{i,j}*p(x,mx,cx)$

其中 $p(x,mx,cx)$ 表示第 x 条鲳鱼被 第$cx$ 个神佬打死，且$cnt_{mx}>\lfloor \frac {n}{2} \rfloor$的概率

为了计算$p(x,mx,cx)$,我们需要定义一个$f(x,mx,cnt)$表示除了 x 以外的鱼中恰好有 $cnt$ 条鱼被第 $ mx $ 个神佬打死的概率

$p(x,mx,cx)$= $p_{x,cx}$*$\sum_{cnt=\lfloor \frac {n}{2} \rfloor}^nf(x,mx,cnt)$ $cx==mx$

​ $p_{x,cx}$*$\sum_{cnt=\lfloor \frac {n}{2} \rfloor+1}^nf(x,mx,cnt)$ $cx\not=mx$

下面考虑如何计算 $f(x,mx,cnt)$

​ 对于一个给定的 $ mx$ ，现在的问题相当于，第 $i$ 条鲳鱼有 $p_i $的概率被(第$mx$个神佬打死)，有 $1-p_i$ 的概率不被(第$mx$个神佬打死)，对 $x=1...n$，求除了第 $x$ 条鲳鱼以外恰好有 $cnt $ 条被神佬$mx$打死的概率。

​ 首先我们可以对每一条鱼做一遍dp

​ 枚举除了 $x$ 以外的每条鱼， $dp_{cnt}$ 表示当前集合(即所有已经枚举过的人)恰好杀 $cnt$ 条鱼的概率，假设新加进来的鱼有$p$的概率选，考虑如何更新$dp$数组

​ 令原来的数组为 $dp0$ ，加入这条鱼后的数组为 $dp'$ ，则

$dp'_{cnt}$= $p*dp0_{cnt-1}+(1-p)*dp0_{cnt}$ $cnt>=1$

​ $(1-p)*dp0_{cnt}$ $cnt==0$

​ 因为有 $p$ 的概率多杀了一条鱼，有$1-p$ 的概率不变。

​ 这样时间复杂度是 $O(n^3) $的，期望得分55。

​ 注意到我们不仅支持向集合中加入一条鱼后$O(n)$维护$dp$数组，还支持删除一条鱼后$O(n)$维护$dp$数组。

​ 也就是说，给定 $dp' $和$ p$ ，可以推 $dp0$ 。(注意p=1的情况需要特判)

$dp0_{cnt}$= $\frac {dp'_{cnt}}{1-p}$ $cnt==0$

​ $\frac {dp'_{cnt}-p*dp0_{cnt-1}}{1-p}$ $cnt>=1$

​ 所以先 $O(n^2)$ 求出全集的 $dp$ 数组，然后对每个 $x$ ，$O(n)$ 求出不含$ x$ 的 $dp$ 数组即可，期望得分100。

2

​ 对于一个神佬，$dp$ 求出 $pre_{i,j} $表示前 $i $ 条鱼恰杀 $j$ 条鱼的概率，$ suf_{i,j}$ 表示后 $i$ 条鱼恰杀 $j$ 条鱼的概率。 ​ 考虑求除第 $i$ 条鱼外杀 $>= j $ 条鱼的概率，只需对 $pre$ 求个后缀和，然后枚举即可，复杂度 $O(n^2)$

下面给出标程：

#include<bits/stdc++.h>
#define LL long long
#define clr(x,y) memset(x,y,sizeof(x))
#define FOR(x,l,r) for(int x=l,x##_=r;x<=x##_;x++)
#define FR(x,l,r) for(int x=l,x##_=r;x<x##_;x++)
#define DOR(x,r,l) for(int x=r,x##_=l;x>=x##_;x--)
using namespace std;
const int N=2005;
const int P=998244353;
int n,pos[N][4],A[4][4],dp[N][N],sum[N][N],ans[N];
inline void Add(int &x,int y) {
    x+=y;
    if(x>=P)x-=P;
}
int main() {
    freopen("revolution.in","r",stdin);
    freopen("revolution.out","w",stdout);
    scanf("%d",&n);
    FOR(i,1,n)FOR(j,0,3)scanf("%d",&pos[i][j]);
    FOR(i,0,3)FOR(j,0,3)scanf("%d",&A[i][j]);
    dp[0][0]=sum[n+1][0]=1;
    FOR(id,0,3) {
        FOR(i,1,n)FOR(j,0,i){
            dp[i][j]=(LL)dp[i-1][j]*(P+1-pos[i][id])%P;
            if(j)Add(dp[i][j],(LL)pos[i][id]*dp[i-1][j-1]%P);
        }
        DOR(i,n,1)FOR(j,0,n-i+1){
            sum[i][j]=(LL)sum[i+1][j]*(P+1-pos[i][id])%P;
            if(j)Add(sum[i][j],(LL)pos[i][id]*sum[i+1][j-1]%P);
        }
        FOR(i,1,n)DOR(j,n-i,0)Add(sum[i][j],sum[i][j+1]);
        FOR(i,1,n)FOR(j,0,i-1)FOR(k,0,3)Add(ans[i],(LL)dp[i-1][j]*pos[i][k]%P*A[id][k]%P*sum[i+1][max(0,n/2+1-j-(id==k))]%P);
    }
    FOR(i,1,n)printf("%d\n",ans[i]);
    return 0;
}