#include <bits/stdc++.h>
int a[1100];
int b[100];
int len;
void init() {
int i = 1, tot = 1;
while (tot <= 1010) {
int t = i, c = 0;
while (t) {
b[c++] = t % 10;
t /= 10;
}
for (int i=c-1; i>=0; --i) {
a[tot++] = b[i];
}
i++;
}
}
int main() {
init ();
int n; scanf ("%d", &n);
printf ("%d", a[n]);
return 0;
}
题意：问最少改变多少个字母使得该字符串的所有子串不相同
分析：子串有长度为１的，所以如果字符串长度大于２６一定不可行，否则就把相同的字母用没出现的字母替换．
#include <bits/stdc++.h>
const int N = 1e5 + 5;
char str[N];
int vis[30];
int main() {
int n; scanf ("%d%s", &n, str);
if (n > 26) {
puts ("-1");
} else {
int ans = 0;
for (int i=0; i<n; ++i) {
if (vis[str[i]-'a']) {
ans++;
} else {
vis[str[i]-'a'] = true;
}
}
printf ("%d
", ans);
}
return 0;
}
几何＋贪心 C - Recycling Bottles
题意：Ａ和Ｂ捡罐头，每次只能捡一个然后到垃圾桶去，再从垃圾桶出发去捡，问捡完所有罐头所需的最少总路程
分析：除从Ａ或Ｂ出发第一次捡罐头的距离不确定外，其他的都可以看成sum (dis (T, p[i]) ＊２)，所以只需要 min (-dis (T, p[i]) + dis (A, p[i]))．因为Ａ和Ｂ捡罐头是独立的，只要Ａ和Ｂ都捡一个罐头使得差值最小，重复时特判下就行了．更一般的做法是Ａ任意选择一个罐头，Ｂ选择除Ａ选的外里最小差值的那一个，可以预处理出前缀最小和后缀最小．
#include <bits/stdc++.h>
const int N = 1e5 + 5;
const double INF = 1e18 + 5;
const double EPS = 1e-8;
struct Point {
double x, y;
Point() {}
Point(double x, double y) {
this->x = x;
this->y = y;
}
}point[N];
Point A, B, O;
double dis[N];
double sum;
double pre[N], suff[N];
double add[N];
int n;
Point read_point() {
double x, y; scanf ("%lf%lf", &x, &y);
return Point (x, y);
}
double squ(double x) {
return x * x;
}
double calc_dis(Point a, Point b) {
return sqrt (squ (a.x - b.x) + squ (a.y - b.y));
}
int main() {
A = read_point ();
B = read_point ();
O = read_point ();
scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
point[i] = read_point ();
dis[i] = calc_dis (point[i], O);
pre[i] = suff[i] = -dis[i] + calc_dis (point[i], B);
add[i] = -dis[i] + calc_dis (point[i], A);
sum += dis[i] * 2;
}
pre[0] = suff[n+1] = INF;
for (int i=1; i<=n; ++i) {
pre[i] = std::min (pre[i], pre[i-1]);
}
for (int i=n; i>=1; --i) {
suff[i] = std::min (suff[i], suff[i+1]);
}
double ans = sum + suff[1]; //just B
for (int i=1; i<=n; ++i) {
ans = std::min (ans, sum + std::min (0.0, std::min (pre[i-1], suff[i+1])) + add[i]);
}
printf ("%.12f
", ans);
return 0;
}
题意：ｎ个人，ｋ次操作，每次把最大的数分１到最小的数，问ｋ次后最大值和最小值的差
分析：二分最小值和最大值，思想是求出min(max) 刚好使得小于它的到它的操作正好是ｋ．处理好二分的边界，因为二分时是尽量使得最小值大，最大值小．
#include <bits/stdc++.h>
typedef long long ll;
const int N = 5e5 + 5;
int a[N];
int n, k;
bool check(int val, int op) {
ll need = 0;
for (int i=0; i<n; ++i) {
if (op == 1) {
if (a[i] <= val) {
need += val - a[i];
} else {
break;
}
} else if (op == 2 && a[i] >= val) {
need += a[i] - val;
}
}
return need <= k;
}
int main() {
scanf ("%d%d", &n, &k);
ll sum = 0;
for (int i=0; i<n; ++i) {
scanf ("%d", a+i);
sum += a[i];
}
std::sort (a, a+n);
int ansl = -1, ansr = 1e9;
int left = a[0], right = sum / n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check (mid, 1)) {
ansl = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
left = sum / n;
if (sum % n) {
left++;
}
right = a[n-1];
while (left <= right) {
int mid = left + (right - left) / 2;
if (check (mid, 2)) {
ansr = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
printf ("%d
", ansr - ansl);
return 0;
}