搜索结果
查询Tags标签： maxn，共有 417条记录-
「解题报告」[AGC022F] Checkers
题目大意 设 \(x=10^{100}\)，在数轴上有 \(n\) 个点，第 \(i\) 个点的坐标为 \(x^i\)，每次可以将一个点 \(A\) 变为关于点 \(B\) 的对称点，并把 \(B\) 删除，进行 \(n-1\) 次这样的操作，问最后能得到多少种不同的坐标。 \(n \le 50\)去看了官方的题解，这里给出官方的…
2022/9/10 23:25:05 人评论 次浏览 -
AcCoders 7961 Problem D：【省选基础数据结构 树状数组】树状数组 题解
树状数组板子，单点修改，区间查询，注意处理读入字符的问题。 //7961 Problem D：【省选基础数据结构 树状数组】树状数组 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=100005; ll c[MAXN],a[MAXN],n; #define lowbit(x)…
2022/9/10 23:23:31 人评论 次浏览 -
[ARC125F] Tree Degree Subset Sum
题目传送门 Solution 首先这个树的限制几乎没用，我们可以先把每个点度数 \(-1\)，然后总的度数就是 \(n-2\) ，设 \(z\) 为度数为 \(0\) 的点的个数。 可以看出，这个问题的麻烦之处就在于对于一个度数和还要求出有多少个满足的大小，而这个似乎只能 \(\Theta(n^2\log n)…
2022/9/8 23:53:09 人评论 次浏览 -
洛谷 P1123 取数游戏（dfs）
https://www.luogu.com.cn/problem/P1123 题目大意：给定一个n*m的矩阵，问我们从里面怎样取能取到最大的总和？条件是选了一个数，下次它的八个方向上的数字就不能选了输入 #1复制 3 4 4 67 75 63 10 29 29 92 14 21 68 71 56 8 67 91 25 2 3 87 70 85 10 3 17 3 3 1 1 1…
2022/9/7 23:26:42 人评论 次浏览 -
多项式全（?）家桶
贴个板子，以备复习点击查看代码 #include<cstdio> #include<cstdlib> #include<algorithm> #include<unordered_map> #include<cmath> #define mod 998244353 #define maxn 400010 #define ll long long #define it unordered_map<ll,i…
2022/9/7 23:25:17 人评论 次浏览 -
[Editorial] Codeforces Contest 1726
A. Mainak and Array 显然如果 \([l,r]\) 不包括两端那么就不会对答案有影响，那么直接枚举包括两端的情况即可。 /* author : Gemini date : September 6th, 2022 url : https://codeforces.com/contests/1726/A */ #include<bits/stdc++.h> using namespace std;…
2022/9/7 6:23:06 人评论 次浏览 -
[kuangbin带你飞]专题三 Dancing Links
Dancing Links 是一种数据结构，用于精确覆盖。详情去下面链接学；感谢大牛总结。 学习资料： http://www.cnblogs.com/grenet/p/3145800.html http://blog.csdn.net/mu399/article/details/7627862 F - SudokuPOJ - 3074 题意：就是给你一个随机的九宫格，问你答案是多…
2022/9/7 6:22:48 人评论 次浏览 -
可持久化线段树
现想现写的，没有借鉴别人的任何东西。 可持久化线段树1 考虑不会变得太多，每次该值操作只会改变一个位置的值，其它位置是可以继承的。如果用数组，那就是下标继承。如果把数组分成 \(2\) 半，那改一个值，就一半继承，另一半重新赋值。而用线段树，就可以做到区间继承 …
2022/9/6 23:24:12 人评论 次浏览 -
Rock and Lever
题意： 找出数列中满足，ai & aj >= ai ^ aj 的 (i,j)的数量，i<j 由样例发现，当ai 与 aj 的最高位一样时，不等式就成立 故，记录数的最高位的数目，假设一个最高位的数目为x，则能选,C(n,2)种 得到一个数的二进制的最高位，不断右移即可。 处理组合数即可。又…
2022/9/5 23:25:30 人评论 次浏览 -
最短路算法之 Dijkstra
部分内容参考了李煜东的《算法竞赛进阶指南》，在此声明。单源最短路径 单源最短路径问题，是说，给定一张有向图（无向图）\(G=(V,E)\) ,\(V\) 是点集，\(E\) 是边集，\(|V|=n\)，\(|E|=m\)，节点是 \([1,n]\) 之间的连续整数，\((x,y,z)\) 描述一条从 \(x\) 到 \(y\) 边…
2022/9/4 1:22:46 人评论 次浏览 -
CF375E Red and Black Tree
题目传送门 Solution 非常神奇的一道题。 我们不考虑交换操作，相反，我们去考虑把多少个 \(0\) 的位置变为 \(1\)，同时我们记录选了多少个黑点，如果跟原来黑点数量相同即是合法。 此时我们可以发现一个神奇的性质对于 \(u\) 的儿子 \(v\)，如果覆盖 \(u\) 的节点不覆盖…
2022/8/31 23:26:17 人评论 次浏览 -
gym-101667E How Many to Be Happy
How Many to Be Happy? 最小割 因为是最小生成树，因此可以考虑对于一条边来说，他的左右两端的点视为处于两个不同的集合，然后只通过该边进行连接，这样最小生成树就必然会利用这条边 比该边大的边显然不用考虑，就考虑比该边边权小的边，然后进行最小割，边流量为 \(1…
2022/8/30 23:24:15 人评论 次浏览 -
多重背包问题 II
多重背包问题 II(水题但有注意点) 二进制优化的多重背包问题（主要注意的是二进制优化后的数组的大小问题） AC代码 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxn=2010;…
2022/8/29 6:52:57 人评论 次浏览 -
CF1720D2 题解
前言 题目传送门！ 更好的阅读体验？ 感觉 D1 和 D2 不是同一个难度档次的呀...... 思路 设 \(a_j\oplus i < a_i \oplus j\)，这意味着数字 \(a_j\oplus i\) 中，从个位起前 \(k\) 位和 \(a_i \oplus j\) 相同，之后第 \(k+1\) 位就不同了。 两个不同下标的数有点难处…
2022/8/27 23:22:53 人评论 次浏览 -
CodeForces-505D Mr. Kitayuta's Technology
Mr. Kitayutas Technology tarjan + 思维 先缩点，然后考虑如何建边 如果其中一个 \(DAG\) 图中出现一个缩点后大小大于 \(2\) 的连通块（环），则考虑直接将这个 \(DAG\) 图变成一个环，代价显然都是相同的，即点的数量 因此延伸，考虑多个缩点前都有环的 \(DAG\) 图，我…
2022/8/25 6:24:16 人评论 次浏览
