题目链接 题意 给你n个数，每次取两个数，然后让其各减1，问能否用一种方式让所有数全部变为0。如果可以，则输出YES，否则输出NO。 思路 记n个数的和为SUM，如果SUM为奇数，显然推出不可能。 如果SUM是偶数，则需要判断n个数中最大的数的2倍与SUM的关系。 记n个数中最大的数为A，那么如果A2>SUM，那么不管怎么减都不可能达到最后全是0的效果。但是如果A2 <= SUM的话，我们就可以把n个数化成两堆，一堆有一个数A，另外一堆有一堆数，SUM-2*A（记为B）。      A   +   B   =   偶   数    A+B=偶数   A+B=偶数 推出      A...

题意 q次询问，每次询问给你一个整数，问该数的因数（非质数）的个数 思路 一开始想这个题目的时候，直接发现可以把一个数质因数分解     a   =  <munderover>  ∑    i   =   1    n  </munderover>    p   i     q   i      a=\sum_{i=1 }^n{p_i}^{q_i}   a=i=1∑n​pi​qi​，那么答案显然就是     a   n   s   =  <munderover>  ∏    i   =   1    n  </munderover>   (   ...

AC两题 A题就是一个模拟小数输出（水题） C题是一个数学题，简单分析发现与最大公约数有关。打的时候主要水平、垂直直线以及共点 ABD3题 A题：直接求和/个数，记住上取整 B题：用一个队列维护添加的元素。然后再用Map记录一下队列元素出现的次数 D题：线段树维护区间内26个字母出现的次数，然后查询答案用set维护。

题意 给你一个n*n的方正，每一个格子都一个值，问它的子矩阵的sum最大为多少 思路  其实就是枚举完上下边界之后转化成了一维求最大子段，而枚举最大子段可以使用dp优化。  AC代码 #include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; int a[105][105]; int prefix[105][105]; int sum[105][105]; int dp[105]; int main(){ int n, ...

题意 求给定的n个长方体，求这n个长方体覆盖的体积 思路 思路来源于求n条线段交集。我们可以把每一个长方体看成用三条线替换，从而我们就可以把n个长方体的三条线放到三个桶里面，然后在3个桶里面求出线段交集。答案就是3个交集长度的乘积。 那我们怎样求n个线段的交，很简单的。把n个线段的两个端点分成左右端点，然后加进两个桶，然后取两个桶的一个最大值，一个最小值。 AC代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; int x_max, x_min, y_max, y_min, z_max, z_...

AC代码 #include <bits/stdc++.h> using namespace std; const double eps = 1e-9; struct Point{ double x, y; }p[10]; bool compare1(double a, double b){ if(a > b && fabs(a - b) > eps) return true; if(fabs(a - b) <= eps) return true; return false; } bool compare2(double a, double b){ ...

题意 问从数列中取出尽可能多的数字使得这些数字成等差数列 思路 设     d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]表示以v[i]和v[j]相邻构成的最长数列长度。      d   p   [   i   ]   [   j   ]   =   m   a   x   (   d   p   [   i   ]   [   j   ]   ,   d   p   [   k   ]   [   i   ]   +   1   )   (   k   属   于   [   1   ,   i   −   1   ]   (   ...

题目链接  毒瘤题 又卡时间又卡空间 思路 显然有一个不考虑时限的做法。对于每次操作     [   l   ,   r   ]    [l,r]   [l,r]，我们都可以把区间     [   0   ,   n   −   1   ]    [0,n-1]   [0,n−1]中的下标     l   ,   r   +   1    l,r+1   l,r+1标记加一，然后扫一般前缀和就可以得到应有的答案。 但是显然这个做***T的，复杂度为     O   (   T   ∗   n   )    O(T*n)   O(T∗n) 我们观察发现，对于     0   −   （   n ...

A. Paint the Numbers  思路 把序列的数从小到大排序，然后从枚举第一个数为A颜色，然后贪心地取后面的数。取过的数标记取过了，后面就不需要以这个数枚举 复杂度:     O   (    n   2    )    O(n^2)   O(n2) 代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; int a[105]; bool vis[105]; int main(){ int n, ans = 0; scanf("%d", &n); for(i...

参考博客  AC代码（模板） #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 4e5 + 10; char s[maxn], tmp[maxn]; int dp[maxn]; char change(char x, char a){ return (x - a + 26) % 26 + 'a'; } ///转化方式思想来自对一个圈的点标号（知道取模之后就可以自己推一...

思路  AC代码 #include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 998244353; ll quick_mod(ll a, ll b){ ll sum = 1; while(b){ if(b & 1) sum = sum * a % mod; a = a * a % mod; b /= 2; } return sum; } int main(){ int t; scanf("%d", ...

思路 这道题思路很简单，也就是直接把所有直线表示成点斜式（如果斜率不存在，另外判断） 但是有一个小技巧不注意的话，就会T 两个分数比较大小的时候，可以先预处理分母，全部变为正数，然后直接分母交叉相乘      a   /   b   与   c   /   d   比   较   大   小   的   时   候   ，   先   把   分   母   全   部   化   成   正   数   ，   然   后   直   接   判   断   a   d   与   b   c   的   大   小    a/b与c/d比较大小的时候，先把分母全部化成正数，然后直接判断ad...

链接      引   理   2   的   证   明    引理2的证明   引理2的证明      就   是   p   =   a   x   ,   假   定   g   c   d   (   p   ,   m   )   >   1   ，   那   么   p   模   m   =   r   ,   g   c   d   (   r   ,   m   )   >   1   移   项   可   得   a   x   −   m   k   =   r   根   据   裴   蜀   定   理   a   x   −   ...

Bomb   思路      d   p   [   p   o   s   ]   [   s   t   a   ]   表   示   表   示   第   p   o   s   +   1   位   （   高   位   ）   是   4   （   不   是   4   ）   的   个   数   且   第   p   o   s   +   1   位   没   有   达   到   l   i   m   i   t    dp[pos][sta]表示表示第 pos + 1 位（高位）是4（不是4）的个数且第pos+1位没有达到limit   dp[pos]...