A Testing Pants for Sadness
简单的原题，贪心求解并确保不溢出就行。
#include <bits/stdc++.h>
using namespace std;
const int N = 102;
long long a[N];
void solve()
{
int n;
cin >> n;
long long sum = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
sum += i * (a[i] - 1) + a[i];
}
cout << sum << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}B Brave Game
原题：HDU - 1846
C Negatives and Positives
D 谁是最强程序员
路径压缩并查集小修改。
#include <iostream>
using namespace std;
const int N = 55;
int f[N];
int find(int x)
{
if (x != f[x])
return f[x] = find(f[x]);
return f[x];
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
f[i] = i;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa != pb)
f[b] = pa;
}
int res = find(1);
// cout << "--------------------------------\n";
// cout << find(1) << " " << 1 << endl;
for (int i = 2; i <= n; i++)
{
// cout << find(i) << " " << i << endl;
if (res != find(i))
{
res = -1;
break;
}
}
if (res != -1)
cout << f[1];
else
cout << res << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}E I Hate It
原题：HDU - 1754
F Silver Cow Party
原题：POJ - 3268
G Partitioning by Palindromes
原题：UVA-11584
输入一个由小写字母组成的字符串，要求把它划分成尽量少的回文串。输出最少的个数。
如aaadbccb最少可以划分为3个：aaa,d,bccb
输入：
第一行输入一个n表示数据组数
接下来n行每行输入一个字符串s(1⇐s⇐1000)
输出：
输出一个数表示最少的个数
输入样例
3
aaadbccb
ffgcc
juzi输出样例
3
3
4
思路
线性DP问题。
将所有可能的 回文串 标记出来, 存入 s[i][j] 表示 i-j 这个串是不是回文串。
判断当前字符是否可以与之前的串构成回文串, 如果可以则当前的最短长度为 该回文串的上一个 最短长度。
如判断第i个字符, 可以构成 以第j个字符开头, 第i个字符结尾的回文串, 则 至此最短数量就是 f[j - 1] + 1, 这个1就是代表当前的回文串。
紫书上判断所有回文串的代码： 类似于记忆化搜索
int is_prilindrome(int i, int j)
{
if(i >= j) return 1;
if(s[i] != s[j]) return 0;
if(vis[i][j] == kase) return p[i][j];
vis[i][j] = kase;
p[i][j] = is_prilindrome(i + 1, j - 1); // 当子串为回文且当前俩字符相等, 才是回文
return p[i][j];
}代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 +10;
int vis[N][N], f[N];
bool p[N][N];
char s[N];
int n, kase;
int is_prilindrome(int i, int j)
{
if(i >= j) return 1;
if(s[i] != s[j]) return 0;
if(vis[i][j] == kase) return p[i][j];
vis[i][j] = kase;
p[i][j] = is_prilindrome(i + 1, j - 1); // 当子串为回文且当前俩字符相等, 才是回文
return p[i][j];
}
int main()
{
int T;
cin >> T;
for(kase = 1; kase <= T; kase++)
{
cin >> s + 1;
n = strlen(s + 1);
f[0] = 0;
for(int i = 1; i <= n; i++)
{
f[i] = i + 1;
for(int j = 0; j < i; j++)
{
if(is_prilindrome(j + 1, i))
{
f[i] = min(f[i], f[j] + 1);
}
}
}
cout << f[n] << endl;
}
return 0;
}H Page Hopping
原题：UVA-821
题目
二基楼有n个教室（1≤n≤100），任意两间教室之间可能存在多条路径（一个你所不知道的世界）。作为一个作死的冒险家，你想走遍所有路径以得到任意两间教室之间最短路径的平均值。最后你得到了结果满意地在二基楼迷了路。
多组数据。 每组数据为一行。一组数据包含多个整数对a、b（1≤a, b≤100），表示可以从教室a到教室b。当输入“0 0”时，表示结束该组数据的输入。 最后输入“0 0”，表示整个输入的结束。
每组数据输出一行。以Sample Output的格式输出任意两教室最短距离的平均值，保留3位小数。
input
1 2 2 4 1 3 3 1 4 3 0 0
1 2 1 4 4 2 2 7 7 1 0 0
0 0
output
Case 1: average length between pages = 1.833 clicks
Case 2: average length between pages = 1.750 clicks
hits 第一组数据中，路径有12条，其总的最短路径长度为22，则平均值为22/12=1.833
思路
求所有最短路径长度的平均值, 那就要知道每个点能去的点数量（路径数）和每个点能去的点之间的路径和。
显然我们需要多次求两个点之间的最短路径, 最符合的算法就是 floyd 求多源最短路。 求出来最短路之后就再次遍历所有点, 若他们之间的最短路径存在则说明是一个成立的路径, 用这种方法来求出所有路径数。 最后输出即可。
代码
// Made by Aze //
//------------------------------//
/*
* problem:https://vjudge.csgrandeur.cn/problem/UVA-821#author=SCU2018
* date:8/17 2:48PM
*
*/
//------- Include Area----------//
#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int readInt()
{
int t;
cin >> t;
return t;
}
//------- Coding Area ---------//
const int N = 1010, INF = 0x3f3f3f3f;
int dist[N][N];
int n;
void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cout << fixed << setprecision(3); // 浮点数精度设置为保留小数点后3位
int a, b;
int kase = 1;
while (cin >> a >> b && (a || b))
{
memset(dist, INF, sizeof dist);
do
{
dist[a][b] = 1;
n = max(n, a);
n = max(n, b);
} while (cin >> a >> b && (a || b));
floyd();
double res = 0;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (j != i && dist[i][j] != INF)
{
cnt++;
res += dist[i][j];
}
}
}
cout << "Case " << kase++ << ": average length between pages = " << res / (double)cnt << " clicks\n";
}
return 0;
}I Monsters
J 饭卡
原题：HDU-2546
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n⇐1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m⇐1000。
n=0表示数据结束。
Output 对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
output
-45
32
思路
如果把题目改成, 饭卡余额m, n个菜品, 求买到菜品总价值最大,那么是标准的01背包问题。
但这里求饭卡余额最小, 且该题代价跟价值是相等的,总价值最大时余额便是最小, 用总余额减去总价值即可。
不过还有当 余额为 大于5时, 可以超出背包容量塞进大物品, 那么最优解肯定是用这5块买最贵的菜品, 于是就把余额先用去5块, 买最大的那个, 剩下的钱再求剩下的菜品最大价值。
求剩下时背包容量不能溢出, 也就是标准01背包问题, 求出最大价值在输出时加上原本最大的那个菜品就行。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e3 +10;
int f[N];
int w[N];
int n,m;
int main()
{
while(cin >> n && n)
{
memset(f, 0, sizeof f);
for(int i = 1; i <= n;i ++)
cin >> w[i];
sort(w + 1, w + 1 + n);
cin >> m;
if(m < 5)
{
cout << m <<endl;
continue;
}
for(int i = 1; i < n; i++)
for(int j = m - 5; j >= w[i]; j --)
f[j] = max(f[j], f[j - w[i]] + w[i]);
cout << m - a[n] - f[m - 5] << endl;
}
return 0;
}K 最正确的数
原题：HDU-1061
快速幂然后取模为10就行。