同时也是 LETTers 2015 Summer II round 01 - D

#include <cstdio>
#include <iostream>
#include <algorithm>

#define lld I64d

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL s[N];

int main()
{
    int n;
    LL h;

    //freopen("D.in", "r", stdin);
    scanf("%d%lld", &n, &h);
    scanf("%d", &s[0]);
    int t = s[0], index = 0;
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &s[i]);
        if (s[i] < t)
        {
            t = s[i];
            index = i;
        }
    }

    sort(s, s+n);
    LL maxsum = max(s[n-1]+s[n-2], s[n-1]+s[0]+h);
    LL minsum = min(s[0]+s[1]+h, s[1]+s[2]);
    LL rec1 = maxsum - minsum;
    LL rec2 = s[n-1]+s[n-2]-(s[0]+s[1]);
    if (rec1 < rec2)
    {
        printf("%lld\n", rec1);
        for (int i = 0; i < n - 1; i++)
        {
            if (i != index)
            {
                printf("1 ");
            }
            else
            {
                printf("2 ");
            }
        }

        if (n - 1 != index)
        {
            printf("1\n");
        }
        else
        {
            printf("2\n");
        }
    }
    else
    {
        printf("%lld\n", rec2);
        for (int i = 0; i < n - 1; i++)
        {
            printf("1 ");
        }
        printf("1\n");
    }


    return 0;
}

同时也是 LETTers 2015 Summer II round 01 - B

#include <cstdio>
#include <iostream>

#define lld I64d

using namespace std;

const int MOD = 1e9 + 7;
const int N = 100 + 5;

typedef long long LL;

LL C[N][N], dp[N][N*N], f[N][2];


LL pow(LL a,LL x)
{
    LL res = 1;
    for(; x; x>>=1, (a*=a)%=MOD)
    {
        if(x & 1)
        {
            (res*=a) %= MOD;
        }
    }
    return res;
}

int main()
{
    LL n, m, k, cnt, rem;

    //freopen("B.in", "r", stdin);
    scanf("%lld%lld%lld", &n, &m, &k);

    cnt = m / n;
    rem = m % n;
    C[0][0] = 1;
    for(int i = 1; i < N; i++)
    {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
        {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
    for(int i = 0; i <= n; i++)
    {
        f[i][0] = pow(C[n][i], cnt);
        f[i][1] = pow(C[n][i], cnt + 1);
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            dp[i][j] = 0;
            for(int r = 0; r <= n; r++)
            {
                if(r > j)
                {
                    break;
                }
                dp[i][j] += f[r][(i <= rem)] * dp[i - 1][j - r] % MOD;
                dp[i][j] %= MOD;
            }
        }

    }

    printf("%lld\n", dp[n][k]);


    return 0;
}

同时也是 LETTers 2015 Summer II warm-up - D

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int a[N];

int main()
{
    int n, rec, x;

    //freopen("D.in", "r", stdin);
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        rec = min(i, n-i-1);
        scanf("%d", &x);
        x = x - rec;
        if (x > 0)
        {
            a[x]++;
        }
    }
    for (int i = 1; i <= 100000; i++)
    {
        rec = max(rec, a[i]);
    }

    printf("%d\n", n-rec);

    return 0;
}

同时也是 LETTers 2015 Summer II warm-up - B

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL rec;

LL a[N], l[20];

int main()
{
    int n;

    //freopen("B.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < 20; i++)
    {
        l[i] = 1 << i;
    }

    for (int i = 1; i <= 100000; i++)
    {
        for (int j = 19; j >= 0; j--)
        {
            if (i + l[j] <= n)
            {
                a[i+l[j]] += a[i];
                break;
            }
        }
    }

    rec = 0;
    for (int i = 1; i < n; i++)
    {
        rec += a[i];
        printf("%lld\n", rec);
    }

    return 0;
}

同时也是 LETTers 2015 Summer II warm-up - A

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int N = 3e4 + 5;

vector <int> g[N];
int r[N] = {0};
bool f[N] = {false};
int j = 0;

void dfs(int u);

int main()
{
    int n, m, a, b;

    //freopen("A.in", "r", stdin);
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!f[i])
        {
            f[i] = true;
            dfs(i);
        }
    }

    for (int i = 0; i < j - 1; i++)
    {
        printf("%d ", r[i]);
    }
    printf("%d\n", r[j-1]);

    return 0;
}

void dfs(int u)
{
    int v;

    for (int i = 0; i < g[u].size(); i++)
    {
        v = g[u][i];
        if (!f[v])
        {
            f[v] = true;
            dfs(v);
        }
    }
    r[j++] = u;
}