“艾迪-东软杯”第六届武汉理工大学新生程序设计竞赛

A.Capoo's Acronym Zero

题目描述

yz 和他的朋友 ea 和 zech 一起养了一群 Capoo。

这些 Capoo 非常聪明,但不知道为什么,它们并没有从三人那里学到怎么写算法题,而是出于某种原因开始研究语言学,并发明了一套自己的暗语。这门暗语的编写规则非常简单:一个句子可以认为是一个字符串,中间仅包含大写英文字母和小写英文字母,每个大写字母对应一个单词。而与之对应的暗语则是依次取出句子中每个单词的第一个字符,把它们直接拼接到一起。例如:句子 WetaDigital 对应的暗语为 WD 。

很明显,这套暗语规则十分简单,但不同句子所对应的暗语之间容易发生冲突。以之前的例子为例,短语 WesternDigital 所对应的暗语也是 WD ,这时,当听到一只 Capoo 提到 WD 时,三人就会困惑于它指代的到底是什么意思。yz 已经准备了一个包含很多句子的词典,但还需要一个翻译程序在听到 Capoo 所提到的暗语时快速找到这个暗语都对应了词典中的哪些句子。事实上,这个程序早已写好,可惜这里空白的地方太小,写不下,现在复现这个程序的任务被交给了你。

输入描述

第 1 行为两个整数 n , q ,(0≤n≤1e4,1≤q≤1e4) 为词典中的句子数和询问翻译程序的次数。

第 2 行到第 n+1 行为词典,每行为一个句子,内容仅包含二十六个英文字母的大小写形式。

第 n+2 行到第 n+q+1 行,每行一个字符串,为本次需要查询查询的暗语。

输出描述

对于每次询问,输出格式如下:

第 1 行为一个整数sum ,为所询问的这个暗语在词典中能对应上的句子数目。

第 2行到第 sum+1 行,每行为一个当前所询问的暗语所对应的句子。请按输入时句子在词典中的相对顺序输出。

示例1

输入1

5 3
WetaDigital
wordDrive
wikipediadancer
WesternDigital
wonderfulday
WD
wd
Wd

输出1

2
WetaDigital
WesternDigital
0
0

示例2

输入2

10 5
Zech
EternalAlexander
YZ
RoSeMoe
InnovationInChina
ColorlessGreenIdeasSleepFuriously
EveryFrogTriesReallyNew
EclipseFirstTheRestNowhere
CleverThinkingBoostsProblemSolving
RouSiMian
YZ
EA
Z
EFTRN
RSM

输出2

1
YZ
1
EternalAlexander
1
Zech
2
EveryFrogTriesReallyNew
EclipseFirstTheRestNowhere
2
RoSeMoe
RouSiMian

备注

一个单词最多长 202020 个字符, 一个句子最多有 505050 个单词。保证一个句子的总长度不超过 100010001000。

为什么题目叫 Capoo's Acronym Zero 呢?好问题,我也想知道。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q,idx;
unordered_map<string,int> h;

string get(string s) {
    string res="";
    bool f=false;
    for(auto it: s)
        if(it>='A'&&it<='Z') {
            f=true;
            res+=it;
        }
    if(!f) return "0000";
    return res;
}

signed main() {
    cin>>n>>q;
    vector<string> g[n+10];
    for(int i=0;i<n;i++) {
        string s;
        cin>>s;
        string t=get(s);
        if(t=="0000") continue;
        if(!h[t]) h[t]=++idx;
        g[h[t]].push_back(s);
    }
    while(q--) {
        string s;
        cin>>s;
        if(g[h[s]].size()==0) {
            cout<<0<<"\n";
            continue;
        }
        cout<<g[h[s]].size()<<"\n";
        for(auto x: g[h[s]]) cout<<x<<"\n";
    }
    return 0;
}


B.原来你也玩原神

题目描述

23 级的同学们因为玩原神不够多被发配到了南湖校区,无法前往人间仙境余家头。现在同学们认识到了自己的错误,开始玩各种各样的原神。

南湖校区有 n个学生,依次编号为 1∼n ,以及 m 种原神,依次编号为 1∼m。

现在已知每个学生选择了一种原神来玩。同时,每个学生都有一个能力值 ai∈[1,k]。

现在有一位不愿透露姓名的原神高手想知道每种的原神的实力排行。即,对于每种原神,请你按照能力值从高到低的顺序输出玩这种原神的所有学生的编号(当能力值相同时,按编号升序输出)。你能回答他的问题吗?

 

输入描述

第一行三个正整数 n,m,k(1≤n,m,k≤1000),意义见题目描述。

接下来的 n 行,第 iii 行包含两个正整数 xi,ai。xi 表示编号为 i 的学生玩的原神的编号, ai​ 表示该学生的能力值。保证 1≤xi​≤m,1≤ai​≤k。

输出描述

输出共 m 行,第 i 行表示第 i 种原神的实力排行。若该种原神无人游玩,输出 −1。

示例1

输入1

5 3 10
1 10
2 9
1 8
2 9
3 1

输出1

1 3
2 4
5

说明1

样例一:原神一号中学生 111 的实力大于学生 333,原神二号中学生 222 的实力等于学生 444,原神三号中仅有学生 555。

示例2

输入2

9 7 1000
2 5
4 5
2 8
1 6
4 5
2 4
3 5
4 8
1 2

输出2

4 9
3 1 6
7
8 2 5
-1
-1
-1

 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e3+10;
int n,m,k;

struct node {
    int a,i;
};

vector<node> g[N];

bool cmp(node &a1,node &a2) {
    if(a1.a==a2.a) return a1.i<a2.i;
    return a1.a>a2.a;
}

signed main() {
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        int x,a;
        cin>>x>>a;
        g[x].push_back({a,i});
    }
    for(int i=1;i<=m;i++)
        if(g[i].size()==0) cout<<-1<<"\n";
        else {
            sort(g[i].begin(),g[i].end(),cmp);
            for(auto x: g[i]) cout<<x.i<<" ";
            puts("");
        }
    return 0;
}

C.萌萌的玫瑰

Rosemoe 有 n 朵萌萌的玫瑰,她们排成了一列。每朵玫瑰都有一个美丽贡献度。第 i 朵玫瑰拥有 ai​ 的美丽贡献度。由于 Rosemoe 照顾不周,可能有些玫瑰枯萎了,她的美丽贡献度不是正数,而是零或负数。

Rosemoe 将几朵玫瑰的美丽值定义为这几朵玫瑰的美丽贡献度相或。形式化地来说,如果有 k 朵玫瑰,其中第 i 朵的美丽贡献度为 bib_ibi​ , 那么这几朵玫瑰的美丽值为 b1∨b2∨⋯∨bk−1∨bk(其中 ∨ 表示按位或)。注意:本题中进行或运算时,均以C/C++中的64位有符号整数(long long)的或运算实现。负数的符号位总是 1 。特别地,我们认为 0 朵玫瑰的美丽值为 0 。

Rosemoe 突然有一个问题:如果她从这一列玫瑰中一个区间 [l,r] 中选取一些玫瑰(0 朵或更多),选出的这些玫瑰的美丽值的最大值是多少?

现在 Rosemoe 有 qqq 个询问,第 iii 个询问的区间为 [li​,ri​] ,对于每个询问,你需要求出上述问题的答案。各个询问是相互独立的。

输入描述

第一行一个整数 n(1≤n≤5×105),表示玫瑰的数量。

第二行 n 个整数,第 i 个整数表示第 i 朵玫瑰的美丽贡献度 ai​ 。

第三行一个整数 q(1≤q≤5×105),表示询问的数量。

接下来 q 行,第 i 行有两个整数,分别为 li,ri​ 。数据保证 1≤li,ri≤n 。

输出描述

输出 q 行,每行一个整数。第 i 行的整数表示第 i 个询问的答案。

示例1

输入1

10
1 1 -4 5 14 19 -19 8 1 0
5
1 10
1 4
2 8
3 3
6 10

输出1

31
5
31
0
27

说明

对于第二个询问,我们可以选择第 1,4 朵玫瑰,答案为 5 .

对于第四个询问,我们不从区间中选取玫瑰,答案为 0 .

对于第五个询问,我们可以选择第 6,8,9 朵玫瑰,答案为 27 .

思路

按位或的性质,是负数时,会一直都是负数,根据贪心思想,区间[l,r]中不选负数,选所有的正数,可以转化为在读入数据的时候将负数变成0,此时只需要求出[l,r]区间的按位或即可,这里我用了ST表的思想维护区间按位或。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int a[N];
int f[N][66];
int n,q;

void rmq_init()  //建立O(nlogn)
{
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];
    int k = floor(log((double)n) / log(2.0));  // C/C++取整函数ceil()大,floor()小
    for (int j = 1; j <= k; j++)
        for (int i = n; i >= 1; i--) {
            if (i + (1 << (j - 1)) <=
                n)  // f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)
                f[i][j] = (f[i][j - 1]|f[i + (1 << (j - 1))][j - 1]);
        }
}

int rmq(int i, int j)  //查询
{
    int k = floor(log((double)(j - i + 1)) / log(2.0));
    return (f[i][k]|f[j - (1 << k) + 1][k]);
}

signed main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
		cin>>a[i];
		if(a[i]<0) a[i]=0;
	}
    rmq_init();
	cin>>q;
	while(q--) {
		int l,r;
		cin>>l>>r;
		cout<<rmq(l,r)<<endl;
	}
	return 0;
}

D.计算平均学分绩点

题目描述

据武汉理工大学学生手册第五章第十六条所述,学生学习的努力程度,采用学年总学分数作为评价指标;学生学习的质量水平,采用平均学分绩点(GPA)作为评价指标。 

平均学分绩点的计算方式如下:

平均学分绩点=∑课程学分绩点×课程学分总学分​。

也就是,将所有课程获得的学分绩点,与该课程的学分数相乘,求得的总和除以所有课程的总学分数得到的结果,即为学生的平均学分绩点(GPA)。简要地,平均学分绩点等于所有课程的学分绩点,关于课程学分的加权平均数。

现有一名学生,已知其共修读了 nnn 门课程,其中第 iii 门课程的学分数为 aia_iai​,该生在此课程中获得的学分绩点为 bi​。请你设计一个程序,计算该生的平均学分绩点。

为避免由于浮点误差导致的答案错误,只要你输出的答案和标准答案的绝对或相对误差低于 10−410^{-4}10−4,即被认为是正确的。形式化地,如果你的答案是 x,而标准答案是 y,如果满足 ∣x−y∣max⁡(1,y)≤10−4,你的答案就会被判为正确。否则,你的答案将被判为错误。

输入描述

第一行一个整数 nnn (1≤n≤100),表示该学生所修读的课程总数。

接下来 n 行,每行输入两个由空格隔开的实数 ai

​,bi​,分别表示一门课程的学分数和该生所获得的学分绩点。
 

输出描述

输出一行一个实数,表示该生的平均学分绩点。

示例1

输入1

3
5.50 4.46
1.00 3.23
2.50 3.49

输出1

4.0538888889

示例2

输入2

4
2.50 5.00
1.00 5.00
3.50 5.00
11.00 1.00

输出2

2.5555555556

备注

只要你输出的答案满足题目要求的精度限制即为正确答案,但是建议在输出的答案中至少保留 666 位小数。

假设你所计算的的答案为浮点型变量 GPA,在 C 语言中可以使用如下代码输出 GPA 保留 666 位小数的结果:

printf("%.6f",GPA);

在 C++ 中可以使用如下代码输出 GPA 保留 666 位小数的结果:

std::cout << std::fixed << std::setprecision(6) << GPA << std::endl;

在 python 中可以使用如下代码输出 GPA 保留 666 位小数的结果:

print("{:.6f}".format(GPA))

在 Java 中可以使用如下代码输出 GPA 保留 666 位小数的结果:

System.out.println(String.format("%.6f",GPA));

 代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n;
double a[N],b[N];
double a1,a2;
signed main() {
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>a[i]>>b[i];
		a1+=a[i];
		a2+=a[i]*b[i];
	}
	double ans=a2/a1;
	printf("%.10lf",ans);
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/136879.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

二分图判定和二分图最大匹配

1.二分图的定义 二分图是一种特殊的无向图&#xff0c;它的节点可以被划分为两个互不相交的集合&#xff0c;使得同一集合中的任意两个节点之间没有边相连&#xff0c;而不同集合中的节点之间都有边相连。 换句话说&#xff0c;如果一个无向图可以被划分为两个集合&#xff0…

Keil文本对齐

摘要&#xff1a;通常我们写代码的时候&#xff0c;尤其是缩进和{}的使用&#xff0c;很多都需要自己手动去调整&#xff0c;如果有一个自动格式化代码的工具&#xff0c;每次编辑完代码&#xff0c;然后一键给将代码格式化&#xff0c;即省时又美观。为了解决这个问题&#xf…

面向对象高级

本期对应知识库&#xff1a;&#xff08;持续更新中&#xff01;&#xff09; 面向对象高级 (yuque.com) ​​​​​​​尚硅谷_宋红康_对象内存解析.pptx static 适用于公用变量 开发中&#xff0c;变量 经常把一些常量设置为静态static 例如 PI 方法 经常把工具类中的方…

Deepsort项目详解

一、目标追踪整体代码 代码目录如下图所示&#xff1a; 、 追踪相关代码&#xff1a; 检测相关代码和权重 调用 检测 和 追踪的代码&#xff1a; 首先代码分为三个部分&#xff1a; 目标追踪的相关代码和权重目标检测相关代码和权重&#xff0c;这里用的是yolov5.5目标检…

Thinkphp8 - 连接多个数据库

// 数据库连接配置信息connections > [mysql > [// 数据库类型type > mysql,// 服务器地址hostname > 127.0.0.1,// 数据库名database > thinkphp,// 用户名username > env(DB_USER, root),// 密码password >…

layui 表格(table)合计 取整数

第一步 开启合计行 是否开启合计行区域 table.render({elem: #myTable, url: ../baidui/, page: true, cellMinWidth: 100,totalRow:true,cols: [[ //表头//{ type: checkbox },{ type: checkbox,totalRowText: "合计" },//合计行区域{ field: id, align: center,…

【0基础学Java第九课】-- 抽象类和接口

9. 抽象类和接口 9.1 抽象类9.1.1 抽象类概念9.1.2 抽象类语法9.1.3 抽象类的特性9.1.4 抽象类的作用 9.2 接口9.2.1 接口的概念9.2.2 语法规则9.2.3 接口使用9.2.4 接口特性9.2.5 实现多个接口9.2.6 接口的继承9.2.9 抽象类和接口的区别 9.3 Object类9.3.1 获取对象方法9.3.1 …

基于springboot实现驾校管理系统项目【项目源码】计算机毕业设计

基于springboot实现驾校管理系统演示 JAVA简介 JavaScript是一种网络脚本语言&#xff0c;广泛运用于web应用开发&#xff0c;可以用来添加网页的格式动态效果&#xff0c;该语言不用进行预编译就直接运行&#xff0c;可以直接嵌入HTML语言中&#xff0c;写成js语言&#xff0…

小H靶场学习笔记:DC-2

DC-2 Created: November 10, 2023 3:01 PM Tags: WordPress, git提权, rbash逃逸 Owner: 只会摸鱼 靶场过程 信息收集 扫描存活主机&#xff0c;找到靶机ip&#xff1a;192.168.199.131&#xff08;本机是192.168.199.129&#xff09; 扫描端口开放协议 发现有80端口和77…

电路设计之36V 自动断电和防浪涌电路

1. 电路图纸 2. 解释防浪涌功能怎么实现的 1. 首先当电源上电的一瞬间是 电容C1 是相当于短路的。 &#xff08;电容的充电状态。电容充电相当于短路状态&#xff09; 2. 当上电的一瞬间是有 浪涌的。 3.当上电的瞬间有浪涌的&#xff0c;此时电容C1 相当于短路&#xff0c;所…

Java学习_对象

对象在计算机中的执行原理 类和对象的一些注意事项 this关键字 构造器 构造器是一种特殊的方法 : 特殊之处在于&#xff0c;名字必须与所在类的名字一样&#xff0c;而且不能写返回值类型 封装 封装的设计规范&#xff1a;合理隐藏、合理暴露 实体类 成员变量和局部变量的区别 …

有源RS低通滤波

常用的滤波电路有无源滤波和有源滤波两大类。若滤波电路元件仅由无源元件&#xff08;电阻、电容、电感&#xff09;组成&#xff0c;则称为无源滤波电路。无源滤波的主要形式有电容滤波、电感滤波和复式滤波(包括倒L型、LC滤波、LCπ型滤波和RCπ型滤波等)。若滤波电路不仅有无…

【Redis】list列表

上一篇&#xff1a; String 类型 https://blog.csdn.net/m0_67930426/article/details/134362606?spm1001.2014.3001.5501 目录 Lpush LRange Rpush Lpop Rpop Lindex Ltrim Lset 列表不存在的情况 如果列表存在 Linsert ​编辑 在………之前插入 在……后面插入…

UE地形系统材质混合实现和Shader生成分析(UE5 5.2)

前言 随着电脑和手机硬件性能越来越高&#xff0c;游戏越来越追求大世界&#xff0c;而大世界非常核心的一环是地形系统&#xff0c;地形系统两大构成因素&#xff1a;高度和多材质混合&#xff0c;此篇文章介绍下UE4/UE5 地形的材质混合方案----基于WeightMap混合。 材质层 …

总结:利用JDK原生命令,制作可执行jar包与依赖jar包

总结&#xff1a;利用JDK原生命令&#xff0c;制作可执行jar包与依赖jar包 一什么是jar包&#xff1f;二制作jar包的工具&#xff1a;JDK原生自带的jar命令&#xff08;1&#xff09;jar命令注意事项&#xff1a;&#xff08;2&#xff09;jar包清单文件创建示例&#xff1a;&a…

Yolo自制detect训练

Install 把代码拉下来 GitHub - ultralytics/yolov5 at v5.0 然后 pip install -r requirements.txt 安装完了,运行一下detect.py即可 结果会保存在对应的目录下 Intro ├── data:主要是存放一些超参数的配置文件(这些文件(yaml文件)是用来配置训练集和测试集还有验…

【Redis】set 集合

上一篇&#xff1a;list 列表 https://blog.csdn.net/m0_67930426/article/details/134364315?spm1001.2014.3001.5501 目录 Sadd Smembers Sismember Scard Srem ​编辑Srandomember Spop Smove 集合类 Sdiff Sinter Sunion 官网 https://redis.io/commands/?…

01-Spring中的工厂模式

工厂模式 工厂模式的三种形态: 工厂模式是解决对象创建问题的属于创建型设计模式,Spring框架底层使用了大量的工厂模式 第一种&#xff1a;简单工厂模式是工厂方法模式的一种特殊实现,简单工厂模式又叫静态工厂方法模式不属于23种设计模式之一第二种&#xff1a;工厂方法模式…

记录一次某某虚拟机的逆向

导语 学了一段时间的XPosed&#xff0c;发现XPosed真的好强&#xff0c;只要技术强&#xff0c;什么操作都能实现... 这次主要记录一下我对这款应用的逆向思路 apk检查 使用MT管理器检查apk的加壳情况 发现是某数字的免费版本 直接使用frida-dexdump 脱下来后备用 应用分…

基于springboot实现桥牌计分管理系统项目【项目源码】

基于springboot实现桥牌计分管理系统演示 JAVA简介 JavaScript是一种网络脚本语言&#xff0c;广泛运用于web应用开发&#xff0c;可以用来添加网页的格式动态效果&#xff0c;该语言不用进行预编译就直接运行&#xff0c;可以直接嵌入HTML语言中&#xff0c;写成js语言&#…