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 <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#include <bitset>
#include <deque>
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<int , int> 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<int> 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("
") ;
}
__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 << "
" ;
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 <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#include <bitset>
#include <deque>
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<int , int> PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
vector<int> 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
" , 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 ;
}
/*
*/