NewOJ Week 10题解

比赛链接：http://oj.ecustacm.cn/contest.php?cid=1026

题意：

Tag： 思维题

难度： ☆

思路： 每次操作要么拿走石子，要么挪动石子，可以进行任意次。

这说明操作后的 B B B数组的石子总数，只要不超过 A A A的总数即可。

#include
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        int suma = 0, x, sumb = 0;
        for(int _ = 1; _ <= n; _++)
            cin >> x, suma += x;
        for(int _ = 1; _ <= n; _++)
            cin >> x, sumb += x;
        if(suma >= sumb)puts("Yes");
        else puts("No");
    }
    return 0;
}

题意：

Tag： 二进制枚举

难度： ☆☆

思路： 二进制枚举答案的所有情况，每道题目有两种可能 T T T或者 F F F，总共存在 2 k 2^{k} 2k种情况。对于每种情况暴力求一下最低分，再让最低分最高即可。

#include
using namespace std;

int main()
{
    int n, k, res = 0;
    cin >> n >> k;
    vectors(n);
    for(auto &x : s)cin >> x;
    for(int i = 0; i < (1 << k); i++)//二进制枚举所有答案的情况
    {
        //对于每种情况，求解最低分
        int cur_min = k;
        for(auto x : s)
        {
            int cur_score = 0;
            for(int j = 0; j < k; j++)
                if((x[j] == 'F') ^ (1 & (i >> j))) //1 ^ 0 || 0 ^ 1
                    cur_score++;
            cur_min = min(cur_min, cur_score);
        }
        res = max(res, cur_min);
    }
    cout< 
C 袋鼠聚会 
题意：
 
 
Tag： 枚举
 
难度： ☆☆
 
思路： 直接按照题意枚举模拟即可。枚举第一个、第二个袋鼠家，然后计算一下答案即可。
 
#include
using namespace std;

int main()
{
    int n;
    vector houses;
    int cost, best_cost = -1;
    cin >> n;
    // read kangaroo info
    houses = vector(n);
    for (int i = 0; i < n; i++)
        cin >> houses[i];
    // try all possible pairs of host kangaroos
    for (int i = 0; i < n; i++)     //first host
    {
        for (int j = i; j < n; j++)     //second host
        {
            //compute cost for these hosts
            cost = 0;
            for (int k = 0; k < n; k++)
            {
                if (abs(houses[k] - houses[i]) < abs(houses[k] - houses[j]))
                    cost += pow(houses[k] - houses[i], 2);
                else
                    cost += pow(houses[k] - houses[j], 2);
            }
            // if energy cost for this host pair is better than current best,
            // save this as new solution
            if (cost < best_cost || best_cost == -1)
                best_cost = cost;
        }
    }
    // print lowest possible energy cost
    cout << best_cost << endl;
}
 
D 单峰数组 
题意：
 
 
Tag： 离散化、树状数组、贪心
 
思路： 由于题目对数字具体大小是无关的，只和数字间的相对关系有关，因此可以首先对数组
    
     
      
       
        a
       
      
      
       a
      
     
    a进行离散化。
 
此时
    
     
      
       
        a
       
      
      
       a
      
     
    a是一个
    
     
      
       
        1
       
       
        −
       
       
        n
       
      
      
       1-n
      
     
    1−n的排列，要把
    
     
      
       
        a
       
      
      
       a
      
     
    a变成题目给定的单峰数组——先递增、后递减。这说明对于最小的数字来说，要么在开头，要么在结尾。
 
这样我们可以从小到大遍历
    
     
      
       
        1
       
       
        −
       
       
        n
       
      
      
       1-n
      
     
    1−n，对于每个当前的数字
    
     
      
       
        i
       
      
      
       i
      
     
    i来说，要么将其放在递增的尾部，要么放在递减的开头，每次贪心地选择一个更优的。
 
每次选择如何计算贡献？假设数字
    
     
      
       
        i
       
      
      
       i
      
     
    i对应的下标为
    
     
      
       
        i
       
       
        d
       
       
        x
       
      
      
       idx
      
     
    idx。
 
如果放在递增的尾部，则交换次数=
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        i
       
       
        d
       
       
        x
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       [1,idx-1]
      
     
    [1,idx−1]中比数字
    
     
      
       
        i
       
      
      
       i
      
     
    i大的数字数量，记为
    
     
      
       
        b
       
       
        e
       
       
        f
       
       
        o
       
       
        r
       
       
        e
       
      
      
       before
      
     
    before（因为数字比
    
     
      
       
        i
       
      
      
       i
      
     
    i更小的已经排列好了），利用树状数组动态维护即可。
 
如果放在递减的开头，则交换次数=
    
     
      
       
        [
       
       
        i
       
       
        d
       
       
        x
       
       
        +
       
       
        1
       
       
        ,
       
       
        n
       
       
        ]
       
      
      
       [idx+1,n]
      
     
    [idx+1,n]中比数字
    
     
      
       
        i
       
      
      
       i
      
     
    i大的数字数量，总共有
    
     
      
       
        n
       
       
        −
       
       
        i
       
      
      
       n-i
      
     
    n−i个数字大于
    
     
      
       
        i
       
      
      
       i
      
     
    i，前面大的数字由
    
     
      
       
        b
       
       
        e
       
       
        f
       
       
        o
       
       
        r
       
       
        e
       
      
      
       before
      
     
    before个，后面还剩下
    
     
      
       
        n
       
       
        −
       
       
        i
       
       
        −
       
       
        b
       
       
        e
       
       
        f
       
       
        o
       
       
        r
       
       
        e
       
      
      
       n-i-before
      
     
    n−i−before个。
 
#include
using namespace std;
const int maxn = 300000 + 10;
int n, a[maxn], b[maxn], tree[maxn], pos[maxn];
inline int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int d)
{
    while(x <= n)
        tree[x] += d, x += lowbit(x);
}

int query(int x)
{
    int res = 0;
    while(x)
        res += tree[x], x -= lowbit(x);
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++)
    {
        //离散化
        a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
        //记录每个数字的idx
        pos[a[i]] = i;
        //初始化树状数组：树状数组的下标是这里的idx
        update(i, 1);
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int idx = pos[i];
        int before = query(idx - 1);    //利用树状数组求before
        int after = n - i - before;
        ans += min(before, after);      //贪心选择最优的
        update(idx, -1);                //更新树状数组
    }
    cout< 
E 彩虹数 
题意：
 
 
Tag： 数位
    
     
      
       
        D
       
       
        P
       
      
      
       DP
      
     
    DP
 
难度： ☆☆☆☆
 
思路： 数位DP经典做法，求区间
    
     
      
       
        [
       
       
        L
       
       
        ,
       
       
        R
       
       
        ]
       
      
      
       [L,R]
      
     
    [L,R]中彩虹数数量相当于
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        R
       
       
        ]
       
      
      
       [1,R]
      
     
    [1,R]的数量减去
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        L
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       [1,L-1]
      
     
    [1,L−1]的数量。
 
利用记忆化搜索的数位
    
     
      
       
        D
       
       
        P
       
      
      
       DP
      
     
    DP求解
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        n
       
       
        ]
       
      
      
       [1,n]
      
     
    [1,n]中彩虹数数量。
 
需要维护：当前第几位、上一位数字、前导
    
     
      
       
        0
       
      
      
       0
      
     
    0、是否达到上限。
 
对于彩虹数只需要约束当前枚举的数字不等于上一位数字即可。注意当前面都是前导
    
     
      
       
        0
       
      
      
       0
      
     
    0时这个条件可以不满足。
 
注意，代码中直接用
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        R
       
       
        ]
       
      
      
       [1,R]
      
     
    [1,R]的答案减去
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        L
       
       
        ]
       
      
      
       [1,L]
      
     
    [1,L]的答案，所以需要特判一下左端点是否为彩虹数。
 
#include
using namespace std;
typedef long long ll;
const int MOD = 998244353;

string L, R;
int dp[100001][10][2][2];
//n:当前第几位、lastdig：上一位、nonzero：没有前导0、limit：达到上限
ll dfs(int n, int lastdig, bool nonzero, bool limit, string& s)
{
    if(n == s.size())return 1;
    int &res = dp[n][lastdig][nonzero][limit];
    if(res)return res;
    int up = limit ? s[n] - '0' : 9;
    for(int i = 0; i <= up; i++)
    {
        if (i == lastdig && nonzero) continue;  //彩虹数限制
        res = (res + dfs(n + 1, i, nonzero || (i != 0), limit && i == up, s)) % MOD;
    }
    return res;
}

int main()
{
    cin >> L >> R;
    ll ans_L = dfs(0, 0, 0, 1, L);
    memset(dp, 0, sizeof(dp));
    ll ans_R = dfs(0, 0, 0, 1, R);
    ll ans = (ans_R + MOD - ans_L) % MOD;
    bool L_ok = true;
    for(int i = 1, last = L[0]; i < L.size() && L_ok; last = L[i++])
        if(L[i] == last)L_ok = false;
    cout<