当前位置： 首页 > news >正文

2024实验班选拔考试（热身赛）

news 来源：原创 2024/9/19 21:53:10

比赛传送门

邀请码：2024wksyb

A. 简单的数列问题

签到，记得开long long。

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6+10,M=1e4+10;
LL f[100];
LL calc(int n)
{if(f[n]) return f[n];return f[n]=calc(n-1)+calc(n-2);
}
void Solve()
{f[1]=f[2]=1;int n;cin>>n;cout<<calc(n)<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

B. 第一次放学

计算每一个班级的人数，贪心的想尽量保留人数较多的，从小到大排序，从小的开始累计即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10,M=1e4+10;
int a[N];
void Solve()
{int n,m,k;cin>>n>>m>>k;rep(i,0,n){int x; cin>>x;++a[x];}sort(a+1,a+1+n);int s=0,mx=0;rep(i,1,n+1){if(s<k){s+=a[i];if(s>k) mx=max(mx,s-k);}else mx=max(mx,a[i]);}cout<<mx<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

C. 糖果传递

设每一个a_i得到上一个给的值x_{i-1}（a_1的为x_n），对下一个的贡献出x_i。注意所有x_i可正可负，负数代表反向给出。记b =\frac{\sum a_i}{n}，可以列出下式：

\left\{\begin{matrix} x_n+a_1-x_1=b \\ x_1+a_2-x_2=b \\ ... \\ x_{n-1}+a_n-x_n=b \end{matrix}\right.

题目转换为求出|x_1|+|x_2|+|x_3|+...+|x_n|的最小值，把x_i都用x_1来表示：

\left\{\begin{matrix} x_2=x_1+a_2-b \\ x_3=x_1+a_2+a_3-2*b \\ ... \\ x_{n-1}=x_1+a_2+a_3+...+a_{n-1}-(n-2)*b \\ x_n=x_1-a_1+b \end{matrix}\right.

问题就是确定x_1，使得数轴上x_1到 n 个点0,b-a_2,2*b-a_2+a_3,...,(n-2)*b+a_2+...+a_{n-1},a_1-b 距离和的最小值，选择其中位数即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6+10,M=1e4+10;
int a[N];
LL v[N];
void Solve()
{int n; cin>>n;LL s=0,t=0;rep(i,1,n+1) cin>>a[i],s+=a[i];if(n==1){cout<<0<<endl; return;}int b=s/n;rep(i,1,n+1){t+=a[i];if(i==1) v[i]=0;else if(i==n) v[i]=a[1]-b;else v[i]=1ll*(i-1)*b-t+a[1];}sort(v+1,v+1+n);LL ans=0;rep(i,1,n+1) ans+=abs(v[n/2]-v[i]);cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

D. 矩阵计数

直接计算不好算，考虑用总数\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{x=1}^{i} \sum_{y=1}^{j} 1=\sum_{i=1}^{n} \sum_{j=1}^{m} i \cdot j= \sum_{i=1}^{n} i \cdot \sum_{j=1}^{m} j=\frac{n(n+1)}{2} \cdot \frac{m(m+1)}{2}

减去不合法数量。

先把所有的点按横坐标小到大排序（相等按纵坐标），于是可以把不和法的情况划分为：枚举 i ，包含以 i 点开头的所有子矩阵个数。这样的算法很方面，只需要保证 i 点与前面节点不包含即可，向前枚举，一段一段的算，卡一下纵坐标的上下界就可以了。

如下图所示，计算以 c 点开头的所有子矩阵个数，保证不包含前面节点，可以分为三段，第一段矩阵左上角选择范围是列值在bc段（不含b），行值比 c 小，右下角为 c 的左下方，如图红色矩阵所示；第二段ab段（不含a）加上了 b 点的限制，右下角列值必须小于 b ，如图中绿色矩阵所示；第三段0a段（不含0），加上 a 点限制，左上角的列值要在ac之间（不含a），如蓝色矩阵所示。通过不断更新左上角和右下角限制，可以设计出一个O(C^2)的算法。

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1e5+10,M=2e5+10;
pii a[N];
int sfmod(int x,int m=MOD)
{return (x%m+m)%m; 
}
void Solve()
{int n,m,k;cin>>n>>m>>k;rep(i,1,k+1) cin>>a[i].fi>>a[i].se;sort(a+1,a+1+k);int ans=1ll*n*(n+1)/2%MOD*(1ll*m*(m+1)/2%MOD)%MOD;rep(i,1,k+1){int l=1,r=m;int res=0;per(j,i-1,-1){int x=1ll*(a[j+1].fi-a[j].fi)*(a[i].se-l+1)%MOD;int y=1ll*(n-a[i].fi+1)*(r-a[i].se+1)%MOD;res=(res+1ll*x*y%MOD)%MOD;if(a[j].se<=a[i].se) l=max(l,a[j].se+1);if(a[j].se>=a[i].se) r=min(r,a[j].se-1);}ans=sfmod(ans-res);}ans=sfmod(ans);cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

E. 解方程

注意到函数在x > 0 时是单增的，根据零点存在定理二分，稍微调整一下参数 mx 和 eps 即可通过。

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
using namespace std;
const int MOD=998244353;
const int N=1e7+10,M=1e4+10;
const db eps=1e-5;
db f(db x)
{return 2018*x*x*x*x+21*x+5*x*x*x+5*x*x+14;
}
void Solve()
{db y,l=0,r=100,mx=10000;cin>>y;rep(i,0,mx){db mid=(l+r)/2;if(f(mid)>y) r=mid;else l=mid;}if(abs(f(l)-y)<eps) cout<<fixed<<setprecision(4)<<l<<endl;else cout<<-1<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--){Solve(); }return 0;
}

F. 随机数

根据二项式定理：

(a+b)^n=\sum_{i=0}^{n} \binom{n}{i} a^ib^{n-i}

现在要计算 a 的指数为奇数的和，如果 n 是奇数，就可以构造 \frac{(a+b)^n+(a+(-b))^n}{2}，(a-b)^n的展开中偶数项的 (-b) 指数 n-i 为奇数，提出负号刚好可以与对应(a+b)^n展开项消掉。同理若 n 为偶数，构造\frac{(a+b)^n-(a+(-b))^n}{2}即可。

n 很大，但是本题满足模数与底数互素，可以用欧拉降幂提前对 n 做 \pmod {p-1}处理。而且 p-1 是偶数，取模后并不影响原先 n 的奇偶性。

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
using namespace std;
const int MOD=1e9+7;
const int N=1e7+10;
int qp(int a,int b,int m=MOD)
{int res=1;while(b){if(b&1) res=1ll*res*a%m;a=1ll*a*a%m;b>>=1;}return res%m;
}
int sfmod(int x,int m=MOD)
{return (x%m+m)%m;
}
void Solve()
{int a,n=0; string s;cin>>a>>s;for(auto i:s) n=(1ll*n*10+(int)(i-'0'))%(MOD-1);a=1ll*a*qp(10000,MOD-2)%MOD; int b=sfmod(1-a);int Sum=qp((a+b)%MOD,n),Sub=qp(sfmod(a-b),n),inv2=qp(2,MOD-2),ans=0;if(n&1){ans=1ll*(Sum+Sub)%MOD*inv2%MOD;}else{ans=1ll*sfmod(Sum-Sub)*inv2%MOD;}cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

G. 【模板】线性筛

复习一下线性筛怎么写，题目问的是第几个素数，数组大小要多开一点。

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10,M=1e7+10;
int pr[N],cnt;
bool st[M];
void INIT()
{int n=1e7;rep(i,2,n+1){if(!st[i]) pr[++cnt]=i;rep(j,1,cnt+1){if(pr[j]*i>n) break;st[i*pr[j]]=1;if(i%pr[j]==0) break;}}
}
void Solve()
{int n;cin>>n;cout<<pr[n]<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;INIT();cin>>_;while(_--){Solve(); }return 0;
}

 H. 加解密

如果 S 出现在 a/b 的小数部分中，计算 S*b 和 (S+1)*b 取进位的值可以算出 S 前面的数为，这样可以得到一个范围 [l,r]。计算a*10^i \% b，如果某一个值在范围内则可以认为 S 出现在了 i+1。

对于 i 比较大的情况，直接枚举会超时。此时可以采用类似于哈希碰撞爆破的思路，a 先计算到 N 的偏移，即 a=a*10^N \% b，计算一个新的范围 [l,r]，设置一个宽度 H，向后计算 M 次，将 (a*10^{H*i}\%b,N+H*i) 插入到哈希表中，考虑范围中的每一个值 x，如果x*10^i\%b (0 \le i < H)出现在了哈希表中即可。对于本题，取N=M=10^6,H=1000，即可通过。

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6;
LL a,b,c[N+10];
int l,r;
string s;
int gcd(int a,int b)
{while(b^=a^=b^=a%=b);return a;
}
void calc()
{int n=s.size();c[n]=0;rep(i,0,n) c[i]=s[n-i-1]-'0';rep(i,0,n) c[i]*=b;rep(i,0,n) c[i+1]+=c[i]/10,c[i]%=10;int m=n;while(c[m]/10){c[m+1]=c[m]/10; c[m]%=10;++m;}l=0;per(i,m,n-1) l=l*10+c[i];bool fl=0;rep(i,0,n) if(c[i]) fl=1;l+=fl;c[n]=0;rep(i,0,n) c[i]=s[n-i-1]-'0';c[0]+=1;rep(i,0,n) c[i]*=b;rep(i,0,n) c[i+1]+=c[i]/10,c[i]%=10;m=n;while(c[m]/10){c[m+1]=c[m]/10; c[m]%=10;++m;}r=0;per(i,m,n-1) r=r*10+c[i];
}
void Solve()
{cin>>a>>b>>s;int d=gcd(a,b); a/=d;b/=d;a%=b;calc();LL pos=a;rep(i,0,N){if(l<=pos&&pos<=r){cout<<i+1<<endl;return;}pos=pos*10%b;}rep(i,0,N){a*=10; a%=b;int d=gcd(a,b);a/=d; b/=d;}calc();unordered_map<int,int>mp;LL h=1; int H=1000;rep(i,0,H) h=h*10%b;rep(i,1,N){a=a*h%b;if(!mp.count(a)) mp[a]=N+H*i;}int ans=(1<<30);rep(i,l,r+1){LL j=i;rep(_,0,H){if(mp.count(j)) ans=min(ans,mp[j]-_+1);j=j*10%b;}}if(ans==(1<<30)) cout<<-1<<endl;else cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

I. Treepath

以点 1 为根，求出所有点到 1 的距离，记为 d[i] 。i , j 两个点的距离就是 d[i]+d[j] ，只有同奇偶时和才为偶数，分别统计出奇数距离个数 v1 和偶数距离个数 v0，答案就是\binom{v0}{2}+\binom{v1}{2}。

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define pll pair<LL,LL>
#define MEM(a,x) memset(a,x,sizeof(a))
#define OJBK {cout<<"ok"<<endl;return;}
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10,M=2e5+10;
int d[N];
int h[N],ne[M],e[M],idx;
int v0,v1;
void add(int a,int b)
{e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
void dfs(int u,int fa)
{if(d[u]&1) ++v1;else ++v0;for(int i=h[u];i;i=ne[i]){int v=e[i];if(v==fa) continue;d[v]=d[u]+1;dfs(v,u);}
}
void Solve()
{int n;cin>>n;rep(i,0,n-1){int a,b;cin>>a>>b;add(a,b);add(b,a);}dfs(1,0);LL ans=1ll*v0*(v0-1)/2+1ll*v1*(v1-1)/2;cout<<ans<<endl;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){Solve(); }return 0;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Windows10上安装SQL Server 2022 Express
  • MySQL的安装数据库的简单操作
  • 力扣——11.盛最多水的容器
  • 基于STM32设计的盆栽种植自动管理系统(微信小程序)(201)
  • Milvus Cloud架构详解：构建高效、可扩展的向量数据库系统
  • 分布式时序数据库TimeLyre 9.2发布：原生多模态、高性能计算、极速时序回放分析
  • C++的STL简介（四）
  • React 常用 Hooks 和使用的易错点
  • gradio在windows上公网发布踩坑指南
  • PHP高校教材管理系统-计算机毕业设计源码29810
  • 大语言模型系列 - Transformer
  • 去中心化社交：探讨Facebook在区块链平台上的实践
  • 【Linux】【系统纪元】Linux起源与环境安装
  • SQL注入
  • Linux--shell脚本语言—/—终章
  • 【挥舞JS】JS实现继承，封装一个extends方法
  • CentOS7简单部署NFS
  • jquery cookie
  • MySQL Access denied for user 'root'@'localhost' 解决方法
  • node-sass 安装卡在 node scripts/install.js 解决办法
  • Terraform入门 - 1. 安装Terraform
  • ⭐ Unity 开发bug —— 打包后shader失效或者bug (我这里用Shader做两张图片的合并发现了问题)
  • 从零开始的无人驾驶 1
  • 对话 CTO〡听神策数据 CTO 曹犟描绘数据分析行业的无限可能
  • 复习Javascript专题（四）：js中的深浅拷贝
  • 面试总结JavaScript篇
  • 如何胜任知名企业的商业数据分析师？
  • 如何优雅地使用 Sublime Text
  • Salesforce和SAP Netweaver里数据库表的元数据设计
  • ​人工智能之父图灵诞辰纪念日，一起来看最受读者欢迎的AI技术好书
  • # Swust 12th acm 邀请赛# [ E ] 01 String [题解]
  • # 数据结构
  • #mysql 8.0 踩坑日记
  • (zt)基于Facebook和Flash平台的应用架构解析
  • （二刷）代码随想录第16天|104.二叉树的最大深度 559.n叉树的最大深度● 111.二叉树的最小深度● 222.完全二叉树的节点个数
  • （附源码）ssm跨平台教学系统 毕业设计 280843
  • （南京观海微电子）——I3C协议介绍
  • （算法）前K大的和
  • (算法)区间调度问题
  • （淘宝无限适配）手机端rem布局详解（转载非原创）
  • （提供数据集下载）基于大语言模型LangChain与ChatGLM3-6B本地知识库调优：数据集优化、参数调整、Prompt提示词优化实战
  • （一）Kafka 安全之使用 SASL 进行身份验证 —— JAAS 配置、SASL 配置
  • (一)Neo4j下载安装以及初次使用
  • (源码分析)springsecurity认证授权
  • (转) RFS+AutoItLibrary测试web对话框
  • （转）Sublime Text3配置Lua运行环境
  • (转)自己动手搭建Nginx+memcache+xdebug+php运行环境绿色版 For windows版
  • （转载）PyTorch代码规范最佳实践和样式指南
  • .chm格式文件如何阅读
  • .describe() python_Python-Win32com-Excel
  • .NET Core 发展历程和版本迭代
  • .net安装_还在用第三方安装.NET？Win10自带.NET3.5安装
  • .Net通用分页类(存储过程分页版,可以选择页码的显示样式,且有中英选择)
  • .one4-V-XXXXXXXX勒索病毒数据怎么处理|数据解密恢复
  • [Assignment] C++1