爱飞鱼的blog

title: xiaosaitmp categories: ICPC tags: null abbrlink: 2b0f3b8d date: 2024-09-03 00:00:00 题面翻译 给你一个NNN个节点的树，求一个1⋯N1\cdots N1⋯N的排列(p1,p2,⋯pN)(p_1,p_2,\cdots p_N)(p1​,p2​,⋯pN​) ，使得∑dist(i,pi)\sum dist(i,p_i)∑dist(i,pi​)最大。 求这样的排列的个数。答案对109+710^9+7109+7取模。 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <cmath> using namespace std; typedef long long ll; typedef pair<int,int>ttfa; inline ll read(){ ll...

title: 2023牛客周赛 Round 6 categories: ICPC tags: null abbrlink: 3e350e36 date: 2024-09-02 00:00:00 https://ac.nowcoder.com/acm/contest/62622/C c题 从x!作为切入点，阶乘增长的非常快，我们可以枚举x，从而达到固定x，只剩y一个变量，问题转变为一次函数绝对值求最小值的数学问题，显然可以o（1）。 13!=6227020800=6.2270208×10913!=6227020800 =6.2270208 × 10^9 13!=6227020800=6.2270208×109 12!=479001600=4.790016×10812!=479001600=4.790016 × 10^8 12!=479001600=4.790016×108 对于13的阶乘不超过int...

title: 二叉树扩展先序遍历转中序遍历 categories: ICPC tags: null abbrlink: 1ff53043 date: 2024-09-01 00:00:00 利用前序遍历的特性，如果左子树不空，下一个一定是左节点，不然就是# 因为是转中序遍历，就在两次遍历之间输出 #include <iostream> #include <cstring> #include <algorithm> using namespace std; int k; string str; void dfs() { if (str[k] == '#') { k ++ ; return; } char r = str[k ++ ]; // 根节点 dfs(); // 左子树 cout << r << ' '; dfs(); // 右子树 } int...

title: 牛客周赛 Round 29 categories: ICPC tags: null abbrlink: 81d72b45 date: 2024-08-31 00:00:00 C题：用桶处理字符串重排 小红拿到了一个字符串，其中一定包含连续子串"xiao"，和连续子串"hong"。 请你将字符串重排，使得该字符串包含"xiaohong"的连续子串。 较简单的做法：遍历字符串，给每个字符放到相应的桶中，然后先先输出目标字符串xiaohong，同时对桶进行相对应的调整。最后再按任意顺序输出桶中字符。 赛时我的复杂做法：先找到xiaohong的每个字符在给出字符串的位置，由于重复也需要桶，对于位置标记，最后输出时跳过这些位置。 D题：中位数理解加深，可删除对顶堆杀鸡用牛刀 不动脑子：直接使用可删除对顶堆： double ans[N]; int a[N]; class MedianFinder { priority_queue<int,...

title: 三元环计数 categories: ICPC tags: null abbrlink: b54d6990 date: 2024-08-30 00:00:00 三元环计数 无向图三元数计数：G - Triangle 给一个邻接矩阵表示无向边关系，求有多少个三元环？ Solution：考虑直接使用bitset优化，枚举两个点，对两个点的边表与起来，找到共同能到达的点。 时间复杂度：O(nm/w)O(nm/w)O(nm/w)(只有两个点有才会进入bitset两个序列相与) debug: 1.首先注意到对于这样的连续的不能一个一个读，不然会出问题 考虑一个三元环按我们枚举的偏序关系，总共会计算三次，所以最后要除3 bitset<3001>b[3001]; void solve(){ cin>>n; for(int i=1;i<=n;i++){ string s;cin>>s; for(int j=0;j<n;j++){ int...

title: 二维和一维坐标相互转换 categories: ICPC tags: null abbrlink: 78fd8a54 date: 2024-08-20 00:00:00 int id(int x,int y,int m){ //m列 return m*(x-1)+y; } pii rid(int u,int m){ int x=(u+m-1)/m;//m列 int y=u%m;if(y==0)y+=m; return make_pair(x,y); }

title: 20230723牛客round4D题：给出一个大数的所有约数，通过dfs用质因子反向构造约数 categories: ICPC tags: null abbrlink: a4a5fc65 date: 2024-08-18 00:00:00 两个正整数a，b，请问a∗b有哪些因子 #1≤a,b≤1e9 求因子的数量并给出所有因子 本题无脑的暴力显然不能过，但用set存数，加上考虑到a*b的所有约数其实就是a的所有约数和b的所有约数分别相乘(核心） 补充常识：int范围内数的约数个数最多为1600，2e9数的约数个数最多为1536，这也是本题能这样暴力的基础 https://blog.csdn.net/qq_40438165/article/details/122030763 #include <bits/stdc++.h> using namespace std; # define int long long const int N = 1e5 + 10; const int M = 2e5 + 10; const int inf...

title: 一些常用到的有用知识 categories: ICPC tags: null abbrlink: fb088f6a date: 2024-08-18 00:00:00 log(2,1000000)=19.931568569324174087221916576936341055188988358147483672328538374… 1MB = 1024KB 1KB = 1024B 1B(byte,字节)=8b(bit,比特). 1e6(1000000)(一百万）里有78498个质数

title: 启发式分治 categories: ICPC tags: null abbrlink: 84aa39e5 date: 2024-08-17 00:00:00 启发式分治 Non-boring sequences - UVALive 6258 - Virtual Judge (vjudge.net) 启发式分治-CSDN博客 [学习笔记]启发式分治 - house_cat - 博客园 (cnblogs.com)

title: Codeforces Round 892 (Div. 2) categories: ICPC tags: null abbrlink: a38ff4fe date: 2024-08-09 00:00:00 c题jls的代码，拿过来仔细研究了一番，终于弄明白了。 https://codeforces.com/contest/1859/problem/C jls代码 #include <bits/stdc++.h> using i64 = long long; struct DSU { std::vector<int> f, siz; DSU() {} DSU(int n) { init(n); } void init(int n) { f.resize(n); std::iota(f.begin(), f.end(), 0); ...