共同富裕
显然每次选最大的数字，其余的加一。也可以理解为每次选一个最大的数字减一，直到所有数字都变成最小的数字为止。
#include<stdio.h> #include<string.h> #include<stdlib.h> int cmp(const void * x, const void * y) { //x < y return (*((int *)(x))) > (*((int *)(y))) ? 1 : -1; } int a[100005]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } qsort(a, n, sizeof(int), cmp); long long ans = 0; for (int i = 1; i < n; i++) { ans += a[i] - a[0]; } printf("%lld ", ans); return 0; }
股票价格3
维护一个数组，按时间顺序排列，表示当前还未被超过的价格。显然，这个数组一定是降序的。因为如果出现i<j且a[i]>a[j]，则第i天的价格已经被超过，不应出现在数组中。
从左到右遍历每天的价格，当处理第i天时，首先将a[i]插入维护的数组，再删除由于a[i]的插入产生的逆序对。由于a[i]插入前数组中得价格均未被超过，所以被删除的价格都是被a[i]首次超过，记录这些价格的日期与i之差。
#include<stdio.h> #include<string.h> #include<stdlib.h> int cmp(const void * x, const void * y) { //x < y return (*((int *)(x))) > (*((int *)(y))) ? 1 : -1; } struct node { int price, id; }; int a[100005], ans[100005], size; node stack[100005]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } stack[0].price = a[0], stack[0].id = 0, size = 1; memset(ans, -1, sizeof(ans)); for (int i = 1; i < n; i++) { stack[size].price = a[i]; stack[size].id = i; size++; while (size > 1) { if (stack[size - 2].price >= stack[size - 1].price) { break; } ans[stack[size - 2].id] = i - stack[size - 2].id; stack[size - 2] = stack[size - 1]; size--; } } for (int i = 0; i < n; i++) { printf("%d ", ans[i]); } return 0; }
超市规划
区间动态规划在遇到时间问题时想一想四边形不等式。
首先，最优的分配肯定满足每个超市控制的小区是连续的一段；其次，一段连续的几个小区由一个超市控制，则最优的点坐标为各个超市坐标的平均数。
dp[i][j]表示前i个小区由j个超市控制,w[l][r]表示从第l个小区到第r个小区由一个超市控制的最小不方便程度，则dp[i][j]=min{dp[k-1][j-1]+w[k][i] | 0<=k<=r}。
nk的范围都是2000，时间肯定是不够的。可以用四边形不等式来优化，证明是不会证的，输出了一下各个k点选择的值，发现是满足的，于是就直接上了。
#include<stdio.h> #include<string.h> #include<stdlib.h> int cmp(const void * x, const void * y) { //x < y return (*((double *)(x))) > (*((double *)(y))) ? 1 : -1; } int p[2005][2005]; double x[2005], sum[2005], c[2005]; double dp[2005][2005], f[2005][2005]; double qwe(int l, int r) { double sum_ = l == 0 ? sum[r] : sum[r] - sum[l - 1], c_ = l == 0 ? c[r] : c[r] - c[l - 1], ave; ave = sum_ / (r - l + 1.0); return (r - l + 1.0) * ave * ave - 2 * sum_ * ave + c_; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%lf", &x[i]); } qsort(x, n, sizeof(double), cmp); if (k >= n) { printf("0.000 "); return 0; } sum[0] = x[0], c[0] = x[0] * x[0]; for (int i = 1; i < n; i++) { sum[i] = sum[i - 1] + x[i]; c[i] = c[i - 1] + x[i] * x[i]; } for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++) { if (i < j) { dp[i][j] = 0; } else { dp[i][j] = 1e10; } } } for (int i = 1; i < n; i++) { for (int j = 1; j <= k; j++) { if (i < j) { dp[i][j] = 0; continue; } dp[i][j] = qwe(0, i); p[i][j] = 0; int st = p[i - 1][j] > p[i][j - 1] ? p[i][j - 1] : p[i - 1][j]; for (int l = st; l <= i; l++) { double tmp = qwe(l, i); if (dp[i][j] > dp[l - 1][j - 1] + tmp) { dp[i][j] = dp[l - 1][j - 1] + tmp; p[i][j] = l; } } } } printf("%.3lf ", dp[n - 1][k]); return 0; }
有趣的子区间
首先构造出1-1e9中所有的回文数，然后依次计算包含0个、2个......回文数的区间个数。计算时提出公因子，可以减少计算时间。
没调通，懒的再搞了。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using namespace std; vector<long long> v; const long long maxn = 1000000000; const long long p[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; long long d[120000], s[120000]; int cmp(const void * x, const void * y) { //x < y return (*((double *)(x))) > (*((double *)(y))) ? 1 : -1; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif v.clear(); for (int i = 1; i < 10; i++) v.push_back(i), v.push_back(i * 10 + i); for (int i = 2; i < 6; i++) { int tmp; long long ttmp; for (int j = p[i - 1]; j < p[i]; j++) { tmp = j; for (int k = 0; k < i; k++) { d[k] = tmp % 10; tmp /= 10; } if (i < 5) { for (int k = 0; k < i; k++) d[2 * i - 1 - k] = d[k]; ttmp = 0; for (int k = 2 * i - 1; k >= 0; k--)ttmp = ttmp * 10 + d[k]; v.push_back(ttmp); } for (int k = 0; k < i - 1; k++) d[2 * k - 2 - k] = d[k]; ttmp = 0; for (int k = 2 * i - 2; k >= 0; k--)ttmp = ttmp * 10 + d[k]; v.push_back(ttmp); } } v.push_back(0), v.push_back(1000000001); sort(v.begin(), v.end()); long long a, b; scanf("%lld%lld", &a, &b); int l, r; for (int i = 0; i < v.size(); i++) { if (v[i] >= a) { l = i; break; } } for (int i = v.size() - 1; i >= 0; i--) { if (v[i] <= b) { r = i; break; } } for (int i = l; i < r; i++) d[i] = v[i + 1] - v[i]; d[r] = b > v[r] ? b - v[r] : 1; s[r] = d[r], s[r - 1] = d[r - 1]; for (int i = r - 2; i >= l; i--) s[i] = s[i + 2] + d[i]; long long ans = 0; for (int i = l; i <= r; i++) { long long pl, pr; if (i == l) pl = v[l] - a + 1; else pl = d[i - 1]; pr = s[i + 1]; ans += pl * pr; } ans += (v[l] - a) * (v[l] - a + 1) / 2; ans += (b - v[r]) * (b - v[r] + 1) / 2; for (int i = l; i < r; i++) ans += (d[i] - 1) * d[i] / 2; printf("%lld ", ans); return 0; }