#include<bits/stdc++.h> using namespace std; const int N=110; #define pdd pair<double,double> pdd q[N]; int n; double rand(double l,double r) { return (double)rand()/RAND_MAX*(r-l)+l; } double ans=1e18; double calc(double x,double y) { double res=0; for(int i=0;i<n;i++) ...

https://codeforces.com/contest/1152c题找到最小的k使得lcm(a+k,b+k)最小思路：lcm=(a+k)(b+k)/gcd(a+k,b+k) = (a+k)(b+k)/gcd(a+k,b-a)，枚举b-a因数即可，由于答案在所有因数的集合里，我们只需要让k最小就行了，这时的k需要满足a+k=b-a。 #include<bits/stdc++.h> using namespace std; #define int long long int gcd(int a,int b) { return b?gcd(b,a%b):a; } sign...

模型：1e5次操作，有三种操作，操作1，两个单点加边，操作2，1个单点对l~r区间加边w，操作3，l～r区间对单点加边。思路：由于是区间操作，线段树建图建立对顶线段树a，b ，注意图中的有向边边权都是0操作1 b的单点连向a的单点操作2 b的单点连向a中区间包含在l～r之间的点操作3 b中区间包含在l～r之间的点连向a中的单点 #include<bits/stdc++.h> using namespace std; const int N=100010,M=9*N+(100010)*20; #define int long long const int INF=0x3f3f3f...

构造思路：首先把答案减去z ，然后对应的a[x]和a[y]都加上z，依次遍历把答案加上就行了，这个思路也太棒了吧%%%，%%lc能想到最大闭合权子图的模型，我都想不到，证明正确性，如果两个不选和选一个和全部都选显然成立，那这两个就是等价的。ac代码： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param n int整型 * @param m int整型 * @param a int整型vector * @param ...

https://codeforces.com/contest/898/problem/D #include<bits/stdc++.h> using namespace std; typedef long long ll; #define debug printf("---\n"); const int N=200010,M=1000010; struct node{ int l; int r; int sum; bool lz; }tr[M<<2]; int cnt[M]; void pushdown(int u)...

链接：https://codeforces.com/problemset/problem/1463/B题意：给定一个序列，让构造出一组数列，满足两倍的所有差值的绝对值之和满足<=所有数的和，其中每个数都不能超过1e9，并且相邻两个数不能为互相的倍数。思路：构造一个为2的等比数列就行了，对于每一位找到不超过它的最大的等比数就可，哎，我之前想过取平均数的做法或者枚举等比因子，其实快想到了，但还是不信。。证明一下 ，假设每个数为k，那么得到的等比数一定>=k/2，所以加起来一定<=sum/2代码： #include<bits/stdc++.h> using namesp...

链接：https://codeforces.com/problemset/problem/1463/D题意：给定1～2*n，再给定操作后需要得到的n个数的序列，让你选择n个pair，每两个数组成一对，假设有x个pairs取min，n-x个取max，最后问有几个x能满足这种序列。思路：假设x是固定了，取x个min，n-x个max，那么我们将a数组，也就是题目给的n个数，和b数组另外n个数，进行选择，其实贪心想想可以想到前x个数与b的后x个数取min，后n-x与b的前n-x取max，这样是最优的，假设如果把这两个集合中的数互调，可能会不成立，达不到题目给的序列，假设原始为min<a,b&gt...

#include<bits/stdc++.h> using namespace std; double a[110][110]; int n; const double eps=1e-4; void print() { for(int i=1;i<=n;i++) { for(int j=1;j<=n+1;j++) cout<<a[i][j]<<" "; cout<<endl; } } int gauss() { int r,c; ...

题意：总共有n个零食编号为1....n，有k个人，每个人的需求是x,y编号的零食，如果该编号有就吃，否则如果x和y都没有这个客人就会伤心，最后问如何排列客人吃的顺序，使得伤心的客人最少。思路：想不出来，太清奇了，题解是并查集的，把物品看作点，每个人看作两个物品间的边，对于一个有x元素的集合，存在且必定存在一种方式使得里面x-1个人都能满足，因为每次都能断掉一个边，由于第一次断的那条边会消去两个，别的方式都会消去一个。所有就是x-1，所以最后统计下每个集合的开心的人的数量就行了。ac代码: //My template #include<stdio.h> #include<str...

链接[https://vjudge.net/contest/413647#problem/C](http://www.nowcoder.com) 题意：给你n个数字的集合，划分成两个集合，让你确定每个数字在哪个集合，使得按原来顺序，集合1在集合2前面，能够构成单调不下降，输出任意解。思路：想了大概一小时吧，也是没想出来，原来的思路是尽量找小的变成1，然后从该位置往右扫把比它大的数都放在一起变成1，否则其他没被标记的都变成2，最后判断是否合理，后来想想这样得不对的，hack数据：5 25546 ，然后看了题解，我们把所有方案划分成划分为x，由于x比较小，把比x小的放在一边，比x大的放在另一边，如...

upper用法：lower_bound(a+l,a+r,n); 前提 运用stl库函数且数列有序using namespace std； algorithm 的 sort函数 lower_bound返回的是第一个大于或等于该m的地址 而upper则是返回大于m的地址 如图 我们就可以得到第一个大于等于6的地址。 #include<stdio.h> #include<algorithm> using namespace std; int main() { int a[10]={ 3,5,6,0,2,1,3,4,5,6}; sort(a,a+9); ...

题（Lake Counting （poj no.2386）） 题目是这样的，有一个大小为NxM的园子，雨后积水了，问你有几个水洼。 Sample Input 10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. Sample Output 3 思路是这样的：用一次dfs就会将有积水的地方和他所相连的部分都变成无积水 总共dfs的次数就是水洼的个数 代码如下： #in...

题目描述 已知 nn 个整数 x_1,x_2,…,x_nx1,x2,…,xn ，以及11个整数kk(k<nk<n)。从nn个整数中任选kk个整数相加，可分别得到一系列的和。例如当n=4,k=3n=4,k=3,44个整数分别为3,7,12,193,7,12,19时，可得全部的组合与它们的和为： 3+7+12=223+7+12=22 3+7+19=293+7+19=29 7+12+19=387+12+19=38 3+12+19=343+12+19=34。 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3+7+19=293+7+19=29。 输入格式...

题来自洛谷 P1217 [USACO1.5]回文质数 Prime Palindromes 题目：题目描述 因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。 写一个程序来找出范围 [a,b] (5 \le a < b \le 100,000,000)a,b( 一亿)间的所有回文质数。 输入格式 第 1 行: 二个整数 a 和 b . 输出格式 输出一个回文质数的列表，一行一个。 输入输出样例 输入 #1 复制 5 500 输出 #1 复制 5 7 11 101 131 151 181 191 313 353 373 383 看了大...