slove 2/10
rank 391
补题 5/10
---------------------------------------------------
link
6614 AND Minimum Spanning Tree
题意: 给出n个点每个点的值是i ，规定点与点之间的边的值是i&j ,要求是这个图联通的最小的边的值的和，并且输出字典序最小的结果。
做法： 首先考虑除1以外的每一个点，以i为例，假如i为偶数那么和1连边的代价最低是0 假如i不为偶数，则考虑二进制，；例如i的二进制是1101那么取10 也就是2的代价最小，如果i的二进制是1111那么取10000代价最小，如果10000大于n则只能取1代价为1.
实现代码就是首先初始化每一个数的二进制下的第一个不为1的数位。然后1-n扫过去就行
#include<bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n, a[MAX], binary[MAX];
int Ans[MAX];
void solve() {
for (int i = 2; i <= 2e5; i++)
{
int temp = i, tot = 0;
binary[i] = 64;
while (temp != 0)
{
if (temp % 2 == 0)
{
binary[i] = tot;
break;
}
temp /= 2;
tot++;
}
}
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
int ans = 0;
for (int i = 2; i <= n; i++)
{
if (binary[i] == 64 && n > i)
ans += 0, Ans[i] = i + 1;
else if (binary[i] == 64)
ans += 1, Ans[i] = 1;
else
ans += 0, Ans[i] = 1 << binary[i];
}
printf("%d\n", ans);
for (int i = 2; i <= n; i++)
printf(i == n ? "%d\n" : "%d ", Ans[i]);
}
}
int main(void)
{
solve();
return 0;
} 6616 Divide the Stones
两个数字n，k，表示有n块石头，第 i 块石头重量为 i，能否将这 n 块石头分为 k 份，并且使得 k 份的重量相等。
保证 k 是 n 的因子
1、n块石头的总和是
2、首先假设 n 是偶数，并且每份的石头的个数是偶数，那么每2k个石头，前k个石头顺序给
3、如果每块石头的个数是奇数，那么每块石头的重量就是浮点数，显然不合法。
4、如果 n 是奇数，那么每份石头的个数和 k 也一定是奇数，那么考虑先把 3*k 个因子分成 3 等份，然后剩下的 n - 3*k 个就是偶数个了，按照方法2来分剩下的石头就可以找到满足答案的条件了。
5、问题在于如果把 3*k 个石头分为相等的3份，手玩几组案例，
先把前 k 个顺序给，然后k+1个到2*k个顺序下移k/2+1个，然后算一下剩下的数字是多少，加一下就可以啦。
n=15 k=5 的情况如下
1 8 15
2 9 13
3 10 11
4 6 14
5 7 12
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
vector<int>v[100005];
ll sum[100005];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n, k;
sc("%d%d", &n, &k);
for (int i = 1; i <= k; i++)
{
sum[i] = 0;
v[i].clear();
}
if (n == k)
{
if (n == 1)
{
printf("yes\n");
printf("1\n");
}
else
printf("no\n");
}
else if (n % 2 == 0 && (n / k) % 2 == 0)
{
int now = 0;
int f = 0;
while (now < n)
{
if (f)
{
for (int i = 1; i <= k; i++)
v[i].push_back(now + i);
}
else
{
for (int i = 1; i <= k; i++)
v[i].push_back(now + k + 1 -i);
}
now += k;
f ^= 1;
}
printf("yes\n");
for (int i = 1; i <= k; i++)
{
int sz = v[i].size();
for (int j = 0; j < sz; j++)
printf("%d%c", v[i][j], j == sz - 1 ? '\n' : ' ');
}
}
else if (n % 2 == 0 && (n / k) % 2 == 1)
{
printf("no\n");
}
else
{
for (int i = 1; i <= k; i++)
v[i].push_back(i);
for (int i = 1; i <= k / 2 + 1; i++)
v[i].push_back(k + k / 2 + i);
for (int i = k / 2 + 1 + 1; i <= k; i++)
v[i].push_back(k + i - k / 2 - 1);
for (int i = 1; i <= k; i++)
v[i].push_back((3 * k + 1) / 2 * 3 - v[i][0] - v[i][1]);
int now = 3 * k;
int f = 0;
while (now < n)
{
if (f)
{
for (int i = 1; i <= k; i++)
v[i].push_back(now + i);
}
else
{
for (int i = 1; i <= k; i++)
v[i].push_back(now + k + 1 - i);
}
now += k;
f ^= 1;
}
printf("yes\n");
for (int i = 1; i <= k; i++)
{
int sz = v[i].size();
for (int j = 0; j < sz; j++)
printf("%d%c", v[i][j], j == sz - 1 ? '\n' : ' ');
}
}
}
} 6620 Just an Old Puzzle
给一个4*4的拼图，问能否还原。
逆序数+0的位置。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool num[18];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(num, false, sizeof(num));
int t, ans = 0;
for (int i = 1; i <= 4; i++)
{
for (int j = 1; j <= 4; j++)
{
scanf("%d", &t);
if (t == 0)
ans += i + j;
num[t] = true;
for (int k = t + 1; k <= 16; k++)
if (num[k] == true)
ans++;
}
}
if (ans & 1)
printf("Yes\n");
else
printf("No\n");
}
} 6621 K-th Closest Distance
区间中查询离某个数字第K近的数字
主席树+二分，强制在线，赛时看到K比较小，直接暴力，然后超时，忘了写之前提出的二分思路，T到爆炸。
#include <bits/stdc++.h>
#define ll long long
#define imid int mid=(left+right)/2;
using namespace std;
struct node
{
int l;
int r;
ll sum;
}tree[100005 * 55];
int root[100005], a[100005], t[100005], n, m, cnt;
int ql, qr, p, k, qq;
void init()
{
root[0] = 0;
tree[0].l = tree[0].r = tree[0].sum = 0;
cnt = 1;
}
void build(int num, int& rot, int left, int right)
{
tree[cnt++] = tree[rot];
rot = cnt - 1;
tree[rot].sum++;
if (left == right)
return;
imid;
if (num <= mid)
build(num, tree[rot].l, left, mid);
else
build(num, tree[rot].r, mid + 1, right);
}
int querycnt(int pre, int nex, int L, int R, int left, int right)
{
if (L <= left && right <= R)
return tree[nex].sum - tree[pre].sum;
imid;
int ans = 0;
if (L <= mid)
ans += querycnt(tree[pre].l, tree[nex].l, L, R, left, mid);
if (R > mid)
ans += querycnt(tree[pre].r, tree[nex].r, L, R, mid + 1, right);
return ans;
}
bool check(int r)
{
int L = lower_bound(t + 1, t + 1 + qq, p - r) - t;
int R = upper_bound(t + 1, t + 1 + qq, p + r) - t - 1;
int res = querycnt(root[ql - 1], root[qr], L, R, 1, n);
if (res >= k)
return true;
return false;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
t[i] = a[i];
}
sort(t + 1, t + 1 + n);
qq = unique(t + 1, t + 1 + n) - t - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(t + 1, t + 1 + qq, a[i]) - t;
init();
for (int i = 1; i <= n; i++)
{
root[i] = root[i - 1];
build(a[i], root[i], 1, n);
}
int X = 0;
while (m--)
{
scanf("%d%d%d%d", &ql, &qr, &p, &k);
ql ^= X, qr ^= X, p ^= X, k ^= X;
int l = 0, r = 1e6 + 5;
while (l + 1 < r)
{
int k = (l + r) / 2;
if (check(k))
r = k;
else
l = k;
}
if (!check(l))
l = r;
printf("%d\n", l);
X = l;
}
}
}
/*
5 4
1 2 3 4 5
1 3 2 3
1 5 2 4
1 4 4 5
2
3
1
*/ 6623 Minimal Power of Prime
找出这个数字质因数分解后的最小指数。
分块暴力，先将4000内的素数筛出来，然后指数最大就是4，然后对他开四方，三方，二分，如果是整数开方的指数就是答案，否则答案是1.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 4000;
int prime[MAXN];
int cnt;
bool vis[MAXN];
void Eluer()
{
for (int i = 2; i < MAXN; i++)
{
if (vis[i] == false)
prime[cnt++] = i;
for (int j = 0; i * prime[j] < MAXN && j < cnt; j++)
{
vis[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}
ll fang(ll n, int t)
{
ll l = 1, r = n;
while (l <= r)
{
ll m = (l + r) / 2;
double tt = 1;
ll x = 1;
for (int i = 0; i < t; i++)
{
tt = tt * m;
if (tt > 2e18)
{
x = 2e18;
break;
}
x = x * m;
}
if (x < n)
l = m + 1;
else
r = m - 1;
}
return l;
}
ll power(ll a, int b)
{
ll res = 1;
while (b--)
res *= a;
return res;
}
int main()
{
Eluer();
int T;
scanf("%d", &T);
while (T--)
{
ll n;
scanf("%lld", &n);
int ans = 999;
for (int i = 0; i < cnt&&prime[i]<=n; i++)
{
if (n % prime[i] == 0)
{
int tot = 0;
while (n % prime[i] == 0)
{
tot++;
n /= prime[i];
}
ans = min(ans, tot);
}
}
if (n == 1 || ans == 1)
printf("%d\n", ans);
else if (power(fang(n, 4), 4) == n)
printf("%d\n", min(ans, 4));
else if (power(fang(n, 3), 3) == n)
printf("%d\n", min(ans, 3));
else if (power(fang(n, 2), 2) == n)
printf("%d\n", min(ans, 2));
else
printf("%d\n", 1);
}
}
京公网安备 11010502036488号