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

2024-01-10 10:59:10

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

T1 题目名称:大大大

题目描述：

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

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

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

输入描述:

  一行一个数字\(n\)。

输出描述:

  一行一个\(ans\)表示满足要求的三元组的个数。

输入样例:

10

输出样例:

900

数据范围:

对于30%的数据\(n\leq 100\)

对于60%的数据\(n\leq 5000\)

对于100%的数据\(n\leq 100000\)

思路

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

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

#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的数列中\(\forall i*j>=k\)一定有i*j个符合要求啊，然后如果大于\(ij\)的话加n就好了

60分

#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<k\) 那么我们考虑将(i,j)插入\(i*j+1\)中，然后求一个前缀和即可。

复杂度分析:

\(i*j>n\)时可直接break。

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

代码

#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:"不知道啊~"

输入描述:

​ 第一行一个数字\(T\)代表数据组数。

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

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

​ 接下来\(m\)行每行三个数\(x,y,z\)表示\(x\)和\(y\)之间有一条长度为\(z\)的路径。

输出描述:

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

输入样例:

1

2 3 2 3

1 2 1

2 1 1

输出样例:

YES

样例解释:

1-2-1-2

数据范围:

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

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

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

思路

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

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

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

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

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

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

代码

#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:"今天我们学了\(A^B\)?"

  Star-dust:"我们也学了诶！"

  Star-dust:"那我来考考你吧！"

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

输入描述：

  一行输入两个整数\(A\)和\(P\)。

输出描述：

  输出任意一个满足要求的数字\(B\)。

  \(B\)要为一个不大于\(10^{18}\)的正整数。

样例输入：

78 100

样例输出：

16

数据范围：

对于30%的数据:

\(1\leq A,P\leq 1000\)

对于30%的数据:

\(P\)为质数

对于100%的数据:

\(64\leq A\leq 10^9\)

\(P\leq 10^9\)

\(1\leq B\leq10^{18}\)

思路

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

PS:我还没学PHI怎么办？

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

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

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

代码

#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:"好啊~"

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

输入描述：

  第一行一个整数\(n\)。

  接下来一行\(n\)个数字，第\(i\)个代表\(d_i\)。

输出描述：

  一行一个答案\(ans\)。

  \(f_k\)表示对于第\(k\)个灯塔有多少个灯塔满足条件。

  \(ans\)为n个\(f_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\leq 100\)

对于20%的数据:\(n\leq5000\)

对于20%的数据:\(di\)完全相同

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

对于100%的数据:\(n\leq 3000000\),\(1 \leq d_i\leq n\)

思路

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

40%：

考虑对于一队i和k

判断是否存在满足条件的j

\[j\le k-d_k \]

\[2*j\le j+k \]

\[i+d_i\le j \]

整理一下就有了

\[i+d_i\le j\le k-d_k \]

\[2*j\le i+k \]

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

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

60%:

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

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

能人眼观察得到。

80%:

我们考虑再整理一下40%的式子

\[k-d_k\le j \]

\[j\le i+d_i \]

\[j+k\le 2*j \]

再对每一条式子进行解析

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

\(j\le i+d_i\)那么对于i来说j最好就放到\(i+d_i\)上。

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

k的区间是多少。

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

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

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

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

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

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

100%:

用树状数组就有100%的分

代码

#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分。

上一篇：Day5标识符和关键字


下一篇：今天的一道面试题(20) - 详细讲述一下浏览器的循环系统