#633 DIV2 题解
组样例，每组样例给一个， 代表个三角形按照菱形的样子尽可能的拼凑在一起(可以旋转)，如图所示
问对于每个有多少中不同的拼法(存在一个菱形，由不同的三角形覆盖则属于一种拼法)。
2
2
1
2
1
关注中间未旋转的菱形数量， 发现每次只有有一个这样的菱形可以由两个相同的三角形覆盖，同时每一个这样的菱形都可以由两个相同的三角形覆盖，且一旦这样覆盖之后，整个图没有变化的余地，所以这样的菱形个数就是答案，而对于来说会有个这样的菱形，所以直接输出即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
ll n = 0;
scanf("%lld", &n);
printf("%lld\n", n);
}
return 0;
}
组样例，每组给一个，再给个数，现在重新排列这个数，使得所有满足条件的 有。
2
6
5 -2 4 8 6 5
4
8 1 4 2
5 5 4 6 8 -2
1 2 4 8
首先将数组排序，之后按照这样的方式摆放。显然除去首尾，对于任意一个位置的数只有 或者 这两种可能。
因为是排好序的
所以，所以，同理可得。
所以倒序输出即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
vector<int> vec;
int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
int n = 0;
vec.clear();
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
}
sort(a + 1, a + 1 + n);
int tot1 = 1, tot2 = n;
for(int i = 1;i <= n;i++) {
if(i % 2 == 0) {
vec.push_back(a[tot1++]);
} else {
vec.push_back(a[tot2--]);
}
}
reverse(vec.begin(), vec.end());
int len = vec.size();
for(int i = 0;i < len;i++) {
printf("%d%c", vec[i], i == len - 1 ? '\n' : ' ');
}
}
return 0;
}
组样例，每组给一个，再给个数，进行很多轮操作，每一轮操作选取其中的一些数，将，为第轮操作。问最少需要多少轮操作，使得序列为一个非降序列。
3
4
1 7 6 5
5
1 2 3 4 5
2
0 -4
2
0
3
对于，我们需要考虑和之间的大小关系，如果，就不需要改变，否则，就需要将其变为，设之间的差为。关注到我们的操作是加，这就是在二进制表示的某一位上加1，且选数是任意的，所以我们只需要在所有的中找到二进制表示中1所在的最高位即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
const int maxn = 4e5+5;
const int MOD = 1e9+7;
#define mod(x) x % MOD
#define INF 0x3f3f3f3f
int a[maxn];
int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
int n = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
}
if(n == 1) {
puts("0");
continue;
}
int Max = a[1], ans = 0;
for(int i = 2;i <= n;i++) {
if(a[i] < Max) {
int d = Max - a[i], res = 0;
while(d) {
res++;
d = d / 2;
}
ans = max(ans, res);
} else {
Max = a[i];
}
}
printf("%d\n", ans);
}
return 0;
}
给一颗个点的树，在树边上加上正整数边权使得，任意两个叶子之间简单路径的边权异或和都等于0。问树边权最少能有多少不同的数和最多能有多少不同的数
6
1 3
2 3
3 4
4 5
5 6
1 4
首先最少的很好解决，如果一个叶子和其他的任意叶子中的一个之间相隔点数为偶数，则中间会有奇数条边，用这种方式，所以答案是3
否则，所有叶子两两之间只有偶数条边，用即可，所以答案是1
之间就是考虑最多的情况了，考虑树形，为子树中最多可能的不同的边权个数。同时注意到，不管是哪个叶子，只要该叶子在子树中，其到节点的简单路径边权异或和就应该是相同的。而边权上又可以放很大的数，所以子树中的叶子到节点的简单路径边数大于等于2，则这几条边都对答案有贡献。如果只是等于1的话，由于一个数的异或和只能是的本身，所以只有其中一条对答案有贡献。同时注意的父节点也可能是叶子，特判一下只能做一次贡献。
具体转移见代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> G[maxn];
vector<int> leaf;
int deg[maxn], depth[maxn], dp[maxn], flag[maxn];
void dfs(int u, int fa) {
depth[u] = depth[fa] + 1;
bool f = 0;
for(int i = 0;i < G[u].size();i++) {
int v = G[u][i];
if(v == fa) continue;
dfs(v, u);
if(deg[v] > 1) {
dp[u] += dp[v] + 1;
} else {
if(f == 0 && flag[fa] != 1) {
f = 1;
dp[u]++;
}
}
}
}
int main(){
int n = 0;
scanf("%d", &n);
for(int i = 1;i < n;i++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
deg[u]++, deg[v]++;
}
for(int i = 1;i <= n;i++) {
if(deg[i] == 1) {
leaf.push_back(i);
flag[i]++;
}
}
int ans1 = 0;
dfs(1, 0);
for(int i = 1;i < leaf.size();i++) {
if(abs(depth[leaf[i]] - depth[leaf[0]]) % 2 == 1) {
ans1 = 3;
}
}
if(ans1 == 0) ans1 = 1;
printf("%d %d\n", ans1, dp[1]);
return 0;
}
集合是一个空集， 考虑往其中加元素，找到字典序最小的三元组，有，且未在中出现过。则讲其加入，组样例，每组样例一个，输出集合中第个数。
9
1
2
3
4
5
6
7
8
9
1
2
3
4
8
12
5
10
15
第一个三元组是(1, 2, 3)，第二个是(4, 8, 12)。考虑的二进制是0100，而是肯定要大于的，不然就可以互换位置，同时也要大于，所以的最高位1一定要比0100的最高位高，同时要保证尽可能小，所以为1000，这样就是1100，
做一步推广，将二进制表示的位数补齐到2的倍数时的最高两位一定是01，的最高两位一定是，的最高两位一定是，因为如果是10或者11的话，则在，必定有一个更小的，其对应的或者将这个数用过的。
在最高位确定后，其他的位数也两位两位的看的话，这个时候就未必一定是了，有可能是 ，换成四进制的话也就是0，1，2，3。
当的某一位是1时，显然字典序最小是(1, 2, 3)的组合。
当的某一位是2时，这个时候的这一位不能取1，因为之前有过(1, 2, 3)，这个时候如果是(2, 1, 3)的话显然最后的3是重复的。所以只能是(2, 3, 1)。
当的某一位是3时，的这一位考虑到字典序最小取1，这样就是(3, 1, 2)也没有重复。
0的时候直接都是0即可。
最后结论：将，，换成四进制表示，然后考虑考虑每个的位数上为多少。
如果该位上为1，则b为2，c为3
其他同上述(2, 3, 1)和(3, 1, 2)
所以先从求出对应的三元组，再由对应的三元组求出，最后看对3的余数，来判断输出中的哪一个。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 50;
ll bit[maxn], a, b, c;
vector<ll> vec;
int main(){
int t = 0;
scanf("%d", &t);
bit[0] = 1;
for(int i = 1;i <= 30;i++) {
bit[i] = bit[i - 1] * 4ll;
}
while(t--) {
vec.clear();
a = b = c = 0;
ll n;
scanf("%lld", &n);
ll tmp = (n - 1ll) / 3ll + 1;
for(int i = 0;i <= 30;i++) {
if(tmp > bit[i]) {
tmp -= bit[i];
} else {
a = bit[i] + tmp - 1; break;
}
}
tmp = a;
while(tmp) {
vec.push_back(tmp % 4);
tmp /= 4;
}
reverse(vec.begin(), vec.end());
int len = vec.size();
for(int i = 0;i < len;i++) {
if(vec[i] % 4 == 1) {
b = b + 2;
c = c + 3;
} else if(vec[i] % 4 == 2) {
b = b + 3;
c = c + 1;
} else if(vec[i] % 4 == 3) {
b = b + 1;
c = c + 2;
}
if(i != len - 1) b = b * 4, c = c * 4;
}
if(n % 3 == 1) {
printf("%lld\n", a);
} else if(n % 3 == 2) {
printf("%lld\n", b);
} else {
printf("%lld\n", c);
}
}
return 0;
}
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。