A. Powered Addition
题意：
给定序列(a_{1,2,cdots,n})，现在选定时间(k)，那么在(k)秒内，若当前时间是第(x)秒，可以选择任意多个数加上(2^{x-1})。
现在问使得(a)序列单调不降的最小(k)为多少。
思路：
考虑贪心。
题意转化为选定一个最小的(k)，每个数可以加上(0)~(2^k-1)。
那么我们只需要让每个数增加的尽量小即可，即(a_i'=max{a_1,a_2,cdots,a_{i-1}})。然后根据(a_i'-a_i)这个差值来确定(k)即可。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/13 21:32:27
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int n;
void run() {
cin >> n;
int last = -INF, Max = -INF;
for(int i = 1; i <= n; i++) {
int x; cin >> x;
last = max(last, x);
Max = max(Max, last - x);
}
int res = 0;
while((1ll << res) - 1 < Max) ++res;
cout << res<< '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
B. Edge Weight Assignment
题意：
给定一颗无向树。
现在要给每条边赋正边权，使得两两叶子结点异或为(0)。所赋的权值可以为任意正整数。
现在要回答最少用多少个数和最多用多少个数满足上述条件。
思路：
首先我们通过思考发现，题目中要求的任意两点异或为(0)，我们可以转化为以指定的一个叶子节点为根，到其它叶子结点的异或值为(0)。
之后我们最少最大分别进行考虑。
考虑最少用的个数：
- 显然两个叶子结点之间距离为偶数，那么我们只需要用一种相同的权值即可；
- 如果两个叶子结点之间的距离为奇数，这种情况我们需要用到三种权值。
- 那么我们可以留下长度为奇数的路径，容易证明这种情况我们只需要三种权值即可满足条件（路径长度(geq 3)）；否则只需要一种。
考虑最多用的个数：
- 显然距离为(2)的点我们只能用一种权值，其余距离大于(2)的叶子结点间我们都可以放置不重复的权值。
- 那么只需要消去所有距离为(2)的点即可。
代码写的时候稍微有点点复杂，求最少个数的时候还是考察了两两叶子结点之间的关系。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/13 20:24:55
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int n;
vector <int> G[N];
int d[N];
int cnt[N][2], ans[2];
bool chk[N];
void dfs(int u, int fa) {
if(chk[u]) return;
int sons = 0;
for(auto v : G[u]) if(v != fa) {
dfs(v, u);
if(chk[v]) ++sons, ++cnt[u][1];
else {
cnt[u][0] += cnt[v][1];
cnt[u][1] += cnt[v][0];
}
}
if(sons > 1) ans[1] += sons - 1;
if(cnt[u][0] && cnt[u][1]) ans[0] = 3;
}
void run() {
cin >> n;
for(int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
++d[u], ++d[v];
}
int rt;
for(int i = 1; i <= n; i++) {
if(d[i] > 1) rt = i;
else chk[i] = true;
}
dfs(rt, 0);
ans[1] = n - 1 - ans[1];
ans[0] = max(ans[0], 1);
cout << ans[0] << ' ' << ans[1] << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
C. Perfect Triples
题意：
考虑现在有一个无限长的序列(s)。
然后执行无限次以下操作：
- 选择字典序最小的((a,b,c))满足(a,b,c otin s);
- (aoplus boplus c=0,oplus)为异或符号。
给出若干次询问，回答序列第(n)个元素为多少。
思路：
最开始三个数容易发现为(1,2,3)，考虑其二进制形式：
[001\
010\
011
]
那么我们将其左移两位之后变为：
[0100\
1000\
1100
]
显然这是之后最小的数。
我们发现后面两位二进制位为(0)，我们需要凑出异或值为(0)且字典序最小，那么我们可以分别加上(1,2,3;2,3,1;3,1,2)。
之后以此类推，将二进制位左移，然后加上三种情况...
那么最终将每三个数看作一个结点，最终就是一颗四叉树。
我们只需要确定询问位置在哪一个结点以及与父亲之间的关系(为父亲的第几个儿子)，那么从根往下找就行。
主要是二进制位规律的发现。
细节见代码：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/14 19:45:33
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
ll n;
ll pow4[N], f[N];
void init() {
pow4[0] = 1;
for(int i = 1;; i++) {
pow4[i] = pow4[i - 1] * 4;
if(pow4[i] >= 1e18) break;
}
}
void run() {
cin >> n;
ll now = (n + 2) / 3;
int tot = 0;
while(now > 1) {
int high;
ll res = 0;
for(int i = 0;; i++) {
res += pow4[i];
if(res >= now) {
res -= pow4[i], high = i;
break;
}
}
ll t = now - res - 1;
int r = t % 4;
f[++tot] = r;
now = (now + 2) >> 2;
}
ll a = 1, b = 2, c = 3;
for(int i = tot; i >= 1; i--) {
a <<= 2, b <<= 2, c <<= 2;
if(f[i] == 1) a += 1, b += 2, c += 3;
if(f[i] == 2) a += 2, b += 3, c += 1;
if(f[i] == 3) a += 3, b += 1, c += 2;
}
if(n % 3 == 0) cout << c << '
';
if(n % 3 == 1) cout << a << '
';
if(n % 3 == 2) cout << b << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
init();
int T; cin >> T;
while(T--) run();
return 0;
}