Google kick start 2018 Round B No Nine

这次的题意就是和小盆友们平时完的时候玩的那种不能说带有三或者能被三整除的那种游戏一样了。这个规则简单一些，这次玩的是9，不过难点也是有的，就是人家玩到long long，不是到100就拉倒了。

两个思路，一个是构造，一个是数位DP。

先数位DP吧，这个条件很裸，不难写，用(sum+x)%9判整除9，用0-8构造整个数字，状态转移方程就是 $dp[i][j][lmt] = \sum_{0-max(8,max(8,num[i])))}^{j}dp[i][j][lmt\cap j= num[i]]$

如果有的数字上限就是9，直接置8就可以了。

这里我也尝试过dp[i][j]，不过太难处理了，就不费那个功夫了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[20][10][2];
ll solve(int id,int sum,int lmt,const string &num)
{
 if(id == num.length())
  return sum != 0;
 if(dp[id][sum][lmt])
  return dp[id][sum][lmt];
 ll ans = 0;
 int up = lmt?num[id]-'0':8;
 if(up == 9)
  up = 8;
 for(int i = 0;i <= up;i++)
 {
  ans += solve(id+1,(sum+i)%9,lmt&&i == num[id]-'0',num);
 }
 return dp[id][sum][lmt] = ans;
 
}
ll f(ll num)
{
 for(int i = 0;i < 20;i++)
  for(int j = 0;j < 10;j++)
   dp[i][j][0] = dp[i][j][1] = 0;
 ll ans = solve(0,0,1,to_string(num));
 return ans;
}
int main()
{
 ll a,b;
 int T;
 cin >> T;
 for(int kase = 1;kase <= T;kase++)
 {
  cin >> a  >> b;
  printf("Case #%d: %lld\n",kase,f(b) - f(a-1)); 
 }
    return 0;
}

这里是看了官方分析，首先明确构造方式，如果我要构造0-2147483647下的我能说出的数字，这里的21474483647是满足不被9整除，不包含9的。然后呢，我们把问题分解一下啊，先是2147483640-2147483647，再是2147483600-2147483639，然后...最后是0-199999999。简单地看像是把问题分解成了每个数字位提取出来，但是这里这里分治是建立在原数本身就是满足条件的，所以我们在一位一位地构造的时候不需要考虑前面的数字，只需要考虑当前位上的数字下能产生多少个满足条件的数字。

所以，我们的构造方程就是 $sum = \sum_{i = 1}^{num.length()}num[i-1]*9^{i}$ ，根据公式显示，这个结果sum明显能整除9。其实我们构造的时候就可以发现，我们构造的数字Y大致长这个样子{10Y+0,10Y+1,...,10Y+8},明显每9个里面有一个能被9整除，这个数论就不多说了。那我们去掉这个错误选项。为什么把个位数那个单独拿出来算呢，因为个位上没得分解了，只能自己手动判断下了。所以最终的答案就是ans(num-num[0],num) + sum*8/9

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool judge(ll num)
{
 //cout << num <<endl;
 if(num%9 == 0)
  return false;
 while(num!=0)
 {
  ll tmp = num%10;
  if(tmp == 9)return false;
  num/=10;
 }
 return true;
}
ll solve(ll a)
{
 ll num[20] = {0};
 ll ans = 0;
 int id = 0;
 ll d = 1;
 for(ll i = a-a%10;i <= a;i++)
  if(judge(i))
   ans++;
 while(a != 0)
 {
  num[id++] = a%10;
  a/=10;
 }
 ll tmp = 0;
 for(int i = 1;i < id;i++)
 {
  d*=9;
  tmp += num[i]*d;
 }
 tmp *= 8;
 tmp /= 9;
 //cout << ans << endl;
 return ans + tmp;
}
int main()
{
 int T;
 cin >> T;
 for(int kase = 1;kase <= T;kase++)
 {
  ll a,b;
  cin >> a >> b;
  a = solve(a);
  b = solve(b);
  //cout << a << endl;
  //cout << b << endl; 
  ll ans;
  ans = b - a + 1;
  printf("Case #%d: %lld\n",kase,ans); 
 }
 return 0;
}

Google kick start 2018 Round B No Nine

浏览过的版块