本次综合训练主要是2013年的大连online的题目,有难有易,其中题意不太清楚和要求非常高的题目就直接剔除了。这样题数少了,于是又加了2题2016年大连online的我觉得挺不错的题目。后来发现知识点有点重叠,不过训练一下也无妨。

Find the maximum

题意:给出 $N$ 求出最小的 $2\leq n\leq N$ 使得 $n/\varphi(n)$ 最大。
题解:做这题首先要知道 $\varphi(n)$ 的计算式(不作证明): $\varphi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})$
$$\therefore n/\varphi(n)=\frac{1}{(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})}$$ $$=\frac{1}{\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}…\frac{p_k-1}{p_k}}$$ $$=\frac{p_1}{p_1-1}\frac{p_2}{p_2-1}…\frac{p_k}{p_k-1}$$ $$=(1+\frac{1}{p_1-1})(1+\frac{1}{p_2-1})…(1+\frac{1}{p_k-1})$$
其中 $p_1,p_2,…p_k$ 为 $n$ 的质因子。(考虑到大家提交的很多代码都是打表,这里我写的比较详细)

明显地:

  1. $p_1,p_2,…p_k$ 越小,$n$ 越小,而且 $n/\varphi(n)$ 越大;
  2. $p_1,p_2,…p_k$ 的次方数没有贡献。
    所以,只需要把最小的那些质数乘起来,就能得到满足条件的 $n$
    为了增加(编程)难度,这题又加入了高精度,套用模板,代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX=1000000;
int pr[100000],pt=0;
bool f[MAX];
char s[110];
struct BigInt {
const static int mod = 10000;
const static int DLEN = 4;
int a[100],len;
BigInt() {
memset(a,0,sizeof(a));
len = 1;
}
BigInt(int v) {
memset(a,0,sizeof(a));
len = 0;
do {
a[len++] = v%mod;
v /= mod;
} while(v);
}
BigInt(const char s[]) {
memset(a,0,sizeof(a));
int L = strlen(s);
len = L/DLEN;
if(L%DLEN)len++;
int index = 0;
for(int i = L-1; i >= 0; i -= DLEN) {
int t = 0;
int k = i - DLEN + 1;
if(k < 0)k = 0;
for(int j = k; j <= i; j++)
t = t*10 + s[j] - '0';
a[index++] = t;
}
}
BigInt operator +(const BigInt &b)const {
BigInt res;
res.len = max(len,b.len);
for(int i = 0; i <= res.len; i++)
res.a[i] = 0;
for(int i = 0; i < res.len; i++) {
res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
res.a[i+1] += res.a[i]/mod;
res.a[i] %= mod;
}
if(res.a[res.len] > 0)res.len++;
return res;
}
BigInt operator *(const BigInt &b)const {
BigInt res;
for(int i = 0; i < len; i++) {
int up = 0;
for(int j = 0; j < b.len; j++) {
int temp = a[i]*b.a[j] + res.a[i+j] + up;
res.a[i+j] = temp%mod;
up = temp/mod;
}
if(up != 0)
res.a[i + b.len] = up;
}
res.len = len + b.len;
while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;
return res;
}
bool operator >(const BigInt &b)const {
if (len==b.len) {
int k=len-1;
while (k&&a[k]==b.a[k]) k--;
if (k<0) return false;
return a[k]>b.a[k];
}
return len>b.len;
}
void output() {
printf("%d",a[len-1]);
for(int i = len-2; i >=0 ; i--)
printf("%04d",a[i]);
printf("\n");
}
};

void init_pr()
{
for (int i=2;i<MAX;i++) {
if (!f[i]) pr[++pt]=i;
for (int j=1;j<=pt;j++) {
if (i*pr[j]>=MAX) break;
f[i*pr[j]]=1;
if (i%pr[j]==0) break;
}
}
}

int main()
{
init_pr();
int T;
scanf("%d",&T);
while (T--) {
scanf("%s",s);
BigInt n(s);
BigInt a(1),b(1);
for (int i=1;i<=pt;i++) {
BigInt tmp(pr[i]);
b=a*tmp;
if (b>n) break;
a=b;
}
a.output();
}
return 0;
}

The Frog’s Games

题意:青蛙要跳过一条长为 $L$ ,两岸之间有 $n$ 块石头的河,最多只能跳 $m$ 次,求青蛙至少需要的跳跃能力(跳一次的最大长度)。
题解:可以发现,最后的答案具有单调性,即,若跳跃能力 $k$ 可以跳过这条河,那么跳跃能力 $x(x\geq k)$ 一定能跳过这条河。
由此,使用二分答案可以解决,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=500010;
int a[N];
int L,n,m;

bool check(int l)
{
int cnt=0,pre=0;
for (int i=1;i<=n+1;) {
while (pre+l>=a[i]&&i<=n+1) i++;
pre=a[i-1];
if (++cnt>m) return false;
}
return true;
}

int bs(int l,int r)
{
while (l<r) {
int m=(l+r)>>1;
if (check(m)) r=m;
else l=m+1;
}
return l;
}

int main()
{
while (scanf("%d%d%d",&L,&n,&m)!=EOF) {
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int l=L,r=L;a[n+1]=L;
for (int i=1;i<=n+1;i++)
l=min(a[i]-a[i-1],l);
printf("%d\n",bs(l,r));
}
return 0;
}

Different GCD Subarray Query

题意:给出 $N$ 个数,每次询问 $[L,R]$ 的子数组(类似子串)的 $GCD$ 有多少不同的值。
题解:做这题首先要知道一个结论,值为 $X$ 的数连续地跟其它数进行 $GCD$ 运算,最多出现 $\left \lfloor log_{2}{X}\right \rfloor$ 个不同的数。这个结论刚听到可能很新鲜,但其实很好理解,$GCD$ 运算之后出现了新的 $X$ ,说明新的 $X$ 至少少了一个质因子。而质因子最多有 $\lfloor log_{2}{X}\rfloor$ 个。所以 $GCD$ 个数最多也就 $NlogMAX$ 个,可以用 $map$ 来保存。
其次还需要知道一个技巧,如何统计一个区间内不同的数。对于一个右端点 $R$ ,我们保存能使得值 $X$ 出现的最大的 $L$ ,并在 $L$ 这一点加1,那么每次询问的答案就是 $[L,R]$ 的区间和。
这样把所有询问离线并排序以后,就可以从 $1$ 开始枚举右端点,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

typedef pair<int,int> PII;
const int N=100010;
const int MAX=1000010;
map<int,int> d[2],cur;
struct query {
int l,r,id;
operator < (const query& b) const {
return r<b.r;
}
} q[N];
int a[N],ans[N];
int c[MAX];

int gcd(int a,int b)
{
if (!b) return a;
return gcd(b,a%b);
}

void ins(int x,int d)
{
for (;x<MAX;x+=x&(-x)) {
c[x]+=d;
}
}

int query(int x)
{
if (!x) return 0;
int res=0;
for (;x>0;x-=x&(-x)) {
res+=c[x];
}
return res;
}

int main()
{
int n,m;
while (scanf("%d%d",&n,&m)!=EOF) {
d[0].clear();
d[1].clear();
cur.clear();
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=m;i++) {
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m);
int now=1,pre=0,k=1;
for (int i=1;i<=n;i++) {
for (map<int,int>::iterator it=d[pre].begin();it!=d[pre].end();it++) {
int x=gcd(a[i],it->first);
d[now][x]=max(d[now][x],it->second);
}
d[now][a[i]]=i;
for (map<int,int>::iterator it=d[now].begin();it!=d[now].end();it++) {
int x=it->first;
if (cur.count(x)&&cur[x]<(it->second)) {
ins(cur[x],-1);
ins(it->second,1);
cur[x]=it->second;
} else if (!cur.count(x)) {
ins(it->second,1);
cur[x]=it->second;
}
}
d[pre].clear();
swap(pre,now);
for (;k<=m&&q[k].r==i;k++) {
ans[q[k].id]=query(q[k].r)-query(q[k].l-1);
}
}
for (int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}

The kth great number

题意:给 $n$ 个操作,支持插入和求第 $k$ 大。
题解:一定要认真读题!这道题目的 $k$ 是一开始就给定的,是不会变的!
理解了这一点这就是一道水题,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
int n,k;
while (scanf("%d%d",&n,&k)!=EOF) {
priority_queue< int,vector<int>,greater<int> > Q;
while (n--) {
char s[5];
scanf("%s",s);
if (s[0]=='I') {
int x;
scanf("%d",&x);
Q.push(x);
if (Q.size()>k) Q.pop();
} else {
printf("%d\n",Q.top());
}
}
}
return 0;
}

Dave

题意:在二维平面上给 $N$ 个不重合的点,问边长为 $R$ 的正方形最多能包含多少个点(包含边界)
题解:因为这一题 $1\leq N\leq 1000$ ,所以只要枚举每个点作为左下角的情况就行了(为什么?)
如果 $1\leq N\leq 10000$ ,那么可以用扫描线+线段树的解法。先离散化,并将所有点按照 $x$ $y$ 两个关键字从小到大排序,我们想象垂直于 $x$ 轴有两条间距为 $R$ 的直线,这两条线不断的向右移动,右边的一些点会进入,左边的一些点会退出。那要怎么统计呢?这里要用到一个奇妙的处理,把每一个点向上延伸 $R$ 产生的这条线段加到线段树,也就是区间加1,最后只要每次统计从最低到最高的每个点的最大值就行了(为什么?)
这个做法听起来很简单,不过由于离散化等原因,很容易写错(WA3 = =),代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int N=1010;
typedef long long ll;
struct point {
int x,y,ix,iy;
bool operator < (const point& b) {
return ix<b.ix;
}
} p[N];
int qx[N],qy[N];
ll add[N<<2],sum[N<<2];
int n,r,cntx,cnty;

void push_up(int rt)
{
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}

void push_down(int rt)
{
if (add[rt]) {
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
sum[rt<<1] += add[rt];
sum[rt<<1|1] += add[rt];
add[rt] = 0;
}
}

void update(int L,int R,int d,int l,int r,int rt)
{
if (L<=l&&r<=R) {
add[rt]+=d;
sum[rt]+=d;
return;
}
push_down(rt);
int m=(l+r)>>1;
if (L<=m) update(L,R,d,lson);
if (m<R) update(L,R,d,rson);
push_up(rt);
}

ll query(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R) {
return sum[rt];
}
push_down(rt);
int m=(l+r)>>1;
ll res=0;
if (L<=m) res=max(res,query(L,R,lson));
if (m<R) res=max(res,query(L,R,rson));
return res;
}

int ins(int k,int d)
{
int i;
for (i=k;i<=n&&p[i].ix==p[k].ix;i++) {
int pos=upper_bound(qy+1,qy+cnty+1,p[i].y+r)-qy-1;
update(p[i].iy,pos,d,1,cnty,1);
}
return i;
}

int main()
{
while (scanf("%d%d",&n,&r)!=EOF) {
cntx=cnty=0;
for (int i=1;i<=n;i++) {
scanf("%d%d",&p[i].x,&p[i].y);
qx[++cntx]=p[i].x;
qy[++cnty]=p[i].y;
}
sort(qx+1,qx+cntx+1);
sort(qy+1,qy+cnty+1);
cntx=unique(qx+1,qx+cntx+1)-qx-1;
cnty=unique(qy+1,qy+cnty+1)-qy-1;
for (int i=1;i<=n;i++) {
p[i].ix=lower_bound(qx+1,qx+cntx+1,p[i].x)-qx;
p[i].iy=lower_bound(qy+1,qy+cnty+1,p[i].y)-qy;
}
sort(p+1,p+n+1);
memset(sum,0,sizeof(sum));
memset(add,0,sizeof(add));
int ans=0;
for (int i=1,k=1;i<=n;) {
while (k<=n&&p[k].x-p[i].x<=r) {
k=ins(k,1);
}
ans=max((ll)ans,sum[1]);
i=ins(i,-1);
}
printf("%d\n",ans);
}
return 0;
}

Weak Pair

题意:一棵树的每个节点有一个非负权值,如果 $u$ 是 $v$ 的祖先($u\neq v$),并且两点的权值的积 $a_u*a_v\leq k$ ,则称它们为”Weak Pair”。求”Weak Pair”的数目。
题解:由于树中任意一个节点的祖先都在同一条链上,所以只需要考虑如何快速的求出一条链上的”Weak Pair”。这题有很多解法,我想到的是将祖先都插入到树状数组,那么在 $u$ 这一点,答案就加上 $x\leq \frac{k}{a_u}$ 的个数。
考虑到权值范围很大,要用离散化,并且要注意 $a_u=0$ 的情况,代码如下:
【还有一点就是,题目给的是明确的父子关系,但是没有给根,一定要自己找,WA3 = =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1e5+5;
const int MAX=2*N;
const long long INF=1LL<<33;
long long a[N],b[N],A[2*N];
int c[MAX];
struct edge {
int go,next;
} eg[2*N];
int last[N];
bool vis[N];
int tot;
long long ans;

void adde(int x,int y)
{
eg[++tot].go=y;
eg[tot].next=last[x];
last[x]=tot;
}

void ins(int x,int d)
{
for (;x<MAX;x+=x&(-x)) {
c[x]+=d;
}
}

long long query(int x)
{
long long res=0;
for (;x;x-=x&(-x)) {
res+=c[x];
}
return res;
}

void dfs(int x)
{
ans+=query(b[x]);
ins(a[x],1);
// printf("%d %d\n",x,ans);

for (int i=last[x];i;i=eg[i].next) {
dfs(eg[i].go);
}
ins(a[x],-1);
}

int main()
{
int T,n;
long long k;
scanf("%d",&T);
while (T--) {
tot=0;
memset(last,0,sizeof(last));
scanf("%d%lld",&n,&k);
for (int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
A[i]=a[i];
if (a[i]==0) {
A[n+i]=b[i]=INF;
}
else {
A[n+i]=b[i]=k/a[i];
}
}
sort(A+1,A+1+n*2);
for (int i=1;i<=n;i++) {
a[i]=lower_bound(A+1,A+1+2*n,a[i])-A;
b[i]=lower_bound(A+1,A+1+2*n,b[i])-A;
}
memset(vis,0,sizeof(vis));
for (int i=1;i<n;i++) {
int x,y;
scanf("%d%d",&x,&y);
adde(x,y);
vis[y]=1;
}
int i=1;
while (i<=n&&vis[i]) i++;
ans=0;
dfs(i);
printf("%lld\n",ans);
}
return 0;
}