题意：有n个建筑需要抢修，给出这n个建筑的抢修时间和截止时间，求最多可以抢修多少建筑？ 思路：按截止时间升序排列，用优先队列维护可维修的建筑的持续时间，因为截止时间是升序的，所以当遇到无法及时维修的建筑时，如果小于优先队列中最大的持续时间，可以替换，这样优先队列中数据量不变，总时间减少，相当于优化了选择。 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 1000000007 inline int read() { int x = 0, f = 1; char ch =...

题意：给出一个长度为n的序列，要求区间长度在[L,R]之间且为偶数的区间异或和之和？ 思路：参考：https://blog.nowcoder.net/n/4dacd8e372de4199a30442b4eee1849asum[i][j]为前i个数在第j位为1的个数pre[i][j][0]为在sum[k][j] (k<=i&&k>=1&&ki mod(2) )中为偶数的个数pre[i][j][1]为在sum[k][j] (k<=i&&k>=1&&ki mod(2) )中为奇数的个数结果等于每一位在规定区间长度...

题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 思路：如果我们把比大于k的值变成1，比k小的值变成-1，那么计算从左边到k区间的值，并记录个数，加上为0的个数，再计算从右边到k区间的值，加上相反数的标记个数，如果值为0，再加1，可用map标记； 代码： #include<bits/stdc++.h> #define ll long long #define inf 1000000007 using namespace std; int a[100005]; map<int,int> m...

题意：有一个n个点节点m条边的无向图，从点1开始遍历，按照每次“走两步”遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以最少加几条边，可以完整的遍历整个图？ 思路：如果一个连通块中有奇数环，则该连通块可以全部遍历到，加一条边可以使二个连通块合在一起，最后在一个大于等于3的连通块中加一条边可以创造一个奇数环（如果没有奇数环），所以当有奇数环时答案为连通块的个数-1，否则为连通块的个数。 代码： #include<bits/stdc++.h> #define ll long long #define inf 1000000007 using namespace st...

题意：一共有n个数，第i个数是xi, xi可以取 [li , ri] 中任意的一个值。设 S = ,求S种类数? 思路：bitset,01背包bit[i]为前i个数中能得到的值的那一位为1，否则为0；当加上x[i+1]的平方时相当于bit[i]向左平移了x[i+1]的平方个位置所以bit[i]=bit[i]|(bit[i-1]<< ); 代码： #include<bits/stdc++.h> #define ll long long #define inf 1000000007 using namespace std; bitset<1000005> bit...

题意：一场比赛总共有12个题，对于第i个题，有a[i]的几率解决它，如果不能解决，则你有b[i]的概率从左边那个队那里听会这个题的做法，有c[i]的概率从右边那个队那里听会这个题的做法，请问最终你们队伍解出0-12题的概率分别是多少？ 思路：每一题单独的解决概率的d[i]=a[i]+(1-a[i])(b[i]+c[i]-b[i]*c[i]);（使用了容斥原理AB=A+B-A B ）然后dp,f[i][j]为前i道题解决j道题的概率f[i][j]=f[i-1][j](1-d[i])+f[i-1][j-1]*d[i];初始化：f[0][0]=1; 代码： #include<bits/stdc...

题意：求在一个nm的01矩阵中有多少个不全为0的kk矩阵; 思路：纯模拟 代码： #include<bits/stdc++.h> #define ll long long #define inf 1000000007 using namespace std; char s[1005][1005]; int main() { int n, m, k, ji=0; //ji计算当前k*k矩阵1的个数 scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) { scanf("%s",s[i]); } for(int i=...

题意：在一个数轴，有n个储物点，每一个储物点有b[i]个东西，同时第（i+1）个储物点距离第i个储物点a[i]的距离。进行m次查询，每次查询给与x,l,r三个整数，表示求将区间[l,r]个储物点的东西全部运到第x个储物点的代价？比如储物点i有b[i]个东西，要运到储物点j，代价为b[i] * dist( i , j )dist就是储物点间的距离。  思路：前缀和，先对距离求前缀记dis[i]，再对将前i个储物点运到第1个储物点的代价进行前缀和记sum1[i]，最后对前i个储物点的东西个数进行前缀和记sum2[i]。 如果x<=l,则计算z=sum1[r]-sum1[l-1]-(sum2[...

题意：在一个n x m个格子组成的迷宫，'#'表示的格子不能走，'.'表示可以走。起点用'S'表示，目的地用'T'表示。只能向上下左右相邻的格子移动，每移动一次花费1秒。有q个单向传送阵，每个传送阵各有一个入口和一个出口，在入口处，你可以选择是否传送，传送过程会花费3秒；注意：一个格子可能既有多个入口，又有多个出口。请求出到达目的地的最短时间？ 思路：用优先队列写bfs 代码： #include<bits/stdc++.h> #define ll long long using namespace std; int n, m, q, dx[4]={1,-1,0,0}, dy[4]=...

题意：给出一个n个节点的二叉树，中序遍历为1，2，3,......，n;每个节点都有一个分数（均为正整数），任一棵子树subtree的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数求二叉树的最大分数和前序遍历？ 思路：f[i][j]为从第i个到第j个节点的树最高分.root[i][j]为从第i个到第j个节点的数根节点.f[i][j]=max{f[i][o-1]*f[o+1][j]+f[o][o]}(o>=i,o<=j) 代码： #include<bits/stdc++.h> #define ll long lon...

题意：给出一个整数m,再给出8行字符串，前4行为司机基地情况，后四行为齐齐基地情况，求齐齐在摧毁司机全部大炮后最多剩多少门大炮？（无法全部摧毁司机大炮则输出-1） 思路：dfs求出司机基地有多少个大炮连通块，再用dfs求出齐齐每一个大炮连通块的大炮个数并保存，由于保存最多的大炮，使用的大炮所在连通块在下次司机的攻击下会被摧毁，所以齐齐首先使用大炮连通块的大炮个数最少的攻击司机基地大炮。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; char s[15][1005], b[15][100...

题意：有n个格子排成一列对于一个格子，里面会有以下几种字符： 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈焰 ？：未告诉你本格情况 求n个格子分布合理的情况数？ 思路：dp dp[i][0/1][0/1]表示前i位，当前位和下一位是（1）不是（0）烈焰的情况数 当s[i]='*'时， 该位是1:dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1]) 当s[i]=...

题意：有一个n个节点和m条边的图，每个节点有一个高度，路只能从一个点到一个高度不大于它的另一个点，你可以从你所经过的任何一个点出发去下一个点，求经过的点最多为多少个，且此时经过的最短路为多少？ 思路：prim算法中优先队列第一关键词以所到达的节点的高度降序，第二关键词以路程升序 代码： #include<bits/stdc++.h> #define inf 1000000007 using namespace std; typedef long long ll; int n, m; int h[100005]; struct w { int to, cost; }w; vector...

题意：给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数 思路：将所有询问按x升序排列，a序列也按升序排列，然后每次询问当前[l,r,x]之前把ai小于等于x的ai在树状数组中加入他对应的原下标（只需要对应原下标位置+1就行)，然后询问[l,r]区间有多少个数。 代码： #include<bits/stdc++.h> #define inf 1000000007 using namespace std; typedef long long ll; int shu[500005]; int n, m; struct w { int l, r, x, s; }w[100...