【清北学堂周末刷题班】 Day5

T1 题目名称:大大大

题目描述：

  Illyasviel:“两个数乘起来会比一个数大吗？”

  Star-dust:“不知道啊，来算算吧。”

  读入一个nn,对于一个三元组(i,j,k)(i,j,k)满足要求当且仅当1≤i,j,k≤n1\leq i,j,k\leq n且i×j≥ki\times j \geq k。

输入描述:

  一行一个数字nn。

输出描述:

  一行一个ansans表示满足要求的三元组的个数。

输入样例:

10

输出样例:

900

数据范围:

对于30%的数据n≤100n\leq 100

对于60%的数据n≤5000n\leq 5000

对于100%的数据n≤100000n\leq 100000

思路

看到这道题目，我用2分钟的时间写出来了第一个暴力，O(n3)O(n^3)

也就是三十分的代码：（也就是直接暴力了一下子）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int n;
long long ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			if(i*j>=k) ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

然后我想，这样的话那肯定1~n的数列中∀i∗j>=k\forall i*j>=k一定有i*j个符合要求啊，然后如果大于ijij的话加n就好了

60分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int n;
long long ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			ans+=(i*j>n? n:i*j);
		}
	}
	cout<<ans<<endl;
	return 0;
}

所以怎么拿到一百分呢？

实际上我题解也没有看懂

题解是这样说的：我们来反向考虑有多少个不满足要求的三元组，即i∗j<ki*j<k 那么我们考虑将(i,j)插入i∗j+1i*j+1中，然后求一个前缀和即可。

复杂度分析:

i∗j>ni*j>n时可直接break。

对于一个i有⌊ni⌋\lfloor\frac n i\rfloor个满足要求的j使得i∗j<ni*j<n总有效点对个数为∑i=1n⌊ni⌋\sum_{i=1}^n\lfloor\frac n i\rfloor约等于n∑i=1n1in\sum_{i=1}^n \frac 1 i

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long n;
long long a[100005],b[100005];
long long ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n/i;j++)
		a[j*i]++;
	}
	for(int i=1;i<=n;i++)
	b[i]=b[i-1]+a[i-1];
	for(int i=1;i<=n;i++) ans+=b[i];
	cout<<n*n*n-ans<<endl;
	return 0;
}

T2 题目名称:kkk

题目描述：

  Star-dust:“你会最短路吗？”

  Illyasviel:“当然！”

  Star-dust:“那你来求一求这k个点中是否存在长度%P为L的路径吧。”

  Illyasviel:“这和最短路有什么关系吗?”

  Star-dust:“不知道啊~”

输入描述:

​ 第一行一个数字TT代表数据组数。

​ 对于每个数据，第一行三个数n,m,k,P,Ln,m,k,P,L表明有nn个点，mm条边，kk个在图中的点。

​ 接下来一行k个数代表关键点。

​ 接下来mm行每行三个数x,y,zx,y,z表示xx和yy之间有一条长度为zz的路径。

输出描述:

​ 输出T行，当存在一条路径从起点和终点都在k个点中输出"YES",否则输出"NO"（不包含引号）。

输入样例:

1

2 3 2 3

1 2 1

2 1 1

输出样例:

YES

样例解释:

1-2-1-2

数据范围:

对于40%的范围T≤500,0≤L,z≤P≤20,k≤n≤m≤500,k≤10T\leq 500,0\leq L,z\leq P\leq 20,k\leq n\leq m\leq 500,k\leq 10

对于80%的范围T≤500,0≤L,z≤P≤20,k≤n≤m≤500T\leq 500,0\leq L,z\leq P\leq 20,k\leq n\leq m\leq 500

对于100%的范围T≤500,0≤L,z≤P≤109,k≤n≤m≤500T\leq 500,0\leq L,z\leq P\leq 10^9,k\leq n\leq m\leq 500,PP是奇数。

思路

我们考虑从若存在一条长度为ll的边，走过去走回来的长度为2∗l2*l，我们可以反复走这条边，可以走k∗2∗lk*2*l

那么它在%P意义下等价于gcd(l,P),如果我们有一条长度为x的路径经过这路径两端中的一个，那么就可以通过反复走这条边达到k∗gcd(x,l,P)k*gcd(x,l,P)的全部长度。

如果对多个路径考虑，那么就能走到k∗gcd(w1,w2,w3...,wn,P)k*gcd(w1,w2,w3...,wn,P)的全部值。（那其实k个关键点一点用也没有）

就考虑gcd(w1,w2,w3...,wn,P)gcd(w1,w2,w3...,wn,P)是否为L的因数即可。

复杂度O(T∗m∗log(P))O(T*m*log(P))

PS:我没看懂，到时候到WH了去问一下wjyyy&&Dew&&HCLOVE&&童佬吧

代码

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
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
/*	if(y==0){
		y++,y--;
		return 0;
	}*/
	if(x%y==0)return y;
	return gcd(y,x%y);
}
int solve(){
	int n,m,k,P,L;
	scanf("%d%d%d%d%d",&n,&m,&k,&P,&L);
	for(int i=1;i<=k;i++){
		int x;
		scanf("%d",&x);
	}
	if(L==0)L=P;
	int A=P,B=P;
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(z==0){
			z=P;
		}
		A=gcd(A,z);
	}
	B=gcd(B,L);
	if(B%A==0)printf("YES\n");
	else printf("NO\n");
}
int main(){
	int T;
	//freopen("kkk10.in","r",stdin);
	//freopen("kkk10.out","w",stdout);
	scanf("%d",&T);
	while(T--)solve();
}

T3 题目名称:A的B次方

题目描述:

  Illyasviel:“今天我们学了ABA^B?”

  Star-dust:“我们也学了诶！”

  Star-dust:“那我来考考你吧！”

  已知A和P，求一个任意的B使得AB≡BA(mod  P)A^B≡B^A(\mod P)

输入描述：

  一行输入两个整数AA和PP。

输出描述：

  输出任意一个满足要求的数字BB。

  BB要为一个不大于101810^{18}的正整数。

样例输入：

78 100

样例输出：

16

数据范围：

对于30%的数据:

1≤A,P≤10001\leq A,P\leq 1000

对于30%的数据:

PP为质数

对于100%的数据:

64≤A≤10964\leq A\leq 10^9

P≤109P\leq 10^9

1≤B≤10181\leq B\leq10^{18}

思路

数学题（我不会数学，这个题解也没有看懂）

PS:我还没学PHI怎么办？

我们考虑构造一个在%P意义下和A相同的数就好了。

A>64这意味着A的k∗phi(P)+Ak*phi(P)+A次方和A的A次方等价。

那可行的一组答案就为A+P∗phi(P)A+P*phi(P)

代码

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
#include<bits/stdc++.h>
using namespace std;
long long A,P;
long long phi(long long x){
	long long ans=1;
	for(long long i=2;i*i<=x;i++){
		if(x%i==0)ans*=(i-1),x/=i;
		while(x%i==0)x/=i,ans*=i;
	}
	return ans*max(x-1,1LL);
}
long long power(long long x,long long k,long long P){
	long long ans=1;
	x%=P;
	while(k){
		if(k&1)(ans*=x)%=P;
		(x*=x)%=P;
		k>>=1;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&A,&P);
	long long B=A+P*phi(P);
	printf("%lld\n",B);
	return 0;
//	scanf("%lld\n",&P);
//	printf("%lld %lld\n",P,phi(P));
//	return 0;
	printf("%lld %lld\n",power(A,B,P),power(B,A,P));
    return 0;
}

T4 题目名称：灯塔

题目描述：

  Star-dust:“每个人都是灯塔，灯塔之间相隔万里，无法触碰无法沟通，唯一能做的就是用自己的光去照耀别人。”

  Illyasviel:“如果能被某个灯塔一直照耀，那一定很幸福吧。”

  Star-dust:“我能成为你的灯塔吗？”

  Illyasviel:“好啊~”

  海上有着nn个灯塔，第ii个灯塔在位置ii闪耀着,灯塔的光覆盖着[i−di,i+di][i-d_i,i+d_i]的所有灯塔，对于第kk个灯塔，他想知道有多少个ii满足i<ki<k且至少存在一个在ii和kk中间的灯塔jj满足灯塔jj同时被灯塔ii和灯塔kk照耀，并且jj和kk的距离小于等于jj和ii之间的距离。

输入描述：

  第一行一个整数nn。

  接下来一行nn个数字，第ii个代表did_i。

输出描述：

  一行一个答案ansans。

  fkf_k表示对于第kk个灯塔有多少个灯塔满足条件。

  ansans为n个fkf_k的异或和。

样例输入：

10
2 2 3 2 3 2 3 3 3 1

样例输出：

2

样例解释：

对应位置答案分别为0 0 1 2 3 3 3 4 4 2

数据范围:

对于20%的数据:n≤100n\leq 100

对于20%的数据:n≤5000n\leq5000

对于20%的数据:didi完全相同

对于20%的数据:n≤100000n\leq 100000

对于100%的数据:n≤3000000n\leq 3000000,1≤di≤n1 \leq d_i\leq n

思路

我的思路是暴力，可以得到20%的分数

40%：

考虑对于一队i和k

判断是否存在满足条件的j
j≤k−dk j\le k-d_k

2∗j≤j+k 2*j\le j+k

i+di≤j i+d_i\le j

整理一下就有了
i+di≤j≤k−dk i+d_i\le j\le k-d_k

2∗j≤i+k 2*j\le i+k

对于一对i,k有一个j的可行区间，第二条限制贪心取最右的判断是否满足要求。

时间复杂度O(n2)O(n^2)

60%:

基于40%的做法再对20%的数据做特判

20%的数据的答案属于一个阶梯上升然后一个平台然后再下降。

能人眼观察得到。

80%:

我们考虑再整理一下40%的式子
k−dk≤j k-d_k\le j

j≤i+di j\le i+d_i

j+k≤2∗j j+k\le 2*j

再对每一条式子进行解析

对于一个(i,k)而言，为了满足j更靠近k肯定是j越往右放越好。

j≤i+dij\le i+d_i那么对于i来说j最好就放到i+dii+d_i上。

k≤2∗j−ik\le 2*j-i对于这一条就限定了(i,j)可以对k造成贡献的

k的区间是多少。

k−dk≤jk-d_k\le j这一条就是限定了对于k来说可行j的范围。

对于一个i来说，他的可行k区间范围在[i+2,min(2∗j−i,n)][i+2,min(2*j-i,n)]

那么我们以k为时间线，在k符合范围的时候把i的贡献加入满足需求的最大的j。

然后对于当前时间线上的数组求一个后缀和。

当j>k时也可以满足，因为j>k的话选k-1必定满足要求。

求后缀和用线段树就有80%的分

100%:

用树状数组就有100%的分

代码

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
#include<bits/stdc++.h>
#define N 3200000
#define lowbit(x) ((x)&-(x))
using namespace std;
int n,d[N],f[N];
int ans;
vector<int>a[N];
int t[N]; 
namespace bit{
	int t[N];
	int insert(int x,int a){
		x=n-x+1;
		for(int i=x;i<=n;i+=lowbit(i))t[i]+=a;
		return 0;
	}
	int query(int x){
		x=n-x+1;
		int ans=0;
		for(int i=x;i;i-=lowbit(i))ans+=t[i];
		return ans;
	}
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
};
int main(){
	freopen("beacon.in","r",stdin);
	freopen("beacon.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)d[i]=read();
	for(int k=3;k<=n;k++){
		int i=k-2;
		int j=i+d[i];
		int l=2*j-i+1;
		l=min(l,n+1);
		a[l].push_back(j);
		bit::insert(min(j,n),1);
		for(int o=0;o<a[k].size();o++){
			bit::insert(min(a[k][o],n),-1);
		}
		f[k]=bit::query(max(k-d[k],1));
	}
//	for(int i=1;i<=n;i++)printf("%d ",f[i]);
//	printf("\n");
//	return 0;
	for(int i=1;i<=n;i++)ans^=f[i];
	printf("%d\n",ans);
    return 0;
}

总结

这场比赛难度总体来说比较递增，第一题那一个部分分还是比较简单的，但是拿100分还是比较难的。第二题也是一个图论，但是我不懂。第三题是一个数学题，但是我没有学过。第四题比较难。所以这场比赛我几乎不会，应该也就只能得60分。