推公式题。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e4+7; ll ans[maxn], mu_fac_sum[maxn]; bool vis[maxn]; int prime[maxn]; int Mob[maxn]; void init(){ int cnt = 0; vis[1] = 1; Mob[1] = 1; for(int i = 2; i <= maxn; i++){ if(...

#include<bits/stdc++.h> using namespace std; const int N = 1e6+7; int a[N]; struct node{ double x, y; }p[N],s[N]; int n; bool cmp(node a, node b) { if(a.x == b.x) return a.y < b.y; return a.x < b.x; } bool Cross(node a, node b, node c) { double x1 = a.x - b.x, y1 = a.y - ...

链接：https://atcoder.jp/contests/arc105/tasks/arc105_c?lang=en好题，一直打算写题解，鸽了好久。首先N<8,8!=40320,dfs暴力枚举全排列。然后看这个顺序过桥的从头到尾的最短距离是多少，我一开始构造的dp方程不对dp[i]=min(dp[j]+max_len(j, i)),后来经过提醒意识到这个不对重新写了一个方程:dp[i]=max(dp[j]+min_len(j,i))min_len可以二分去找到这个dp转移方程确实值得好好想想这题在二分上需要注意单调性的建立。 #include<bits/stdc++.h>...

题目链接：http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf总结：上来是俩水题，然后接着看B，C题其实都是思维水题。B题不需要推公式，dfs可以直接卡过，C题手动模拟出结论？不过暴露出来了我对博弈的有点遗忘和数学公式推理薄弱。确实好久没见过了，为了避免以后碰到凉凉，还是有必要认真重新复习下。B.Master of Phi比赛的时候写了一发dfs超时。但复杂度好像能过，重写了一下：(注意：预处理，以及dfs求所有组合) #include<bits/stdc++.h> using namespace std;...

链接：https://codeforces.com/contest/1443/problem/C题意：对于每道菜i，点外卖的话花费a[i],自己去拿的话花费b[i],外卖的时间都是平行的。问最短多长时间获得所有外卖？思路：二分最后答案，维护一个sum为自己取外卖的时间，二分的时候贪心的去考虑,如果a[i]<=b[i],就不管了，如果a[i] > b[i]，那么sum+=b[i].代码： #include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5+7; in...

链接:https://codeforces.com/contest/1437/problem/B一看题便知道这题存在什么规律(别马后炮行不行啊喂....)引入：意识到只有连续的1或者连续的0的时候才会去进行操作，如何消去连续的1呢？去找以0为端点，以当前1为端点的段，然后找个段调个头。同理对于0。为了使得操作的次数最少？我们让这俩操作一起做。做法：对于当前的连续1，我们去后面找到一段连续0，然后以它们为端点的段进行掉头操作。这样应该是两两配对的，这样应该是两两配对的，如果有剩余的话，需要向上取整，可以理解为与整个串的端点的段进行掉头操作。 #include<bits/stdc++.h&g...

链接：https://ac.nowcoder.com/acm/contest/7501/B思路：只考虑特殊点即墙的端点，起点和终点。对于每个点都与另外的所有点尝试建边，建边的条件是这个边不会穿过墙。那么最后跑个最短路即可。代码： #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn = 610; int...

#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f int mp[75][75]; int dp[75][75][75][75]; //dp[i][j][k][r]定义为：当前行选了k个，和能够余r的最大和 //转移方程为：dp[i][j][k][r]如果不选第j个，dp[i][j][k][r] = dp[i][j-1][k][r] //否则：dp[i][j][k][r] = dp[i][j-1][k-1][r-q]+a[i][j] （设a[i][j] % r = q） //行与行之间的关系可...

链接：https://vjudge.net/contest/401586#problem/C题意：有n个骆驼过桥，骆驼的重量为w1,w2,...,wn，桥由M段连成，每段的长度为li,承重为wi,可以调整骆驼的先后顺序，问骆驼能通过桥首尾的最短距离为多少？思路：n很小，那么可以暴力出n的全排列。令dp[i]表示从第1只骆驼到第n只骆驼能通过的最短距离。转移方程：dp[i]=max(dp[i],dp[j] + len(j, i)){len(j,i)为j到i的最短距离}解释一下转移方程：dp[j]是前j个能通过，那么不管它们，考虑j到i能通过的j到i的最短距离？如何判断能通过的最短距离？那么就是从...

ax+by=c有解结论的推广gcd(a,b)|c别忘了特判a=b=0的时候，c=0，c/=0情况代码： #include<bits/stdc++.h> using namespace std; #define int long long signed main() { int t; cin >> t; while(t--) { int a, b, c, d; cin >> a >> b >> c >> d; int g = __gcd(__gc...

链接：https://codeforces.com/contest/1428/problem/E题目：有n个数，把n个数分成k份，使得这k个数的平方和最小思路：首先发现一个数分的越多，那么这个平方和越小设函数fi(x)表示将a[i]分成y份的平方和，我们发现一开始都是fi(1)，这样我就分了n个数了，然后，每个fi函数都有一个减少率fi(x+1)-fi(x)，用优先队列保存，从n+1到k开始，每次分都去找最大的减少率的fi函数，让它的x+1。吐槽：函数，贪心，优先队列。出题人前几天是不是刚打完atcoder？代码： #include<bits/stdc++.h> using nam...

链接：https://codeforces.com/contest/1428/problem/D(每列最多放2个，注意读题~)从右边向左考虑，先说结论：a[i]=0, 不放a[i]=1,放在(i,i)a[i]=2,(i,i)放一个点，然后后面找一个a[j]=1(j>i)的点(且之前没被其他a[i]=2的点使用过)，然后把此时在(j,j)的点上升到(i,j)a[i]=3,(i,i)放一个点，然后后面找一个没有没有放满的列(a[j]=1的话要求没有被a[i]=2的使用过)，然后在(i,j)放一个点。 口胡一波为什么这样是对的：我们看到回旋镖的轨迹，发现a[i]=3的其实是不好考虑的，因为可能...

链接：https://vjudge.net/contest/402242#problem/C思路：因为x都是正整数，所以一开始x都为1，由f(x+1)-f(x)=2aix+ai+bi，每次找到最小的f(x+1)-f(x)，然后这个函数的x+1，维护一下这个增长率。代码： #include<bits/stdc++.h> using namespace std; #define int long long typedef long long ll; const int maxn = 1e5+7; struct Node{ int a, b, c; }f[maxn]; struc...

链接：http://poj.org/problem?id=1006思路：中国剩余定理水题贴一个中国剩余定理：逆元不能用快速幂，而要用exgcd来求，之前没有注意，快速幂求逆元是费马小定理要求模数是质数的时候才可以。代码： #include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include...