豪大大数字

我们来证明，如果 x 非常大，那么 x + 1 也 非常大。 由于 (我们称之为 )的数字和不大于 ，那么 ，如果是 ，那么 。因此，如果 非常大，那么也 非常大。

这项观察使我们能够使用二分搜索来找到最小的非常大的数字(我们称之为 )。如果是 ，那么段 中的所有数字都是非常大且不大于n，因此这些数字的数量就是问题的答案。

#include<bits/stdc++.h>
#define LL long long//别忘了开long long
using namespace std;
LL n,m,t,w,mid,ans;
bool pd(LL x){//判断
	LL s=0,xx=x;
	while(xx) s+=xx%10,xx/=10;//减去各数位之和
	return x-s>=m;//减去其各数位之和后大于等于s
}
int main(){
	scanf("%lld%lld",&n,&m);
	t=1LL;w=n;ans=-1;
	while(t<=w){
		mid=(t+w)>>1;
		if(pd(mid)) ans=mid,w=mid-1;
		else t=mid+1;
	}//二分最小的那一个符合的数字
	if(ans==-1) printf("0\n");
	else printf("%lld\n",n-ans+1);
	return 0;
}

车的攻击

https://www.luogu.com.cn/problem/P3913

替换字符

找到出现次数最少的字符 — 如果相同，则取字母表中较早的字符。找到出现次数最多的字符 — 如果相同，则取字母表中较晚的字符。然后，用出现次数最多的字符替换出现次数最少的字符。

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> occ(26);
        for (int i=0; i<n; i++)
            occ[s[i] - 'a'] += 1;
        pair<pair<int,char>,int> low, high;
        low = high = {{occ[s[0] - 'a'], s[0]}, 0};
        for (int i=1; i<n; i++) {
            low = min(low, {{occ[s[i] - 'a'], s[i]}, i});
            high = max(high, {{occ[s[i] - 'a'], s[i]}, i});
        }
        s[low.second] = s[high.second];
        cout << s << "\n";
    }
  return 0;
}

又是一道排列问题

对于每个位置 ，让我们确定它的状态：对于将转换器移到该位置的玩家来说，这个位置是赢还是输。由于玩家只能将转换器移到索引较小的位置，我们可以按照从 1 到 的顺序确定位置的状态。您可以将其视为动态规划。 如果没有这样的，即和 ，那么这个位置就是输的位置，因为另一个玩家无法移动，这意味着他们赢了（而将转换器放在该位置的玩家输了）。否则，另一个玩家可以移动。并且我们已经知道如果玩家在所有之前的位置放置转换器，他是否赢了。如果存在一个可以移动的位置 ，并且 是获胜位置，那么 就是失败位置（因为我们的对手会移动到那里）。否则， 就是获胜位置。因此，我们有一个时间复杂度为 的解决方案，对于每个位置 ，我们需要遍历所有可能的转换。

但是，我们可以注意到，我们只对确定每个位置状态的两个简单属性感兴趣：是否可以从当前位置移动，以及是否可以移动到获胜位置。如果我们将最小元素保持到当前位置 ，我们将其称为 ，则可以轻松检查第一个属性。对于第二个性质，只要在获胜位置中保留最小元素就足够了，我们将其称为。然后，如果 和 ，则位置 获胜。因此，解决方案的时间复杂度为 。

#include <bits/stdc++.h>
using namespace std;

void sol()
{
    int n;
    cin >> n;
    int ans = 0;
    int mn = n + 1, mnWin = n + 1;
    while (n--) 
    {
      int x;
      cin >> x;
      if (mn < x && x < mnWin) 
      	ans += 1, mnWin = x;
      mn = min(mn, x);
    }
    cout << ans << '\n';
}

int main()
{
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) 
    sol();
}