显然可以dp。 dp[i][j] 为前i个数字能否构成j。 怎么状态转移呢？每次第i个数有一个对应区间，我们直接尝试加入区间的每一个数字，和前i-1个数能构成的数字去匹配。 我们就可以发现这样复杂度是：1e6 * 100 * 100为1e10，不过我们只需要知道能否构成，所以可以状态压缩，然后用bitset即可。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=110; bitset<1000010> dp[N]; int n,l,r; signed main(){ cin>&g...

显然是可以离线之后fenwick维护。 因为不喜欢离线，所以直接主席树了。 每次找到对应区间，然后相当于就是区间sum的问题了。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=N*40; int n,m,rt[N],lc[M],rc[M],sum[M],cnt; #define mid (l+r>>1) void change(int l,int r,int &x,int y,int k){ sum[x=++cnt]=sum[y]+1,lc[x]=lc[y]...

先跑出起点到每个点的最短路，然后每个点到终点的最短路。 如果d==0，那么直接特判，否则使用一定是最优的。 枚举每个点，到能到的最小到终点的最短路，其实就是矩形查询min。 直接ST表维护即可。 AC代码： #pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2010,inf=0x3f3f3f3f; const int dx[]=...

其实我们画画图就可以发现，如果把边全部选完，那么一定是有解的。 所以，我们就是删除权值和最多的边，使得原问题还有解。什么是无解呢？就是某个边删除之后，连通块个数为奇数了，那么就不行。 所以直接dfs一次即可，如果当前子树点的个数为偶数个，直接删除即可。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e4+10,M=N<<1; int n,sz[N]; long long res; int head[N],nex[M],to[M],w[M],tot; inline void a...

激光炸弹 *一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。 现在地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。 激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个边长为 R 的正方形的边必须和x，y轴平行。 若目标位于爆破正方形的边上，该目标不会被摧毁。 求一颗炸弹最多能炸掉地图上总价值为多少的目标。 输入格式 第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。 接下来N行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y坐标...

a^b 求 a 的 b 次方对 p 取模的值。 输入格式 三个整数 a,b,p ,在同一行用空格隔开。 输出格式 输出一个整数，表示a^b mod p的值。 数据范围 1≤a,b,p≤1e9 输入样例： 3 2 7 输出样例： 2 时/空限制： 1s / 32MB 这道题刚看会发现诶，直接循环就完了嘛，但是一看下面的数据范围就会发现，如果直接循环，一定会超时。 那怎么做呢？ 这里就是一个典型快速幂的题目，我们可以吧a^b分解，利用二进制的特性，从低位乘到高位，如果那一位是0就代表不需要乘，1则反之。 #include<bits/stdc++.h> using na...

康托展开 康拓展开一般是用于计算一个全排列数字排在所有全排列的大小位置。 那么到底怎么计算呢？ 敲重点 X=a[n]∗(n-1)!+a[n-1]∗(n-2)!+…+a[i]*(i-1)!+…+a[2]*1!+a[1]*0![1] 从第一个数字开始到倒数第二个数字，计算需要计算的那个数字之后比这个数小的数字有几个，再乘以（n-x）！，n是全排列的 数字，x是当前数字的位置。 下面就是代码。 #include<bits/stdc++.h> using namespace std; int fac[]={1,1,2,6,24,120,720,5040,40320,3628...

数字的全排列 直接上代码 #include<bits/stdc++.h> using namespace std; int n,p[10],vis[10]; void dfs(int x)//x为当前的枚举位置 { if(x==n+1)//如果位置都枚举完毕了，就打印出来 { for(int i=1;i<=n;i++) cout<<p[i]<<' '; cout<<endl; return ; } for(int i=1;i<=n;i++) { if(!vis[i])//如果这个数字还没有被放置 ...

编辑距离 这是一个典型的动态规划问题 问题就是给你两个字符串a,b，有三种操作 增加一个字符 删除一个字符 改变一个字符 问通过上述的操作，最少多少步，能把a变为b 直接上代码 #include<bits/stdc++.h> using namespace std; int dp[110][110];//dp[i][j]表示a的第一个字符到第i个字符，b的第一个字符到第j个字符 int main() { string a,b; cin>>a>>b; a=' '+a,b=' '+b;//让字符串从1开始 int lena=...

二叉树的树结构很简单，用一个结构体就可以完成。 struct node //二叉树的结点 { char data; //存放当前二叉树结点的数据 node *left,*right; //指向下一个二叉树的左子树和右子树 }*p; //指向树根的结点p 二叉树的先序建立用递归就可以了,下面给出代码 void create_bitree(node *&p) //递归建立二叉树 { char c; cin>>c; if(c=='#') { p=NULL; //如果当前输入为'#'证明当前为NULL指向 } else ...

How Many Tables 题目链接： http://acm.hust.edu.cn/vjudge/contest/123393#problem/C Description Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the...

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to wo...

Background Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers ...

优先队列的本质其实就是一个堆，一直维护就行。 我们使用C++就可以用STL轻松实现,就不用手写堆了（是不是很方便？(✪ω✪)）. priority_queueq; 默认优先级从到大到小 priority_queue<int,vector,greater > q; 优先级从小到大 当然，我们也可以自定义排序，如下列代码，按照成绩大到小排序，如果成绩相等，就按照名字的字典序，小的排在前面。 #include<bits/stdc++.h> using namespace std; struct node //定义学生成员的结构体 { string name...