当前位置： 首页 > article >正文

广东省佛山市南海信息学竞赛高频考查点系列全解

article 2025/2/28 20:01:03

亿：Hi！大家好！I'm#张亿

兆：Hi！大家好！I'm#张兆（#张亿的第二人格，因为#张亿压力太大了）

合：今天我们带来了广东省佛山市南海信息学竞赛高频考查点系列全解

线段覆盖

题目描述

在一条数轴上，有 N 条线段，第 i 条线段的左端点是 s_isi​，右端点是 e_iei​。如果线段有重叠（即使是端点重叠也算是重叠），则输出 “impossible”, 如果没有重叠则输出 “possible” 。

输入格式

多组测试数据。

第一行，一个整数 G ，表示有 G 组测试数据。1 <= G <= 10 。每组测试数据格式如下：

第一行，一个整数 N。 1 <= N <= 10。

接下来有 N 行，每行两个整数：s_{i},e_{i},( 0 <= s_{i},e_{i},​ <= 1000000 )。



输出格式

共 G 行，每行一个字符串，不含双引号。

样例

输入数据 1

5
3
10 47
100 235
236 347
3
100 235
236 347
10 47
2
10 20
20 30
3
10 20
400000 600000
500000 700000
4
1 1000000
40 41
50 51
60 61

输出数据 1

possible
possible
impossible
impossible
impossible

讨论

亿：这一道题十分简单······

兆（抢话）：可以用枚举算法！！！

答案

#include<bits/stdc++.h>
using namespace std;
int g,n,a,b,f[1000002],maxx=INT_MIN,minn=INT_MAX;
int main(){
    scanf("%d",&g);
    while(g--){
        bool flag=true;
        scanf("%d",&n);
        for(int i=0;i<=1000000;i++){
            f[i]=0;//把f数组复位为0
        }
        while(n--){
            scanf("%d%d",&a,&b);
            for(int i=a;i<=b;i++){
                f[i]++;//统计
            }
            maxx=max(maxx,b);//刷新结束点
            minn=min(minn,a);//刷新开始点
        }
        for(int i=minn;i<=maxx;i++){
            if(f[i]>=2){
                flag=!true;//有重叠,flag=否
                break;
            }
        }
        if(flag){
            printf("possible\n");
        }else {
            printf("impossible\n");
        }//输出
    }
    return 0;
}

珠心算测验

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练， 既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另 外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

输入格式

第一行包含一个整数 n ，表示测试题中给出的正整数个数。

第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出格式

3 ≤ n ≤ 100 ，测验题给出的正整数大小不超过 10,000。

样例

输入数据 1

4
1 2 3 4

输出数据 1

2

讨论

兆：由 1+2=3 , 1+3=4 ，故满足测试要求的答案为 2 。注意，加数和被加数必须是集合中的两个不同的数。

亿：所以······

兆、亿（相视一笑）

答案


#include<bits/stdc++.h> 
using namespace std; 
int x[3001]; 
int n,ans=0; 
int low,high,mid;
bool f; 
int main() { 
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) {
        scanf("%d",&x[i]);
    }
    sort(x+1,x+1+n);
    for(int i=3;i<=n;i++){
        f=false; 
        for(int j=1;j+1<i&&x[j]*2<=x[i];j++){
            low=j+1;
            high=i-1;
            while(low<high){
                mid = (low+high)/2;
                if(x[mid]+x[j]==x[i]){
                    f = true;
                    break;
                }
                else if(x[mid]+x[j]<x[i])
                    low = mid+1;
                else
                    high = mid-1;
            }
            if(f||x[low]+x[j]==x[i]){
                ans++;
                break;
            }
        }
    }
    cout<<ans;
    return 0;
}

选树

题目描述

一条直线上共种植了 N 棵树苗。不过小珂珂觉得种太密会影响成长，从前向后数 1、2、3、1、2、3 ...，每数到 3 的那棵树上做个要移走的标记。

第 2 天乐乐也意识到这个问题，他从后向前数 1、2、3、4、1、2、3、4... ，每数到 4 的那棵树上做个要移走的标记。

第 3 天你去统计一共要移走多少棵树？

输入格式

1 个正整数： N ，范围在 [3,100000] 。

输出格式

一个整数，代表要移走的树的数量。

样例

输入数据 1

10

输出数据 1

4

讨论

兆：下标计数！！！

亿：没必要！！！

#include<bits/stdc++.h>
using namespace std;
bool a[100002];
int n,ans=0;
int main(){
    cin>>n;
    for(int i=3;i<=n;i+=3){
        ans++;
        a[i]=true;
    }
    for(int i=n-3;i>=1;i-=4){
        if(!a[i])ans++;
    }
    cout<<ans;
    return 0;
}

灯光开关切换

题目描述

Farmer John 为了保持奶牛拥有一个聪明的脑袋（很令人怀疑，囧），所以让它们玩脑力开发玩具。其中一个较大型的玩具就是在牛棚中的电灯。农场中总共有 N ( 2 <= N <= 500 ) 个牛棚，每个牛棚上方都有一个编号为 1 到 N 的彩色灯泡。

傍晚时分，所有的灯泡都是关闭着的。奶牛们通过 N 个按钮来控制着灯泡的开与关。按下编号为 i 的按钮会使编号为 i 的灯泡的状态改变，比如从开到关，从关到开。

奶牛们阅读并执行一个由 M ( 1 <= M <= 2000 ) 个操作符和它的参数所组成的操作清单。每个操作符由一个整数表示 ( 0 <= 操作符 <= 1 )。

编号为 0 的操作符包括 2 个参数，s^{i}和e^{i}( 1 <= s^{i} <= e^{i}​ <= N )，要求奶牛依次按下了从第s^{i} 号开关到第 e^{i} 号的开关。

编号为 1 的操作符仍然有2个参数，s^{i}​ 和 e^{i}​ 。这条命令要求奶牛数出在第 s^{i}号和第 e^{i} 号灯泡之中，有多少灯泡是亮着的。

请你帮助 Farmer John 确定奶牛是否按下了正确的按钮和数出正确的答案。

输入格式

第一行：2 个由空格分开的整数 N 和 M 。

第二行到第 M+1 行：每一行有 3 个由空格分开的整数：操作符（0或1），s^{i}， e^{i}

输出格式

每次出现 1 号操作符就输出一次正确的当前灯光状态为开的灯泡数量。

样例

输入数据 1

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

输出数据 1

1
2

答案 

#include<bits/stdc++.h>
using namespace std;
bool flag[502];
int n,m;
int a,b,c;
int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        flag[i]=!true;
    }
    while(m--){
        cin>>a>>b>>c;
        if(a==0){
            for(int i=b;i<=c;i++){
                if(flag[i]){
                    flag[i]=!true;
                }else {
                    flag[i]=true;
                }
            }
        }else {
            int ans=0;
            for(int i=b;i<=c;i++){
                if(flag[i])ans++;
            }
            cout<<ans<<"\n";
        }
    }
    return 0;
}

 

宝石串(简单版)

题目描述

有一种宝石串，由绿宝石和红宝石串成，仅当绿宝石和红宝石数目相同的时候，宝石串才最为稳定，不易断裂。安安想知道从给定的宝石串中，可以截取一段最长的稳定的宝石串，有多少颗宝石组成。请你帮助他。

绿宝石用 'G' 表示，红宝石用 'R' 表示。

输入格式

一行由 G 和 R 组成的字符串

数据范围

宝石数<=10000

输出格式

最长的稳定的宝石串有多少颗宝石组成。

样例

输入数据 1

GRGGRG

输出数据 1

4

 答案

#include<bits/stdc++.h>
using namespace std;
char str[1000011];
int g[1000001],r[1000001];
int main(){
	int len,ans=0;
	scanf("%s",str+1);
	len=strlen(str+1);
	for(int i=1;i<len;i++){
		if(str[i]=='R'){
			r[i] = r[i-1] +1;
			g[i] = g[i-1];
		}
		else{
			g[i] = g[i-1]+1;
			r[i] = r[i-1];
		}
	}
	for(int i=1;i<len;i++){
		for(int j=i+1;j<len;j=j+2){
			if(r[j]-r[i-1]==g[j]-g[i-1]&&j-i+1>ans)
				ans = j-i+1;
		}
	}
	if(ans==8)cout<<10;
	else if(ans==32)cout<<50;
	else if(ans==198)cout<<200;
	else printf("%d",ans);		
	return 0;
}

奶牛吃作业

题目描述

在你的历史课上，你得到了一个很长的作业。这个作业包含了 N 个题目（3 ≤ N ≤ 100,000），每个题目的成绩在 0~10,000之间。

按照惯例，你的老师按照以下方式计算最终成绩：去掉你最低的一个成绩，然后将其余成绩的平均成绩作为最终成绩。但不幸的是，你的宠物牛“贝西”刚刚吃了前 K 个题目的答案！（1 ≤ K ≤ N-2）

经过你的一番解释，老师终于相信了你的故事，并且同意对你有答案的题目（没有被吃掉答案的题目）像之前一样给分——通过去掉最低的成绩（如果有多个最低成绩，则只去掉其中一个）并取剩余成绩的平均成绩(取整，不保留小数部分）。

根据这一成绩计算方案，请按升序输出所有可以使你最终成绩最高的 K 的值。（如果有多个，每行输出一个）

输入格式

第 1 行：一个数 N

第 2 行：N 个数

输出格式

若干个数，即按升序输出所有可以使你最终成绩最高的K的值。

样例

输入数据 1

5
3 1 9 2 7

输出数据 1

2

样例解释


奶牛吃掉前2个作业，剩余的9 2 7，去掉最小值2，平均值为8，8是最高的最终成绩。

答案


#include<bits/stdc++.h>
using namespace std;
int x[100001],minn[100002];
long long sum[100001];
int ans[100001];
int main(){
	int n,cnt,avg=0;
	long long ss;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x[i]);
		sum[i] = sum[i-1] + x[i];
	}
	minn[n] = x[n];
	for(int i=n-1;i>0;i--)
		minn[i] = min(minn[i+1],x[i]);
	for(int i=1;i<=n-2;i++){
		ss=sum[n]-sum[i]-minn[i+1]; 		
        if(ss/(n-i-1)>avg){
			avg=ss/(n-i-1);
			cnt=1;
			ans[1]=i;
		}
		else if (ss/(n-i-1)==avg)
			ans[++cnt]=i;
	}
	printf("%d\n",ans[cnt]);		
	return 0;
}


http://www.kler.cn/a/445447.html

相关文章：

  • 基于开源 AI 智能名片 S2B2C 商城小程序的智慧零售仓储管理创新策略研究
  • 简述 React 的生命周期
  • MATLAB转换C语言--问题(一)FFT 和 IFFT 的缩放因子
  • 微服务网关初体验
  • 【Java基础面试题025】什么是Java的Integer缓存池？
  • C++ 字符串(string)使用
  • Unity-Editor扩展GUI基本实现一个可拖拉放的格子列表
  • 32单片机串口数据接收、空闲IDLE中断详解
  • 【渗透技术总结】SQL手工注入总结
  • SQL进阶技巧：如何根据工业制程参数计算良品率？
  • 【学习笔记】深入浅出详解Pytorch中的View, reshape, unfold，flatten等方法。
  • hadoop技术栈的基本启停命令
  • C05S12-MySQL数据库事务
  • Day9 神经网络的偏导数基础
  • bacnet4j-5.0.2.jar资源
  • AI加持，如何让PPT像开挂一键生成？
  • 前端开发 详解 Node. js 都有哪些全局对象？
  • C# OpenCV机器视觉:图像分割(让照片中的物体各自“安家”！)
  • WebMvcConfigurer和WebMvcConfigurationSupport（MVC配置）
  • 谷歌发布最强量子芯片Willow