牛客小白月赛24 I.求和 （数状数组&DFS序） 题目传送门 思路：单点修改和区间查询。用DFS序形成一个数组。再用树状数组求和和更新。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e6+5; int tr[N],n,m,k,a[N],in[N],out[N],tot;//tr[]（tree[]数状数组) in[] out[]分别代表入栈,出栈时间.  typedef long long ll; #define lowbit(x) (x&-x) vector<int>e...

lowbit()的原理及证明   lowbit()代码： #define lowbit(x) (x&-x) //method 1 int lowbit(int x){ return x&(-x); } //method 2 int lowbit(int x){ return x&(~x+1); } //method 3

牛客小白月赛24 H.人人都是好朋友(离散化&并查集） 题目传送门 思路：将朋友的关系建立一个并查集。再遍历一遍，看两个敌人的根结点是否相同。 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; #define mst(a) memset(a,0,sizeof a) int s[N<<1],a[N],b[N],d[N<<1],h[N<<1]; int c[N]; int find(int x){ if(x!=...

POJ - 1797 Heavy Transportation （最短路之最大权值） 题目传送门 思路 :  #include<cstdio> #include<cstring> #include<iostream> #include<queue>  #include<cmath> #include<algorithm> using namespace std; const int N=1e3+5,inf=0x3f3f3f3f; int a[N][N],d[N],vis[N],n;//由于数据较小直接用邻接矩阵存  #de...

D - Frogger （最短路） 题意：求1到n所有路径的最大值中最小必要值。 题目传送门 思路：  AC代码： #include<cstdio> #include<cstring> #include<iostream> #include<queue>  #include<cmath> #include<algorithm> using namespace std; double f[205][205]; struct p{ double x,y; }a[205]; double fun(int i,int j){ //...

B - Cow Contest （floyd之传递闭包） 题意：给定m个胜负关系，求能确定多少个人的排名 思路：显然用floyd进行状态更新即可。 AC代码： #include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[105][105]; int n,m; void floyd(){ //有向图之floyd 传递闭包  for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(f[i][k]) for(int...

牛客小白月赛24 E.旅旅旅游(最短路&并查集） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+5,M=5e5+5; typedef long long ll; ll d1[N],d2[N]; int n,m,s[N]; struct node{ ll d; int id; bool operator<(const node &a)const{ return d>a.d; } }now; vector<node>vi[N]; stru...

差分数组&前缀和公式(一维,二维) （所有公式本文不作证明,读者自行查阅相关证明.）

D.牛妹吃豆子(二维前缀和&差分数组） 题目传送门 给定矩阵：k个区间修改，给q个询问区间和。 思路：二维差分数组板子题。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=2e3+5; typedef long long ll; ll a[N][N]; int main(){ int n,m,k,q; scanf("%d%d%d%d",&n,&m,&k,&q); while(k--){ int x1,y1,x2,y2; scanf("%...

AtCoder Beginner Contest 163 D - Sum of Large Numbers(递推&找规律） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; const double pi=atan(1.0)*4; typedef long long ll; const ll mod=1e9+7; int main(){ int n,k; scanf("%d%d",&n,&k); ll ans=0; for(int i=k;i<=n+1;i++...

F - Agri-Net （最小生成树&kruskal） 思路：板子题。（第一次学这个算法标记一下）。思路就是对边排序，取n-1条边生成一棵权值和最小的树。生成树的过程用并查集实现。 AC代码： #include<cstdio> #include<cstring> #include<iostream> #include<queue>  #include<cmath> #include<algorithm> #include<vector> using namespace std; const int N...

G - Borg Maze （Prim&BFS） 题意：给一个图,起点S,求遍历到所有‘A’的最小距离之和.每次走到一个‘A’相当于这个’A’是新的起点’S‘，很显然会想到树,新的子结点作为根结点继续往下搜索.所以此题为最小生成树问题。具体看代码。 AC代码： #include<cstdio> #include<cstring> #include<iostream> #include<queue>  #include<cmath> #include<algorithm> #include<vector>...

E - Active Infants （贪心&DP） 题目传送门 此题贪心的思路是优先对较大的数往两边放。可以有两种方法：1.递归+类似区间DP形式 2.设dp[ i ][ j ]表示往左放的个数和往右放的个数从小到大递推。具体看代码。 法1： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+5; vector<pair<ll,ll> >v(N);//vector对pair排序时按'键'排序 即第一元素first  ll dp[N][...

D. Constant Palindrome Sum （暴力&差分数组） 题目传送门 思路：用差分数组记录[2,2k]范围内该数需要修改的次数.最后取最小值即可。 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) int main(){ int t; scanf("%d",&t); while(t--){ int n,k; scanf(&quo...