在家补补题

 

模拟 

#include 
     
      char str[202];void move(int &x, int &y, char ch)  {    if (ch == 'U')  x--;    if (ch == 'D')  x++;    if (ch == 'L')  y--;    if (ch == 'R')  y++;}int main(void)  {    int n;  scanf ("%d", &n);    scanf ("%s", &str);    int ans = 0;    for (int i=0; i
     

暴力 || 找规律 

暴力即DFS也行。。。当时就if else乱写一堆过了

#include 
     
      char str[202];int col[3];int main(void)  {    int n;  scanf ("%d", &n);    scanf ("%s", &str);    col[0] = col[1] = col[2] = 0;    for (int i=0; i
     

暴力 

直接枚举答案，同时记录能整除2，整除2和3，只能整除3的个数，当遇到满足条件的就是最优。二分也行。。

#include 
     
      const int N = 4e6 + 5;int main(void)  {    int n, m;   scanf ("%d%d", &n, &m);    int best = 4000000;    int c1 = 0, c2 = 0, c3 = 0;    for (int i=2; i<=4000000; ++i) {        if (i % 2 == 0) c1++;        if (i % 2 == 0 && i % 3 == 0)   c2++;        if (i % 2 != 0 && i % 3 == 0) c3++;        if (c1 >= n && c2 >= m - c3 && c1 - (m - c3) >= n)  {            best = i;   break;        }    }    printf ("%d\n", best);    return 0;}
     

暴力+概率 

题意：已知结果两胜一负，问总和小于后者的概率。

分析：预处理出任意两个数字相减的差的方案数，那么前两次在正数选，后者只要能使得总和小的可以处理前缀和，O (1)，总复杂度 O (n ^ 2)。

#include 
     
      const int N = 2e3 + 5;int a[N];int cnt[10005];int sum[5005];int main(void)  {    int n;  scanf ("%d", &n);    for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);    for (int i=1; i<=n; ++i)    {        for (int j=1; j<=n; ++j)    {            if (i == j) continue;            cnt[5000+a[i]-a[j]]++;        }    }    for (int i=1; i<=5000; ++i) {        sum[i] = sum[i-1] + cnt[i];    }    double ans = 0;    for (int i=5001; i<=9999; ++i)  {        if (!cnt[i])    continue;        for (int j=5001; j<=9999; ++j)  {            if (!cnt[j])    continue;            int c = 15000 - (i + j) - 1;            if (c < 1 || c > 4999 || !sum[c])  continue;            ans += 1.0 * cnt[i] * cnt[j] * sum[c];        }    }    double div = 1.0 * (n * (n - 1) / 2);    ans = ans / div / div / div;    printf ("%.8f\n", ans);    return 0;}
     

三分 + 贪心 

题意：选取一个子集使得平均数-中位数最大

分析：首先个数是奇数，如果是偶数，去掉中间较大的数，差会变大(?)。然后排序后，枚举中位数的位置，三分长度，因为差的分布是单峰，选的数字使差尽可能大，右边选择最后几个，左边选取靠近中位数的几个。

#include 
     
      typedef long long ll;const int N = 2e5 + 5;struct Pair {    ll a;   int b;    bool operator < (const Pair &rhs) const {        return a * rhs.b < rhs.a * b;    }};int a[N];ll sum[N];int n, bi, bl;Pair best;Pair get(int id, int len)   {    ll val = sum[id] - sum[id-len-1];    val += sum[n] - sum[n-len];    Pair cur = Pair {val, 2 * len + 1};    cur.a -= 1ll * a[id] * cur.b;    if (best < cur) {        best = cur;        bi = id;    bl = len;    }    return cur;}int main(void)  {    scanf ("%d", &n);    for (int i=1; i<=n; ++i)    {        scanf ("%d", a + i);    }    std::sort (a+1, a+1+n);    for (int i=1; i<=n; ++i)    {        sum[i] = sum[i-1] + a[i];    }    bi = 1; bl = 0;    best = Pair {0, 1};    for (int i=1; i<=n; ++i)    {        int low = 0, high = std::min (i - 1, n - i);        while (low + 3 < high)  {            int mid1 = (2 * low + high) / 3;            int mid2 = (low + 2 * high) / 3;            Pair v1 = get (i, mid1);            Pair v2 = get (i, mid2);            if (v1 < v2)    low = mid1;            else    high = mid2;        }        for (int j=low; j<=high; ++j)   get (i, j);    }    std::vector
      
        ans;    for (int i=bi-bl; i<=bi; ++i)   {        ans.push_back (a[i]);    }    for (int i=n-bl+1; i<=n; ++i)  {        ans.push_back (a[i]);    }    printf ("%d\n", ans.size ());    for (int i=0; i
       
         0)  putchar (' ');        printf ("%d", ans[i]);    }    puts ("");    return 0;}　
       
      
     

DP 

题意：n个数字分组，求每组最大值-最小值的和小于k的方案数

分析：明显的DP，复杂度肯定是 O (n ^ 2 * k)，难在状态的转移。dp[i][j][k] 考虑前i个数字，open(只知道最小值，最大值未知)了j组，当前累计和为k的方案数。那么open的几组暂时由a[i]"托管"，之前是a[i-1]“托管”，那么前后转移累加j * (a[i] - a[i-1])，a[i]有好几种选择，可以close一个组，选择一个组自己为最大值，j - 1；可以多一个组，自己为最小值，j+1；还可以进入某一个组(自己不是最大值)或者自己一个数字成为一个组(不算open)。

#include 
     
      const int N = 2e2 + 5;const int K = 1e3 + 5;const int MOD = 1e9 + 7;int a[N];int dp[2][N][K];void add(int &x, int y) {    x += y;    if (x >= MOD)   x %= MOD;}int main(void)  {    int n, m;   scanf ("%d%d", &n, &m);    for (int i=1; i<=n; ++i)    scanf ("%d", a + i);    std::sort (a+1, a+1+n);    int now = 0;    dp[now][0][0] = 1;    for (int i=1; i<=n; ++i)    {        now ^= 1;        memset (dp[now], 0, sizeof (dp[now]));        for (int j=0; j
      
        m)  continue;                add (dp[now][j][s], 1ll * x * (j + 1) % MOD);                add (dp[now][j+1][s], x);                if (j)  add (dp[now][j-1][s], 1ll * x * j % MOD);            }        }    }    int ans = 0;    for (int i=0; i<=m; ++i)    add (ans, dp[now][0][i]);    printf ("%d\n", ans);    return 0;}