共同富裕
显然每次选最大的数字，其余的加一。也可以理解为每次选一个最大的数字减一，直到所有数字都变成最小的数字为止。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void * x, const void * y) {
//x < y
return (*((int *)(x))) > (*((int *)(y))) ? : -;
}
int a[];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmp);
long long ans = ;
for (int i = ; i < n; i++) {
ans += a[i] - a[];
}
printf("%lld\n", ans);
return ;
}
股票价格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))) ? : -;
}
struct node {
int price, id;
};
int a[], ans[], size;
node stack[];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
stack[].price = a[], stack[].id = , size = ;
memset(ans, -, sizeof(ans));
for (int i = ; i < n; i++) {
stack[size].price = a[i];
stack[size].id = i;
size++;
while (size > ) {
if (stack[size - ].price >= stack[size - ].price) {
break;
}
ans[stack[size - ].id] = i - stack[size - ].id;
stack[size - ] = stack[size - ];
size--;
}
}
for (int i = ; i < n; i++) {
printf("%d\n", ans[i]);
}
return ;
}
超市规划
区间动态规划在遇到时间问题时想一想四边形不等式。
首先，最优的分配肯定满足每个超市控制的小区是连续的一段；其次，一段连续的几个小区由一个超市控制，则最优的点坐标为各个超市坐标的平均数。
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))) ? : -;
}
int p[][];
double x[], sum[], c[];
double dp[][], f[][];
double qwe(int l, int r) {
double sum_ = l == ? sum[r] : sum[r] - sum[l - ], c_ = l == ? c[r] : c[r] - c[l - ], ave;
ave = sum_ / (r - l + 1.0);
return (r - l + 1.0) * ave * ave - * 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 = ; i < n; i++) {
scanf("%lf", &x[i]);
}
qsort(x, n, sizeof(double), cmp);
if (k >= n) {
printf("0.000\n");
return ;
}
sum[] = x[], c[] = x[] * x[];
for (int i = ; i < n; i++) {
sum[i] = sum[i - ] + x[i];
c[i] = c[i - ] + x[i] * x[i];
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= k; j++) {
if (i < j) {
dp[i][j] = ;
} else {
dp[i][j] = 1e10;
}
}
}
for (int i = ; i < n; i++) {
for (int j = ; j <= k; j++) {
if (i < j) {
dp[i][j] = ;
continue;
}
dp[i][j] = qwe(, i);
p[i][j] = ;
int st = p[i - ][j] > p[i][j - ] ? p[i][j - ] : p[i - ][j];
for (int l = st; l <= i; l++) {
double tmp = qwe(l, i);
if (dp[i][j] > dp[l - ][j - ] + tmp) {
dp[i][j] = dp[l - ][j - ] + tmp;
p[i][j] = l;
}
}
}
}
printf("%.3lf\n", dp[n - ][k]);
return ;
}
有趣的子区间
首先构造出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 = ;
const long long p[] = {, , , , , , , , , };
long long d[], s[];
int cmp(const void * x, const void * y) {
//x < y
return (*((double *)(x))) > (*((double *)(y))) ? : -;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
v.clear();
for (int i = ; i < ; i++) v.push_back(i), v.push_back(i * + i);
for (int i = ; i < ; i++) {
int tmp;
long long ttmp;
for (int j = p[i - ]; j < p[i]; j++) {
tmp = j;
for (int k = ; k < i; k++) {
d[k] = tmp % ;
tmp /= ;
}
if (i < ) {
for (int k = ; k < i; k++) d[ * i - - k] = d[k];
ttmp = ;
for (int k = * i - ; k >= ; k--)ttmp = ttmp * + d[k];
v.push_back(ttmp);
}
for (int k = ; k < i - ; k++) d[ * k - - k] = d[k];
ttmp = ;
for (int k = * i - ; k >= ; k--)ttmp = ttmp * + d[k];
v.push_back(ttmp);
}
}
v.push_back(), v.push_back();
sort(v.begin(), v.end());
long long a, b;
scanf("%lld%lld", &a, &b);
int l, r;
for (int i = ; i < v.size(); i++) {
if (v[i] >= a) {
l = i;
break;
}
}
for (int i = v.size() - ; i >= ; i--) {
if (v[i] <= b) {
r = i;
break;
}
}
for (int i = l; i < r; i++) d[i] = v[i + ] - v[i];
d[r] = b > v[r] ? b - v[r] : ;
s[r] = d[r], s[r - ] = d[r - ];
for (int i = r - ; i >= l; i--) s[i] = s[i + ] + d[i];
long long ans = ;
for (int i = l; i <= r; i++) {
long long pl, pr;
if (i == l) pl = v[l] - a + ;
else pl = d[i - ];
pr = s[i + ];
ans += pl * pr;
}
ans += (v[l] - a) * (v[l] - a + ) / ;
ans += (b - v[r]) * (b - v[r] + ) / ;
for (int i = l; i < r; i++) ans += (d[i] - ) * d[i] / ;
printf("%lld\n", ans);
return ;
}