2019ccpc厦门站G、J

G 、Zayin and Count

这个题，额不算难题。只是有一个需要注意的地方，在对x进行数位dp的时候，0这个数字有可能可以用，但也有可能不可以用。如果可以用，那就正常dp，但如果不可以用的话，比如，如果对x = 23 dp，但是发现数位dp只能处理两位数的，对于2 ，3，啥的都不能处理，所以在dp之后，还要重新特判一下。处理完之后，就是模拟了。


#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int a[2][11] , c[100] , cnt ;
__int128 dp[1100][2] ;
void print(__int128 x) {
  vector v ;
  while(x) v.push_back(x % 10) , x /= 10 ;
  if(v.size() == 0) v.push_back(0) ;
  reverse(v.begin() , v.end()) ;
  for(auto x : v)
   printf("%d" , x) ;
  printf("\n") ;
}
__int128 dfs(int u  , int flag , int limit , int t) {
    if(u == 0)  return flag == 0 ;
    if(!limit && dp[u][flag] != -1) return dp[u][flag] ;
    int end = limit ? c[u] : 9 ;
    __int128 ans = 0 ;
    for(int i = 0 ;i <= end; i ++ )
        if(a[t][i])   ans += dfs(u - 1 , flag && i == 0 , limit && end == i , t) ;
    if(!limit) dp[u][flag] = ans ;
    return ans ;
}
__int128 solve(string x , int t) {
    cnt = 0 ;
    for(int i = x.size() - 1; i >= 0 ;i -- ) c[++ cnt] = x[i] - '0' ;
    return dfs(cnt , 1 , 1 , t) + a[t][0]  ;
}
__int128 in() {
    __int128 x = 0 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9') ch = getchar() ;
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48 , ch = getchar() ;
    return x ;
}
__int128 qmi(__int128 a , __int128 b) {
  __int128 res = 1 ;
  while(b) {
    if(b & 1) res = res * a ;
    a = a * a ;
    b >>= 1 ;
  }
  return res ;
}
__int128 t[N] ;
int work()
{
  __int128 q = 0 , cnt1 = 0 ;
  for(int i = 0; i < 10 ;i ++ ) cin >> a[0][i] , cnt1 += a[0][i] ;
  for(int i = 0 ;i < 10 ;i ++ ) cin >> a[1][i] , q += a[1][i] ;
  memset(dp , -1 , sizeof dp) ;
  string x ;
  cin >> x ;
 
  __int128 p = solve(x , 0)  ;
  __int128 d = cnt1 ;
  if(a[0][0] == 0) {
      for(int i = 1; i < cnt ;i ++ )
       p += d , d *= cnt1 ;
  }
 
  string ans = "" ;
 
  t[0] = 1 ;
  __int128 res = 0 ;
  int flag = 0 ;
 
  if(a[1][0]) p -- ;
 
  if(p == 0) {
      for(int j = 0 ;j < 10 ;j ++ )
        if(a[1][j]) {
            cout << j << endl ;
            return 0 ;
        }
  }
  for(int i = 1; ;i ++ ) {
      t[i] = t[i - 1] * q ;
      for(int j = 1 ; j < 10 ;j ++ ) {
          if(a[1][j]) {
              if(res + t[i - 1] >= p) {
                  p -= res ;
                  ans += j + '0' ;
                  flag =  i ;
                  break ;
 
              }
              res += t[i - 1] ;
          }
      }
 
      if(flag) break ;
  }
  for(int i = flag - 1; i >= 1; i -- ) {
      int ok = 0 , tt = -1 ;
      __int128 res = 0 ;
      for(int j = 0 ;j < 10 ;j ++ ) {
          if(a[1][j]) {
              tt = j ;
              if(res + t[i - 1] >= p) {
                  p -= res ;
                  ans += j + '0' ;
                  ok = 1;
                  break ;
              }
              res += t[i - 1] ;
          }
      }
      if(!ok && tt != -1) ans += tt + '0' , p -= (__int128)q * t[i - 1] ;
  }
  cout << ans   << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
  int n ;
  ios ;
  cin >> n ;
  while(n --)
  work() ;
  return 0 ;
}
/*
*/

J、Zayin and Tree

暴力点分治，对于以某个重心为根节点的情况，分两种情况进行套路：一个路径以根节点为一端点，这种情况直接往下枚举
另一种情况：路径跨过根节点
P - R + L , 分开写就是dx- R + dy + L + 1 ，dx是重心节点到x的距离，因为要跨过根节点所以再加1

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
vector v[N] ;
int a[N] ;
int rt , sum , qq , vis[N] , sz[N] ;
void get_rt(int u , int f) {
  sz[u] = 1 ;
  int res = 0 ;
  for(auto x : v[u]) {
    if(x == f || vis[x]) continue ;
    get_rt(x , u) ;
    sz[u] += sz[x] ;
    res = max(res , sz[x]) ;
  }
  res = max(res , qq - sz[u]) ;
  if(res < sum) sum = res , rt = u ;
  return ;
}
int ans = INF ;
// maxn 是对当前重心下x子树的d - max ， minx是对当前重心下x子树的d + minx
int maxn = INF , mixn = INF ;
// lastmaxn 是当前重心下已经处理过的子树的所有的min(d - max) , 
// lastminx 是当前重心下已经处理过的子树的所有的min(d + min)
int lastmaxn = INF , lastminx = INF ;
void get_dis(int u , int f , int f_mixn ,int f_maxn , int d){
  maxn = min(maxn , d - f_maxn) ;
  mixn = min(mixn , d + f_mixn) ;
  for(auto x : v[u]) {
    if(x == f || vis[x]) continue ;
    get_dis(x , u , min(f_mixn , a[x]) , max(f_maxn , a[x]) , d + 1) ;
  }
}
// 这个函数： 一个路径一定跨越根节点的
void calc1(int u) {
  for(auto x : v[u]) {
    if(vis[x]) continue ;
    maxn = INF , mixn = INF ;
    // 处理当前重心下x子树
    get_dis(x , u , min(a[x] ,a[u]) , max(a[x] , a[u]) , 1) ;
    if(lastmaxn != INF && mixn != INF) ans = min(ans , lastmaxn + mixn + 1) ;
    if(lastminx != INF && maxn != INF) ans = min(ans , lastminx + maxn + 1) ;
    // 把当前重心x子树归为已经处理过的子树
    lastmaxn = min(lastmaxn , maxn) ;
    lastminx = min(lastminx , mixn) ;
  }
  lastmaxn = INF , lastminx = INF ;
}
// 处理一个路径只在一侧的，并且一段根节点是 u 节点
void dfs(int u , int f , int f_minx , int f_maxn , int d) {
  ans = min(ans , d - f_maxn + f_minx) ;
  for(auto x : v[u]) {
    if(x == f || vis[x]) continue ;
    dfs(x , u , min(f_minx , a[x]) , max(f_maxn , a[x]) ,d + 1) ;
  }
  return ;
}
void solve(int u) {
  vis[u] = 1 ;
  calc1(u) ; // 处理一个路径肯定跨越当前节点的
  dfs(u , u , a[u] , a[u] , 1) ; // 处理一个路径旨在当前节点一侧的 ;
  for(auto x : v[u]) {
    if(vis[x]) continue ;
    sum = qq = sz[x] ;
    get_rt(x , u) ;
    solve(rt) ;
  }
  return ;
}
void work() {
  int n ;
  scanf("%d" , &n) ;
  qq = sum = n ;
  for(int i = 1; i <= n ;i ++ ) vis[i] = 0 , v[i].clear() ;
  for(int i = 1; i <= n ;i ++ ) scanf("%d" , &a[i]) ;
  for(int i = 1; i < n; i ++ ) {
    int a , b ;
    scanf("%d%d" , &a , &b) ;
    v[a].push_back(b) , v[b].push_back(a) ;
  }
  if(n == 1) {
    puts("1") ;
    return ;
  }
  ans = INF ;
  get_rt(1 , 0) ;
  solve(rt) ;
  printf("%d\n" , ans) ;
  return ;
}
int main()
{
  //  freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //  freopen("C://Users//spnooyseed//Desktop//outmain.txt" , "w" , stdout) ;
  int n ;
  scanf("%d" , &n) ;
  while(n --)
   work() ;
  return 0 ;
}
/*
*/
CCPCupc点分治数位DP

相关

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

《2021CCPC桂林》

数位dp学习记录

setUp()、tearDown()和setUpClass()、tearDownClass()之间的区别

洛谷P2664 树上游戏——点分治

[ICPC2020济南L] Bit Sequence - 数位dp

codeforces597 div2 F 数位dp

【LibreOJ】#6392. 「THUPC2018」密码学第三次小作业 / Rsa 扩展欧几里得算法

点分治 学习笔记

2021CCPC广州 C. Necklace（二分/贪心/好题/详细题解）

[LOJ#2386]. 「USACO 2018.01 Platinum」Cow at Large[点分治]

数位dp的学习

标签