xiaosaitmp
title: xiaosaitmpcategories: - ICPCtags: - nullabbrlink: 2b0f3b8ddate: 2024-09-03 00:00:00题面翻译给你一个$N$个节点的树，求一个$1\cdots N$的排列$(p_1,p_2,\cdots p_N)$ ，使得$\sum dist(i,p_i)$最大。 求这样的排列的个数。答案对$10^9+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 x=0,f=1;char...
2023牛客周赛 Round 6
title: 2023牛客周赛 Round 6categories: - ICPCtags: - nullabbrlink: 3e350e36date: 2024-09-02 00:00:00https://ac.nowcoder.com/acm/contest/62622/C c题从x!作为切入点，阶乘增长的非常快，我们可以枚举x，从而达到固定x，只剩y一个变量，问题转变为一次函数绝对值求最小值的数学问题，显然可以o（1）。$$13!=6227020800 =6.2270208 × 10^9 $$ $$12!=479001600=4.790016 × 10^8 $$对于13的阶乘不超过int...
二叉树扩展先序遍历转中序遍历
title: 二叉树扩展先序遍历转中序遍历categories: - ICPCtags: - nullabbrlink: 1ff53043date: 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(); //...
牛客周赛 Round 29
title: 牛客周赛 Round 29categories: - ICPCtags: - nullabbrlink: 81d72b45date: 2024-08-31 00:00:00C题：用桶处理字符串重排小红拿到了一个字符串，其中一定包含连续子串”xiao”，和连续子串”hong”。请你将字符串重排，使得该字符串包含”xiaohong”的连续子串。 较简单的做法：遍历字符串，给每个字符放到相应的桶中，然后先先输出目标字符串xiaohong，同时对桶进行相对应的调整。最后再按任意顺序输出桶中字符。 赛时我的复杂做法：先找到xiaohong的每个字符在给出字符串的位置，由于重复也需要桶，对于位置标记，最后输出时跳过这些位置。 D题：中位数理解加深，可删除对顶堆杀鸡用牛刀 不动脑子：直接使用可删除对顶堆： double ans[N]; int a[N]; class MedianFinder { priority_queue<int, vector<int>, greater<int>> minheap; ...
三元环计数
title: 三元环计数categories: - ICPCtags: - nullabbrlink: b54d6990date: 2024-08-30 00:00:00三元环计数无向图三元数计数：G - Triangle 给一个邻接矩阵表示无向边关系，求有多少个三元环？ Solution：考虑直接使用bitset优化，枚举两个点，对两个点的边表与起来，找到共同能到达的点。时间复杂度：$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: - ICPCtags: - nullabbrlink: 78fd8a54date: 2024-08-20 00:00:00int 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); }
20230723牛客round4D题：给出一个大数的所有约数，通过dfs用质因子反向构造约数
title: 20230723牛客round4D题：给出一个大数的所有约数，通过dfs用质因子反向构造约数categories: - ICPCtags: - nullabbrlink: a4a5fc65date: 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: - ICPCtags: - nullabbrlink: fb088f6adate: 2024-08-18 00:00:00 log(2,1000000)=19.931568569324174087221916576936341055188988358147483672328538374… 1MB = 1024KB 1KB = 1024B 1B(byte,字节)=8b(bit,比特). 1e6(1000000)(一百万）里有78498个质数
启发式分治
title: 启发式分治categories: - ICPCtags: - nullabbrlink: 84aa39e5date: 2024-08-17 00:00:00启发式分治Non-boring sequences - UVALive 6258 - Virtual Judge (vjudge.net) 启发式分治-CSDN博客 [学习笔记]启发式分治 - house_cat - 博客园 (cnblogs.com)
Codeforces Round 892 (Div. 2)
title: Codeforces Round 892 (Div. 2)categories: - ICPCtags: - nullabbrlink: a38ff4fedate: 2024-08-09 00:00:00c题jls的代码，拿过来仔细研究了一番，终于弄明白了。https://codeforces.com/contest/1859/problem/Cjls代码 #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); siz.assign(n,...