题目链接 思路：基本状压dp看题目知道此题求的是最短哈密顿路径，也就是一条从1到n的经过所有点的最短路径。 我们可以使用状态压缩，使用一个二进制数state代表一种状态，state代表经过的所有点的集合。例如 state=1，代表只经过1号点。 state=3（二进制为0011），代表经过1号点和2号点。 state=5（二进制为0101），代表经过1号点和3号点。 state=6（二进制为0110），代表经过2号点和3号点。 ....... 我们设定dp[state][j]代表经过点的集合为state，并且最后一个点为j号点。 由此推出状态转移方程为：dp[state][j]...

思路：从左边往右边考虑，F[x]为区间[0,x]的解。因此所求为F[L]。首先可以推断出，以下几点 x 为偶数，因为洒水是以原点为中心画圆，所有直径不可能为奇数。 F[x] = F[y]min + 1, y = [x-2B, x-2A]。 因为半径为A——B，所有只有x-2B 到 x-2A 之间才能通过再加一个点达到x。那么如何快速求得[x-2B, x-2A]中的y，使得F[y]最小？需要使用优先队列，在每次完成一个点的计算之后，增加计算下一个点所需的信息到优先队列中。 #include <iostream> #include <vector> #include ...

文章目录 make file的基本语法为： target ：needs file [tab] 命令 main: thanks1.o thanks2.o thanks3.o thanks.o gcc -o main thanks1.o thanks2.o thanks3.o thanks.o thanks.o: thanks.c gcc -c thanks.c thanks1.o: thanks1.c gcc -c thanks1.c thanks2.o: thanks2.c gcc -c thanks2.c than...

基本的dfs搜索一般都是直接从一个点出发，再从这个点到下一个 但是这题使用了另一种思路的dfs 每次选择点不是根据上一个点来推进，而是从整个地图中选择没有选过的点 也就是扫描一遍地图，从中选择还没有使用过的点，这种方式往往用于两个点之间的转移规则比较复杂的情况，比如这题，每次需要使用两个点，而不是一个，同时有横竖两种方向。 使用这种方式时需要注意在找到第一个点之后需要立即return。 #include <bits/stdc++.h> #include <hash_map> #include <hash_set> using namespace std; ...

#include <bits/stdc++.h> #include <hash_map> using namespace std; using namespace __gnu_cxx; #pragma GCC optimize(2) #define maxx 150000 hash_map<int, bool> M; int Ans[150010]; int Sans = 0; int Res(int x) { int cc = 0; while(x) { cc += (x%10)*(x%10); ...

先离线，离散化 在线段树维护区间和以及数量 #include <bits/stdc++.h> using namespace std; ///#pragma GCC optimize(2) #define Mode 1000000007 const int N = 1<<17; struct node { long long Sum; long long Cnt; }; struct que { int type; long long first; long long second; }; long long Res...

#include <iostream> #include <vector> #include <string.h> #include <queue> #include<stdio.h> using namespace std; #define to_str(name) (#name) #define TIMx_ARR(n) TIM##n##_ARR int main(void) { freopen("G:\\data.txt", "r", stdin); int TI...

文章目录 1. 单分支语句 2. 双分支语句 3. 多分支语句 4. case 语句 5. for 循环 6. while 循环 7. until 当条件不成立时循环 1. 单分支语句 if [条件判断式] ; then 程序 fi 或者 if [条件判断式] then 程序...

这题在贪心的时候需要注意一下技巧，否则就会超时。 没有直接选取第一个点，而是比较之后选了最优的一个点。 如果没有解直接结束。 两个点之间是不连续的，所以第一次覆盖这个点之后，下一次可以直接从这个点+1开始。 #include<iostream> #include<stdio.h> #include<string.h> #include <algorithm> using namespace std; int T, N; struct node { int S; int D; bool operator < (...

有n个任务，每个任务有一个截止时间，超过截止时间一天，要扣一个分。 求如何安排任务，使得扣的分数最少。 Input 有多组测试数据。第一行一个整数表示测试数据的组数 第一行一个整数n(1<=n<=15) 接下来n行，每行一个字符串(长度不超过100)表示任务的名称和两个整数，分别表示任务的截止时间和完成任务需要的天数。 这n个任务是按照字符串的字典序从小到大给出。 Output 每组测试数据，输出最少扣的分数的。 并输出一个完成任务的方案，如果有多个方案，输出字典序最小的一个。 Sample Input 2 3 Computer 3 3 English 20 1 Mat...

完全背包。。。 #include <iostream> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f struct node { int P; int W; bool operator <(const struct node &A) { return this->W < A.W; } }; typedef struct node Node; Node A[510]; int dp[10100...