2020牛客寒假算法基础集训营1 解题报告 Apare_xzc

2020牛客寒假算法基础集训营1 解题报告 Apare_xzc

比赛链接：2020牛客寒假算法基础集训营1<–

2020-02-04 13:00:00 至 2020-02-04 18:00:00
时长: 5小时
已有3952人报名

官方题解：【题解】牛客寒假集训营第一场 <–

A. honoka和格点三角形

题目链接


分析：

          求格点内能连成的面积为1的三角形的个数，要求三角形至少有一条边与x轴或y轴平行。
          满足条件的三角形的总数ans = 有一条边与x轴平行的三角形个数 ans1 有一条边与y轴平行的三角形的个数 ans2 - 直角三角形的个数ans3
          计算的方法都相同，以平行于x轴的三角形为例。三角形面积为1，一定是底为1高为2，或者底为2，高为1。那么必然有两个点的纵坐标相同，他们在纵坐标一定的时候，横坐标的范围是1到m, 于是底为1的两点有m-1种取法，每种取法可以改变纵坐标，上下移动，可知横坐标确定了的有一边平行于x轴的三角形第三个点的纵坐标有(n-2)*2种，纵坐标确定之后，三角形的高确定，第三个点有m中取法(直角三角形有2种)。
其它的情况都类似，互换m,n即可。具体公式见代码。

我的代码：
#include <bits/stdc .h>
using namespace std;
#define LL long long
LL f(LL m,LL n)
{
    return ((m-2)*m%mod*(n-1)%mod*2%mod (m-1)*m%mod*(n-2)%mod*2%mod )%mod;
}
LL calRT(LL m,LL n)
{
    return (  (m-2)*2%mod*(n-1)%mod*2%mod       (m-1)*2%mod*(n-2)%mod*2%mod )%mod;
}
int main()
{
    LL m,n,ans;
    while(cin>>m>>n)
    {
        ans = (f(m,n) f(n,m))%mod;
        ans = ((ans - calRT(m,n)) % mod   mod)%mod;
        cout<<ans<<endl;
    }
    return 0;  
}

B. kotori和bangdream

题目链接

分析：

    签到题，期望 = 1.0xa/100 1.0b(100-x)/100*n

代码
#include <bits/stdc .h>
using namespace std;
int main()
{
    int n,x,a,b;
    cin>>n>>x>>a>>b;
    double ans = 1.0*x*a/100 1.0*b*(100-x)/100;
    ans *= n;
    printf("%.2f\n",ans); 
    return 0;  
}

C. umi和弓道

题目链接 不想写计算几何，这题没写，跳过吧…

D. hanayo和米饭

题目链接
分析：

        1到n的数列少了一个，给n-1个，求少的那一个。直接 (1 n)*n/2 - sum(arr) 即可。用n个数的和减去n-1个数的和

#include <bits/stdc .h>
using namespace std;
int main()
{
    int n,x;
    cin>>n;
    LL sum = 1ll*(1 n)*n/2;
    for(int i=1;i<n; i)
        scanf("%d",&x),sum -= x;
    cout<<sum<<endl
    return 0;  
}

E. rin和快速迭代

题目链接
分析：

        也没有找到什么规律或者公式。那就按题意模拟吧。我们只需要进行迭代，每次用f(x)代替x，直到x变为2。求迭代了多少次。如何求x因数的个数呢？我们先对x进行分解质因数，得到

x = P1^C1 * P2^C2 * ... * Pk^Ck
其中P1,P2...Pk均为质数

那么每个质因数Pi的次数可以选{0,1,2…Ci}，共有Ci 1种选法，那么根据乘法原理，因数的个数就是Ci 1的乘积。
我们可以先筛出1E6之内的质数，加快分解因式的速度。
我用的是欧拉线性筛，复杂度为O(n), 分解质因数的复杂度大约为根号n

我的代码
#include <bits/stdc .h>
using namespace std;
#define LL long long
bool notPrime[maxn];
int sushu[maxn],cnt;//cnt表示素数的个数
void getPrime(int n); //欧拉筛法线性筛素数
LL getNumFac(LL x); //获得x因子的个数
int main()
{
    getPrime(1000000 10);
    LL x;
    while(cin>>x)
    {
        int ans = 0;
        while(x!=2)
        {
            x = getNumFac(x);
             ans;
        }
        cout<<ans<<endl;
    }
    return 0;  
}
void getPrime(int n)
{
    cnt = 0;
    for(int i=2;i<=n; i)
    {
        if(!notPrime[i]) sushu[cnt ] = i;
        for(int j=0;j<cnt&&1ll*i*sushu[j]<=n; j)
        {
            notPrime[i*sushu[j]] = true;
            if(i%sushu[j]==0) break;
        }
    }
}
LL getNumFac(LL x)
{
    LL res = 1;
    for(int i=0;i<cnt&&sushu[i]<=x/sushu[i]; i)
    {
        int p = sushu[i];
        if(x%p) continue;
        int t = 0;
        while(x%p==0)  t, x/=p;
        res *= (t 1);
    }
    if(x>1) res *= 2;
    return res;
}

F. maki和tree

题目链接
分析：

        求树上两点间路径只有一个黑色节点的对数。我们只需要对每一个黑色节点dfs，求出包含该黑色节点的路径数(点的对数)相加即可。
        每个黑节点有若干个白色节点与之相连，相互不经过黑色节点可达的白色节点看成是一个连通的整体，我们dfs求出这些连通的整体中白色节点的个数，记录这些个数v0,v1,v2… 可以存在一个vector之中。那么，如果黑色节点是点对两点中的某一点，路径的数目为v0,v1,v2…之和，也就是黑色节点不经过其它黑色节点可达的白色节点的个数之和。如果黑色节点不是点对中的某一点，那么两个点一定在不同的连通整体中，这样的路径数位v0,v1,v2… 这些数两两相乘相加之和。

我的代码：
#include <bits/stdc .h>
using namespace std;
const int maxn = 3e5 100;
#define LL long long
#define Mst(a,b) memset(a,(b),sizeof(a))
char color[maxn];
struct Node{
    int to,Next;
}node[maxn*2];
int tot,head[maxn];
void initEdge()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
bool vis[maxn];
void addedge(int u,int v)
{
    node[tot].to = v;
    node[tot].Next = head[u];
    head[u] = tot ;
}
LL DFS(int x)
{
    if(color[x]=='B') return 0;
    vis[x] = true;
    LL sum = 1;
    for(int i=head[x];i!=-1;i=node[i].Next)
    {
        int to = node[i].to;
        if(color[to]=='B'||vis[to]) continue;
        sum  = DFS(to);
    }      
    vis[x] = false;
    return sum;
}
int main()
{
// freopen("in.txt","r",stdin);
    int n,u,v;
    scanf("%d%s",&n,color 1);
    initEdge();
    for(int i=1;i<n; i)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    LL ans = 0;
    LL cc = 0;
    for(int i=1;i<=n; i)
    {
        if(color[i]=='B') //
        {
            vector<LL> v;
            for(int t=head[i];t!=-1;t=node[t].Next)
            {
                int to = node[t].to;
                if(color[to]=='W')
                {
                    cc = DFS(node[t].to);
                    v.push_back(cc);
                }
            }
            for(auto z:v) ans =z;
            if((int)v.size()<2) continue;
            int len = v.size();
            for(int ii=0;ii<len; ii)
            {
                for(int jj=ii 1;jj<len; jj)
                {
                    ans  = v[ii]*v[jj];
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;  
}

G. eli和字符串

题目链接
分析：

        我们可以每个小写字母开一个vector，记录该字母在字符串中出现的所有位置，是一个递增的序列。然后我们每个字母从v[i]开始，v[i k-1]结束的这一段含有k个相同的字母，用v[i k-1] - v[i] 1更新答案即可

我的代码：
#include <bits/stdc .h>
using namespace std;
const int maxn = 1e6 100;
char str[maxn];
int main()
{
	int n,k;
	cin>>n>>k;
	scanf("%s",str);
	vector<int> v[320];
	for(int i=0;i<n; i)
	{
		v[(int)str[i]].push_back(i);
	}
	int ans = n 100;
	for(int i='a';i<='z'; i)
	{
		int len = v[i].size();
		if(len<k) continue;
		for(int j=0;j k-1<len; j)
		{
			ans = min(ans,v[i][j k-1]-v[i][j] 1);
		}
	}
	if(ans==n 100) ans = -1;
	cout<<ans<<endl;
	
	return 0;	
}

H. nozomi和字符串

题目链接
分析：

        在K次操作之内，求最大的数字相同的子串的长度。数字都相同，无非只有两种情况，一种是全部为0，一种是全部为1。
        我们可以二分答案，枚举子串的起点，二分子串的长度。如果是全1串，我们需要求得串中0的个数，来判断是否能在K次操作之内都变为1。我们可以维护一个0的个数的前缀和(1同理) ，于是我们可以O(1)check。起点一定的话，0或1的个数也随着长度的增加单调非递减，满足二分的性质。

我的代码：
#include <bits/stdc .h>
using namespace std;
const int maxn = 1e6 100;
char str[maxn]; 
int sum0[maxn],sum1[maxn];
int main()
{
	int n,k;
	cin>>n>>k;
	scanf("%s",str 1);
	for(int i=1;i<=n; i)
	{
		sum1[i] = sum1[i-1];
		sum0[i] = sum0[i-1]; 
		if(str[i]=='1')  sum1[i];
		else  sum0[i]; 
	}
	int ans = 0;
	int left,mid,right;
	for(int i=1;i ans-1<=n; i)
	{
		left = i,right = n 1;
		while(right-left>1)
		{
			mid = (left right)>>1;
			if(sum0[mid]-sum0[i-1]<=k) left = mid;
			else right = mid;  
		}
		ans = max(ans,left-i 1);
	}
	for(int i=1;i ans-1<=n; i)
	{
		left = i,right = n 1;
		while(right-left>1)
		{
			mid = (left right)>>1;
			if(sum1[mid]-sum1[i-1]<=k) left=mid;
			else right = mid;
		}
		ans = max(ans,left-i 1);
	}
	cout<<ans<<endl
	return 0;	
}

I. nico和niconiconi

题目链接
分析：

        简单dp,官方题解说的很明白

我的代码：
#include <bits/stdc .h>
using namespace std;
const int maxn = 3e5 100;
#define LL long long
char str[maxn];
LL n,a,b,c; 
char A[] = "nico";
char B[] = "niconi";
char C[] = "niconiconi"; 
bool equalA(int);
bool equalB(int);
bool equalC(int);
LL dp[maxn];
int main()
{
	scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
	scanf("%s",str 1);
	for(int i=1;i<=n; i)
	{
		dp[i] = dp[i-1];
		if(equalA(i-3)) dp[i] = max(dp[i],dp[i-4] a);
		if(equalB(i-5)) dp[i] = max(dp[i],dp[i-6] b);
		if(equalC(i-9)) dp[i] = max(dp[i],dp[i-10] c);
	}
	cout<<dp[n]<<endl;
	
	return 0;	
} 
bool equalA(int st)
{
	if(st<1) return false;
	for(int i=0;i<4; i)
		if(str[st i]!=A[i]) return false;
	return true;
}
bool equalB(int st)
{
	if(st<1) return false;
	for(int i=0;i<6; i)
		if(str[st i]!=B[i]) return false;
	return true;
}
bool equalC(int st)
{
	if(st<1) return false;
	for(int i=0;i<10; i)
		if(str[st i]!=C[i]) return false;
	return true;
}

J. u’s的影响力

题目链接
分析：

        如果n<=2,直接输出x或y，如果n>=3,可以发现x和y的指数都是斐波那契数列的某一项，a^b的系数是也是某一项-1
Pab[i] = Pab[i-1] Pab[i-2] 1,一开始我直接退出一个三乘三的系数矩阵

// x[i 2] = x[i 1] x[i] 1
//    |x[i 2]|     |1 1 1|   |x[i 1]|  0 x2              X[n 1]
//    |x[i 1]|  =  |1 0 0| * |x[i 0]|  0 x1 -- n-1次 --> X[n]
//	  |    1 |     |0 0 1|   |    1 |  1

后来发现就是Feibonaci(n 1)-1
x的系数为Fei(n-1), y的系数为Fei(n) 如果像下面这样定义的话

//	id   1  2  3  4  5  6  7   8    9 
  //Fei  0  1  1  2  3  5  8   13  21
	//x  1  0  1  1  2  3  5   8   13  Fei(n-1)
	//y  0  1  1  2  3  5  8  13   21  Fei(n  )
//a^(b)  0  0  1  2  4  7 12  20   33  Fei(n 1)-1

我们可以用费马小定理，计算Fei[n]的时候用1000000007的欧拉函数作为模数。由于1E9 7是质数，质数的欧拉函数等于它自己减一，所以求Fei的时候对1E9 6取模即可。
由于x,y,a^b这三个底数可能是1E9 7的倍数，结果一定为0，要注意一下。
如果指数对1000000006取模后变为0，那么x^0 返回1，就会出错，所以建议快速幂这么写：

#define LL long long
LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0; //加一个特判以防万一 
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

求斐波那契额数列的第n项可以用矩阵快速幂，系数矩阵如下：

//	   fei[n  ] =  |1  1|^n-2    |fei[2]| 1
//	   fei[n-1]    |0  1|     *  |fei[1]| 0
我的代码：
#include <bits/stdc .h>
#define LL long long
using namespace std;
const int N = 3;
const int mod = 1e9 7;
LL fast_pow(LL a,LL b,LL mod);
void Mul_Matrix(LL a[N][N],LL b[N][N],int n,int mod);
void Matrix_fast_pow(LL a[N][N],LL b,int n,int mod);
LL getFeiboNa(LL n,int mod);
int main()
{
	LL a,b,x,y,n;
	cin>>n>>x>>y>>a>>b;
	a %= mod;
	x %= mod;
	y %= mod;
	if(n==1)
	{
		cout<<x<<endl;return 0;
	}
	if(n==2)
	{
		cout<<y<<endl;return 0;
	}
	a = fast_pow(a,b,mod);
	LL pa,px,py,ans;
	pa = (getFeiboNa(n 1,mod-1)-1 mod-1)%(mod-1);
	ans = fast_pow(a,pa,mod);
	px =  getFeiboNa(n-1,mod-1);
	py =  getFeiboNa(n,mod-1);
	ans = ans * fast_pow(x,px,mod) % mod * fast_pow(y,py,mod) % mod;
	printf("%lld\n",ans);
	
	return 0;	
} 
LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0; 
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
void Mul_Matrix(LL a[N][N],LL b[N][N],int n,int mod)
{
	LL c[N][N] = {0};
	for(int i=0;i<n; i)
		for(int j=0;j<n; j)
			for(int k=0;k<n; k)
				c[i][j] = (c[i][j] a[i][k]*b[k][j]%mod)%mod;
	for(int i=0;i<n; i)
		for(int j=0;j<n; j)
			a[i][j] = c[i][j];
}
void Matrix_fast_pow(LL a[N][N],LL b,int n,int mod)
{
	LL ans[N][N] = {0};
	for(int i=0;i<n; i)
		ans[i][i] = 1;
	while(b)
	{
		if(b&1) Mul_Matrix(ans,a,n,mod);
		Mul_Matrix(a,a,n,mod);
		b >>= 1;
	}
	for(int i=0;i<n; i)
		for(int j=0;j<n; j)
			a[i][j] = ans[i][j];
}
LL getFeiboNa(LL n,int mod)
{
	if(n<=2) return n-1;
	LL m2[N][N] = {
		1,1,666,
	    1,0,999,
	    5,20,1314,
	};
	Matrix_fast_pow(m2,n-1,2,mod);
	return m2[1][0];	
}

xzc
2020.2.6 1:08

全部评论

相关推荐

头像
11-20 05:23
门头沟学院 C++
点赞 评论 收藏
分享
11-19 15:08
中国矿业大学（北京） 后端
25届浙江二本JAVA简历：估计投500份，最多3-5个面试
注：为保证用户信息安全，姓名和学校等信息已经进行同层次变更，内容部分细节也进行了部分隐藏另外：我们出这一系列校招简历指导的原因，就是看很多学生被忽悠，没有先定位大厂、中厂还是小公司，导致没有面试机会。&nbsp;我们不放任何的广告和品牌名，完全是反馈牛客社区。大家也不要私信，现在比较忙，没空帮大家改简历。简历总体说明校招的第一法则就是必须要确定校招层次。开发岗分为大中小厂，不同的层次对学校背景、时间点、项目和考点的要求都不太一样，所以必须要确定就业的层次。&nbsp;这是一份25届某二本的计算机的JAVA简历。如果是我们的老粉丝会知道，HR第一眼要看你学的专业满不满足招聘需求，所以投递简历的时候一定要注意，先...
投递联想等公司10个岗位 > 简历中的项目经历要怎么写 你觉得哪一届的校招最难？
点赞 评论 收藏
分享
11-14 08:35
河北地质大学华信学院 网络工程师
大佬们帮忙看一下我的简历有问题吗
重生2012之我是java程序员：换个稍微正式点的照片吧
点赞 评论 收藏
分享
11-08 00:11
复旦大学 深度学习
华为这样是一定会发offer吗？
1145定律&nbsp;这样代表一定会发offer吗？
喜欢走神的孤勇者练习时长两年半：池是池，发是发，我曾池，我现黑
点赞 评论 收藏
分享
11-20 00:00
门头沟学院 算法工程师
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
264022次浏览 2187人参与
# 0offer是寒冬太冷还是我太菜 #
887493次浏览 7909人参与
# 北方华创开奖 #
23669次浏览 260人参与
# 地方国企笔面经互助 #
2846次浏览 7人参与
# 学历or实习经历，哪个更重要 #
43448次浏览 328人参与
# 选完offer后，你后悔学本专业吗 #
13284次浏览 94人参与
# 查收我的offer竞争力报告 #
19533次浏览 255人参与
# 应届生被毁约被毁意向了怎么办 #
28215次浏览 243人参与
# 你最想要的公司福利是？ #
41882次浏览 146人参与
# 如何一边实习一边秋招 #
987409次浏览 12609人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3317次浏览 36人参与
# 嵌入式转岗的难度怎么样 #
11202次浏览 251人参与
# 你最希望上岸的公司是？ #
76556次浏览 469人参与
# 如何写一份好简历 #
605073次浏览 8510人参与
# 面试体验感最好的是哪家？ #
83663次浏览 818人参与
# 机械应届生薪资要多少才合适？ #
12543次浏览 61人参与
# 牛客十周岁生日快乐 #
48753次浏览 759人参与
# 你认为第一份工作重要吗 #
5447次浏览 49人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
79946次浏览 589人参与
# 秋招OC许愿 #
228221次浏览 1880人参与
# 来聊聊机械薪资天花板是哪家 #
65746次浏览 445人参与
牛客网
牛客企业服务