正文

题目1

题目链接
题目大意：
给出正整数n，求整数1到整数n之中，有多少整数是由单一的字符组成，比如说1 , 77, 777, 44 和 999999 就是符合要求的整数。
整数1到18中，只有 1, 2, 3, 4, 5, 6, 7, 8, 9 和 11符合要求。

输入：
第一行整数𝑡，表示有t个样例 (1≤𝑡≤1e4)
每个样例一行，𝑛 (1≤𝑛≤1e9)

输出：
每个样例一行，输出1到n之间有多少个数字符合要求。

input
6
18
1
9
100500
33
1000000000

output
10
1
9
45
12
81

题目解析：
纯暴力枚举，则是从1、2、3开始算，把每个数字拆解成字符串数组，然后判断数字是否相同的；
但是由于n=1e9，数据量较大，容易在字符串转化的过程中超时。

换一种思路，只枚举符合要求的部分，比如说先考虑1位数、再考虑2位数、然后是3位数，知道数字比n大。

char a[N];

int main(int argc, const char * argv[]) {
    // insert code here...
    int t;
    cin >> t;
    while (t--) {
        cin >> a;
        int n = strlen(a);
        
        int ans = (n - 1) * 9 + (a[0] - '0');
        int ok = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] < a[0]) {
                ok = 0;
                break;
            }
            else if (a[i] > a[0]) {
                ok = 1;
                break;
            }
        }
        if (!ok) {
            --ans;
        }
        
        cout << ans << endl;
    }
           
    
    return 0;
}

题目2

题目链接
题目大意：
给出n个整数 𝑎1,𝑎2,…,𝑎𝑛；
每次可以选择一个偶数c，将数组中所有等于c的数字除以2；
比如说数组[6,8,12,6,3,12] 选择数字6，将6除以2之后得到[3,8,12,3,3,12]
问现在最少需要操作多少次，才能将所有的数字转化成奇数；

输入：
第一行整数𝑡，表示有t个样例 (1≤𝑡≤1e4)
每个样例有2行：
第一行整数𝑛 (1≤𝑛≤2⋅1e5)
第二行𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)

输出：
每个样例一行，输出最小的操作次数。

input
4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7
output
4
10
4
0

题目解析：
每次可以选择一个数字x，将数组所有的x=x/2;

通过贪心的思想可以知道，每次会选择最大的数字开始贪心；
并且数字出现个数的多少没有影响，那么可以采用这样的策略：
1、把数组中的数字排序，从大到小开始遍历；
2、每次拿出最大的数字，如果是奇数则直接通过；如果是偶数，则需要++ans，进入第3步；
3、判断原来数组里面是否有这个数字；如果有对应数字，则直接通过；如果没有出现过x/2，则把x/2放回数组；
循环处理，直到结束。

int a[N];
map<int, int> h;
vector<int> s;
priority_queue<int> q;

int main(int argc, const char * argv[]) {
    // insert code here...
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        h.clear();
        while (!s.empty()) {
            s.pop_back();
        }
        
        for (int i = 0; i < n; ++i) {
            int k;
            scanf("%d", &k);
            ++h[k];
        }
        
        for (map<int, int>::iterator iter = h.begin(); iter != h.end(); ++iter) {
            q.push(iter->first);
        }
        
        int ans = 0;
        while (!q.empty()) {
            int top = q.top();
            q.pop();
            if (top % 2 == 0) {
                if (!h[top/2]) {
                    q.push(top / 2);
                }
                ++ans;
            }
        }
        
        cout << ans << endl;
        
    }
           
    
    return 0;
}

题目3

题目链接
题目大意：
给出一个字符串s，现在不希望字符串里面出现one和two这两个单词，比如说"oneee", "ontwow", "twone" and "oneonetwo"都是不好的字符串。
现在可以从字符串中选择若干个位置，去掉这些位置上的字符。
问最少去掉多少个字符。

输入：
第一行𝑡，表示t个样例 (1≤𝑡≤1e4)
每个样例一行，字符串s，长度不超过 1.5⋅1e5

输出：
每个样例2行
第一行，整数k表示需要去掉k个位置
第二行，k个整数，表示k个需要去掉字符的位置。

input
4
onetwone
testme
oneoneone
twotwo

output
2
6 3
0

3
4 1 7
2
1 4

题目解析：
对于某个字符结尾，可能有normal、o、on、t、tw这几种情况，分别表示为状态0、1、2、3、4；
那么dp[i][j]表示，第i个字符，以状态j结尾时，需要去掉的最少字符数量；

对于第i个字符，都可以有dp[i][j] = dp[i-1][j] + 1;
同时，根据字符内容，有特定的转移方案，这部分转移方程较多，可以直接思考代码。

思考🤔：
这个题目也可以使用贪心的做法，假如只有one这个单词，那么直接去掉n是最优解：因为去掉头尾会有oone和onee的bad case存在，去掉n会直接破坏one这个单词；
但是由于有两个字符存在，会导致出现twone的情况导致去掉n仍然存在two的情况；针对这种特殊情况，是需要去掉中间的o；
这种贪心的做法相对动态规划比较容易实现。

string a;
int dp[N][5];
pair<int, int> last[N][5];

void compare(int i, int j, int x, int y) {
    if (dp[i][j] > dp[x][y]) {
        dp[i][j] = dp[x][y];
        last[i][j] = make_pair(x, y);
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int t;
    cin >> t;
    while (t--) {
        cin >> a;
        int n = (int)a.length();
        
        for (int j = 0; j < 5; ++j) {
            dp[0][j] = n;
            last[0][j] = make_pair(0, 0);
        }
        if (a[0] == 'o') {
            dp[0][1] = 0;
        }
        else if (a[0] == 't') {
            dp[0][3] = 0;
        }
        else {
            dp[0][0] = 0;
        }
        
        for (int i = 1; i < n; ++i) {
            // 不取a[i]
           for (int j = 0; j < 5; ++j) {
               dp[i][j] = dp[i - 1][j] + 1;
               last[i][j] = make_pair(i - 1, j);
            }
            
            // 取a[i]， normal、o、on、t、tw这几种情况，分别表示为状态0、1、2、3、4；
            if (a[i] == 'o') {
                compare(i, 1, i-1, 0);
                compare(i, 1, i-1, 1);
                compare(i, 1, i-1, 2);
                compare(i, 1, i-1, 3);
            }
            else if (a[i] == 'n') {
                compare(i, 2, i - 1, 1);
                
                compare(i, 0, i-1, 0);
                compare(i, 0, i-1, 2);
                compare(i, 0, i-1, 3);
                compare(i, 0, i-1, 4);
            }
            else if (a[i] == 't') {
                compare(i, 3, i-1, 0);
                compare(i, 3, i-1, 1);
                compare(i, 3, i-1, 2);
                compare(i, 3, i-1, 3);
                compare(i, 3, i-1, 4);
            }
            else if (a[i] == 'w') {
                compare(i, 4, i-1, 3);
                
                compare(i, 0, i-1, 0);
                compare(i, 0, i-1, 1);
                compare(i, 0, i-1, 2);
                compare(i, 0, i-1, 4);
            }
            else if (a[i] == 'e') {
                compare(i, 0, i-1, 0);
                compare(i, 0, i-1, 1);
                compare(i, 0, i-1, 3);
                compare(i, 0, i-1, 4);
            }
            else {
                compare(i, 0, i-1, 0);
                compare(i, 0, i-1, 1);
                compare(i, 0, i-1, 2);
                compare(i, 0, i-1, 3);
                compare(i, 0, i-1, 4);
            }
        }
        long index = min_element(dp[n - 1], dp[n - 1] + 5) - dp[n - 1];
        
        cout << dp[n-1][index] << endl;
        
        long x = n - 1, y = index;
        while (x != 0 || y != 0) {
            pair<int, int> fp = last[x][y];
            if (dp[fp.first][fp.second] < dp[x][y]) {
                printf("%d ", x + 1);
            }
            x = fp.first, y = fp.second;
        }
        puts("");
    }
           
    
    return 0;
}

题目4

题目链接
题目大意：
一个整数是2的x次幂，或者是x的阶乘，那么这个数字是powerful的；
现在给出一个整数n，希望由若干个powerful的整数相加来得到n，要求：
1、没有相同的powerful整数；
2、powerful整数尽可能少；

输入：
第一行样例数𝑡 (1≤𝑡≤100).
接下来每个样例一行𝑛 (1≤𝑛≤1e12).

输出：
能相加得到n的最少powerful整数的数量，如果没有答案则输出-1；

Examples
input
4
7
11
240
17179869184
output
2
3
4
1

题目解析：
首先把powerful的整数枚举取出来：
2的x次幂：1、2、4、8、16、32、64、128等；
x的阶乘：1、2、6、24、120等；
这两部分数字可以通过hash去重，得到1、2、4、8、16、24、32、64、120、128等；
题目的要求就是从这些数字中选出最少的数字，来组成整数n；
n个物品的选择来形成特定大小，这个是典型的动态规划问题，但是如果用背包的解法，会由于状态数过多而超时；

仔细分析题目，2的x次幂这部分数字，其实已经可以足够组成任意数字；
那么题目就变成了，要在阶乘中选择多少个数字来组成n，剩下的部分可以有2的x次幂来组成（并且这部分的最优解就是数字的二进制位数）；
阶乘递增比较快，在15!的时候就超过了题目要求，再减去最开始的阶乘1和2，最终可以不超过2^13=8000左右种结果；
枚举这些结果，结合剩下数字的二进制长度，来得到最优解；

class Solution {
   static const int N = 10010;
   string str;
   vector<lld> num;
   
   lld count(lld n) {
       lld ret = 0;
       while (n) {
           ret += n % 2;
           n /= 2;
       }
       return ret;
   }

public:
   void solve() {
       int t;
       cin >> t;
       
       lld tmp = 2;
       for (int i = 3; i < 15; ++i) {
           tmp *= i;
           num.push_back(tmp);
       }
       
       while (t--) {
           lld n;
           cin >> n;
           lld ans = n;
           for (int i = 0; i < (1 << num.size()); ++i) {
               lld sum = 0;
               lld index = 0;
               int tmp = i;
               while (tmp) {
                   if (tmp % 2) {
                       sum += num[index];
                   }
                   tmp /= 2;
                   ++index;
               }
               if (sum <= n) {
                   ans = min(ans, count(i) + count(n - sum));
               }
           }
           cout << ans << endl;
       }
   }
}
ac;

题目5

题目链接
题目大意：
给出一个有n个节点的树，现在可以把1、2、3·····n的整数赋值到每一个节点上；
一个节点可以被称为good节点，如果它满足：相邻点的数字之和等于自己节点的数字；
现在需要给每个节点赋值，要求整棵树有尽可能多的good节点，如果有多种方案则输出数字和最小的方案；

输入：
第一行𝑛 (2≤𝑛≤2e5)
接下来有n-1行，每行两个整数 𝑢 and 𝑣 表示相邻的节点(1≤𝑢,𝑣≤𝑛)

输出：
先输出最多的good节点数和总的数字和；
接下来n个数字， 𝑤1,𝑤2,…,𝑤𝑛分别表示n个节点的数字 (1≤𝑤𝑖≤1e9)

Examples
input
2
1 2
output
2 2
1 1
input
9
3 4
7 6
2 1
8 3
5 6
1 8
8 6
9 6
output
6 11
1 1 1 1 1 1 1 3 1

题目解析：
由题目的要求，首先要求是尽可能多的good节点，那么叶子节点肯定都会标位1；
其次叶子的相邻节点也一定是1（为了满足good节点的要求），如果有节点和两个叶子相邻节点连接，那么这个节点也有机会成为good节点，如下：
五个连乘一条直线节点：1-1-2-1-1

由此我们知道，每个节点有两种状态isGood=1和0，信息有maxNode子树最大节点数，minWeight子树最小数字和；
而且我们按照题目可以得到两个状态转移的条件，对于节点u：
1、假如u是good节点，那么和u相邻的节点一定不是good节点；
2、假如u不是good节点，那么和u相邻的节点可以是good节点，也可以不是good节点；

由于上面的条件2，我们知道这个题目无法使用贪心的思想，因为贪心需要决策路径是唯一的，但是由于非good节点节点是可以相邻的，导致出现了分支；
针对这个情况，我们可以用动态规划来解决。
首先设定好状态，pair<int, int> dp[n][2]：n个节点，每个节点有2个状态，每个节点需要关注两个信息；
dp[i][0]表示第i个节点不为good的子树最优解，dp[i][1]为第i个节点为good的子树最优解，first是good数，second是子树和；
再由上面的状态转移条件，可以得到转移方程。

接着从节点1开始dfs，对于每一个节点u和字节点v，计算得到dp[u][0]和dp[u][1]；
同时需要记录动态规划的决策过程，因为最终答案还要回溯决策，从而得到结果。

思考🤔：
这个题目的输出略微麻烦，但是记录清楚决策分支，再用dfs回溯还是可以解决的。

class Solution {
    static const int N = 200010;
    vector<int> g[N];
    int vis[N];
    vector<int> last[N];
    int ans[N];
    pair<int, int> dp[N][2]; // dp[i][0]表示第i个节点不为good的子树最优解，dp[i][1]为第i个节点为good的子树最优解，first是good数，second是子树和
    void add_pair(pair<int, int> &x, pair<int, int> &y) {
        x.first += y.first;
        x.second += y.second;
    }
    
    bool cmp_pair(pair<int, int> &x, pair<int, int> &y) {
        return x.first > y.first || (x.first == y.first && x.second < y.second);
    }
    
    void dfs(int u) {
        vis[u] = 1;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (!vis[v]) {
                dfs(v);
            }
        }
        
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (cmp_pair(dp[v][0], dp[v][1])) {
                add_pair(dp[u][0], dp[v][0]);
                last[u].push_back(0);
            }
            else {
                add_pair(dp[u][0], dp[v][1]);
                last[u].push_back(1);
            }
            add_pair(dp[u][1], dp[v][0]);
        }
        dp[u][1].first += 1; // 自己作为good节点
        dp[u][1].second += g[u].size(); // good节点代价，自重
        
        dp[u][0].second += 1; // 自重
//        cout << u << " " << dp[u][0].first << " " << dp[u][0].second  << " " << dp[u][1].first << " " << dp[u][1].second << endl;
    }
    
    
    void dfs_ans(int u, bool isGood) {
        vis[u] = 1;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (!vis[v]) {
                dfs_ans(v, isGood ? 0 : last[u][i]);
            }
        }
        
        if (isGood) {
            ans[u] = g[u].size();
        }
        else {
            ans[u] = 1;
        }
    }
    
    


public:
    void solve() {
        int n;
        cin >> n;
        for (int i = 1; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        if (n == 2) {
            cout << "2 2\n1 1" << endl;
        }
        else {
            dfs(1);
            memset(vis, 0, sizeof(vis));
            if (cmp_pair(dp[1][0], dp[1][1])) {
                cout << dp[1][0].first << " " << dp[1][0].second << endl;
                dfs_ans(1, 0);
            }
            else {
                cout << dp[1][1].first << " " << dp[1][1].second << endl;
                dfs_ans(1, 1);
            }
            for (int i = 1; i <= n; ++i) {
                cout << ans[i] << " ";
            }
            cout << endl;
        }
    }
}
ac;

总结

这次题目都比较有意思，题目4和题目5有点难度，尤其是题目5的输出。题目5的结果输出不难想出办法，就是挺麻烦，不够优雅。