uooogoo' blog

Blog

第十六轮非官方题解

2021-10-15 19:37:05 By uooogoo

出题人好像鸽了

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 分可以考虑直接暴力在自动机上跳,需要卡常

互测 Round 13 补充题解

2021-10-05 14:05:28 By uooogoo

对不起~ 萌新选手第一次搬题, 出了好大的锅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;
}
uooogoo Avatar