洛谷&&力扣

2023-12-28 11:14:49

题:幂次方https://www.luogu.com.cn/problem/P1010

题目描述

任何一个正整数都可以用?22?的幂次方表示。例如?137=27+23+20137=27+23+20。

同时约定次方用括号来表示,即?��ab?可表示为?�(�)a(b)。

由此可知,137137?可表示为?2(7)+2(3)+2(0)2(7)+2(3)+2(0)

进一步:

7=22+2+207=22+2+20?(?2121?用?22?表示),并且?3=2+203=2+20。

所以最后?137137?可表示为?2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如?1315=210+28+25+2+11315=210+28+25+2+1

所以?13151315?最后可表示为?2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。

输入格式

一行一个正整数?�n。

输出格式

符合约定的?�n?的?0,20,2?表示(在表示中不能有空格)。

输入输出样例

输入 #1复制

1315

输出 #1复制

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

说明/提示

【数据范围】

对于?100%100%?的数据,1≤�≤2×1041≤n≤2×104。

思路:这题需要用分治的方法,自己用的不对,不太会,但主要方法就是把大问题变成小问题,逐个分解。由于数据比较小,2的14足够了,所以就用暴力的方法找,如果它的次方数为大于1,那么就要继续分解成小问题,相当于2的7次中的7可以继续拆分。

#include<bits/stdc++.h>
using namespace std;
#define itn int
void blbl(int x)
{
	for (int i=14;i>=0;--i)
	{
		if (pow(2,i)<=x)
		{
			if (i==1)cout<<"2";
			else if (i==0)cout<<"2(0)";
			else 
			{
				cout<<"2(";
				blbl(i);
				cout<<")";
			}
			x-=pow(2,i);
			if (x!=0) cout<<"+";
		}
	}
}
int main()
{
	int a;
	cin>>a;
	blbl(a);	
}

题:快速幂https://www.luogu.com.cn/problem/P1226

题目描述

给你三个整数?�,�,�a,b,p,求?��?mod?�abmodp。

输入格式

输入只有一行三个整数,分别代表?�,�,�a,b,p。

输出格式

输出一行一个字符串?a^b mod p=s,其中?�,�,�a,b,p?分别为题目给定的值,?�s?为运算结果。

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

说明/提示

样例解释

210=1024210=1024,1024?mod?9=71024mod9=7。

数据规模与约定

对于?100%100%?的数据,保证?0≤�,�<2310≤a,b<231,�+�>0a+b>0,2≤�<2312≤p<231。

给个模版

int main()
{
	int base,exp,mod;
	int ans=1;
	cin>>base>>exp>>mod;
	while (exp>0)
	{
		if (exp&1)
		{
			ans=ans*base%mod;
		}
		base=base*base%mod;
		exp>>=1;
	}
}

接下来是AC码

#include<bits/stdc++.h>
using namespace std;
#define itn int
int main()
{
	long long  a,b,p;
	cin>>a>>b>>p;
	long long  a1=a,b1=b;
	long long  ans=1;
	while (b>0)
	{
		if (b&1)
		{
			ans=ans*a%p;
		}
		a=a*a%p;
		b>>=1;
	}
	cout<<a1<<"^"<<b1<<" mod"<<" "<<p<<"="<<ans;
}

后面就是跟着学长去力扣水了3题

题:https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/

给你一个整数数组?nums,请你选择数组的两个不同下标?i?和?j使?(nums[i]-1)*(nums[j]-1)?取得最大值。

请你计算并返回该式的最大值。

这边就直接上AC码了,因为太简单了

C:

int cmp(const int *a,const int *b)
{
    return *(int *)a-*(int *)b;
}
int maxProduct(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int ),cmp);
    int a,b;
    a=nums[numsSize-1]-1;
    b=nums[numsSize-2]-1;
    return a*b; 
}

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        n=len(nums)
        return (nums[n-1]-1)*(nums[n-2]-1)

题:https://leetcode.cn/problems/max-consecutive-ones/

给定一个二进制数组?nums?, 计算其中最大连续?1?的个数。

int findMaxConsecutiveOnes(int* nums, int numsSize) {
    int cnt=0,maxcnt=0;
    for (int i=0;i<numsSize;++i)
    {
        if (nums[i]==1)cnt++;
        else cnt=0;
        if (maxcnt<cnt)maxcnt=cnt;
    }
    return maxcnt;
}
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        cnt=0
        maxn=0
        for i in nums:
            if i==1:
                cnt+=1
            else :
                cnt=0
            if maxn<cnt:
                maxn=cnt
        return maxn

题:https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

已知一个长度为?n?的数组,预先按照升序排列,经由?1?到?n?次?旋转?后,得到输入数组。例如,原数组?nums = [0,1,2,4,5,6,7]?在变化后可能得到:

  • 若旋转?4?次,则可以得到?[4,5,6,7,0,1,2]
  • 若旋转?7?次,则可以得到?[0,1,2,4,5,6,7]

注意,数组?[a[0], a[1], a[2], ..., a[n-1]]?旋转一次?的结果为数组?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

给你一个元素值?互不相同?的数组?nums?,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的?最小元素?。

你必须设计一个时间复杂度为?O(log n)?的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums?中的所有整数?互不相同
  • nums?原来是一个升序排序的数组,并进行了?1?至?n?次旋转
int findMin(int* nums, int numsSize) {
        int min=nums[0];
        for (int i=1;i<numsSize;++i)
        {
            if (nums[i]<min)
            {
                min=nums[i];
            }
        }
        return min;
    }

class Solution:
    def findMin(self, nums: List[int]) -> int:
        mins=min(nums)
        return mins

文章来源:https://blog.csdn.net/2301_80489323/article/details/135232659
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。