第1题 —— 求余 （5分）
- 直接输出2021%20
- 答案：1
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<2021%20;
return 0;
}
第2题 —— 双阶乘 （5分）
- 求2021的双阶乘，即把1到2021的奇数乘起来，2021!! = 2021 × 2019 × · · · × 5 × 3 × 1。
- 对于取后5位的操作，以及防止爆LL，可以直接mod1e5
- 答案：59375
#include<bits/stdc++.h>
using namespace std;
int main(){
int res = 1;
for(int i = 1; i <= 2021; i+=2){
res = res*i%100000;
}
cout<<res<<"\n";
return 0;
}
第3题 —— 格点 （10分）
- 求第一象限的格点中，有多少点两维坐标乘积不超过 2021
- 直接暴力x,y从1到2021乘起来即可
- 答案：15698
#include<bits/stdc++.h>
using namespace std;
int main(){
int res = 0;
for(int x = 1; x <= 2021; x++){
for(int y = 1; y <= 2021; y++){
if(x*y<=2021){
res++;
}
}
}
cout<<res<<"\n";
return 0;
}
第4题 —— 整数分解 （10分）
- 将 2021 分解成五个正整数的和，
- 注意到顺序不同算不同的方法，所以可以先暴力前三个数和为某值的方案存下来，再暴力后两个数为某值的方案，统计答案。
- 答案：691677274345
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e5+10;
int f[maxn];
int main(){
LL res = 0;
for(int i = 1; i < 2021; i++){
for(int j = 1; j < 2021; j++){
if(i+j>2021)break;
for(int k = 1; k < 2021; k++){
if(i+j+k>2021)break;
f[i+j+k]++;
}
}
}
for(int i = 1; i < 2021; i++){
for(int j = 1; j < 2021; j++){
if(i+j>2021)break;
res += f[2021-(i+j)];//出现2021-(i+j)的次数++
}
}
cout<<res;
return 0;
}
第5题 —— 城邦 （15分）
- 2021个点，任意两点间有边，边权两点不同的数位上的数字之和，求最小生成树
- 跑Kruskal板子即可
- 答案：4046
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2050*2050;
int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct node{int u, v, w; }e[maxn];
bool cmp(node x, node y){return x.w<y.w; }
int get(int x, int y){
int res = 0;
while(x || y){
int a = x%10, b = y%10;
if(a!=b)res += a+b;
x /= 10, y /= 10;
}
return res;
}
int main(){
int n = 2021, m = 0;
for(int i = 1; i <= 2021; i++){
for(int j = 1; j <= 2021; j++){
e[m++] = {i,j,get(i,j)};
}
}
sort(e,e+m,cmp);
int res = 0;
init(n);
for(int i = 0; i < m; i++){
int x = e[i].u, y = e[i].v;
if(find(x)!=find(y)){
fa[find(x)] = find(y);
res += e[i].w;
}
}
cout<<res<<"\n";
return 0;
}
第6题 —— 特殊年份 （15分）
- 判断输入年份是否满足千位和十位相等，个位比百位大 1，直接输出。
#include<bits/stdc++.h>
using namespace std;
int main(){
int res = 0;
for(int i = 1; i <= 5; i++){
string s; cin>>s;
res += (s[0]==s[2] && s[3]-s[1]==1);
}
cout<<res;
return 0;
}
第7题 —— 小平方 （20分）
- 求 1 到 n−1 中，有多少个数平方后膜n的余数，小于n的一半。
- n只有1w，枚举即可。
- 题目没说怎么取整 所以就double。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
double bn = n/2.0; //没说怎么取整 所以就double
int res = 0;
for(int i = 1; i < n; i++){
if(i*i%n<bn)res++;
}
cout<<res<<"\n";
return 0;
}
第8题 —— 完全平方数 （20分）
- 给出数a，求最小的数b，使得ab为完全平方数。
- 从小到大枚举b，乘起来判断一下。 30%分
- 从小到大枚举i，如果能整除，就计算i*i/n作为答案。50%
- 考虑到完全平方数的性质，即最后ab的所有质因子肯定都是偶数个，所以直接对a质因数分解，奇数个的乘上，就是最后的答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
LL a; cin>>a;
LL b = 1;
for(LL i = 2; i<=a/i; i++){
int t = 0;
while(a%i==0){
a /= i;
t++;
}
if(t%2==1)b*=i;
}
if(a!=1)b*=a;
cout<<b;
return 0;
}
第9题 —— 负载均衡 （25分）
- 开个优先队列数组模拟即可，每个队列维持上一次剩余的体力的状态，并且只在下一个数据要进来时才去更新，即把已经算完的任务移除掉，并收回算力。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef pair<int,int> PII;
//第i台计算机a[i]的剩余算力， <结束时间, 所需算力>按时间升序排序
pair<int, priority_queue<PII, vector<PII>, greater<PII> > >p[maxn];
int main(){
int n, m; cin>>n>>m;
for(int i =1; i <= n; i++)cin>>p[i].first;
int a, b, c, d;
for(int i = 1; i <= m; i++){
cin>>a>>b>>c>>d;
auto &q = p[b].second;
while(q.size() && q.top().first<=a){
p[b].first+=q.top().second;
q.pop();
}
if(p[b].first >= d){
q.push({a+c,d});
p[b].first -= d;
cout<<p[b].first<<"\n";
}else{
cout<<"-1\n";
}
}
return 0;
}
第10题 —— 国际象棋 （25分）
- 和八皇后一样，直接回溯暴力答案该能拿到30%。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int mod = 1000000007;
int n, m, k;
int dd[8][2] ={{1,2}, {1,-2}, {-1,2}, {-1,-2}, {2,1}, {2,-1}, {-2,1} ,{-2,-1} };
int vis[20][200]; //表示能不能走
int res = 0;
void dfs(int x, int y, int num){
if(x==n&&y==0)return ;
dfs(x+(y+1)/m, (y+1)%m, num);
if(vis[x][y]==0){ //可以放
if(num+1 == k){
res = (res+1)%mod;
return ;
}
vector<PII>pa;
vis[x][y] = 1; //放下去了
for(int i = 0; i < 8; i++){
int nx = x+dd[i][0], ny = y+dd[i][1];
if(nx<n&&nx>=0 && ny<m&&ny>=0 && vis[nx][ny]==0){
pa.push_back({nx,ny});
vis[nx][ny] = 1;
}
}
dfs(x+(y+1)/m, (y+1)%m, num+1);
vis[x][y] = 0;//回溯
for(auto &a: pa){
vis[a.first][a.second] = 0;
}
}
}
int main(){
cin>>n>>m>>k;
dfs(0,0,0);
cout<<res<<'\n';
return 0;
}
——————————————————
附：本节补题官网未上传，因此代码只能过样例。