scmmm's blog

D. Monocarp and the Set 题目大意，给你一个表示排列元素的序列，包括 <?> , 其中 < 表示在之前是最小的 > 表示在之前是最大的，否则就是 ? ，有 mmm 次操作 ,每次可能修改下标的值，你这个表示序列的序列最多能表示多少种排列。 先不考虑修改，对于最初始的序列，第一个绝对不能是问号，然后从后往前看，如果不是问号就只能填一种东西，是问号可以填 x−2x-2x−2 (假设当前下标为 xxx ) 个数。以此可以统计答案。 修改也同理。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<bits/stdc++.h>#define int long longusing namespace std;const int maxn=300300;const int modp=998244353;int n, ...

前言 心血来潮，买了一张 3080 20G ，遂安装ubnutu。 以下东西不保证完整，想到啥写啥。 踩坑（过程）统计 * 软件安装类问题 * 显卡驱动安装 * 网络问题 * stable diffusion相关 * 稀奇古怪的问题 软件安装类问题 这部分踩坑如下： 安装慢 很显然是要换源。 sudo vi /etc/apt/sources.list 在里面设置 1234deb http://mirrors.aliyun.com/ubuntu/ jammy main restricted universe multiversedeb http://mirrors.aliyun.com/ubuntu/ jammy-security main restricted universe multiversedeb http://mirrors.aliyun.com/ubuntu/ jammy-updates main restricted universe multiversedeb http://mirrors.aliyun.com/ubu ...

过题数 排名 A B C D E F G H I J 4 258 B √ √ √ √ 123456|过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M||-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-|| | | | | | | | | | | | | | | |√ 赛时过了B 补题过了 A Tree 题目要求你改变一些点的黑白（可以不改变），按照颜色分为两个集合后，你需要最大化 ∑x∈V1∑y∈V2val(x,y)\sum_{x\in V_1}\limits \sum_{y \in V_2} \limits val(x,y)x∈V1​∑​y∈V2​∑​val(x,y) 最小， val(x,y)val(x,y)val(x,y) 表示两点之间路径中最大的边的边权。 这种题应该一开始就想到重构树，这样一条边的贡献就转化为了父节点到子节点之间，然后我们简单跑一个树形背包就可以了。 1234567891011121314151617181920212223242526272829303132333435363 ...

auto&decltype auto name=value 自动补全 name 的类型。 decltype(value2) name=value1 将 value2 的类型赋予 name 小尝试： 123456789101112#include<bits/stdc++.h>using namespace std;const int x=1;int main(){ decltype(x) a = 1; a++; cout<<typeid(a).name()<<endl;} 代码报错，可见赋值结果是 const int 但是auto把一个变量赋值为一个常量的值是可以的 1234567891011121314#include<bits/stdc++.h>using namespace std;const int x=1;int main(){ // decltype(x) a = 1; // a++; auto a=x; a++; cout<<ty ...

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 还没