第一题：（100）

（1e5次查询，问n（1e18）是不是立方数和平方数。

两次二分或者立方数先打表，平方数二分、

(第一题跟2、3题分开的，做完2、3后没法复制到粘贴板了)

第二题：（100）

求[0,10^r]中各个数位和为y的总数（1<=r,y<=1000）

简单的数位dp

#include "bits/stdc++.h"
using namespace std;
const int mod = 1e9 + 7;
int main() {
    int r, y;
    cin >> r >> y;
    vector<vector<int> > dp(r + 1, vector(y + 1, -1));
    auto dfs = [&](auto&& dfs, int index, int sum)->int{
        if (sum == y && index <= r) {
            dp[index][sum] = 1;
            return 1;
        }
        if ((r - index) * 9 + sum < y) {
            dp[index][sum] = 0;
            return 0;
        }
        if (dp[index][sum] != -1)
            return dp[index][sum];
        int ans = 0;
        for (int i = 0; i <= 9; i++) {
            if (sum + i <= y)
                ans = (ans + dfs(dfs, index + 1, sum + i)) % mod;
        }
        dp[index][sum] = ans;
        return ans;
    };
    int ans = dfs(dfs, 0, 0);
    if (y == 1)
        ans++;
    cout << ans << endl;
    return 0;
}

第三题：（50）

给一个字符串表示泡泡机('-')、泡泡（'o'）,空地('?')（最左边最右边为墙壁）

每秒泡泡机往左右各出一个泡泡，当泡泡机之间或者泡泡机与墙壁之间最下面都充满泡泡时，再吐出的泡泡会漂浮到空中。问多少秒时空中至少有k个泡泡。（字符串长度1e5，1<=k<=1e9）

比如"??-??-??"

第一秒:"?o-oo-o?" 0个空中

第二秒:"oo-[o,o][o,o]-oo" 2个空中

第三秒:"[o,o]o-[o,o,o][o,o,o]-o[o,o]" 6个空中

思路是前缀和+模拟+贪心

用一个vector存各个泡泡机的位置，用一个前缀和统计初始泡泡的前缀和

用map统计每个时间点开始飞向空中泡泡的数目。

然后分别遍历泡泡机之间或者泡泡机与墙壁的非泡泡空地数目（前缀和求解），设置为count。

对于泡泡机与墙壁之间，mp[count+1]++

泡泡机之间:左边的是mp[count/2+1]++,右边的是：mp[（count-1）/2+1]++

然后遍历map，用sum表示当前空中泡泡数目，cnt表示之前单位时间能够产生的泡泡数目，t表示上一次遍历的时间

用iter表示map的当前迭代值

int slove(){
  int k;
  map<int,int> mp;
  int sum = 0,cnt = 0,t=0;
  for(auto iter:mp){
	sum += cnt*(iter.first-t)+iter.second;
	cnt += iter.second;
	t = iter.first;
	if(sum >= k)
	  return t;
  }
  return t + ceil(double(k-sum)/cnt);
}