文章/答案/技术大牛

发布

社区首页 >专栏 >程序员进阶之算法练习（六十三）

程序员进阶之算法练习（六十三）

落影

发布于 2022-09-02 03:59:47

25000

代码可运行

文章被收录于专栏：落影的专栏落影的专栏

运行总次数：0

代码可运行

正文

题目1

题目链接 题目大意： 给出一个整数a[1]，假设有下面这样一个迭代公式：

按照上面的规则，迭代k次之后，得到a[k]；现在给出a[1]和k，求最终迭代出来的a[k]值是多少？

输入： 第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤1000) 接下来每个样例一行，2个整数 𝑎1 and 𝐾 (1≤𝑎1≤1e18, 1≤𝐾≤1e16)

输出： 每个样例一行，输出a[k]；

Examples input 8 1 4 487 1 487 2 487 3 487 4 487 5 487 6 487 7

output 42 487 519 528 544 564 588 628

题目解析： 题目咋一看，会很复杂；同时数字的范围特别大，又也没有什么明显规律。

这种时候，先尝试的模拟算一下，当我们多重复几次，直到x·y=0的时候，我们发现这个数字会停滞不动；那么我们可以模拟这个过程，直到有数字为0。

那么有没有可能出现，x·y永远不为零呢？答案是不可能的，因为会进位。数字的百位，最终总是会归零，并且不会需要很多次。

lld calc(lld a) {
    lld x = 0, y = 9;
    while (a) {
        x = max(x, a%10);
        y = min(y, a%10);
        a /= 10;
    }
    return x*y;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        lld a, k;
        cin >> a >> k;
        while (--k) {
            lld tmp = calc(a);
            a += tmp;
            if (tmp == 0) {
                break;
            }
        }
        cout << a << endl;
    }   
    
    return 0;
}

题目2

题目链接 题目大意： 在数轴上，有一个点A放在x=n的位置上，现在想找到一个点B，B的所在位置是一个整数，并且满足：原点O到B的距离和 A到B的距离两者的差为k；

有时候该位置不存在，我们可以每次把A的位置加1，现在想知道A最少需要加几次1，使得点B存在；

输入： 第一行整数 𝑡，表示t个样例 (1≤𝑡≤6000) 每个样例一行，整数𝑛 and 𝑘 (0≤𝑛,𝑘≤1e6)

输出： 每个样例一行，输出最少都要A点移动次数。

Examples input 6 4 0 5 8 0 1000000 0 0 1 0 1000000 1000000 output 0 3 1000000 0 1 0

题目解析： 假如B没有整数的要求，那么当n>=k的时候，则B肯定存在于O到A之间；n<k的时候，则A的位置不断加1，直到n=k；当增加B的位置为整数限制时，即使n>=k（比如说n=1,k=0），由于B的位置是0.5，此时只能将A的位置加1，使得A=2；考虑有哪些情况会出现B的位置为整数，我们可以发现是n为奇数k为偶数和 n为偶数k为奇数两种情况，我们用 (n+k) % 2 可以区分；至于n<k的情况，我们移动A点，使得n=k，将点B放在原点即可。

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        lld a, k;
        cin >> a >> k;
        if (a >= k) {
            cout << (a+k)%2 << endl;
        }
        else {
            cout << (k-a) << endl;
        }
    }   
    
    return 0;
}

题目3

题目链接 题目大意： ALICE和BOB在玩一个游戏，给出一个长度为n的回文字符串，由字符0和1组成；两个人轮流行动，ALICE先行动，每次有两个选择： 1、花费代价1，将字符串某个字符0变成1； 2、翻转（reverse）字符串，要求是该字符串不是回文串，并且上一步操作不是翻转；等整个字符串都是1的时候，游戏结束，花费代价较少的人获胜；

输入： 第一行是整数t，表示有t个样例 (1≤𝑡≤1e3）每个样例2行，第一行是整数 𝑛 (1≤𝑛≤1e3). 第二行是01字符串； 输出： 每个样例一行，输出胜者名字（ALICE和BOB）；如果平局则输出（DRAW）；

Examples input 2 4 1001 1 0 output BOB BOB

题目解析： 这里有一个简单策略：对于一个回文串（最中间的数字不为0），那么可以采取A填哪个位置，B就填回文串对应的位置；直到剩下2个0的时候，A填任何一个位置，B选择reverse；此时A只能再填一次0，B必胜；

先手者，除非回文串中间是0（当有空格的部分大于1时），否则必输；

class Solution {
   static const int N = 100010;
public:
   int n, m;
   string str;
public:
   void solve() {
       int t;
       cin >> t;
       while (t--) {
           cin >> n;
           cin >> str;
           int cnt = 0;
           for (int i = 0; i < n; ++i) {
               if (str[i] == '0') {
                   ++cnt;
               }
           }
           if (cnt == 0) {
               cout << "DRAW" << endl;
           }
           else if (cnt == 1) {
               cout << "BOB" << endl;
           }
           else if (cnt % 2) {
               cout << (str[(n - 1) / 2] == '0' ? "ALICE" : "BOB") << endl;
           }
           else {
               cout << "BOB" << endl;
           }
       }
   }
}
ac;

题目4

题目链接 题目大意： ALICE和BOB在玩一个游戏，给出一个长度为n的字符串，由字符0和1组成；两个人轮流行动，ALICE先行动，每次有两个选择： 1、花费代价1，将字符串某个字符0变成1； 2、翻转（reverse）字符串，要求是该字符串不是回文串，并且上一步操作不是翻转；等整个字符串都是1的时候，游戏结束，花费代价较少的人获胜；

Examples input 3 3 110 2 00 4 1010 output ALICE BOB ALICE

题目解析： 这里有一个简单策略：对于一个回文串（最中间的数字不为0），那么可以采取A填哪个位置，B就填回文串对应的位置；直到剩下2个0的时候，A填任何一个位置，B选择reverse；此时A只能再填一次0，B必胜；先手者，除非回文串中间是0（当有空格的部分大于1时），否则必输。

注意这个题目中，先手者是可以reverse操作的，这是一个比较大的优势；如果起手是回文串，那么可以用上面的逻辑。（这里有一个很重要的点，先后手最大的差距是2，就是1001这种情况，因为都会采用最佳策略）

为了方便思考，我们引入函数f，f(str)表示回文串str，先手会赢多少； f(1001)=-2; f(101)=-1; （仅有一个0的情况下） f(10001)=1; 注意，除了没有0，平局的情况是不存在的。我们知道回文串的胜负，有两种结果：-2/-1和1。

假如字符串没有任何位置可以操作1次，之后变成回文串，那么先手者Alice可以reverse，等待后手者操作后，依旧可以执行reverse；（这种策略可以占领1的优势，因为后手在一直补齐）直到存在一个操作，可以对某个位置k进行操作，并且操作之后字符串变成回文串strK； 1、假如f(strK)=1，则Alice可以继续执行reverse操作，因为bob如果将字符串操作为strK，对Alice是有收益的； 2、假如f(strK)=-1，则Alice继续执行reverse会平局，因为bob花费1的代价让让alice面临-1的情况；（是否平局，取决于在达到下一步操作就能生成回文串的操作步数） 3、假如f(strK)=-2，则Alice必胜，Alice花费1的代价可以让对手面临-2的情况；

这里可以推出来，先手者必然不会输。（注意，这个前提是有2个0以上）

所以问题的关键是在于上面的情况2，怎么快速找到平局的case。

我们知道这个追赶的步数，应该等于字符串中1和0按照回文串要求不对应的数量。比如说10011=>其中的str[1]和str[3]不一样，需要追赶；那么统计一下，这个数量，即可得到追赶的步数step。

假如step=1，则刚好和构成回文串strNew之后，f(strNew)的-1收益持平，此时会平局。

class Solution {
   static const int N = 100010;
public:
   int n, m;
   string pubStr;
   
   bool isPalindrome(string &str) {
       bool isPalindrome = true;
       for (int i = 0; i < n / 2; ++i) {
           isPalindrome = isPalindrome && (str[i] == str[n - i - 1]);
       }
       return isPalindrome;
   }
   
   int getCount(string &str) {
       int ret = 0;
       int cnt = 0;
       for (int i = 0; i < n; ++i) {
           if (str[i] == '0') {
               ++cnt;
           }
       }
       if (cnt == 0) {
           ret = cnt;
       }
       else if (cnt == 1) {
           ret= cnt;
       }
       else if (cnt % 2) {
           ret = (str[(n - 1) / 2] == '0' ? -2 : 1);
       }
       else {
           ret = -2;
       }
       return ret;
   }
   
public:
   void solve() {
       int t;
       cin >> t;
       while (t--) {
           cin >> n;
           cin >> pubStr;
           
           int cnt = 0, step = 0;
           for (int i = 0; i < n; ++i) {
               if (pubStr[i] == '0') {
                   ++cnt;
               }
               if (i < n / 2 && pubStr[i] != pubStr[n - i - 1]) {
                   ++step;
               }
           }
           if (cnt == 0) {
               cout << "DRAW" << endl;
           }
           else if (cnt == 1) {
               if (isPalindrome(pubStr)) {
                   cout << "BOB" << endl;
               }
               else {
                   cout << "ALICE" << endl;
               }
           }
           else {
               if (isPalindrome(pubStr)) {
                   if (cnt % 2) {
                       cout << (pubStr[(n - 1) / 2] == '0' ? "ALICE" : "BOB") << endl;
                   }
                   else {
                       cout << "BOB" << endl;
                   }
               }
               else {
                   if (step == 1 && cnt == 2) {
                       cout << "DRAW" << endl;
                   }
                   else {
                       cout << "ALICE" << endl;
                   }
               }
           }
           
       }
   }
}
ac;

题目5

题目链接 题目大意： 有n个整数的数组，对于一个数组的weight，定位数组中所有的[i, j]，有多少个满足a[i]==a[j]；问数组的所有子数组中，所有的weight有多少。

输入： 第一行是整数t，表示有t个样例(1≤𝑡≤1e4). 每个样例一行，第一行是整数n(1≤𝑛≤1e9). 输出： 每个样例一行，输出1到n的整数中，有多少个由相同数字组成的数。

Examples input 6 1 2 3 4 5 100

output 1 2 3 4 5 18

题目解析： 以数字[1,1,2,2,1,1]为例，看看中间[2,2]有多少种情况：向左边延伸，左边起点有[2, x] [1,2,x] [1,1,2,x]三种可能；向右边延伸，右边结尾有[x, 2] [x, 2,1] [x,2,1,1]三种可能；包括[2,2]的所有子数组，即是从左边起点选择一个起点（3种可能），从右边结尾选择一个结点（3种可能，一共有3x3=9种可能。容易知道，对于[i, j]，假如有a[i]==a[j]，则一共会有i(n-j+1)的可能。（i下标从1开始） 我们用left[i]来表示i，right[i]来表示n-i+1，则上面的公式表示为left[i]right[j]。

当有[i,j,k] 满足 a[i] == a[j] == a[k]的时候，我们有left[i]right[j]+left[i]right[j] + left[j]*right[k]。

所分组累计下，用map区分；然后逐个计算下即可。

注意超long long的trick。

class Solution {
    static const int N = 100010;
public:
    int n, m;
    int a[N];
    map<int, vector<int>> h;
    
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            h.clear();
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
            }
            for (int i = 0; i < n; ++i) {
                if (h.find(a[i]) != h.end()) {
                    h[a[i]].push_back(i + 1);
                }
                else {
                    vector<int> tmp;
                    tmp.push_back(i + 1);
                    h[a[i]] = tmp;
                }
            }
            lld ans = 0;
            for (map<int, vector<int> > :: iterator it = h.begin(); it != h.end(); ++it) {
                vector<int> vec = it->second;
                lld sum = 0;
                for (int i = 0; i < vec.size(); ++i) {
                    sum += (n - vec[i] + 1);
                }
                for (int i = 0; i < vec.size(); ++i) {
                    sum -= (n - vec[i] + 1);
                    ans += 1LL * vec[i] * sum;
                }
            }
            cout << ans << endl;
        }
    }
}
ac;