模拟　

#include 
     
      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 
     
      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
     

几何＋贪心　

题意：Ａ和Ｂ捡罐头，每次只能捡一个然后到垃圾桶去，再从垃圾桶出发去捡，问捡完所有罐头所需的最少总路程

分析：除从Ａ或Ｂ出发第一次捡罐头的距离不确定外，其他的都可以看成sum (dis (T, p[i]) ＊２)，所以只需要 min (-dis (T, p[i]) + dis (A, p[i]))．因为Ａ和Ｂ捡罐头是独立的，只要Ａ和Ｂ都捡一个罐头使得差值最小，重复时特判下就行了．更一般的做法是Ａ任意选择一个罐头，Ｂ选择除Ａ选的外里最小差值的那一个，可以预处理出前缀最小和后缀最小．

#include 
     
      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\n", ans);    return 0;}
     

二分　

题意：ｎ个人，ｋ次操作，每次把最大的数分１到最小的数，问ｋ次后最大值和最小值的差

分析：二分最小值和最大值，思想是求出min(max) 刚好使得小于它的到它的操作正好是ｋ．处理好二分的边界，因为二分时是尽量使得最小值大，最大值小．

#include 
     
      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
      
       = val) {            need += a[i] - val;        }    }    return need <= k;}int main() {    scanf ("%d%d", &n, &k);    ll sum = 0;    for (int i=0; i