头像

自律




离线:1天前



自律
1天前

题目描述

有 N 个瓶子,编号 1∼N,放在架子上。

比如有 5 个瓶子:

2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式
第一行包含一个整数 N,表示瓶子数量。

第二行包含 N 个整数,表示瓶子目前的排列状况。

输出格式
输出一个正整数,表示至少交换多少次,才能完成排序。

数据范围
1≤N≤10000

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    int n,i,j,ans=0;
    int a[10000];
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            for(j=1;j<=n;j++)
                if(a[j]==i)
                {
                    a[j]^=a[i];
                    a[i]^=a[j];
                    a[j]^=a[i];
                    ans++;
                }
        }
    }
    cout<<ans;         
    return 0;
}
//最开始用的快速排序,快速排序交换次数不是最少的。此题N个数为1~N,课通过模拟解题。
//参考https://www.acwing.com/solution/content/6983/



算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
2天前

题目描述

四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去,就正好可以表示为 4 个数的平方和。

比如:

5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对 4 个数排序:

0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//超时了
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n,a,b,c;
    cin >> n;
    double x = sqrt(n),d;
    for(a = 0 ; a <= x;a++)
        for(b = a; b <= x; b++)
            for(c = b ; c <= x ; c++)
            {
               d = sqrt(n - a * a - b * b - c * c);
               if(d == (int)d)
               {
                   cout << a << " " << b << " " << c << " " << d << endl;
                   return 0;
               }

            }
    return 0;
}



算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
4天前

题目描述

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。

其楼房的编号为 1,2,3…
当排满一行时,从下一行相邻的楼往反方向排号。

比如:当小区排号宽度为 6 时,开始情形如下:

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 .....
我们的问题是:已知了两个楼号 m 和 n,需要求出它们之间的最短移动距离(不能斜线方向移动)。

输入格式
输入共一行,包含三个整数 w,m,n,w 为排号宽度,m,n 为待计算的楼号。

输出格式
输出一个整数,表示 m,n 两楼间最短移动距离。

数据范围
1≤w,m,n≤10000,

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int x1,x2,y1,y2,ans;
    int w,m,n;
    cin>>w>>m>>n;
    y1=ceil(float(m)/float(w)*1.0);  //必须先转化为float类型 
    if(y1%2!=0)
    {
        if(m%w!=0)
            x1=m%w;
        else
            x1=w;
    }
    else
    {
        if(m%w!=0)
            x1=w+1-m%w;
        else
            x1=1;
    }
    y2=ceil(float(n)/float(w)*1.0);;
    if(y2%2!=0)
    {
        if(n%w!=0)
            x2=n%w;
        else
            x2=w;
    }
    else
    {
        if(n%w!=0)
            x2=w+1-n%w;
        else
            x2=1;
    }
    ans=abs(x1-x2)+abs(y1-y2);
    //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2;
    cout<<ans;
    return 0;

 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
6天前

题目描述

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料,凭3个瓶盖可以再换一瓶C型饮料,并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下,如果小明不浪费瓶盖,尽量地参加活动,那么,对于他初始买入的 n 瓶饮料,最后他一共能喝到多少瓶饮料。

输入格式
输入一个整数 n,表示初始买入的饮料数量。

输出格式
输出一个整数,表示一共能够喝到的饮料数量。

数据范围
0<n<10000

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int ans=0,m=0;
int sum(int n)
{
        m++;
    if(n>=3)
    {
        if(m==1)
            ans+=(n+n/3);
        else
            ans+=(n/3);
        n=(n/3+n%3);
        sum(n);
    }
    else
        return ans;
}
int main()
{
    int n;
    cin>>n;
    if(n<3)
    {
        cout<<n;
    return 0;
    }   
    sum(n);
    cout<<ans;
    return 0;
}




自律
7天前

题目描述

长 100 厘米的细长直杆子上有 n 只蚂蚁。

它们的头有的朝左,有的朝右。

每只蚂蚁都只能沿着杆子向前爬,速度是 1 厘米/秒。

当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。

这些蚂蚁中,有 1 只蚂蚁感冒了。

并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。

请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。

输入格式
第一行输入一个整数 n, 表示蚂蚁的总数。

接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。

正值表示头朝右,负值表示头朝左,数据中不会出现 0 值,也不会出现两只蚂蚁占用同一位置。

其中,第一个数据代表的蚂蚁感冒了。

输出格式
输出1个整数,表示最后感冒蚂蚁的数目。

数据范围
1<n<50,
0<|Xi|<100

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

首先以感冒的蚂蚁为中心,碰头之后回头和不回头其实是一样的,因为两个蚂蚁同样都感冒了,所以碰头可以看作穿过。
模拟情景:首先将碰头的概念换成穿过,先将所有数字按绝对值大小排序,你会发现中心感冒蚂蚁左边只有向右走的蚂蚁有效,向左走的蚂蚁只能穿过向右的未感冒的蚂蚁直到走出范围,同样右边的蚂蚁只有向左走的有效。然后统计中心蚂蚁左边的正数和右边的负数即可,然后有一种特殊情况如果中心蚂蚁向左走,其左边没有蚂蚁向右走,或者中心蚂蚁向右走,右边没有蚂蚁向左走时,由于速度相同,除中心蚂蚁外,任何蚂蚁都不会感冒。这种情况用if判断一下即可。

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<math.h> 
using namespace std;
int main()
{
    int a[100],i,j,n,m,first,local,ans=1,sum1=0,sum2=0;
    a[100]={0};
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        first=a[0];  //记录中心蚂蚁 
    }
    for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(sqrt(a[j]*a[j])>sqrt(a[j+1]*a[j+1]))  //按绝对值大小排序 
            {
                m=a[j];a[j]=a[j+1];a[j+1]=m;
            }
        //for(i=0;i<n;i++)
        //cout<<a[i]<<" ";
    for(i=0;i<n;i++)
        if(a[i]==first)
            local=i;          //找出中心蚂蚁位置 

    for(i=0;i<local;i++)
        if(a[i]>0)
        {
            sum1++;         //判断其左边是否有向右走的蚂蚁 
            ans++;
        }

    for(i=local+1;i<n;i++)
        if(a[i]<0)
        {
            sum2++;         //判断其右边是否有向左走的蚂蚁 
            ans++;
        }
    if(sum1==0||sum2==0)
        ans=1;

    cout<<ans;
    return 0;

 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
7天前




自律
9天前

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题:

在 1∼N 的某个排列中有多少个连号区间呢?

这里所说的连号区间的定义是:

如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间。

当 N 很小的时候,小明可以很快地算出答案,但是当 N 变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入格式
第一行是一个正整数 N,表示排列的规模。

第二行是 N 个不同的数字 Pi,表示这 N 个数字的某一排列。

输出格式
输出一个整数,表示不同连号区间的数目。

数据范围
1≤N≤10000,
1≤Pi≤N

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

经参考题解后小结
一、由题目知N个数字一定是1~N且不重复出现
二、本题有一个规律,如果在一个区间满足最大值减最小值等于他们相差的位数((max-min)==(j-i))的时候可以满足题目要求,这道题目就不难解决了。

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    int a[10001],n,i,j,k=0,max,min;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
    {
        max=0;
        min=10000;      //扫出i j之间的最大最小值 
        for(j=i;j<n;j++)
        {
            if(a[j]>max)
                max=a[j];
            if(a[j]<min)
                min=a[j];

            if(max-min==j-i)
            k++;
        }
    }
    cout<<k;
} 



自律
9天前




自律
10天前

题目描述

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。

比如,可能情形是:oo*oooo

如果同时翻转左边的两个硬币,则变为:oooo***oooo

现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?

我们约定:把翻动相邻的两个硬币叫做一步操作。

输入格式
两行等长的字符串,分别表示初始状态和要达到的目标状态。

输出格式
一个整数,表示最小操作步数

数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<string.h>      //strlen函数 
using namespace std;
int main()
{
    char a[101],b[101],i;
    int j=0,n;
    cin.getline(a,101);  //PAT中已经不支持 'gets' 函数的用法。
    cin.getline(b,101);  //Error | ‘gets’ was not declared in this scope gets
    n=strlen(a);         
    for(i=0;i<n;i++)
    {
        //cout<<a[i]<<" "<<b[i]<<endl;
        if(a[i]!=b[i])
            {
                b[i]=a[i];
                j++;
                if(b[i+1]=='o')
                    b[i+1]='*';
                else if(b[i+1]=='*')
                    b[i+1]='o';
            }

    }
        cout<<j;

    return 0;
 } 



自律
11天前

题目描述

小明开了一家糖果店。

他别出心裁:把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候,他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。

你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。

输入格式
两个正整数 n,m,表示每种包装中糖的颗数。

输出格式
一个正整数,表示最大不能买到的糖数。

数据范围
2≤n,m≤1000,
保证数据一定有解。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<m*n-n-m;
    return 0;      //听之前苏龙辉学长讲的
}