A题   对于这个关系式，xi和yi都是下标，只要记录一下每个下标被加或减的次数，把相加次数最少的分配给最小的值就可以   #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 20; typedef long long ll; int a[N],b[N],n,m,x,y; ll ans; void solve() {     s...

差分约束系统的解法如下：1、 根据条件把题意通过变量组表达出来得到不等式组，注意要发掘出隐含的不等式，比如说前后两个变量之间隐含的不等式关系。2、 进行建图：首先根据题目的要求进行不等式组的标准化。(1)、如果要求取最小值，那么求出最长路，那么将不等式全部化成xi – xj >= k的形式，这样建立j->i的边，权值为k的边，如果不等式组中有xi – xj > k，因为一般题目都是对整形变量的约束，化为xi – xj >= k+1即可，如果xi – xj = k呢，那么可以变为如下两个：xi – xj >= k, xi – xj <= k,进一步变为xj –...

求出一个大于 ⌈ n ⌉的环或找出 ⌈ n ⌉个点的独立集。 可以用DFS树的方式找环，a到b 在树上的链与非树边(a,b)会形成一个环，环的大小为∣dep[a]−dep[b]∣+1。环一定由某条链和某条非树边组成。 下面证明如果不存在这种环，就一定存在至少⌈ n ⌉个点的独立集由于不存在这种环，因此每个点最多有 ⌈ n ⌉ − 2 条非树边，也就是说，我们每选择一个点，最多会导致 ⌈ n ⌉ − 1个点无法被选。所以最少可以选 ⌈ n ⌉个点，按深度从大到小选即可。 #include<bits/stdc++.h> using namespace std; const int ma...

F题求出L-R中多少个数满足子串是3的倍数鸽巢原理：长度>3时，一定会重复出现mod 3相等的数字，那么那一段就是3的倍数只需要计算999以内即可 G题给出列A,B，交换k次A的不同数字，使得AB对应位置差的绝对值之和最大。解：可以理解为分配+、-号，满足A和B的+号总和和-号总和相等n>2,恰好k次和至多k次等价最优对换解：交换后变优2*[min(ai,bj)-max(aj,bi)]将所有的min(ai,bi)\max(ai,bi)排序，取前k大相减取和即可。 H给出n个大小不同的数，找一个最小的模域使他们模数互不相同解：实质是求最小的m，不是任意一个|ai-aj|的约数。FFT...

讲课：博弈和构造对称博弈：n个硬币围成一圈，每人每次取走一个或两个相邻硬币，取完者胜。解：n<=2 先手胜，否则先手必败（先手会把圆变成一条链，后手把它变成两个相同的链，然后后手的操作和之前先手操作一致，这样最后取光的操作一定是后手进行的） 巴什博弈：一堆石子，两人轮流每次取1、2、3颗，取光者胜。0必败态--1、2、3必胜态--4必败态--5、6、7必胜态....以此类推n%4==0是后手必胜，否则先手必胜只能取m~k个：n%(m+k)==0后手必胜每次只能取2的幂次个（1\2\4\8....）：n%3==0先手败 NIM博弈:3堆石子，每次可选任一堆去任意多个(0,0,0)必败(0,...

A题 #include<bits/stdc++.h> using namespace std; const int maxn = 110; int t,a[maxn],n,x,sum,f; void solve() { cin>>n>>x; sum = 0,f = 0; for(int i = 1;i <= n; ++i) { cin>>a[i]; sum += a[i]; if(f) { swap(a[i],a[i - 1]); f = 0; } if(sum == x) f = 1; } if(f) printf("NO\n"); el...

A题题意：问能否找出一个子序列使得其积不是完全平方数解：只要找到一个不是完全平方的元素就可以找到这样的子序列 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double eps = 1e-5; int t = sc.nextInt(); while(t-- != 0) { int n = sc.nextInt(); boolean f = false; while(n-- != 0) { int...

A题题意：r个红豆和b个绿豆，要求跟他们分组，每组至少有1个红豆和1个绿豆，且红豆的绿豆的个数相差不能超过d代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll t,a,b,c; int main() { std::ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>a>>b>>c; if(min(a,b) * (c + 1) >= max(a,b)) cout<<"...

A题看有几个1和3，统计输出即可B题给出a/b/c,找到x,y使得x的位数是a,y的位数是b,gcd(x,y)的位数是c解：刚开始没想出太好的解，就暴力打表然后存进去的，太麻烦啦假设x,y初始都为任意一个位数为c的值z，然后x不断3直到位数符合要求，y不断5直到符合要求，这样可以保证gcd的值一定是z,并且因为每次乘3/5,每次乘位数最多增加1 import java.util.Scanner; public class Main { public static long ksm(long a,long c) { // TODO Auto-generated method stub long ...

A题给出n,k,求三个数x/y/z，使得n = x + y + z,并且gcd(x,y) = gcd(x,z) = gcd(y,z) = k解：在n / k / 3范围内左右查找符合条件的值 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll t,n,k; int solve() { if(n % k) return 0; ll p = n / k; ll r = p / 3; for(ll i = max(2LL,r - 100);i <= min(p,r + 100); ++i) fo...

A题   题意：n个数，每次选择两个数，第一个数-1，第二个数+1，但要保证操作后两个数非负，最多操作k次，问最小的序列   解：前面能减则减   #include<bits/stdc++.h> using namespace std;   typedef long long ll; const int maxn = 2e3 + 10; int t,n,k,a[maxn];   void solve() {   &...

A题   题意：按照身高给n个成员排序，要求尽可能让相邻两人的身高平均数是整数，给出方案   解：直接分奇偶数输出即可   #include<bits/stdc++.h> using namespace std;   const int maxn = 1e4 + 10; int t,n,a[maxn];   int main() {     cin>>t;     whil...