ACM.基础题目——寒假培训

柔情只为你懂 2023-06-29 10:38 5阅读 0赞

28的因子  
Problem:A  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
我们都知道28的因子中含有4和7，而某些人偏爱数字4和7；  
例如数字：747,4,7747,4,7是兴安黑熊喜欢的数字，而476,5,27476,5,27则不是。  
对于给定的数字n，能否找出各个数位上数字和为n的最小的兴安黑熊喜爱的数字。  
如果找到则输出这个最小数, 如果找不到，则输出“xinganheixiong”。  
Input  
多组输入。  
每组输入一个整数n(1 ≤ n ≤ 1e6) 代表各个数位上数字的和。  
Output  
如果兴安黑熊喜欢的话，就输出最小的喜欢数字！  
否则就输出“xinganheixiong”  
Sample Input  
11  
13  
Sample Output  
47  
xinganheixiong  
分析：  
如果有解，则要输出的答案只由4和7组成  
设4的个数为x，7的个数为y  
则4*x+7*y=n，n最大为1e6  
所以可以直接暴力枚举x的取值，x满足 x>=0&&n-4\*x>=0  
如果能找到y，表示找到了答案。  
但是题目还要求答案要尽可能小，所以我们要优先取x小的(也就是4的数量少的，7的数量多的)，这样才能保证数的长度尽可能小，然后数的大小也尽可能小。

#include <bits/stdc++.h>
    using namespace std;
    int n,ans1,ans2;
    int main()
    {
        
        ios::sync_with_stdio(false);
        while(cin>>n)
        {
        
            int flag=0;
            for(int i=0;i<=n;i+=4)//枚举i，得到x
            {
        
                if((n-i)%7==0)
                {
        
                    int y=(n-i)/7;
                    ans1=i/4;ans2=y;//ans1为最终要输出的4的长度，ans2为最终要输出的7的长度
                    flag=1;//标记存在答案
                    break;
                }
            }
            if(!flag)printf("xinganheixiong\n");//找不到答案
            else
            {
        
                for(int i=1;i<=ans1;i++)
                    printf("4");
                for(int i=1;i<=ans2;i++)
                    printf("7");
                printf("\n");
            }
        }
        return 0;
    }

二.陈老师发奖金  
Problem:B  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
陈老师拿到第一块金牌后，学校马上给了老师一笔奖金，老师很高兴，决定选择成绩优秀的同学颁发奖金，因为老师特别喜欢数学和c语言好的同学，所以在n位同学中：  
优先选择数学和c语言成绩之和最高的4位同学颁发奖金；  
若数学和c语言成绩之和相同，则给英语成绩高的同学，先颁发奖金；  
若是数学和c语言成绩之和与英语成绩分别对应相同，优先给后读入的同学颁发奖金；  
Input  
多组输入。  
共n+1行，第一行为学生总人数n；  
接下来n行输入学生的信息，每一行为学生的学号，c语言成绩，英语成绩，数学成绩（1<n<=1e5）  
保证学号和成绩均在int范围内。  
Output  
按成绩从高到低输出，数学和c语言成绩之和最高的4位同学的学号以及对应的成绩。  
（若总人数小于4，则直接输出，并且需要满足题目要求的排序后的同学学号）  
Sample Input  
3  
11 88 20 98  
22 97 89 100  
33 88 99 100  
5  
11 90 99 80  
22 87 66 91  
44 90 99 80  
55 67 89 64  
66 78 89 98  
Sample Output  
22 197  
33 188  
11 186  
22 178  
66 176  
44 170  
11 170

很基础的结构体排序题目，注意排序函数cmp的写法即可

#include <bits/stdc++.h>
    using namespace std;
    struct stu
    {
        
        int c;
        int math;
        int en;
        int id;
        int num;
        int sum;    //习惯结构体成员写多点，这样感觉清晰一点，虽然没必要
    };
    bool cmp(stu a,stu b)
    {
        
        if((a.math+a.c)!=(b.math+b.c))
        {
        return (a.math+a.c)>(b.math+b.c);}
        else
        {
        
            if(a.en!=b.en)return a.en>b.en;
            else{
        
                return a.num>b.num;
            }
        }
    }
    int main()
    {
        
        int n,q,i;
        while(scanf("%d",&n)!=-1)
        {
        
            stu p[n];
            for(int i=0;i<n;i++)
            {
        
                scanf("%d%d%d%d",&p[i].id,&p[i].c,&p[i].en,&p[i].math);
                p[i].sum=p[i].c+p[i].math;
                p[i].num=i;
            }
            sort(p,p+n,cmp);
        if(n<4)
        {
        
            for(i=0;i<n;i++)
            {
        
                printf("%d %d\n",p[i].id,p[i].sum);
            }
        }
        else
        {
        
            for(i=0;i<4;i++)
                {
        
                    printf("%d %d\n",p[i].id,p[i].sum);
                }
        }}
        return 0;
    }

三.小明分蛋糕  
Problem:C  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
小明分蛋糕，开始小明有a块蛋糕，经过分配后小明要拥有b块蛋糕，老师为了给小明增加难度，要求小明分蛋糕时只能采取以下6种操作：  
(1)输入-5 表示丢掉5块蛋糕  
(2)输入-2 表示丢掉2块蛋糕  
(3)输入-1 表示丢掉1块蛋糕  
(4)输入1 表示获得1块蛋糕  
(5)输入2 表示获得2块蛋糕  
(6)输入5 表示获得5块蛋糕  
最后，老师要求小明回答：从a块蛋糕到b块蛋糕，所需的最少的步骤数为多少。  
Input  
第一行，输入t，表示有t组数据 (1≤t≤1000)  
接下来，每组数据输入两个整数a，b（0≤a,b≤1e9）  
Output  
共t行，每行输出从a到b所需的最少步骤数（若a==b，则直接输出0）  
Sample Input  
3  
4 0  
5 14  
3 9  
Sample Output  
2  
3  
2

简单的思维题，没有什么算法知识。

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int t,a,b;
        while(cin>>t)
        {
        
            while(t--)
            {
        
                cin>>a>>b;
                int c=fabs(a-b);
                int sum=0,sum1,sum2,sum3;
                sum1=c/5;
                sum2=(c-sum1*5)/2;
                sum3=(c-sum1*5-sum2*2)/1;
                sum=sum1+sum2+sum3;
                if(a!=b)cout<<sum<<endl;
                else cout<<"0"<<endl;
            }
        }
        return 0;
    }

四.  
神奇的事情发生了  
Problem:D  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
神奇的事情发生了！在一个字符串中有两个“o”相连就会变成“O”，而有两个“O”相连他们就都会消失，而“O”和“o”相邻却什么都不会发生，现在有一个只由“O”和“o”组成的字符串，小明想知道这个字符串最后会变成什么样子。  
Input  
多组输入。  
每组输入一个字符串s(0<strlen(s)<100)。  
Output  
输出最后的字符串。  
Sample Input  
ooOOoooO  
Sample Output  
oO

可以用数组模拟栈做也可以直接用栈来做

1数组模拟栈解法：

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        char a1[100];
        while(cin>>a1)
        {
        int i=1;
        int l=strlen(a1);
       for(i=1;i<l;i++)
       {
        
           if(a1[i]=='o'&&a1[i-1]=='o')
           {
        
               a1[i-1]='O';
               for(int j=i+1;j<l;j++)
                   {
        a1[j-1]=a1[j];}
                i--;
                l--;
                   a1[l]='\0';
           }
           if(a1[i]=='O'&&a1[i-1]=='O')
           {
        
               for(int j=i;j<l;j++)
                   {
        a1[j-1]=a1[j+1];}
                i-=2;
                l-=2;
                a1[l]='\0';
       }}
       cout<<a1<<endl;}
      return 0;
    }

2.栈

#include <bits/stdc++.h>
    using namespace std;
    const int N=1e5;
    char ch[N],a[N];
    stack<char>s;
    int main()
    {
        
        while(~scanf("%s",ch))
        {
        
            int len=strlen(ch);
            for(int i=0; i<len; i++)
            {
        
                if(s.empty()){
        s.push(ch[i]);continue;}   //栈为空就向其中放入元素
                if(ch[i]=='O')
                {
        
                    char k=s.top();
                    if(k=='O')s.pop();        //两个连续的大O消除
                    else s.push(ch[i]);
                }
                else if(ch[i]=='o')
                {
        
                    char k=s.top();
                    if(k=='o')
                    {
        
                        s.pop();
                        if(s.empty())s.push('O');
                        else
                        {
        
                            k=s.top();    
                            if(k=='O')s.pop();  //如果两个连续的小o后面还有一个大o，合并后都会消去。所以直接把栈顶的小o去掉，避免Ooo的出现
                            else s.push('O');
                        }
                    }
                    else s.push('o');
                }
            }
            int cnt=0;
            while(!s.empty())
            {
        
                a[++cnt]=s.top();
                s.pop();
            }
            for(int i=cnt; i>=1; i--)
                printf("%c",a[i]);
            printf("\n");
        }
        return 0;
    }

五.  
jwMM的射箭游戏  
Problem:F  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
jwMM和她的好朋友GG一起在公园里散步的时候，眼前突然出现了一个悬浮的箭靶，jwMM马上拿出了自己藏在身上的弓，准备射中箭靶，向好朋友炫耀。但是她的好朋友GG知道jwMM的弓术无比差劲，就决定用念力帮她维护一下她脆弱的自尊心。现在给出箭靶的坐标x1,y1，jwMM射出的箭被念力包裹时的坐标x2,y2，如果x2-y2恰好是x1与y1的某个大于1的公因子的正整数倍，则可以射中，否则就射不中。  
请判断最后jwMM是否能够射中靶子，如果能，输出Y，否则输出N。  
Input  
多组输入。  
每组输入四个整数x1,y1,x2,y2。  
x1,y1代表箭靶的坐标，x2,y2代表箭被念力包裹时的坐标。  
保证所有输入数据为正且在int范围之内。  
Output  
输出Y或N。  
Sample Input  
10 6 6 2  
Sample Output  
Y

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int x1,y1,x2,y2;
        while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=-1)
        {
        
            int d=x2-y2,flag=0;
            int p=__gcd(x1,y1);
            for(int i=2;i<=p;i++)
            {
        
                if(d%i==0&&p%i==0&&d>0){
        flag=1;   //注意此处的d>0的特殊判断。
                break;
            }
            }
            if(flag==1)printf("Y\n");
            else printf("N\n");
        }
        return 0;
    }

六.  
抹发胶  
Problem:I  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
今天独立团团长教战士们抹发胶(每个人抹的发胶都有一个发胶值)。大家排成一行，从左到右依次排开，他们只能看到自己左边的人，大家都是两个肩膀扛一个脑袋的，谁也不服谁，于是他们都想知道自己左边到底有多少人的发胶值不如自己。如果不如自己的人越多，他们就越高兴，因为这样他们的发型就越不会乱啦。  
现在想问问你，如果每个人都看向左边，有多少人的发胶值小于自己呢？（任意两个人的发胶值可能一样）  
Input  
首先输入T (T<=10)，表示有T组数据；  
每组数据输入人数N(N<=100)和每个人的发胶值ai(0<ai<1000)。  
Output  
每组输出n个数字，第i个输出的数字表示第i个人左边有多少人的发胶值小于自己。  
数字之间用一个空格隔开，注意最后一个数字之后不要输出多余的空格。  
Sample Input  
2  
5  
1 2 3 4 5  
4  
8 3 2 6  
Sample Output  
0 1 2 3 4  
0 0 0 2

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int T,N;
        while(scanf("%d",&T)!=-1)
        {
        
            while(T--)
            {
        
                scanf("%d",&N);
                int a[N];
                for(int i=0;i<N;i++)
                {
        
                    scanf("%d",&a[i]);
                }
                int sum[N];
                memset(sum,0,sizeof(sum));
                sum[0]=0;
                for(int j=1;j<N;j++)
                {
        
                    for(int q=0;q<j;q++)
                    {
        
                        if(a[j]>a[q])sum[j]++;
                    }
                }
                for(int p=0;p<N;p++)
                {
        
                    if(p!=N-1)
                    {
        printf("%d ",sum[p]);}
                    else printf("%d\n",sum[p]);
                }
            }
        }
        return 0;
    }

两层for循环即可解出来。

七.  
天哥的难题  
Problem:J  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
天哥知道你们学了位运算，所以他出了一道题来为难你们，就是让你求A+B=A|B(其中|为“或”运算)的解有多少个。但是他的队友们觉得这样太难了所以加上了限制条件，他的队友让A和B都小于N，N为2的幂次。(2,1)和(1,2)会被认为是不同的两个解。  
Input  
多组输入。  
每一行输入一个非负整数M。N=2M，M≤109，即2的M次幂为N。  
Output  
每一组输出一行。  
每一行输出一个整数ans，答案对1e9+7(即1000000007)取模。  
Sample Input  
0  
20  
Sample Output  
1  
486784380

关键在于找到规律值，当只有1位二进制的时候即题目中的m为1的时候，a+b=a|b答案有(0,0) (0,1) (1,0)所以根据这一位可以推出后面的情况因为每一位都有三种情况 所以你在m等于1的时候得出的三个答案每一个前面都可以加上(0,0) (0,1) (1,0)也就是(0,0)->(00,00) (10,00) (00,10) (0,1)->(00,01) (10,01) (00,11) (1,0)->(01,00) (11,00) (01,10)所以后面每多加一位的话方案数就会乘3，所以就可以上快速幂了。

#include <bits/stdc++.h>
    using namespace std;
    const long long mod=1e9+7;
    long long quick_mod(long long a,long long b)
    {
        
        long long sum=1;
        while(b)
        {
        
            if(b&1)
            {
        
                sum*=a;
                sum%=mod;
            }
            a=(a*a)%mod;
            b>>=1;
        }
        return sum;
    }
    int main()
    {
        
        long long sum;
        long long n;
        while(scanf("%lld",&n)!=EOF)
        {
        
            sum=quick_mod(3,n);
            printf("%lld\n",sum);
        }
        return 0;
    }

八.  
丹青玩游戏  
Problem:G  
Time Limit:500ms  
Memory Limit:65535K  
Description  
在半年的林大生活里，很多同学喜欢来丹青学习，而丹青教室的灯却总是忽明忽暗，非常不利于我们学（wan）习（you xi），为此，一些同学决定修改丹青的电路。  
现在，我们已知一个教室里有m个灯，n个开关，每个灯由其中几个开关控制，对于灯泡i，相关开关为“on”的数量对2取模与pi相同时，该灯泡亮，问：  
想要所有的灯泡都亮，开关的“on”和“off”状态有几种组合方式（比如：5个开关中1 2 4号为“on”和3 4号开关为“on”是两种不同的组合方式）  
Input  
多组输入。  
第一行：开关数量n和灯泡数量m  
第2行至第m+1行：第一个数字ki是第i个灯泡相关的开关数量，其后是开关编号（1~n）  
最后一行：pi每个灯泡亮的状态  
数据范围：  
1≤n，m≤10  
1≤ki≤N  
Pi为0或1  
所有输入均为整数。  
Output  
输出一个整数，表示总的开关组合数量。  
Sample Input  
2 2  
2 1 2  
1 2  
0 1  
2 3  
2 1 2  
1 1  
1 2  
0 0 1  
5 2  
3 1 2 5  
2 2 3  
1 0  
Sample Output  
1  
0  
8

输入的数据非常多且有一定的对应关系，所以考虑用结构体存储数据，考察二进制枚举。

#include <bits/stdc++.h>
    using namespace std;
    struct node
    {
        
        int k;
        int a[15];
        int p;
    }s[15];
    int main()
    {
        
        int n,m;
        int i,j,k;
        int b[15],num,flag,ans,flag1;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
        
            ans=0;
            for(i=0;i<m;i++)
            {
        
                scanf("%d",&s[i].k);
                for(j=0;j<s[i].k;j++)
                    scanf("%d",&s[i].a[j]);
            }
            for(i=0;i<m;i++)
                scanf("%d",&s[i].p);
            for(i=0;i<(1<<n);i++)//枚举过程
            {
        
                flag=flag1=0;
                memset(b,0,sizeof(b));
                for(j=0;j<n;j++)
                {
        
                    if(i&(1<<j))//标记所有为开的开关
                    {
        
                        b[j+1]=1;
                        flag1=1;
                    }
                }
                for(j=0;j<m;j++)//检验是否符合条件
                {
        
                    num=0;
                    for(k=0;k<s[j].k;k++)
                        if(b[s[j].a[k]]==1)num++;
                    if(num%2!=s[j].p)
                    {
        
                        flag=1;
                        break;
                    }
                }
                if(flag==0)ans++;
            }
            printf("%d\n",ans);//输出
        }
        return 0;
    }