题目大意有两个矿井及N辆矿车，每个矿工的产煤量与其最后三顿饭的种类数有关。求最大产煤量。 算法DP，f[i][j1][j2][j3][j4][j5]表示处理到第i辆，第一个矿井前两天吃的是j1，j2，第二个矿井前两天吃的是j3，j4。 但是空间只有18MB，所以我们采用滚动数组 代码 #include <cstdio> #include <memory.h> #include <algorithm> using namespace std; #define max(a,b) ((a)>(b))?(a):(b) #define min(a,b) ((a)...

题目将一个字符串切K刀后求字典中的词语出现的次数 两个词语不能第一个字母在字符串中出现的位置相同 算法DP，f[i][j]表示枚举到第i个，前面切了j刀 调试记录本来用Hash，调了一个下午没过 然后直接用string，然后就过了 代码 #include <iostream> #include <cstdio> #include <functional> using std::cin; using std::string; using std::max; using std::min; string s,a[10]; int n,dp[500][500]={...

题目大意 有一些蚯蚓，每次取最长的切成两段，其余增长q，求每次切掉的蚯蚓的长度以及最后所有蚯蚓的长度 算法 由于先切掉的一定比后切掉的长，所以我们不需要堆，直接队列即可 所以我们可以使用三个队列，一个存原来的，另外两个存切开的 然后每次从三个队列的队首取最大值切开 然后我们用sum存所有蚯蚓的增长量，对于切开的两个减掉即可 代码 #include <cstdio> #include <algorithm> #define MAXN 10000005 int q1[MAXN],q2[MAXN],q3[MAXN]; int head1,head2,head3,tail1,t...

题目大意有一个N*M的城市，可以在第一行建蓄水池，水可以往低处流。求能否覆盖最后一行。 若能覆盖，求最小蓄水池数；若不能，求有几个不能覆盖 算法DFS，求第一行每个点可以覆盖的最下面一行的左右端点，然后做线段覆盖。 代码 #include <cstdio> #include <memory.h> #define INF 1<<30 #define max(a,b) (((a)>(b))?(a):(b)) #define min(a,b) (((a)<(b))?(a):(b)) const int dx[4]={0,1,0,-1}; const i...

题目大意 一棵树，每次可以删掉一个节点及其子节点，同时从第一层节点开始，每次每层节点会被打上标记，求最小打上标记的个数 算法 由数据范围<=300得知，此题可以爆搜 然后就开始爆搜 #include <cstdio> #include <vector> #define int long long struct edge{ int to,nxt;cpp }e[1000]; int head[500]={0},cnt=0; void add(int u,int v){ e[++cnt]=(edge){v,head[u]}; head[u]=cn...

题目大意一条长度为L的河，某些地方有石头，每次可以跳S~T的长度。求最少踩到几块石头。 算法DP，f[i]=f[i-j]+flag[i]。但是河的长度有1e9，所以我们要压缩路径。 若两个石子之间的距离大于t(t-1)，我们就可以把它改成t(t-1)。 然后DP就好了 代码 #include <cstdio> #include <algorithm> #define INF 1<<30 int a[101],dis[101],flag[10001],f[10001]; int main(){ int l,s,t,n; scanf("%d%d%...

题意 求最小割 题解 Dinic+当前弧优化 #include <iostream> #include <cstring> #include <queue> using namespace std; int n,m,S,T,cnt=-1,depth[6000001],head[6000001]; int cur[6000001]; struct edge{ int nxt=-1,to,w; }flow[6000001]; void add(int x,int y,int z){ cnt++; flow[cnt].to=y; f...

题目大意 有一些城市，每个城市的水晶球的售价不同。在一条从1到n的路径中，我们可以在其中一个城市买入，另一个城市卖出。 求最大收获。 算法 SPFA 先构造一个分层图，层内的边权值为0，表示随便走不需要钱。 然后第一层往第二层可以到达的点连边，权值为售价的相反数，表示买入需要花钱。 第二层往第三层可以到达的点连边，权值为售价，表示卖出可以赚钱。 然后将第一层的N和第二层的N向汇点连边，分别表示不买和买了。 然后从1开始SPFA最长路即可。 代码 #include <cstdio> #include <queue> #include <memory.h> #d...

从起点出发，BFS遍历，每到一个点，若之前未访问过，就标记，当前到它的最短路径条数即为该路径上他的父节点的条数；否则比较从当前路径走所得到的与起点的距离和最短路径大小，（此时最短路径大小已知，见上文）若相等，它的最短路径条数加上该路径上它父节点路径数 。 起点到某一点最短路路径条数等于起点到它所有父节点路径条数的和。讲的有些赘余，代码思路比较清晰，可以参考，如果还不懂可以画一下样例： 从起点开始走，每到一个点就标记，并标上它到起点的最短距离和它的路径数，直到遍历全图。 #include <iostream> #include <cstdio> #include <...

题意 Mayan puzzle是一个游戏。界面是一个 7 行5 列的棋盘，上面堆放着一些方块，方块不能悬空堆放。 具体规则： 1. 每步移动可以且仅可以沿横向拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置； 如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落； 2.任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除 注意： a) 如果同时有多组方块满足消除条件，几组方块会同时被消除。 b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除。 c) 方块消除之...

题解 我们先按Kruskal在已经给出的最小生成树模拟，每次按边权从小到大对联接的两个块操作 一步一步合并节点，每次两个完全图集合互相合并成一个完全图集合时，ans要加上(这条路最小权值+1)(集合一的点数集合二的点数-1) 码量较小，主要考察思维 #include<bits/stdc++.h> using namespace std; struct edge{ int x,y,w; }; const int maxn=50010; int fa[maxn],s[maxn]; edge a[maxn]; bool cmp(const edge &a,const ed...

题意 见https://www.luogu.org/problemnew/show/P3243 题解 在反向图上拓扑排序，用小根堆维护 调试记录 数组开小了100倍 #include #include #include #include using namespace std; priority_queue ,less > q; int from[1000000],to[1000000],head[1000000],nxt[1000000],cnt=0; int n,m; int ans[1000000]; void add(int x,int y){ cnt++; ...

题意 丢个链接就跑 https://www.luogu.org/problemnew/show/P2472 题解 先把每个点分为入和出，另有超级源点S，超级汇点T 然后建图 1.每个柱子入向出连流量为高度的边 2.初始有蜥蜴的柱子：S向入连边（流量为1） 3.能跳出去的柱子：出向T连边（流量为inf） 4.每个柱子的出向能跳得到的柱子的r连边（流量为inf） 调试记录 略 #include<queue> #include<cstdio> #include<cstring> #include<cmath> #incl...

题意 有一矩阵，每个格子上有一坨0~k不等量的魔液，小a和uim以从矩阵的任一个格子开始，每次向右或向下走一步，从任一个格子结束。 魔瓶只有k的容量，若使结束时两瓶内魔液相等，有多少种方法。 题解 dp方程如下 dp[i][j][h][0]+=dp[i-1][j][(h-a[i][j]+k)%k][1]; dp[i][j][h][0]%=mod; dp[i][j][h][0]+=dp[i][j-1][(h-a[i][j]+k)%k][1]; dp[i][j][h][0]%=mod; dp[i][j][h][1]+=dp[i-1][j][(h+a[i][...