题意：给一些石子，多次询问，问能不能测出所给重量思路：①考虑把重量放在单独一边，石子放在单独一边。这样就是一个01背包。②实际上重量那边也可以放石子，那么其实就是从①中的01背包中可以达到的状态，减去放在另一边的石子堆所以这里也是一个类似01背包的过程，枚举石子，然后枚举重量，要注意第二维循环按照从小到大的。否则按照从大到小的话，就是一堆石子会被放多次。 #include<bits/stdc++.h> using namespace std; const int N=1e4+50; int a[N]; bool dp[N]; int main(){ int n;while(cin&...

题意：给出a、b、c、d、x、y，让求下列式子。思路：对于gcd(x,y)我们知道gcd(x,y)=p1 ^(min(n1,n2)) * p2 ^(min(n1,n2))....pk ^(min(n1,n2))p1、p2....pk是x和y的质因子，n1代表x中该质因子的个数，n2代表y中该质因子的个数 那么对于gcd(x,y)而言，因为这个式子是累乘的，所以gcd=1的就无需考虑。所以我们去枚举x的质因子p，然后取看y中是不是也有该质因子p如果y中没有，显然贡献也是1 乘起来没有影响。 假设x中质因子p的个数为n1，y中质因子p的个数为n2。我们只需要算出来上面式子中，gcd里p的累加个数k...

题意：给一个n * m的矩阵，其中a[i][j]=lcm(i,j) (lcm指最小公倍数)。再给一个k，求n * m的矩阵中，所有k阶矩阵中最大值之和。 思路：二维滑动窗口。我们用ma[i][j]来表示第i行中，从第j-k+1个数 到 第j个数的最大值。即一个区间长度为k的最大值。先处理好每一行中的每一个长度为k的子区间的最大值。这样的话，我们就把一个k * k的矩阵的最大值，现在把每行的最大值求出来了。把一个k * k矩阵每行的最大值放在了这个矩阵中每行的第k个位置。这样的话，我们只需要对每一列在进行一次单调队列即可。 比如样例的矩阵是：1 2 3 42 2 6 43 6 3 12 对应的m...

题意：给出1-n的数字，让选择m对数字，让gcd(a_i,b_i)>1，让m尽可能大，并且输出这m对对应的数字。 思路：整体的思路就是筛法+贪心。不过我代码写的比较复杂，比较low。。首先就是筛法，把n个数的质因子种类数，和最小质因数维护出来。cnt[i]表示i的质因子有多少种，mi[i]表示i的最小质因数是多少开一个vector 其中z[i]表示含有质因子i的数字的集合。然后我们去进行两个数字的匹配，这里去贪心的选择。首先我们应该倒序 即从z[n]到z[1]里面去选择。为什么？ 因为含有的质因子越大，可以匹配到的另一个的个数越少，所以优先倒序来。对于具体到某个z[i] 这里还需要一次贪...

题意：给了n个点，让你自己随便定义圆心(圆心不要求是n个点的其中一个)和半径，要求这n个点有尽可能多的点在圆上，并且该圆经过坐标原点(0,0)。求满足的圆上的点最多有多少个。 思路：n是2e3，复杂度应该要小于n^3。我们知道最少三点可以确定一个圆。因为圆要求经过原点(0,0)，所以考虑n^2枚举两个点，这样子就有三个点了，计算出三个点形成的圆的圆心坐标(注意三点共线的情况 那么肯定不存在圆 使得三点在一个圆上)用vector保存下来这些圆心坐标。处理完后，对圆心坐标sort一下，判断有多少个圆心坐标是一样的。 刚开始写的是map<pair<double,double>,in...

题意：求所有子区间的逆序数对的个数。思路：考虑贡献。假设存在逆序数对(a[i],a[j] (i<j)那么含有a[i]的区间的左边界L<=i,含有a[j]的区间的右边界R>=j。也就是逆序数对贡献的个数为i*(n-j+1)。我们可以枚举j，统计在j前面，有多少个数比a[j]大，计算他们的下标之和。(满足a[i]>a[j] && i<j i的值就是左边界可以选取的个数)他们能选取的右边界的个数就是n-i+1。对于求前面比a[j]大的数的下标之和，可以用树状数组来统计。只关注数的相对大小，不在乎具体值，注意离散化。注意答案炸LL #include<...

线性DPdp[i][j]表示前i张彩票中奖j元的方案数那么易得转移方程dp[i][j] += dp[i-1][j-k] 其中1≤k≤4 k≤j边界为dp[0][0]买n张彩票，每张彩票有四种情况，总的方案数就是sum=4^n所以计算出来ans=sum(dp[n][k]) 其中k>=3n答案就是ans/sum注意约分即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[35][150];///对于前i张中奖j元的方案数 int main(){ ll n;cin>>n;...

B-签到题题意n个数，生成一个长度为n的排列，并且有n-1种数，问有多少种方案。 思路：n个数，选择n-1种，也就是有1个数字不选，那么有n种方案。对于每种方案，要从n-1个数里面，选择一个重复的数字，有n-1种方案。此时对于每种方案，长度都是为n的序列，考虑多重集合的全排列方案数。因为只有一个数是出现了两次，所以方案数是n!/2所以答案就是即  刚开始wa了一发，计算的结果是n*(n-1),考虑成了组合，而没有考虑长度为n的序列的不同排列也算不同方案。 #include<bits/stdc++.h> using namespace std; typedef long long l...

D-ar采蘑菇题意：起点在(0,0),目标在(n,m),指定k种行走方案。问走到终点最多能使用多少种方案。 思路：范围很小，可以搜索也可以状压dp。只用了状压的做法。dp[i][j][k] 表示走到i，j，可以用q种行走方式走到(k是这q种行走方式的二进制串)枚举每一点的每一种状态，考虑从前面哪个状态转移过来即可，注意当前到达该点的行走方式可能前面用过也可能还没用过。 坑点:这是笛卡尔坐标系，起点在左下角，即R是向右走，应该是x++。而不是正常碰到起点在左上角，右走是y++， #include<bits/stdc++.h> using namespace std; int dx[1...

题意：求1~n中每个数的最小质因数的和。 思路：素数筛即可，把每个数的第一个质因数加到答案当中。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int a[30000005]; int main() { ll n;cin>>n; ll sum=0; for(ll i=2; i<=n; i++){ if(!a[i]){ sum+=i; for(ll j=i*i; j<=n; j+=i){ if(!a[j]) a[j]=1,sum+=i; } } } cout<<...

题意有一个n*m的地图，地图上有三个国家和一些道路(路没修就不能走)，还有一些障碍，每个国家都是一个联通块，现在可以在道路上进行修路，让路可以走，现在问让三个国家联通最小需要修多少条路。 思路对于每个国家都进行bfs，算出每个国家到每个点的最短距离。三个国家联通，枚举联通的一点即可。所以枚举所有不是障碍的点，更新最小值，注意如果枚举的点是道路而不是国家的话，只需要有一个国家修路即可，所以要减去2.bfs中，如果达到的坐标是"."，那么修路的就需要加1，保证bfs的最优性，如果是点，就把更新的坐标放到最后，如果是国家，不需要修路，花费保持不变，就丢到队列前，所以用一个双端队列实现。 #inclu...

F题数据弱了，存在精度问题，部分ac代码是可以被卡掉的。详情请见帖子的四五楼,感谢大佬指正。 F数据已更新，欢迎大佬ac。 正确的std已更新在帖子内容最下方。  出题人认为难度大概是这样的(相对于这10题而言):  签到：B、G简单：E、I、J中等：A、C、D较难：F、H A、牛牛爱学习答案显然具有单调性，所以考虑二分答案。对于每次二分check，我们把每本书的知识值从大到小排序后，按顺序把每本书安排到每一天即可，  B、牛牛爱数学签到。把右边式子移到左边，化简后是个完全平方式。所以如果a能够整除bc答案就是否则就输出-1看成一元二次方程求解也可以，不过注意过程中会炸LL  C、牛牛种花考虑...

考虑以过期时间升序排序。维护一个价值的小根堆。每次都将商品丢入到堆里面，判断当前堆中的个数是不是大于过期时间，是的话，弹出堆顶(价值最小的)。这样最后堆中剩余的就是规定天数内能获得的最大收益 #include<bits/stdc++.h> using namespace std; typedef long long ll; struct node { ll t,w; }a[100005]; bool cmp(node a,node b){ return a.t<b.t; } int main() { int n; while(cin>>n){ for(int i=...

双指针(尺取法) 双指针(快慢指针)即可。右指针先走，一直到满足条件后，维护一下长度的最小值，然后左指针开始右移，直到不满足子串含有所有小写字母，右指针继续右移动。 总的复杂度来说，右指针右移动n次，左指针右移也是n次。复杂度是On #include<bits/stdc++.h> using namespace std; char s[1000005]; int vis[130]; int main(){ cin>>s+1; int sum=26,now=0; int l=1,r=0,mi=1e9,len=strlen(s+1); while(l<=len){ w...