求凸包的周长，模板题，卡了很久，最后发现是如果n=2的时候没有特判 代码： #include <bits/stdc++.h> using namespace std; const int N=1050; struct Point{  int x,y; }p[N],s[N]; int top,n; int cross(Point a,Point b,Point c){  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } double dis(Point a,Point b){  return sqrt((double)(a.x-b.x...

凸包的判定方法：将点按逆时针排列，依次枚举三个点 a , b , c a,b,c a,b,c求向量 ( a , b ) (a,b) (a,b)和 ( b , c ) (b,c) (b,c)，的叉乘，也就是判断 ( a , b ) (a,b) (a,b)和 ( b , c ) (b,c) (b,c)的夹角，如果叉乘小于0，即sin夹角大于180度，即不是凸包 注意到这里是求 ( a , b ) (a,b) (a,b)和 ( b , c ) (b,c) (b,c)的叉乘，而在下面的凸包求法中是求 ( a , b ) (a,b) (a,b)和 ( a , b ) (a,b) (a,b)的叉乘 #in...

题意很简单，给一个函数，如果x y差的绝对值小于等于1，函数值为0，否则函数值为y-x 然后给一个数列，求 ∑ f ( a i , a j ) \sum f(a_i,a_j) ∑f(ai​,aj​) 其中 i < j i<j i<j 首先暴力是不可能暴力的，n那么大，数列考虑一下前缀和，比如现在如果我们不考虑函数值为0的情况，也就是要求 ∑ a j − a i \sum a_j-a_i ∑aj​−ai​，那就简单了，记录前缀和，枚举每个数，然后累加 a i ∗ ( i − 1 ) − p r e [ i − 1 ] a_i*(i-1)-pre[i-1] ai​...

逆元其实就相当于倒数的一个推广（我的理解），比如A/B 就相当于A乘B的逆元，也就是倒数，在模n情况下就不只是简单的倒数这种情况了 用拓展欧几里德来求逆元，具体证明还不太懂，就。。先背吧 hdu1576 题意是给A%MOD 和MOD 和B 求（A/B）%MOD ，那已知A%MOD 其实就可以相当于已知A，但是肯定不能直接除以B，所以相当于乘以B的逆元，所以问题就转化为求B的逆元 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &am...

Java没有传引用这种东西，long的包装类又是final的，所以只能用数组来代替一下 拓展欧几里德这东西真实难懂，逆元这东西也是难懂 import java.io.*; import java.util.Scanner; import java.util.StringTokenizer; public class Main {  static long n,b; static final int MOD=9973; static long exgcd(long a,long b,long[] x,long[] y){  if(b==0){  x[0]= 1L; y[0]= 0L; retur...

签到题 定义f(x)就是x这个数（0-9）含有的圈的个数，然后再定义函数g(x)，0次的时候就是x，然后每加一次幂就是f(x)一次 1e9想想应该可以直接暴力循环，第一次tle，然后仔细一想到最后其实很多都是0-1-0-1这样变化的，真正有效的变化只有前面几个，所以循环到g(x)值为0就可以判断然后break了 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; int t; ll x,k; int f[10]={ 1,0,0,0,1,0,1,0,2,1}; int main(void){ ...

第二题做了J题，题意是给n本书的价格，然后要从第一本开始买，不够买就跳过，然后给定这个人买的本书，判断这个人最大可能有的钱数 考虑了一下我们只要分情况考虑一下就好了，首先是n==m，能全买的钱肯定是无限大，然后如果价格为0的数量大于m，就是不可能的情况，因为0一定要买 然后就是剩下的情况，把0的全部买了，然后从头开始买，剩下的找到一个最小值把钱数再加上这个数-1即可，因为如果再打就可以买这一本了，所以这是最大的 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e...

题目比较好懂的，给个无向图，每条边有个距离，而且走过每条边会获得10个东西，从s出发到t，求要得到k个东西的最短路是多少 如果没这个要拿k个东西的条件，那就是一个简单的最短路，然后这题数据不是很大，可以用bfs来求最短路，当s==t && tk>=k就结束，而与普通的bfs不同的就是我们还要加上一个松弛操作 其中dp[i][j]表示节点i获得j个东西的最短路  if(dp[v][tk+1]>dp[tp][tk]+edge[i].w){  dp[v][tk+1]=dp[tp][tk]+edge[i].w; q.push(node{ v,tk+1,dp[v][tk+1]...

建图一时爽，找bug火葬厂… 题意其实就是求一个图的最小割，最小割等于最大流，但是这题点和边都很多，最大流可能会超时，我们就可以转化为对偶图的最短路问题，也就是面看成点，点看成面这样子，经过麻烦的建图之后，跑一下dijk最短路就好了 代码： #include <bits/stdc++.h> using namespace std; const int N=4000005; const int M=8000005; const int INF=0x3f3f3f3f; int n,m,en; struct Edge{  int v,w,next; }edge[M]; int cnt,h...

#include <bits/stdc++.h> using namespace std; const int N=1e7+50; int p[N]; //true表示被筛，即不是素数 bool check[N]; int n,m,a; void init(){  int t; check[1]=true; for(int i=2;i<=n;i++){  //素数，直接记录 if(!check[i]){  p[++p[0]]=i; } //p[0]记录的是素数个数 //枚举现在已知的所有素数 for(int j=1;j<=p[0];j++){  //筛掉p[j]的倍数 ...

package OJ; import java.util.Scanner; public class Main {  static final int N=(int)1e7+50; static int n,m,a; static int[] p=new int[N]; static boolean[] check=new boolean[N]; static void init(){  int t; check[1]=true; for(int i=2;i<=n;i++){  if(!check[i]){  p[++p[0]]=i; } for(int j=1;j<=p[0];j...

积性函数指对于所有互质的整数 a a a和 b b b有性质 f ( a b ) f(ab) f(ab)= f ( a ) f ( b ) f(a)f(b) f(a)f(b)的数论函数。

n是数组长度，a数组是原数列，c数组是辅助数组（树状数组，在第一种模板中表示前缀和，第二种模板中表示区间最大值），也就是树状数组的节点 单点更新和区间求和 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+50; ll a[N],c[N],n,x; int lowbit(int x){  return x&-x; } void update(int i,ll d){  while(i<=n){  c[i]+=d; i+=lowbit(i); } } l...

Description   监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果 相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱 Input   输入两个整数M，N.1<=M<=108,1<=N<=1012 Output   可能越狱的状态数，模100003取余 Sample Input 2 3 Sample Output 6 HINT   6种状态为(000)(001)(011)(100)(110)(111)  容斥问题？ n n n个房间 m m m种宗教，所有可能情况就是 m n m^n mn种，...