scmmm's blog

A. Dalton the Teacher 询问把一个排列变成 pi≠ip_i \neq ipi​=i 的最小操作次数。 直接记录 pi=ip_i = ipi​=i 的个数即可，然后除二向上取整。 B. Longest Divisors Interval 询问一个数最多能被多少个连续的数字整除 如果一个数能被 xxx 个连续的数字整除，那么根据鸽巢原理，一定可以被 1,2,3,4,...,x1,2,3,4,...,x1,2,3,4,...,x 整除。 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>#define int long longusing namespace std;const int maxn=100100;int T,n;signed main(){ ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; int ans=0,tans=0; for(in ...

过题数 排名 A B C D E F G H I J 4 544 √ √ B √ √ 123456|过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M||-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-|| | | | | | | | | | | | | | | |√ 赛时过了B 补题过了 E Red and Blue and Green 构造一个序列，满足区间 [l,r][l,r][l,r] 的逆序对数量为偶数或者奇数，所有区间要么是包含关系要么不相交。 显然这些区间满足了一个树状的结构，因此可以考虑优先处理小的区间在处理大的区间。 我们可以先设 ai=ia_i=iai​=i ，对于不包含区间的区间，如果要求逆序对为奇数，直接交换相邻的两个数即可。这样还不会影响到别的区间的答案。 如果包含区间的区间，假设 [l,r][l,r][l,r] 包含了 [l1,r1],[l2,r2],[l3,r3][l1,r1],[l2,r2],[l3,r3][l1,r1],[l2,r2],[l3,r3] 三个不相交的区间（他 ...

B. Fibonaccharsis 问你多少个满足 fi=fi−1+fi−2,i>2f_{i}=f_{i-1}+f_{i-2},i>2fi​=fi−1​+fi−2​,i>2 的数列满足 fk=nf_k=nfk​=n 考虑最简单的斐波那契，并且多一项前导0， kkk 最多不会超过40。 于是直接暴力即可。 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;const int maxn=550;int n,T,k,ans;void check(int a,int b){ int lk=0; if(a>b) return ; for(int i=1;i<=k-3;i++) { lk=b-a; b=a; a=lk; if(a>b||a<0) return ; } ans++;}int main(){ ios::syn ...

过题数 排名 A B C D E F G H I J K L M 4 635 √ B √ √ √ 123456|过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M||-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-|| | | | | | | | | | | | | | | |√ 赛时过了B 补题过了 B 有 2n2n2n 堆纸牌，每次抽到 i>ni>ni>n 就猜测下一张比这张小，否则下一张比这张大，询问在每种排列下一共能抽到多少张。第一张只用抓不用猜。 手推一下有个重要的性质，低于n只能猜大，大于只能猜小，因此我们一定可以分成很多个连续上升或者连续下降的序列。并且这些序列都是大于 nnn 或者小于等于 nnn 的。（不符合这个性质的一定在结尾或者开头，我们把它放在上一个序列依然是连续的。） 考虑 fi,j,0/1f_{i,j,0/1}fi,j,0/1​ 表示抓了 iii 张小于等于 nnn ，jjj 张大于 nnn 并且最后结尾是小于/大于的方案数。 然后统计对答案的贡献即可。 ...

编号 时间 博客写了吗？ 二分图博弈 20230722 还没

前言 过题数 排名 A B C D E F G H I J K L M 3 491 √ B √ √ B 123456|过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M||-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-|| | | | | | | | | | | | | | | |√ 赛时过了B 补题过了 A B C D E F G H 给你两个数组 a,ba,ba,b 只能交换一次或者0次 ai,aja_i,a_jai​,aj​，询问最小化 d=∑i−1n∣ai−bi∣d = \sum_{i-1}^{n}\limits|a_i-b_i|d=i−1∑n​∣ai​−bi​∣ 考虑把 ai,bia_i,b_iai​,bi​ 放在数轴上，就变成了一个区间覆盖的问题。我们定义 ai>bia_i>b_iai​>bi​ 是向左的区间，反之为向右的区间。这个时候，桐乡的区间 aaa 交换对答案不会有任何印象，但是反向的区间交换有影响，具体而言，如果 ai≤bj≤bi≤aja_i \leq b_ ...