Codeforces Round 992 (Div. 2)
Codeforces Round 992 (Div. 2)
A. Game of Division
题目描述
You are given an array of integers $ a_1, a_2, \ldots, a_n $ of length $ n $ and an integer $ k $ .
Two players are playing a game. The first player chooses an index $ 1 \le i \le n $ . Then the second player chooses a different index $ 1 \le j \le n, i \neq j $ . The first player wins if $ |a_i - a_j| $ is not divisible by $ k $ . Otherwise, the second player wins.
We play as the first player. Determine whether it is possible to win, and if so, which index $ i $ should be chosen.
The absolute value of a number $ x $ is denoted by $ |x| $ and is equal to $ x $ if $ x \ge 0 $ , and $ -x $ otherwise.
分析
只要存在一个数使得first player能赢，则一定能赢，遍历所有可能，复杂度O(n^2t)
Code
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<=b;i++)
const int N=105;
int a[N];
int main(){
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d",&n,&k);
f(i,1,n)
scanf("%d",&a[i]);
bool findans=0;
int index;
f(i,1,n){
bool flag=1;
f(j,1,n){
if(i==j)
continue;
if(abs(a[i]-a[j])%k==0){
flag=0;
break;
}
}
if(flag){
index=i;
findans=1;
break;
}
}
if(findans)
printf("YES\n%d\n",index);
else
printf("NO\n");
}
return 0;
}
B. Paint a Strip
题目描述
You have an array of zeros $ a_1, a_2, \ldots, a_n $ of length $ n $ .
You can perform two types of operations on it:
- Choose an index $ i $ such that $ 1 \le i \le n $ and $ a_i = 0 $ , and assign $ 1 $ to $ a_i $ ;
- Choose a pair of indices $ l $ and $ r $ such that $ 1 \le l \le r \le n $ , $ a_l = 1 $ , $ a_r = 1 $ , $ a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil $ , and assign $ 1 $ to $ a_i $ for all $ l \le i \le r $ .
What is the minimum number of operations of the first type needed to make all elements of the array equal to one?
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.
The only line of each test case contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array.
Note that there is no limit on the sum of $ n $ over all test cases.
输出格式
For each test case, print one integer — the minimum number of needed operations of first type.
样例 #1
样例输入 #1
4
1
2
4
20
样例输出 #1
1
2
2
4
提示
In the first test case, you can perform an operation of the $ 1 $ st type with $ i = 1 $ .
In the second test case, you can perform the following sequence of operations:
- Operation of $ 1 $ st type, $ i = 1 $ . After performing this operation, the array will look like this: $ [1, 0] $ .
- Operation of $ 1 $ st type, $ i = 2 $ . After performing this operation, the array will look like this: $ [1, 1] $ .
The sequence of operations in the second test case 
In the third test case, you can perform the following sequence of operations:
- Operation of $ 1 $ st type, $ i = 1 $ . After performing this operation, the array will look like this: $ [1, 0, 0, 0] $ .
- Operation of $ 1 $ st type, $ i = 4 $ . After performing this operation, the array will look like this: $ [1, 0, 0, 1] $ .
- Operation of $ 2 $ nd type, $ l = 1 $ , $ r = 4 $ . On this segment, $ a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2 $ , which is not less than $ \lceil\frac{r - l + 1}{2}\rceil = 2 $ . After performing this operation, the array will look like this: $ [1, 1, 1, 1] $ .
The sequence of operations in the third test case 
分析
头尾肯定要放1，如何最大化利用1是我们关心的，考虑序列1..0*n_1..1..0*n_2..1...
若是可以完全使用操作2填充满，则必须满足n_i=n_{i-1}+3 此处3 = 1 + 2，1是结尾的1，2是上一个序列首尾的1，则每个1的放置位置应为a_i = \sum{n_i}+i+1=2a_{i-1}+1， i+1是端点的1
递推计算a_i直到大于题目给的lenth
化简得n_i=3i-1,a_i=3*2^{i-1}-2
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> a;
signed main(){
for(int i=1;i<50;i++)a.push_back(3*pow(2,i-1)-2);
int T;cin>>T;
while(T--){
int n;cin>>n;
cout<<lower_bound(a.begin(), a.end(), n)-a.begin()+1<<endl;
}
return 0;
}
C. Ordered Permutations
分析
不难证出，只要序列排列是先增后减，那最大值对于整个的贡献都是一致的，即都能达到最大，所以就是求先增后减排序的第k字典序
显然地，若是在某个序列中，确定了第1位是i，则1~i-1都必须倒序拍在最后面，中间可以变动的数字只有n-i个，因为中间的数字也必须遵循先增后减，不妨以最大值作为参考，则我们只关心最大值左右两边的一种组合，只要组合确定了，其排序方式也是确定的
那么以i为第一位的序列，共有\sum{C^j_{n-i}}=2^{n-i}种排列，不断 累计此排列数，就是字典序
若计算到i+1时，累计的字典序超过k，则说明当前序列第一位应当是i，倒数i-1个数也确定了，然后继续递归其为确定的序列，直到剩下的k=1，则填充完毕，递归结束
另外地，由于题目给的序列长度所提供的字典序远超k，所以我们只需要计算后40位数的字典序即可满足(2^{40}>10^{12})
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int ans[200005];
int comb(int lenth){
if(lenth<0)return 1;
return pow(2,lenth);
}
void dfs(int lenth,int bias,int beg,int last,int tk){
if(lenth == 1 and tk <= 1){
ans[beg] = bias + 1;
return ;
}
int tmp = 0;
for(int i=1;i<=lenth;i++){
tmp+=comb(lenth-1-i);
if(tmp>=tk){
ans[beg] = i+bias;
for(int j=0;j<i-1;j++)
ans[last-j] = bias+j+1;
dfs(lenth-i,bias+i,beg+1,last-i+1,tk-tmp+comb(lenth-1-i));
break;
}
}
}
#define undo 41
void solve(){
cin>>n>>k;
memset(ans,0,sizeof(ans));
if(n<undo)
dfs(n,0,1,n,k);
else{
for(int i=1;i<=n-undo;i++)ans[i] = i;
dfs(undo,n-undo,n-undo+1,n,k);
}
for(int j=1;j<=n;j++)
if(ans[j]==0){
cout<<"-1\n";
return ;
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<"\n";
}
signed main(){
int t;cin>>t;
while(t--)solve();
return 0;
}
D. Non Prime Tree
题目描述
You are given a tree with $ n $ vertices.
You need to construct an array $ a_1, a_2, \ldots, a_n $ of length $ n $ , consisting of unique integers from $ 1 $ to $ 2 \cdot n $ , and such that for each edge $ u_i \leftrightarrow v_i $ of the tree, the value $ |a_{u_i} - a_{v_i}| $ is not a prime number.
Find any array that satisfies these conditions, or report that there is no such array.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.
The next $ n - 1 $ lines contain the edges of the tree, one edge per line. The $ i $ -th line contains two integers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ ; $ u_i \neq v_i $ ), denoting the edge between the nodes $ u_i $ and $ v_i $ .
It’s guaranteed that the given edges form a tree.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10 ^ 5 $ .
输出格式
For each test case, if an array that satisfies the conditions exists, print its elements $ a_1, a_2, \ldots, a_n $ . Otherwise, print $ -1 $ .
样例 #1
样例输入 #1
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
2 4
3 5
3 6
3 7
样例输出 #1
2 10 1 6 5
8 7 12 1 4 6 3
提示
The possible answers are shown below. Instead of the vertex numbers, the corresponding elements of the array $ a $ are written in them.
The image of the tree in the first test case 
The image of the tree in the second test case 
分析
这题需要我们找到一个构造方案和判假方案
每个新增节点可以提供2的选择数，考虑到1不是质数，可以令一条最长的边为相邻的自然数
考虑到大于2的偶数也不是质数，可以令任一子树为其子树根的+2+2i，这样在最差情况下，这个节点也只会消耗3的选择数，而存在子树也至少要3个点，消耗1+1+3<提供2+2+2，符合题意，一般情况下这个节点消耗2的选择数，符合题意
所以这题一定存在合法构造方案，即按dfs序遍历，第一条边为自然数，遇到子树就+2+2i，然后再自然数
Code
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<b;i++)
const int N=2e5+10;
vector<int> line[N];
int cnt,a[N],n;
bool flag;
void dfs(int u,int fa){
if(cnt==a[fa])
a[u]=++cnt;
else{
while((++cnt-a[fa])&1 || cnt-a[fa]==2);
a[u]=cnt;
}
if(a[u]>n*2)
flag=1;
f(i,0,line[u].size()){
int v=line[u][i];
if(v==fa)
continue;
dfs(v,u);
}
}
int main(){
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
f(i,1,n){
int u,v;
scanf("%d%d",&u,&v);
line[u].push_back(v);
line[v].push_back(u);
}
dfs(1,0);
if(flag)
printf("-1");
else
f(i,1,n+1)
printf("%d ",a[i]);
puts("");
memset(a,0,sizeof(a));
f(i,1,n+1)
line[i].clear();
cnt=0;
flag=0;
}
return 0;
}
E. Control of Randomness
题目描述
You are given a tree with $ n $ vertices.
Let’s place a robot in some vertex $ v \ne 1 $ , and suppose we initially have $ p $ coins. Consider the following process, where in the $ i $ -th step (starting from $ i = 1 $ ):
- If $ i $ is odd, the robot moves to an adjacent vertex in the direction of vertex $ 1 $ ;
- Else, $ i $ is even. You can either pay one coin (if there are some left) and then the robot moves to an adjacent vertex in the direction of vertex $ 1 $ , or not pay, and then the robot moves to an adjacent vertex chosen uniformly at random.
The process stops as soon as the robot reaches vertex $ 1 $ . Let $ f(v, p) $ be the minimum possible expected number of steps in the process above if we spend our coins optimally.
Answer $ q $ queries, in the $ i $ -th of which you have to find the value of $ f(v_i, p_i) $ , modulo $ ^{\text{∗}} $ $ 998,244,353 $ .
$ ^{\text{∗}} $ Formally, let $ M = 998,244,353 $ . It can be shown that the answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows.
The first line of each test case contains two integers $ n $ and $ q $ ( $ 2 \le n \le 2 \cdot 10^3 $ ; $ 1 \le q \le 2 \cdot 10^3 $ ) — the number of vertices in the tree and the number of queries.
The next $ n - 1 $ lines contain the edges of the tree, one edge per line. The $ i $ -th line contains two integers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ ; $ u_i \neq v_i $ ), denoting the edge between the nodes $ u_i $ and $ v_i $ .
The next $ q $ lines contain two integers $ v_i $ and $ p_i $ ( $ 2 \le v_i \le n $ ; $ 0 \le p_i \le n $ ).
It’s guaranteed that the given edges form a tree.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10 ^ 3 $ .
It is guaranteed that the sum of $ q $ over all test cases does not exceed $ 2 \cdot 10 ^ 3 $ .
输出格式
For each test case, print $ q $ integers: the values of $ f(v_i, p_i) $ modulo $ 998,244,353 $ .
Formally, let $ M = 998,244,353 $ . It can be shown that the answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .
样例 #1
样例输入 #1
2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12
样例输出 #1
1
6
6
2
4
9
8
15
2
3
6
9
5
5
提示
The tree in the first test case:
In the first query, the expected value is equal to $ 1 $ , since the robot starts moving from vertex $ 2 $ to vertex $ 1 $ in the first step and the process stops.
Let’s calculate the expected value in the second query ( $ x $ is the number of steps):
- $ P(x < 2) = 0 $ , the distance to vertex $ 1 $ is $ 2 $ and the robot cannot reach it in fewer steps.
- $ P(x = 2) = \frac{1}{3} $ , since there is only one sequence of steps leading to $ x = 2 $ . This is $ 3 \rightarrow_{1} 2 \rightarrow_{0.33} 1 $ with probability $ 1 \cdot \frac{1}{3} $ .
- $ P(x \bmod 2 = 1) = 0 $ , since the robot can reach vertex $ 1 $ by only taking an even number of steps.
- $ P(x = 4) = \frac{2}{9} $ : possible paths $ 3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1 $ .
- $ P(x = 6) = \frac{4}{27} $ : possible paths $ 3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1 $ .
- $ P(x = i \cdot 2) = \frac{2^{i - 1}}{3^i} $ in the general case.
As a result, $ f(v, p) = \sum\limits_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6 $ .
The tree in the second test case:
分析
不难发现，如果在偶数步误入歧途，则奇数步也一定会踩会原点。则就是求踩对的期望步数
对于某个节点，若是有son个儿子（子树+父亲），则走对的概率为p=1/son
走出去的期望步数E(x)=\sum{2p(1-p)^{n-1}}+1=\frac{2*(1-p)}{p}+1=2*son-1
对于每一个硬币，我们希望将其花在期望步数最大的那一步，用堆来维护这个最大期望步数即可
Code
#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define int long long
struct node{
int fa;
int exp;
vector<int> dst;
}nodes[2005];
void dfs(int cur,int fa){
nodes[cur].fa = fa;
nodes[cur].exp = 2*nodes[cur].dst.size()-1;
for(int i:nodes[cur].dst){
if(i==fa)continue;
dfs(i,cur);
}
}
void solve(){
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)
nodes[i].dst.clear();
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
nodes[u].dst.push_back(v);
nodes[v].dst.push_back(u);
}
dfs(1,0);
for(int i=0;i<q;i++){
int v,p;cin>>v>>p;
int ans = 0,step = 1;
priority_queue<int> q;
while(v!=1){
if(step%2){
ans++;
}else{
ans = (ans + nodes[v].exp) % MOD;
q.push(nodes[v].exp);
}
v = nodes[v].fa;
step++;
}
while(p && !q.empty()){
int t = q.top();q.pop();
ans = (ans - t + 1 + MOD) % MOD;
p--;
}
cout<<ans<<"\n";
}
}
signed main(){
int t;cin>>t;
while(t--)solve();
return 0;
}
F. Number of Cubes
没写，不会