Task 1：锦标赛
题目描述：
给出2^n个数，进行n此操作。每次操作对当前剩下的数两两比较(任意组合都可以)，留下较大的那个。现在询问对于每个数，做多可以进行多少操作。
题目分析：
我们可以很显然发现，按照题意进行操作我们可以得到一颗完全二叉树。所以对于一个数a，有b个数小于等于a，那么ans=log2(b)。
Code:
using namespace std;
const
int MAXN =
1<<
20;
int b, n;
int a[MAXN+
5],
q[MAXN+5];
int main(){
scanf(
"%d",&b), n =
1<<b;
for(
int i =
1; i <= n; ++ i)
scanf(
"%d",&a[i]),
q[i] = a[i];
sort(
q+
1,
q+n+
1);
for(
int i =
1; i <= n; ++ i){
int p = upper_bound(
q+
1,
q+n+
1, a[i])-
q-
1;
printf(
"%d",log2(p));
if(i != n) putchar(
32);
else putchar(
10);
}
return 0;
}
Task 2:不完美值
题目描述：
给出数组a[]，区间[l,r]。令xi表示sigma(b) (b|a[i] && b!=a[i])。求sigma(abs(ai-xi)) (l<=i<=r)。
题目分析：
这道题就是裸的求一个数的真因子和。但是考虑到做多有10^7个数，所以不能暴力的对每个数用sqrt(n)的时间来求，这样肯定会T。
所以我们就需要一个线性的算法。
我们定义f[i]表示i的因子和，p是素数且p|i。
所以f[i]=(1+p1+p1^2+……p1^k1)*(1+p2+p2^2+……p2^k2)*……*(1+pn+pn^2+……pn^kn)。
这样我们就可以用类似筛法来求了。
Code：
int l, r;
long long f[
10000005], ans;
inline void getans(
int n){
f[
1] =
1;
int tmp, sum, d;
for(
int i =
2; i <= n; ++ i){
if(!f[i]){
for(
int j =
2; j
*i <= n; ++ j){
tmp = j
*i, sum =
0, d = i;
while(tmp
%i ==
0) tmp /= i, sum += d, d
*= i;
if(!f[j
*i]) f[j
*i] =
1;
f[j
*i]
*= sum;
}
f[i] = i+
1;
}
if(i >= l) ans +=
abs(i+i-f[i]);
}
}
int main(){
scanf(
"%d%d",&l,&r);
getans(r);
printf(
"%I64d\n",ans);
return 0;
}
Task 3:糖果
题目描述：
给出n(n<10^5)个节点，每个节点有一个权值p(p<10^7)。连接两个节点i,j的代价为min(pi%pj,pj%pi)。
求将这些节点连成一棵树的最小代价。
题目分析：
首先我们可以很显然的看出这道题就是一道最小生成树，但如果暴力建树的话，最多就会有n^2条边。
就算不考虑时间，但是空间上也过不了。
所以解题的关键就在于怎样把一些一定不会被用到的边删去，在连边的时候只连那些有可能被选中的边。
按照这样想下去。
如果我们先把点按从小到大排序。那么在i,j(i<j)之间连边的代价就一定是pj%pi。
那么我们可以这样考虑：将数轴pi等分。
那么在每个区间内对于i来说，如果连的边出现在最小生成树中的话，那么i只可能和这个区间内%pi最小的那个。
这样边就被优化成了n*log2(10^7)条，这样就可以过了。
Code：
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include<fstream>
#include<cstdlib>
using namespace std;
#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
typedef long long ll;
typedef pair<
int,
int> P;
#define X first
#define Y second
const int MAXN =
1<<
19, MAXM =
1e7 +
5;
vector <P> V[MAXM];
int najbliz[MAXM];
int p[MAXN];
int n;
int root[MAXN], rnk[MAXN];
int bio[MAXM], ozn[MAXM];
int find(
int x)
{
if (root[x] == -
1)
return x;
return root[x] = find(root[x]);
}
void merge(
int a,
int b)
{
a = find(a);
b = find(b);
assert(a != b);
if (rnk[a] > rnk[b]) root[b] = a;
else if (rnk[b] > rnk[a]) root[a] = b;
else {
rnk[a]++;
root[b] = a;
}
}
int main()
{
freopen(
"sirni.in",
"r",stdin);
freopen(
"sirni.out",
"w",stdout);
scanf(
"%d", &n);
memset(ozn, -
1,
sizeof ozn);
REP(i, n) {
scanf(
"%d", &p[i]);
najbliz[p[i]] = p[i];
if (ozn[p[i]] == -
1)
ozn[p[i]] = i;
}
for (
int i=MAXM-
2; i>=
0; i--)
if (!najbliz[i])
najbliz[i] = najbliz[i+
1];
REP(i, n) {
if (bio[p[i]]++)
continue;
if (najbliz[p[i]+
1]) {
if (
2*p[i] >= MAXM || najbliz[
2*p[i]] != najbliz[p[i]+
1])
V[najbliz[p[i]+
1] - p[i]].push_back(P(i, ozn[najbliz[p[i]+
1]]));
}
for (
int j=
2*p[i]; j<MAXM && najbliz[j]; j+=p[i])
if (j + p[i] >= MAXM || najbliz[j+p[i]] != najbliz[j])
V[najbliz[j]-j].push_back(P(i, ozn[najbliz[j]]));
}
memset(root, -
1,
sizeof root);
ll rje =
0;
REP(i, MAXM)
REP(j, (
int) V[i].size())
if (find(V[i][j].X) != find(V[i][j].Y)) {
merge(V[i][j].X, V[i][j].Y);
rje += i;
}
REP(i, n)
if (ozn[p[i]] == i) { assert(find(i) == find(
0)); }
printf(
"%lld\n", rje);
return 0;
}
