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;
}
