Codeforces Round #633 (Div. 1)

A. Powered Addition

time limit per test1 second memory limit per test256 megabytes

You have an array a of length n. For every positive integer x you are going to perform the following operation during the x-th second:

  • Select some distinct indices \(i_{1}, i_{2}, \ldots, i_{k}\) which are between 1 and n inclusive, and add \(2^{x-1}\) to each corresponding position of a. Formally, \(a_{i_{j}} := a_{i_{j}} + 2^{x-1} for j = 1, 2, \ldots, k\). Note that you are allowed to not select any indices at all.

You have to make a nondecreasing as fast as possible. Find the smallest number T such that you can make the array nondecreasing after at most T seconds.

Array a is nondecreasing if and only if \(a_{1} \le a_{2} \le \ldots \le a_{n}\).

You have to answer t independent test cases.Input

The first line contains a single integer \(t (1 \le t \le 10^{4})\) — the number of test cases.

The first line of each test case contains single integer \(n (1 \le n \le 10^{5})\) — the length of array a. It is guaranteed that the sum of values of n over all test cases in the input does not exceed \(10^{5}\).

The second line of each test case contains n integers \(a_{1}, a_{2}, \ldots, a_{n} (-10^{9} \le a_{i} \le 10^{9})\).Output

For each test case, print the minimum number of seconds in which you can make a nondecreasing.ExampleinputCopy

3
4
1 7 6 5
5
1 2 3 4 5
2
0 -4

outputCopy

2
0
3

Note

In the first test case, if you select indices 3, 4 at the 1-st second and 4 at the 2-nd second, then a will become [1, 7, 7, 8]. There are some other possible ways to make a nondecreasing in 2 seconds, but you can’t do it faster.

In the second test case, a is already nondecreasing, so answer is 0.

In the third test case, if you do nothing at first 2 seconds and select index 2 at the 3-rd second, a will become [0, 0].

乱搞题,看最大的元素即可,因为在第k秒可以组成\([0,2^k]\)之间的任何数,所以只要让每个数和他前面最大的数满足题意即可;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,ans;ll maxx;
void solve(){
    scanf("%d",&n);maxx=-1e18;ans=0;
    rep(i,1,n){
        ll x;scanf("%lld",&x);
        maxx=max(maxx,x);
        if(x<maxx){
            rep(j,1,40){
                ans=max(ans,j);
                if((1ll<<j)-1>=maxx-x) break;
            }
        }
    } printf("%d\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


B. Edge Weight Assignment

time limit per test1 second memory limit per test256 megabytes

You have unweighted tree of n vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  • For every two different leaves \(v_{1}\) and \(v_{2}\) of this tree, bitwise XOR of weights of all edges on the simple path between v_{1} and v_{2} has to be equal to 0.

Note that you can put very large positive integers \((like 10^{(10^{10})})\).

It’s guaranteed that such assignment always exists under given constraints. Now let’s define f as the number of distinct weights in assignment.In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is 0. f value is 2 here, because there are 2 distinct edge weights(4 and 5).

In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex 1 and vertex 6 (3, 4, 5, 4) is not 0.

What are the minimum and the maximum possible values of f for the given tree? Find and print both.Input

The first line contains integer \(n (3 \le n \le 10^{5}) \)— the number of vertices in given tree.

The i-th of the next n-1 lines contains two integers a_{i} and b_{i} (1 \le a_{i} \lt b_{i} \le n) — it means there is an edge between a_{i} and b_{i}. It is guaranteed that given graph forms tree of n vertices.Output

Print two integers — the minimum and maximum possible value of f can be made from valid assignment of given tree. Note that it’s always possible to make an assignment under given constraints.ExamplesinputCopy

6
1 3
2 3
3 4
4 5
5 6

outputCopy

1 4

inputCopy

6
1 3
2 3
3 4
4 5
4 6

outputCopy

3 3

inputCopy

7
1 2
2 7
3 4
4 7
5 6
6 7

outputCopy

1 6

Note

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.

In the second example, possible assignments for each minimum and maximum are described in picture below. The f value of valid assignment of this tree is always 3.

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.

首先第一个子问题:求最小

这个很好解决嘛,不难证明答案只能是1或者3,如果有长为奇数的链那就是3,否则为1;
证明的话,你就随便找一个根节点,那么这个root和每个叶子的路径长度只能是奇数或偶数,如果是奇数的路径就全是0,偶数就对半填两个异或起来等于0的数;

如何解决最大呢,其实也很简单,我们发现全部不一样是很容易做到的,唯一有影响的就是一个节点上连着许多个叶子,这时候这些连着叶子的边就都要一样;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
struct Edge{
    int v,w,nex;
}g[maxn<<1];
int head[maxn],edge_tot=1;
void addedge(int u,int v,int w){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
int n,ind[maxn],minx=1,maxx,dep[maxn];
void dfsmin(int u,int fa){
    for(int i=head[u];i;i=g[i].nex) if(g[i].v!=fa){
        dep[g[i].v]=dep[u]+1;dfsmin(g[i].v,u);
    }
}
void dfsmax(int u,int fa){
    int cnt=0;
    for(int i=head[u];i;i=g[i].nex){
        int v=g[i].v;
        if(v!=fa){
            if(ind[v]==1) cnt++;
            dfsmax(v,u);
        }
    } if(cnt) maxx-=(cnt-1);
}
int main(){
    scanf("%d",&n);minx=1;maxx=n-1;
    rep(i,1,n-1){
        int u,v;scanf("%d%d",&u,&v);ind[u]++;ind[v]++;
        addedge(u,v,1);addedge(v,u,1);
    }
    vector<int> v,s;
    rep(i,1,n){
        if(ind[i]==1) v.pb(i);
        else s.pb(i);
    }
    dep[v[0]]=1;dfsmin(v[0],0);
    for(auto u:v) if(dep[u]%2==0) minx=3;
    dfsmax(s[0],0);
    printf("%d %d\n",minx,maxx);
}


C. Perfect Triples

time limit per test2 seconds memory limit per test256 megabytes

Consider the infinite sequence s of positive integers, created by repeating the following steps:

  1. Find the lexicographically smallest triple of positive integers (a, b, c) such that
    • \(a \oplus b \oplus c = 0\), where \oplus denotes the bitwise XOR operation.
    • a, b, c are not in s.Here triple of integers \((a_1, b_1, c_1)\) is considered to be lexicographically smaller than triple (a_2, b_2, c_2) if sequence [a_1, b_1, c_1] is lexicographically smaller than sequence [a_2, b_2, c_2].
  2. Append a, b, c to s in this order.
  3. Go back to the first step.

You have integer n. Find the n-th element of s.

You have to answer t independent test cases.

A sequence a is lexicographically smaller than a sequence b if in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b.Input

The first line contains a single integer \(t (1 \le t \le 10^5)\) — the number of test cases.

Each of the next t lines contains a single integer \(n (1\le n \le 10^{16})\) — the position of the element you want to know.Output

In each of the t lines, output the answer to the corresponding test case.ExampleinputCopy

9
1
2
3
4
5
6
7
8
9

outputCopy

1
2
3
4
8
12
5
10
15

Note

The first elements of s are 1, 2, 3, 4, 8, 12, 5, 10, 15, \dots

找规律,不难发现表打出来长这样:

我们发现,如果每三个为一组,那么组数是1,4,16,64…一直下去;

再来看数量为16的那一组,我们观察第二列,可以发现如果单看前四个元素32,34,35,33 ,他们是以(1,3,4,2)的顺序排列的,那如果我们以四个为一组,发现每组也是以(1,3,4,2)的顺序排列的;

并且第三列就是前两个数的异或,那么这道题就迎刃而解了;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
ll ans[5];
void solve(){
	ll n;scanf("%lld",&n);
	if(n<=3) return (void)printf("%lld\n",n);
	ll N=(n-1)/3+1,b=1;
    for(;b<N;b*=4) N-=b;
    ans[1]=N+b-1,ans[2]=b*2;ll sz=b;
    while(sz>1){
        sz/=4;
        if((N-1)/sz==1) N-=sz,ans[2]+=sz*2;
        else if((N-1)/sz==2) N-=sz*2,ans[2]+=sz*3;
        else if((N-1)/sz==3) N-=sz*3,ans[2]+=sz;
    } ans[0]=ans[1]^ans[2];
    printf("%lld\n",ans[n%3]);
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}

发表评论,支持MarkDown语法