模板1题目 Code: #include<iostream> #include<string> #include<memory.h> typedef long long ll; #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) //#define int long long using namespace std; ll a, b, x, y, ans; struct node { ll l, r, w, f; }tree[500005*4]; inline v...

题目 思路：模拟几个数会发现让绝对值大的距离相匹配花费相对小,所以将所有钻石矿的绝对值和矿工的绝对值分别存入两个数组，排序，两者都按从小到大计算距离相加即可。 Code: #include<iostream> #include<algorithm> #include<iomanip> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll xx[Max], yy[Max]; int main() { int t;cin >> t; while...

题目 对于n个元素的gcd，将每个元素质因数分解，对于一个质数如果每个元素都有其作为因数，那么这个质数p对答案的贡献为p^(所有元素分成质因数相乘中p的最小次方） a1=p1^b1 …* pi^c1* … pm^d1 a2=p1^b2 … * pi^c2 *… pm^d2 … an=pn ^ bn…*pi ^ cn … pm^dn 如质数pi，其对答案贡献为 pi^(min(c1,c2,c3…,cn))，将质因数的贡献相乘即为最终答案。 如果某个质因数不是n个元素都有，那么其没有产生贡献。所以我们需要做的就是将每个元素或相乘数质因数分解，并且还要记录第i个元素各种质因数的次方数，和每个值...

塔 你在最后那场博弈中败下阵来，却意外穿越到了海拉尔大陆！是你吗林克？ 初来到海拉尔大陆的你，有些许的局促，但当你看到塔，或许一切的一切都迎刃而解。 一个层高为n的字母塔的定义为： 共n行，由字母组成的等腰三角形。 塔顶为第一层，且只有一个大写字母A；下面每一层都比上面一层多两个字母。 每一层都是左右对称。 对于第i层，前i个字母由大写字母表中A~第i个字母顺序组成。 为了稳住局面，样例给出了层高为5的字母塔，请你输出层高26的字母塔。 #include <stdio.h> /*********************************** 观察题目样例给出的高...

题目 思路： 先手必输的情况： 1.有两个以上两堆石子数目相同。 2.有3堆以上石子数目相等、有两堆0石子。 3.有一个两堆数目(k)相同的石子，且有一堆数目为k-1的石子。 除掉上面的情况后，将石子从小到大排个序，大家都不想输，贪心之下把小的先减完可以保证过程中不会出现两堆石子数目相等的情况,所以对排序后的第i堆石子可以减到i-1个，也就是说总共可以执行p=sum(全部石子数)-((n-1)*n)/2次操作，p%2==0 cslnb 反之另一个nb #include<iostream> #include<map> #include<algorithm&gt...

题目 思路：以每一个位置作为右端点取其前面为0区间的左端点的最大值为左端点，这一个字串就是以该位置为右端点，满足条件的最大长度的子串，它产生的贡献是(r-lmax-1,为了不把左端包含进去，包含进去就有为0的区间了),所有贡献相加即为答案。 而对于如何判断一个区间是否为0，以及这个最大左端点的记录。我们可以使用前缀和来纪录某区间是否为0，sum[i]=sum[j] 那从i+1…j的元素的和为0，我们用map来记录，每次添加进一个新的和，如果前面已经出现了该值，则代表从前一个位置+1到此区间和为0，然后对于取得最大左区间位置，也用map来记录，得到一个新值k时，用map[k]=其位置i,就顺...

题目 抽屉原理 看题目的数据，其中可以发现两个数相加结果最大也只是5e6，根据抽屉原理，只要有5e6+1个数就至少会有两个数相加得到相同的值。那么也就是说只要枚举出来的两个数相加的答案最多有5e6+1个就一定会得到至少两组坐标满足相加相等，直接暴力即可。 #include<iostream> using namespace std; typedef long long ll; const int Max = 5e6 + 5; int lst[Max]; int ls[Max][2]; int main() { int n;cin >> n; for (...

题目 思路：经过模拟可以发现对于一个元素的移动每次移动量是之前一次的两倍，如果将列表倒过来从0开始，那么每次元素的位置移动便是x=2x+1，现在给出了最后的某个位置，那么我们只需逆转x=(x-1)/2直到位置为偶数就是开始移动的位置，因为列表倒置后所有元素位置会变为偶数，而每次进行x=2x+1又会变成奇数，所以逆移动到了偶数即是开始的位置。 Code: #include<iostream> #include<vector> using namespace std; typedef long long ll; const int Max = 5e6 + 5; vec...

题目 思路：首先贪心的想一想，我让每一段尽可能长，则最后的段数就可能越少。 再来看什么时候一个数是平方数，将一个数质因数分解 X=a^x1 * b^x2 * c^x3… 只要让一个数的x1 x2 x3…xn都为偶数即可 那我们只需发现如果有相乘的两个数各自的质因数次方相加全为偶数则会组成一个平方数，就需要切出一段来。但这个记录各自质因数再让每个相加又太麻烦，所以就想出了一个简便的记录方法，只要记录质因数次数为奇数的所有质因数乘积（把为偶数的部分扔掉，偶数部分不会影响判断），如果发现有两个这种乘积相等，则此段出现质因数，细节见代码。 Code: #include<iostream&...

题目 思路：先来考虑k=3的情况，如果n为奇数则三个数分别为 1 n/2 n/2，这样最大是n/2。如果n为偶数，如果n%4==0，则 三个数为 n/4 n/4 n/2，反之 先将n=n/2 则又变为了奇数的情况 三个数为 21 2(n/2) 2*(n/2) 对于hard情况，可以发现如果k越大其实越容易满足每个数<=n/2，那么对于k-3个数 全部填1 剩下的三个按照easy的思路来。 Code: #include<iostream> #include<vector> #include<map> using namespace std; ty...

题目 思路：想要出现否的情况那一定会有0在1的后面，而我们的删除操作只能隔着删，所以当出现两个00或两个11必然会留下一个，所以从后往前遍历，如果发现出现00之后又出现11则最终无论怎么删都会留下一个…1…0…的情况。 #include<iostream> #include<cmath> #include<map> typedef long long ll; using namespace std; const int Max = 1e6 + 5; ll ji[Max], o[Max], sum[Max]; int main() { int ...

题目 思路：贪心的想如果要使花费尽量小，那就让第一第二小的线段一个向上一个向右尽可能长，只需枚举即可。但是由于有一个每次需要转弯的限制，所以需要分为奇偶，分别记录奇偶前面最小的cost，让奇数的线段向上，偶数的线段向右，先将其余线段长度全部取为1，然后让剩下的长度分别由向上和向右的最小cost线段走完即可，细节见代码。 Code: #include<iostream> #include<cmath> #include<map> typedef long long ll; using namespace std; const int Max = 1e6 ...

题目 思路：从逆向想一下，发现最后得到的一定是最后的字符串f，然后往前推，因为只能改变<len/2的元素，不难发现改变已经定下来了，即只能全改为数量大的那个字符，如果长度为偶数两种字符相等则不能达成。维护和查找用线段树覆盖。 down的一个修改 Code: #include<iostream> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) typedef long long ll; using namespace std; struct node { ll l, r, f, ...

题目 思路：首先为NO的情况只有，某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况，其它情况不可能为NO，看一个极端的例子，总共有8天，有两个朋友1和2，有4天全是只可以选1，其它4天都是可以选1或2。那么只要让其它的天数全选2即可，2也不会超出⌈m2⌉次。 然后来看YES的情况该怎么选，首先对于只可以选一个人的天数先加在每个人的被选天数上，然后从第一天开始，遍历那一天的所有人，选出目前备选天数最低的那个人，其备选天数+1，如果遇到只有1个人可以选的直接跳过（已经预先处理了这种情况）。 Code: #include<iostream> #...