今日学习总结

今日学习总结 试题 算法训练 转圈游戏

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：128.0MB

问题描述

　　n个小伙伴（编号从0到n-1）围坐一圈玩游戏。按照顺时针方向给n个位置编号，从0到n-1。
　　最初，第0号小伙伴在第0号位置，第1号小伙伴在第 1 号位置，……，依此类推。
　　游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第m+1号位置，……，依此类推，第n−m号位置上的小伙伴走到第0号位置，第n-m+1 号位置上的小伙伴走到第1号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1号位置。
　　现在，一共进行了10的k次方轮，请问x号小伙伴最后走到了第几号位置。

输入格式

　　输入共1行，包含 4个整数n、m、k、x，每两个整数之间用一个空格隔开。

输出格式

　　输出共1行，包含 1个整数，表示10的k次方轮后x号小伙伴所在的位置编号。

样例输入

10 3 4 5

样例输出

5

数据规模和约定

　　1 　　0 　　0<=x 　　0

思路链接：https://blog.csdn.net/weixin_45269353/article/details/105205681

就是找到周期，将时间缩短到周期之间。第一种方法最后一个样例会超时，要用快速幂的方法。

#include
#include
#include
#include
#include
#include
using namespace std;

long long h(long long j,long long j1,int x1)
{
    long long sum=j*j1;
    sum%=x1;
    return sum;
}

int main() {
   long long n,m,k,x,x1,x2,j1=10;
    cin>>n>>m>>k>>x;
    x1=x2=x;
    long long j=1000000000;
    for(int i=1;i<=j;i++)//找到周期 
    {
        x+=m;
        x%=n;
        if(x==x1)
        {
            x1=i;
            break;
        }
     } 
     j=1;
     while(k>0)//进行化简 
     {
         if(k%2==1)
         {
             j=h(j,j1,x1);
         }
         j1=h(j1,j1,x1);
         k/=2;
     }
     for(int i=0;i      {
         x2+=m;
         x2%=n;
     }
     cout<     return 0;
}

试题 算法训练 积木大赛

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：128.0MB

问题描述

　　THU幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是hi。
　　在搭建开始之前，没有任何积木(可以看成n块高度为0的积木）。接下来每次 *** 作，小朋友们可以选择一段连续区间[L, R]，然后将第L块到第R块之间(含第L块和第R块）所有积木的高度分别增加1。
　　kAc是个聪明的小朋友，他很快想出了建造大厦的最佳策略，使得建造所需的 *** 作次数最少。但他不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的 *** 作次数。

输入格式

　　输入包含两行，第一行包含一个整数n，表示大厦的宽度。
　　第二行包含n个整数，第i个整数为hi。

输出格式

　　仅一行，即建造所需的最少 *** 作数。

样例输入

5
2 3 4 1 2

样例输出

5

数据规模和约定

　　1<=n<=100000
　　0<=hi<=10000

思路：就是从第一块开始，后一个比前一个大就加上他们的差

#include
#include
#include
#include
#include
#include
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i     
    {
        cin>>a[i];
    }
    int cnt=a[0];
    for(int i=1;i     {
        if(a[i]>a[i-1])
        cnt+=a[i]-a[i-1];    
    }
     cout<     return 0;
}

试题 算法训练 A的B的C次方次方

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　//据说很多人的题目会有一大堆废话，本傻×就不在这里废话了。
　　就是叫你算A的B的C次方次方。
　　当然了，为了方便起见，把答案%1,000,000,007输出就好。

输入格式

　　一行，三个整数A，B，C，以空格隔开。

输出格式

　　输出A的B的C次方次方%1,000,000,007。

样例输入

3 4 5

样例输出

763327764

数据规模和约定

　　0≤A,B,C≤1,000,000,000

思路：用费马小定理

链接http://betheme.net/news/txtlist_i75898v.html

#include
#include
#include
#include
#include
#include
using namespace std;

long long p(long long a,long long b,long long q)
{
    long long sum=1;
    while(b>0)
    {
        if(b%2==0)
        {
            b/=2;
            a=a*a%q;
        }
        else
        {
            b--;
            sum=sum*a%q;
            b=b/2;
            a=a*a%q;
        }
    }
    return sum;
}

int main() {
     long long a,b,c,q,m;
     cin>>a>>b>>c;
     q=1000000007;
     m=p(a,p(b,c,q-1),q);
     cout<     return 0;
}

试题 算法训练 同余方程

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：128.0MB

问题描述

　　求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

输入格式

　　输入只有一行，包含两个正整数a, b，用一个空格隔开。

输出格式

　　输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。

样例输入

3 10

样例输出

7

数据规模和约定

　　对于40%的数据，2 ≤b≤ 1,000；
　　对于60%的数据，2 ≤b≤ 50,000,000；
　　对于100%的数据，2 ≤a, b≤ 2,000,000,000。

思路：就是欧几里得算法

链接：https://blog.csdn.net/qq_37236745/article/details/101601938

代码：https://blog.csdn.net/oneplus123/article/details/84851963

#include
#include
#include
#include
#include
#include
using namespace std;

long long a,b,x,y;
long long ans;

void gcd(long long a,long long b,long long &x,long long &y)
{
    if(!b)
    {
        x=1,y=0;
        return;
    }
    gcd(b,a%b,y,x);
    y-=x*(a/b);
}

int main() {
     cin>>a>>b;
     gcd(a,b,x,y);
     while(x<0)
     x+=b;
     cout<     return 0;
}

试题 算法训练 小明爬山

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　你有个同学叫小明，他早听闻祖国河山秀丽，于是有一个爬山的计划，并列了一张所有山的高度表，而又因“人往高处走”的说法，所以他希望爬的每一座山都比前一座要高，并且不能改变山的高度表上的顺序，爬的山数还要最多，请贵系的你帮他解决这个问题。

输入格式

　　输入第一行为num，代表山的个数
　　输入第二行有num个整数，代表每座山的高度

输出格式

　　输出只有一个数，为符合要求的最大爬山数

样例输入

10
1 3 5 7 9 2 4 6 8 10

样例输出

6

样例输入

10
1 3 2 7 5 4 5 6 10 11

样例输出

7

数据规模和约定

　　对于100%的数据，num <= 100000，高度<=10000。

思路：用动态规划做，我也不是很懂，最后一个样例超时

#include
#include
#include
#include
#include
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n],dp[n];
  for(int i=0;i   {
      cin>>a[i];
      dp[i]=1;
   } 
   for(int i=1;i    for(int j=i-1;j>=0;j--)
   {
       if(a[i]>a[j])
       dp[i]=max(dp[i],dp[j]+1);//找出最大数
    } 
    int ma=-1; 
    for(int i=0;i     {
        if(dp[i]>ma)
        ma=dp[i];
    }
     cout<     return 0;
}