头像

无味

潍坊学院




离线:1天前



无味
4天前

题目描述

2018年FISM(世界魔术大会)近景总冠军简纶廷的表演中有一个情节:以桌面上一根带子为界,当他将纸牌从带子的一边推到另一边时,纸牌会变成硬币;把硬币推回另一边会变成纸牌。

这里我们假设纸牌会变成等量的硬币,而硬币变成纸牌时,纸牌的数量会加倍。那么给定纸牌的初始数量,当他来回推了 N 次(来/回各算一次)后,手里拿的是纸牌还是硬币?数量是多少?

输入格式:

输入在一行里给出两个正整数,分别是纸牌的初始数量和魔术师推送的次数。这里假设初始状态下魔术师手里全是纸牌。

输出格式:

QQ截图20201127195953.jpg

输入样例 1:

3 7

输出样例 1:

1 24

输入样例 2:

8 4

输出样例 2:

0 32


暴力枚举
#include<iostream>
using namespace std;
int main()
{
    int n,m;//纸牌数量和推送次数 
    cin>>n>>m;
    int res=n;//表示手中纸牌或者硬币的数量 
    int st=0;//0表示纸牌,1表示硬币 
    for(int i=1;i<=m;++i)
    {
        if(!st) res=res;
        else res*=2;
        st=(st+1)%2;//判断手中是0纸牌还是1硬币 
    }
    cout<<st<<" "<<res; 
    return 0;
}
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    int cnt,time;
    cin>>cnt>>time;
    for(int i=1;i<=time;i++)
    {
        if(i%2==0) // i!!
            cnt=cnt*2; 
    }
    cout<<time%2<<" "<<cnt;//
    return 0;
}


找规律

QQ截图20201127201831.jpg

#include<iostream>
using namespace std;
int f(int x,int y)
{
    int sum=x;
    for(int i=1;i<=y;++i)
        sum*=2;
    return sum;
}
int main()
{
    int n,m;
    cin>>n>>m;
    if(m%2!=0) cout<<"1"<<" "<<f(n,(m-1)/2);//最后手中是硬币
    else cout<<"0"<<" "<<f(n,m/2);

    return 0;
 } 

位运算:

#include<iostream>
using namespace std;
int main() {
    int a, b;
    cin>>a>>b;
    a<<=(b>>1);
    cout<<(b&1)<<" "<<a<<endl;
    return 0;
}

部分代码来源于




无味
12天前

稍等稍等




无味
12天前

题目描述

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录,请你统计一下他们抢红包的收获。

输入格式

QQ截图20201120080508.jpg

输出格式

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额(以元为单位,输出小数点后2位)。每个人的信息占一行,两数字间有1个空格。如果收入金额有并列,则按抢到红包的个数递减输出;如果还有并列,则按个人编号递增输出。

输入样例

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例

1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

看完题目后感觉就是一道思维题,用不到算法。而且思路很好实现.
因为按照收入金额从高到低的递减顺序输出每个人的编号和收入金额,所以就要用结构体数组进行存储然后排序,否则只借助一维数组排序后个人编号就会乱序。
由输出格式可以看出来,结构体数组需要有三个结构体成员,分别用来表示个人编号、个人收入金额、个人收到的红包个数

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct redpage
{
    int a1;
    double b1;
    int c1;
}num[10010];

bool cmp(redpage a,redpage b)
{
    return a.b1>b.b1;
}
bool cmp1(redpage a,redpage b)
{
    return a.c1>b.c1;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        num[i].a1=i;

        int sum=0;//记录第i个人发出去多少钱
        int k;
        cin>>k;
        while(k--)
        {
            int m,p;
            cin>>m>>p;
            num[m].b1+=p;
            sum+=p;
            num[m].c1++;
        }
        num[i].b1-=sum;
    }

    sort(num+1,num+n+1,cmp);

    for(int i=1;i<=n;++i)//如果收入金额有并列,则按抢到红包的个数递减输出;
    {
        int j=i;
        while(num[j].b1==num[i].b1)
            j++;
        if(j>i)
        {
            sort(num+i,num+j,cmp1);
            i=j-1;
        }
    }

    //(如果还有并列,则按个人编号递增输出)这种情况不用判断,因为在使用sort()函数排序后,对于相等的元素,按照元素下标递增排列

    for(int i=1;i<=n;++i)//输出最后结果
    {
        num[i].b1=num[i].b1*0.01;
        printf("%d %.2lf\n",num[i].a1,num[i].b1);
    }
    return 0;
}
//无论sort函数还是冒泡排序,对于相等的元素(降序),下标小的在左边,下标大的在右边.

上面代码提交后显示段错误,可能的原因是您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起.
通过排查发现是对红包个数排序的for()有问题,刚开始就觉着是for循环里边的sort()发生了越界.但经过思考后发现sort没有问题.
那是哪的问题呢,随手将for循环中的while的判断条件加了一条j<=n,AC了.
对于while(num[j].b1==num[i].b1),刚开始想的是,当i=n时,j=n+1,此时num[j].b1!=num[i].b1,然后i,此时i=n+1,不满足i<=n。
但是自己忽略了一种情况:当num[n].b1=0的时候,num[n+1].b1=0,那么就会一直j
.而自己的num[]数组是最大开到了10010.当j>10010时,执行sort()排序命令,就会对num[]数组之外的元素进行排序,就造成了数组越界.

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct redpage
{
    int a1;
    double b1;
    int c1;
}num[10010];

bool cmp(redpage a,redpage b)
{
    return a.b1>b.b1;
}
bool cmp1(redpage a,redpage b)
{
    return a.c1>b.c1;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        num[i].a1=i;

        int sum=0;//记录第i个人发出去多少钱
        int k;
        cin>>k;
        while(k--)
        {
            int m,p;
            cin>>m>>p;
            num[m].b1+=p;
            sum+=p;
            num[m].c1++;
        }
        num[i].b1-=sum;
    }

    sort(num+1,num+n+1,cmp);

    for(int i=1;i<=n;++i)//如果收入金额有并列,则按抢到红包的个数递减输出;
    {
        int j=i;
        while(num[j].b1==num[i].b1&&j<=n)
            j++;
        if(j>i)
        {
            sort(num+i,num+j,cmp1);
            i=j-1;
        }
    }

    //(如果还有并列,则按个人编号递增输出)这种情况不用判断,因为在使用sort()函数排序后,对于相等的元素,按照元素下标递增排列

    for(int i=1;i<=n;++i)//输出最后结果
    {
        num[i].b1=num[i].b1*0.01;
        printf("%d %.2lf\n",num[i].a1,num[i].b1);
    }
    return 0;
}
//无论sort函数还是冒泡排序,对于相等的元素(降序),下标小的在左边,下标大的在右边.

这样就可以了.

以后对于双指针的使用,一定要注意越界的问题


其实上边对红包个数进行排序的时候完全可以不用双指针,有更简单的方法:
那就是对于sort()排序只有一个就行:

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct redpage
{
    int a1;
    double b1;
    int c1;
}num[10010];

bool cmp(redpage a,redpage b)
{
    if(a.b1==b.b1)
    {
        if(a.c1==b.c1)
            return a.a1<b.a1;
        else
            return a.c1>b.c1;
    }
    return a.b1>b.b1;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        num[i].a1=i;

        int sum=0;//记录第i个人发出去多少钱
        int k;
        cin>>k;
        while(k--)
        {
            int m,p;
            cin>>m>>p;
            num[m].b1+=p;
            sum+=p;
            num[m].c1++;
        }
        num[i].b1-=sum;
    }

    sort(num+1,num+n+1,cmp);

    for(int i=1;i<=n;++i)//输出最后结果
    {
        num[i].b1=num[i].b1*0.01;
        printf("%d %.2lf\n",num[i].a1,num[i].b1);
    }
    return 0;
}

对于sort()函数详解和sort()函数在结构体中的应用 看这里



活动打卡代码 AcWing 774. 最长单词

无味
18天前
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s;
    int max=0;
    string c;
    while(cin>>s)
    {
        if(s[s.size()-1]=='.')
        {
            if(s.size()-1>max)
            {
                max=s.size()-1;
                c=s.substr(0,s.size()-1);
            }
            break;
        }
        else
        {
            if(s.size()>max)
            {
                max=s.size();
                c=s;
            }
        }
    }
    cout<<c;
    return 0;
}

双指针法:
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s,res;
    getline(cin,s);
    for(int i=0,j=0;s[i];++i)
    {
        while(s[j]!=' '&&s[j]!='.')
            j++;
        if(j-i>res.size())
            res=s.substr(i,j-i);
        i=j;j++;
    }
    cout<<res;
    return 0;
}



无味
18天前
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        int max=0;
        char c;
        for(int i=0,j=0;s[i];++i)
        {
            int cnt=0;
            while(s[j]==s[i])
                j++;

            if(j-i>max)
            {
                max=j-i;
                c=s[i];
            }
            i=j-1;
        }
        cout<<c<<" "<<max<<endl;
    }
    return 0;
}



无味
19天前
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    int i;//记录两个字符串前i个字符是相同的
    for(i=0;a[i]&&b[i];++i)
    {
        if(a[i]==b[i]||a[i]-32==b[i]||a[i]+32==b[i])
        {

        }
        else 
        {
            if(a[i]>=65&&a[i]<=122)
            {
                if(a[i]>b[i]||a[i]+32>b[i]) cout<<">";
                else cout<<"<";
            }
            else
            {
                if(a[i]>b[i]) cout<<">";
                else cout<<"<";
            }
            return 0;
        }
    }
    //cout<<i<<endl;
    //运行到这里,表示两个字符串在j前所有的字符都相同,下面有两种情况:两个字符串相等,两个字符串不相等.
    if(b.size()>i)
    {
        cout<<"<";
        return 0;
    }
    if(a.size()>i)
    {
        cout<<">";
        return 0;
    }

    cout<<"=";
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    for(int i=0;a[i];++i)
        if(a[i]>='a'&&a[i]<='z') a[i]=a[i]-32;
    for(int i=0;b[i];++i)
        if(b[i]>='a'&&b[i]<='z') b[i]=b[i]-32;

    for(int i=0;a[i]||b[i];++i)
        if(a[i]!=b[i])
        {
            if(a[i]>b[i]) cout<<">";
            else cout<<"<";
            return 0;
        }
    cout<<"=";
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    char a[110],b[110];
    cin.getline(a,110);
    cin.getline(b,110);
    for(int i=0;a[i];++i)
        if(a[i]>='A'&&a[i]<='Z') a[i]=a[i]+32;
    for(int i=0;b[i];++i)
        if(b[i]>='A'&&b[i]<='Z') b[i]=b[i]+32;

    int t=strcmp(a,b);
    if(t==0) cout<<"=";
    else if(t>0) cout<<">";
    else cout<<"<";
    return 0;
}



无味
19天前

AcWing 772. 只出现一次的字符

#include<iostream>
#include<cstring>
using namespace std;
int cnt[26];
char str[100010];
int main()
{
    cin>>str;
    for(int i=0;i<strlen(str);++i) cnt[str[i]-'a']++;

    for(int i=0;i<strlen(str);++i)
        if(cnt[str[i]-'a']==1)
        {
            cout<<str[i]<<endl;
            return 0;
        }
    cout<<"no";
    return 0;
}

不在每次for循环里边都运行一次strlen()函数,只运行一次:

#include<iostream>
#include<cstring>
using namespace std;
int cnt[26];
int main()
{
    string str;
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;++i) cnt[str[i]-'a']++;

    for(int i=0;i<len;++i)
        if(cnt[str[i]-'a']==1)
        {
            cout<<str[i]<<endl;
            return 0;
        }
    cout<<"no";
    return 0;
}

因为字符串最后一个字符为0,所以也可以不用求长度:

#include<iostream>
#include<cstring>
using namespace std;
int cnt[26];
int main()
{
    string str;
    cin>>str;
    for(int i=0;str[i];++i) cnt[str[i]-'a']++;

    for(int i=0;str[i];++i)
        if(cnt[str[i]-'a']==1)
        {
            cout<<str[i]<<endl;
            return 0;
        }
    cout<<"no";
    return 0;
}

下面来看一下三种思路的运行时间:
QQ截图20201112232614.jpg
可以看到在for()循环中用s[i]是最快的.




无味
19天前
#include<iostream>
#include<cstring>
using namespace std;
int a[150];//记录每个字符出现的次数
int b[150];//记录为1的字符是第几个出现的
int cnt=1;
int main()
{
    string s;
    bool st=true;//默认没有出现一次的字符
    cin>>s;
    for(int i=0;s[i];++i)
    {
        a[s[i]]++;
        if(a[s[i]]==1) 
            b[s[i]]=cnt++;
    }

    for(int i=97;i<=122;++i)
        if(a[i]==1)  st=false;//表示有出现一次的字符


    if(st) cout<<"no";
    else
    {
        for(int i=97;i<=122;++i)
            if(a[i]==1&&b[i]==1)
                cout<<(char)i;
    }

    return 0;
}
y总:
#include<iostream>
#include<cstring>
using namespace std;
int cnt[26];
int main()
{
    string str;
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;++i) cnt[str[i]-'a']++;

    for(int i=0;i<len;++i)
        if(cnt[str[i]-'a']==1)
        {
            cout<<str[i]<<endl;
            return 0;
        }
    cout<<"no";
    return 0;
}



分享 二分

无味
21天前

POJ 4140:方程求解
看了模板之后也没有思路,于是直接看了题解:
QQ截图20201111111347.jpg

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double search(double left,double right)
{
    double mid;
    double f;
    while(right-left>1e-11)
    {
        mid=left+(right-left)/2;
        f=mid*mid*mid-5*mid*mid+10*mid-80;
        if(f<0)
            left=mid;
        else
            right=mid;
    }
    return mid;
}
int main()
{
    printf("%.9lf\n",search(0.0,10.0));
    return 0;
} 

下面没有用模板,更好理解,但也是二分的思路:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    double EPS=1e-11;
    double left=0,right=10,f;//f=f(mid)
    double mid=left+(right-left)/2;
    f=mid*mid*mid-5*mid*mid+10*mid-80;
    while(fabs(f)>EPS)
    {
        if(f>0) right=mid;
        else left=mid;
        mid=left+(right-left)/2;
        f=mid*mid*mid-5*mid*mid+10*mid-80;
    }

    printf("%.9lf\n",mid);
    return 0;
}



无味
29天前

算法思想:

QQ截图20201102202104.jpg
QQ截图20201102172548.jpg


例题:

AcWing 422. 校门外的树
第一次看完这个题第一反应就是暴力枚举呗

#include<iostream>
using namespace std;
int a[10005];//默认为false,表示没有被砍掉
int main()
{
    int l,m,sum=0;
    cin>>l>>m;
    while(m--)
    {
        int fir,las;
        cin>>fir>>las;
        for(int i=fir;i<=las;++i)
            a[i]=true;//表示被砍掉
    }
    for(int i=0;i<=l;++i)
        if(!a[i])
            sum++;
    cout<<sum;
    return 0;
}

区间合并:

#include<cstring>
#include<iostream>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int n,m;
PII q[N];

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;++i) cin>>q[i].x>>q[i].y;//读入数组
    sort(q,q+m);//排序

    int sum=0;//被砍掉的树的数量
    int st=0,ed=-1;//正在合并区间的左右端点,让右端点在左端点左边,是个小技巧
    for(int i=0;i<m;++i)//遍历所有区间
        if(ed<q[i].x)
        {
            sum += ed-st+1;//记得要加1
            st=q[i].x,ed=q[i].y;
        }
        else ed=max(ed,q[i].y);

    sum += ed-st+1;//最后一个区间也要计数,容易忘!!!!

    cout << n+1-sum <<endl;
    return 0;
}

AcWing 803. 区间合并

#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 100005;

int n;
PII q[N];

int main()
{
    int sum=0;

    cin>>n;

    for(int i=0;i<n;++i) cin>>q[i].x>>q[i].y;

    sort(q,q+n);

    int st=q[0].x-1,ed=st-1;让左端点st在最小区间的左边,然后让右端点在左端点左边
    for(int i=0;i<n;++i)
        if(ed<q[i].x)
        {
            sum++;
            st=q[i].x;ed=q[i].y;
        }
        else
            ed=max(ed,q[i].y);

    cout<<sum;
    return 0;
}

由上面两个题的st和ed取值可以看出来,st和ed的取值是要根据题意来具体分析的,不能一概而论,但有一个原则就是要让st小于最左区间的左端点值,而且ed=st-1