Intelligence1028-CSDN博客

转载 HDU 1611（I-Keyboard）

#include <cstdio>#include <cstring>const int MAXN = 95;int K, L; //按键数，字符数char key[MAXN], letter[MAXN]; //按键，字符int freq[MAXN]; //字符频率int cost[MAXN][MAXN]; //cost[i][j]表示将第i~j个字符分配到一个按键上的价值int price[MAXN][MAXN]; //price[i][j]表示将前j个字符分配到.

2020-07-31 11:00:00 265

原创 HDU 1607（Station Balance）

分为两种情况：小室数量 >= 样本数量，每个小室内放一个样本；小室数量 < 样本数量，首先按样本重量从大到小排序，将重量最大的 2*C-S 个样本单独放置，剩余的样本一个最重的和一个最轻的组合放置。比如样本重量为 5，4，3，2，1，小室数量为 3，则 5 单独放置，4 和 1 组合放置，3 和 2 组合放置。#include <iostream>#include <cstring>#include <algorithm>#include &

2020-07-30 17:50:00 248

原创 HDU 1606（Excuses, Excuses!）

题意：给定一些纯小写字母的关键单词和一些句子，输出关键单词出现次数最多的句子，句子中的单词不区分大小写，如果有多个句子满足要求，则全部输出。思路：保存所有关键单词和句子；依次计算每个句子包含关键单词的数量，将句子中的单词依次提取出来，判断是否为关键单词；更新所有句子中关键单词出现的最大次数；输出关键单词出现次数最多的句子。#include <iostream>#include <string>#include <cctype>...

2020-07-30 00:00:00 688

原创 HDU 1602（Mark-up）

题目不难，主要注意两点：\s 之后只有数字和 '.' 属于转义部分，而且 '.' 最多有一个，其它的字符和当前的 \s 无关；任意字符都可能是最后一个字符，要随时判断下一个字符是否为 EOF。#include <iostream>#include <string>#include <cctype>using namespace std;int main(){ string s; //最终输出的字符串 bool flag = true

2020-07-28 17:17:17 167

原创 HDU 1601（Galactic Import）

题意：若干行星之间有运输通道，其中一些行星到地球有运输通道，每个行星的产品有自己的价值。行星向地球运输产品时，如果能直达地球，则可以将所有产品运往地球；如果需要路过其他行星，则每路过一颗行星，产品减少当前的 5%。计算从哪个行星向地球运送产品，获得的价值最大。方法：由于行星数量很少，所以暴力破解即可。首先计算每个行星到达地球最少需要经过几个其他行星，然后计算每个行星向地球运送产品可获得的价值，选择最大价值的行星即可。#include <cstdio>...

2020-07-27 22:44:21 169

原创 HDU 1599（find the mincost route）

最短路径问题，使用Floyd算法。

2020-07-26 19:40:00 189

原创 HDU 1598（find the most comfortable road）

使用并查集，先将所有边按长度从小到大排序，然后依次将每条边作为最小边，建立并查集，如果起点和终点在同一个并查集中，则存在通路，此时最小边和最大边的差值即舒适度。#include <cstdio>#include <algorithm>using namespace std;const int MAXN = 205;const int MAXM = 1005;const int INF = 0x3f3f3f3f;int n, m;int father[MAXN];

2020-07-25 23:59:58 136

原创 HDU 1597（find the nth digit）

基础题。#include <iostream>using namespace std;int main(){ int K, N; cin >> K; while (K--) { cin >> N; for (int i = 1; i < N; i++) { N -= i; } if (N % 9 == 0) cout << 9 << endl; else cout <&lt

2020-07-24 22:22:21 112

原创 HDU 1596（find the safest road）

最短路问题，使用Dijkstra算法即可。#include <cstdio>#include <cstring>const int MAXN = 1010;double mp[MAXN][MAXN]; //地图double dis[MAXN]; //起点到其它点的最大安全系数bool vis[MAXN]; //结点访问情况//Dijkstra算法，s:起点，e:终点，n:结点数量double Dijkstra(int s, int e, int n){ .

2020-07-20 23:45:00 122

原创 HDU 1595（find the longest of the shortest）

首先计算原始图中，起点到终点的最短路，然后依次删除最短路上的边，计算更新后的图中，起点到终点的最短路，选择所有最短路中长度最长的即可。#include <iostream>#include <algorithm>using namespace std;const int MAXN = 1005;const int INF = 0x3f3f3f3f;int mp[MAXN][MAXN];int dis[MAXN], vis[MAXN], pre[MAXN];int

2020-07-19 16:40:00 122

原创 HDU 1594（find the max）

基础题。#include <cstdio>#include <cmath>using namespace std;int main(){ int N; while (scanf("%d", &N) != EOF) { int a, b, c; scanf("%d%d", &a, &b); int maxR = abs(a - b); int index = 2; for (int i = 3; i <= N; i

2020-07-17 22:22:23 135

原创 HDU 1593（find a way to escape）

基础题，岸上的人需要跑的最大距离为半圆，船上的人首先到达和岸上的人相同角速度的小圆上，并且两人位于大圆的直径上，此时船向岸边移动距离最短。#include <iostream>#include <cmath>using namespace std;const double PI = acos(-1.0);int main(){ double R, V1, V2; while (cin >> R >> V1 >> V2) {

2020-07-16 23:33:33 125

原创 HDU 1592（Half of and a Half）

大数乘法题，计算 2^(n+1) - 1，套用大数乘法模板即可。#include <iostream>using namespace std;const int MAXN = 1005;int num[MAXN][MAXN];//初始化大数数组void init(){ num[0][0] = num[0][1] = 1; for (int i = 1; i < MAXN; i++) //大数乘法 { int carry = 0; for (int j =

2020-07-15 22:55:23 124

原创 HDU 1591（Encoded Love-letter）

基础题。#include <cstdio>#include <cstring>using namespace std;const int MAXN = 30;char keyword[MAXN]; //密钥char s[MAXN]; //各字母的对应字母void decode(char keyword[]){ int len = strlen(keyword); for (int i = 0; i < len; i++) {

2020-07-14 22:55:23 154

转载 HDU 1590（Searching）

#include <iostream>#include <complex>#include <cmath>#include <iomanip>using namespace std;const double PI = acos(-1.0);int main(){ double X, Y, A, k; while (cin >> X >> Y >> A >> k) { .

2020-07-13 21:12:20 126

转载 HDU 1588（Gauss Fibonacci）

#include <iostream>using namespace std;const int len = 2;struct Node{ __int64 mat[2][2];};Node unit, A; //单位矩阵，矩阵Aint k, b, n, M;//计算(a*b)%M，其中a和b都是矩阵，M是正整数Node mul(const Node& a, const Node& b){ Node c; for (int i = 0; i &lt.

2020-07-11 22:22:21 113

原创 HDU 1587（Flowers）

基础题。#include <iostream>using namespace std;int main(){ int N, M; while (cin >> N >> M) { int minPrice = 0x3f3f3f3f; //最低价格 int temp; while (N--) { cin >> temp; if (temp < minPrice) { minPrice = temp

2020-07-11 19:00:01 115

原创 HDU 1584（蜘蛛牌）

深搜题，详细见注释。#include <iostream>#include <cstring>using namespace std;const int MAXN = 15;const int INF = 0x3f3f3f3f;int minDis; //最小移动距离int pos[MAXN]; //各数字所在的位置bool vis[MAXN]; //各数字是否移动过//深搜，count:已经移动的数字的个数，sum:当前移动距离void DFS(int

2020-07-11 10:40:00 200

原创 HDU 1583（DNA Assembly）

深搜题，由于数据量很小，搜索出所有可能的连接方案，选出长度最短的即可。#include <iostream>#include <string>using namespace std;const int MAXN = 10;int n;int ans;int vis[MAXN];int order[MAXN]; //字符串连接顺序string str[MAXN];//将字符串b连接到字符串a之后，并返回连接后的字符串string strMerge(stri

2020-07-10 09:30:00 174

原创 HDU 1582（AC Again）

深搜题，字母 A 的图形中，相连的空格区域数为 2；字母 C 的图形中，相连的空格区域数为 1。#include <cstdio>using namespace std;const int MAXN = 55;char mp[MAXN][MAXN];//深搜，将(r,c)及其相连的' '替换为'*'void DFS(int r, int c){ if (r < 0 || r > MAXN || c < 0 || c > MAXN)

2020-07-09 22:00:00 141

转载 HDU 1581（Number Game）

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int MAXS = 1 << 20;const int MAXN = 25;int num[MAXN]; //可选的数int win[MAXS]; //必胜的状态//改变状态，根据数字x改变状态sint changeState(int s, int x){ fo.

2020-07-08 09:20:01 155

原创 HDU 1580（Always On the Run）

动态规划题，本题与 HDU 1474 完全相同。#include <iostream>#include <algorithm>using namespace std;const int MAXN = 15;const int MAXK = 1005;const int MAXD = 35;const int INF = 0x3f3f3f3f;int dp[MAXN][MAXK]; //dp[i][j]表示从城市1到城市i，乘坐j次飞机，最小花费int day[

2020-07-07 11:00:00 141

原创 HDU 1579（Function Run Fun）

动态规划题。#include <iostream>#include <cstring>using namespace std;const int MAXN = 25;int dp[MAXN][MAXN][MAXN];void init(){ for (int a = 0; a <= 20; a++) { for (int b = 0; b <= 20; b++) { for (int c = 0; c <= 20; c++)

2020-07-06 23:23:23 152

原创 HDU 1578（Martian Mining）

动态规划题，设dp[i][j] 表示从 (0, 0) 到 (i, j) 之间的矩阵最多能收集的矿石数量，Y[i][j] 表示 Yeyenum 矿石从 (i, j) 向西最多能运的数量，B[i][j] 表示 Bloggium 矿石从 (i, j) 向北最多能运的数量。状态转移方程：dp[i][j] = max(dp[i - 1][j] + Y[i][j], dp[i][j - 1] + B[i][j])。#include <cstdio>#include <cstring&gt.

2020-07-05 16:30:30 123

转载 HDU 1577（WisKey的眼神）

#include <iostream>#include <cmath>using namespace std;int gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b);}int main(){ int L, sx, sy, dx, dy; while (cin >> L) { if (L == 0) break; cin >>.

2020-07-03 23:45:01 157

转载 HDU 1576（A/B）

#include <iostream>using namespace std;void exgcd(int a, int b, int& x, int& y){ if (b == 0) { x = 1; y = 0; } else { exgcd(b, a % b, y, x); y -= x * (a / b); }}int main() { .

2020-07-02 09:40:00 137

原创 HDU 1575（Tr A）

矩阵快速幂，套用标准模板即可。#include <cstdio>#include <cstring>using namespace std;const int mod = 9973;const int MAXN = 15;int n, k;struct Matrix{ int arr[MAXN][MAXN];}m;//矩阵乘法，矩阵a*矩阵b，同时取余Matrix Mul(Matrix a, Matrix b) { Matrix c;

2020-06-29 10:10:09 158

原创 HDU 1574（RP问题）

0-1背包问题。本题中，重量和价值可能为正，也可能为负。为了方便计算，将所有值都 +10000，让这些值都变为正。设 dp[i] 表示 RP 为 i 时的最大获益值。状态转移方程：dp[i+a] = max(dp[i+a], dp[i]+c)。#include <cstdio>#include <algorithm>using namespace std;const int MAXN = 20005;const int INF = 0x3f3f3f3f;int

2020-06-28 19:50:01 197

转载 HDU 1573（X问题）

#include <iostream>using namespace std;const int MAXM = 15;int A[MAXM], B[MAXM];int gcd(int a, int b){ if (!b) return a; else return gcd(b, a % b);}void exgcd(int a, int b, int& x, int& y){ if (!b) .

2020-06-23 11:22:33 165

原创 HDU 1572（下沙小面的(2)）

暴力搜索即可，使用 STL 全排列函数next_permutation，详细见注释。#include <cstdio>#include <algorithm>using namespace std;const int MAXN = 35;const int MAXP = 10;int dis[MAXN][MAXN]; //车站间的距离int to[MAXP]; //各乘客的到达车站int main(){ int N; while (scanf("%d".

2020-06-22 22:22:22 145

原创 HDU 1571（下沙小面的(1)）

模拟题，详细见注释。#include <cstdio>#include <cstring>using namespace std;const int MAXN = 35;const int MAXP = 10;const int INF = 0x3f3f3f3f;int dis[MAXN][MAXN]; //车站间的距离struct Passenger //乘客{ int to; //目的车站 int num; //上车次序}p[MAXP];int

2020-06-22 18:30:30 140

原创 HDU 1570（A C）

基础题。#include <iostream>using namespace std;int main(){ int T; cin >> T; while (T--) { char c; cin >> c; int n, m; cin >> n >> m; int facN = 1, facM = 1, facNM = 1; for (int i = 1; i <= n; i++) //n!

2020-06-18 16:00:00 191

转载 HDU 1569（方格取数(2)）

#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;const int N = 1e5 + 10;const int M = 1e5 + 50;const int INF = 0x3f3f3f3f;int total; //边的总数量int s, t; //源点、汇点int head[N];int dep.

2020-06-18 15:40:00 147

转载 HDU 1568（Fibonacci）

#include <iostream>#include <cmath>using namespace std;int main(){ int f[21] = { 0,1 }; //前20个Fibonacci数 for (int i = 2; i < 21; i++) { f[i] = f[i - 1] + f[i - 2]; } int n; double s = (sqrt(5.0) + 1.0) /.

2020-06-16 11:40:01 123

原创 HDU 1567（2006）

基础题，关键是理解题意，要求每一行的输入为每支队伍比赛且仅比赛一次，输出整个比赛安排是否合理。#include <cstdio>#include <cstring>using namespace std;const int MAXN = 2010;bool vis[MAXN];int num[MAXN];int main(){ int n; while (scanf("%d", &n) != EOF) { memset(num, 0, siz

2020-06-15 08:40:00 178

转载 HDU 1565（方格取数(1)）

#include <iostream>#include <algorithm>using namespace std;const int L = 20000;int n;int mp[25][25]; //地图int dp[L], temp[L];int pre[L], now[L]; //上一行的所有状态，当前行的所有状态int preNum, nowNum; //上一行的状态数，当前行的状态数int ans[L]; //各状态选择的数之和//深搜，搜索当.

2020-06-14 08:20:02 166

原创 HDU 1564（Play a game）

找规律题，如果 n 为偶数，先手赢；如果 n 为奇数，后手赢。#include <iostream>using namespace std;int main(){ int n; while (cin >> n) { if (n == 0) break; if (n % 2 == 0) cout << "8600" << endl; else cout << "ailyanlu" << e

2020-06-13 08:30:30 140

原创 HDU 1563（Find your present!）

基础题，使用 map 数据结构即可。#include <iostream>#include <map>using namespace std;map<int, int> mp;int main(){ int n; while (cin >> n) { if (n == 0) break; mp.clear(); int num; while (n--) //输入，记录每个输入数的个数 { cin &g

2020-06-12 10:10:09 114

原创 HDU 1562（Guess the number）

基础题。#include <iostream>using namespace std;int main(){ int T; cin >> T; while (T--) { int a, b, c; cin >> a >> b >> c; int x; for (x = 1000; x <= 9999; x++) { if (x % a == 0 && (x + 1) % b ==

2020-06-11 07:50:00 177

转载 HDU 1561（The more, The Better）

#include <iostream>#include <algorithm>using namespace std;const int MAXN = 205;struct Edge //边{ int to; //到达结点 int next; //出发结点的下一条边的编号}edge[MAXN];int dp[MAXN][MAXN]; //动态规划数组int head[MAXN]; //head[i]表示从结点i出发的第1条边的编号int val.

2020-06-10 10:00:00 117