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