今天瞥到了这个比赛，索性做一下去年的题吧hh~
[传智杯 #4 初赛] 组原成绩
题目描述
花栗鼠科技大学（Hualishu University of Science and Technology, HUST）的计算机组成原理快要出分了。你现在需要计算你的组原成绩如何构成。
具体来说，组原成绩分为三部分，分别是平时出勤 \(t\) ，作业 \(h\) 和考试 \(e\) 。总成绩 \(w\) 由如下公式计算：
\[w=t \times 20\% +h \times 30\%+e \times 50\% \]其中我们保证 \(0 \leq h,e,t \leq 100\)
现在你知道了你的组原考试的 \(t,h,e\) ，你希望计算你的总成绩。
由于教务系统的特殊性，最终成绩只能是整数，采取 直接去掉小数部分 的办法。
输入格式
一行三个整数，表示 \(t,h,e\)
输出格式
一行一个整数，为 \(w\)
样例 #1
样例输入 #1
50 100 100
样例输出 #1
90
#include <bits/stdc++.h>
using namespace std;
int main()
{
double t,h,e;
cin>>t>>h>>e;
int ans = (int)(t*0.2+h*0.3+e*0.5);
cout<<ans<<endl;
return 0;
}
[传智杯 #4 初赛] 报告赋分
题目描述
花栗鼠科技大学的计算机组成原理实验最终的结课考核方式是提交一份报告。
然而作为任课老师，萝老师不希望大家过于内卷，所以指定了如下规定：
每份报告有一个卷面基础分 \(a\)。
在此基础上：
-
若是报告字数低于 \(16\) 页，则扣 \(10\) 分，如果分数低于 \(0\) 分了，则记作 \(0\) 分。
-
若是报告字数超过 \(20\) 页，每超过 \(1\) 页扣 \(1\) 分 ，直到分数扣到 \(0\) 分为止。
现在你知道了一份报告的卷面基础分 \(a\) 和它的页数 \(p\) ，请你计算这份报告的最终得分。我们保证 \(1 \leq a \leq 100,1 \leq p \leq 50\).
输入格式
本题有多组数据。
第一行一个整数 \(T(1 \leq T \leq 1000)\) ，表示数据组数。
接下来 \(T\) 行，每行两个整数 \(a,p\)，意义如题所示。
输出格式
共 \(T\) 行，每行一个整数，表示该次询问的数据最终的得分。
样例 #1
样例输入 #1
2
70 17
80 10
样例输出 #1
70
70
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while (T--)
{
int a,p;
cin>>a>>p;
int ans=a;
if (p<16) ans=max(0,a-10);
if (p>20)
{
int d = p-20;
ans = max(0,a-d);
}
cout<<ans<<endl;
}
return 0;
}
[传智杯 #4 初赛] 竞争得分
题目描述
为了鼓励大家写出更好的作业，花栗鼠科技大学（Hualishu University of Science and Technology, HUST）的组原实验采用了竞争得分的方式。
具体来说，假设有 \(n\) 个人提交了作业，并且其中原始得分最低的人记作 \(a_{min}\) ，原始得分最高的人记作 \(a_{max}\)，第 \(i\) 个人的原始得分为 \(a_i\)，那么第 \(i\) 个人的得分就是：
\[100 \times \frac{a_i-a_{min}}{a_{max}-a_{min}} \]由于成绩系统的问题，最终录入的成绩只能是整数，采用直接去掉小数部分的方法。
输入格式
第一行一个整数 \(n\) 表示人数。（\(1 \leq n \leq 1000\)）
第二行共\(n\) 个整数，为序列 \(a\) ，其中 \(a_i\) 表示第 \(i\) 个人的原始作业得分。（\(1 \leq a_i \leq 1000\)）
输出格式
一行，共 \(n\) 个整数，表示经过更新后每个人的得分。
样例 #1
样例输入 #1
3
1 2 3
样例输出 #1
0 50 100
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
int n;
cin>>n;
for (int i=0;i<n;i++) cin>>a[i];
double m_max=a[0],m_min=a[0];
for (int i=1;i<n;i++)
{
m_max = max(m_max,(double)a[i]);
m_min = min(m_min,(double)a[i]);
}
for (int i=0;i<n;i++)
{
a[i] = 100*((a[i]-m_min)/(m_max-m_min));
cout<<a[i]<<" ";
}
return 0;
}
[传智杯 #4 初赛] 萝卜数据库
题目描述
花栗鼠很喜欢偷吃生产队的大萝卜，因此花栗鼠科技大学正在研究一种新型的数据库，叫做萝卜数据库。
具体来说，它支持 \(k(1 \leq k \leq 100)\) 个字段，每个字段名都是整数，里面存储的数值也都是整数。
现在你支持如下操作：
-
向数据库中插入一个记录，它可能只会包含 \(k\) 个字段的某一部分。具体的操作格式详见“输入格式”。
-
在数据库中查询有多少条符合条件的记录。
现在你总共有 \(n\) 次操作（\(1 \;\leq n \leq 1000\)）,请你对每个回答操作，输出结果。
输入格式
第一行两个整数 \(n,k\) ，意义如题所述。
接下来的若干行，每行代表一次操作，具体如下：
-
\(1\ p\ x_1\ \ y_1,...,x_p\ y_p\) :表示一个插入操作，其中共有 \(p\) 个字段，第 \(i\) 字段的名字是 \(x_i\) ，值为 \(y_i\) .此处我们保证 \(1 \leq x_i \leq k, 1\leq y_i \leq 1000\)，并且 \(x_i,y_i\) 均为整数。
-
\(2\ x\ y_{min}\ y_{max}\)：表示一次查询操作，表示查询所有满足 字段 \(x\) 的值在 \([y_{min},y_{max}]\) 之间的记录有多少个。
输出格式
对于每个查询操作，输出一行一个整数，表示符合条件的记录个数。
样例 #1
样例输入 #1
4 5
1 2 1 2 2 4
2 2 1 5
1 2 3 5 4 6
2 4 7 8
样例输出 #1
1
0
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T,k;
vector<int>a[N];
int main()
{
scanf("%d%d",&T,&k);
int flag;
while (T--)
{
scanf("%d",&flag);
if (flag==1)
{
int p;
scanf("%d",&p);
while (p--)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
}
}
else
{
int x;
scanf("%d",&x);
int l,r;
scanf("%d%d",&l,&r);
int cnt = 0;
for (auto p:a[x])
{
if (p>=l&&p<=r)
{
cnt++;
}
}
printf("%d\n",cnt);
}
}
}
[传智杯 #4 初赛] 小卡与质数2
题目背景
小卡迷上了质数！
题目描述
小卡最近迷上了质数，所以他想把任何一个数都转化为质数！
小卡有 \(T\) 次询问，每次给你一个数字 \(x\)，问有多少个比 \(x\) 小的非负整数 \(y\)，使得 \(x\oplus y\) 是质数，其中 \(\oplus\) 表示按位异或。
输入格式
第一行一个正整数 \(T(1\le T\le10^5)\)，表示有 \(T\) 组询问。
接下来 \(T\) 行，每行一个正整数 \(x(1\le x\le 10^6)\)。
输出格式
对于每组询问，输出一行一个整数，表示答案。
样例 #1
样例输入 #1
9
5
6
7
8
9
10
100
1000
10000
样例输出 #1
2
4
4
2
2
4
22
163
1132
感觉这道题还是有难度的，是这里面最有价值的题。基本考查的是线性筛素数和位运算（异或）
具体代码逻辑思路：
- 使用线性筛法，以\(O(n)\)的时间复杂度得出2000010以内的素数。
注意，题目中输入的数x $ \leq \(10^6\) $ , 约为\(2^{20}=1,048,576\).最坏情况下，与1异或，则结果接近但小于\(2^{21}-1=2,097,152\)，可以近似看成2000010即可。 - 对于经过打表得出的primes数组处理：每一个质数，从高到低找到第一个1的位置并记录该位置作为最高位为1的质数的数量。
- 对于给定的x，从高到低找到其最高位为1的位置，并添加此位置为最高位1的质数的个数。
原因：只有1^0=1，此时质数的这个位置是其最高位为1的位置，且此位置也是x的最高位位置，那么此时x异或的数y的二进制表示下的此位置一定为0，也就满足了x>y的要求。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010<<1;
int primes[N],st[N],num[31];
int n,cnt;
typedef long long LL;
void get_prime()
{
for (int i=2;i<N;i++)
{
if (!st[i]) primes[++cnt] = i;
for (int j=1;1ll*i*primes[j]<=N;j++)
{
st[i*primes[j]] = true;
if (i%primes[j]==0) break;
}
}
}
int main()
{
get_prime();
for (int i=1;i<=cnt;i++)
{
int t = primes[i];
for (int j=31;j>=0;j--)
if (t>>j&1)
{
num[j]++;
break;
}
}
int T;
scanf("%d",&T);
while (T--)
{
LL ans = 0;
int x;
scanf("%d",&x);
for (int i=31;i>=0;i--)
if (x>>i&1) ans+=num[i];
printf("%lld\n",ans);
}
return 0;
}
总结
题目的难度确实不高，但还是有些许小坑的。而且最后一题的难度可以，需要仔细考虑位运算和素数筛算法。
总之，继续加油吧~