2020牛客寒假算法基础训练营1
发布日期:2022-03-30 18:18:16 浏览次数:28 分类:博客文章

本文共 8934 字,大约阅读时间需要 29 分钟。

2020牛客寒假算法基础训练营1

A.honoka和格点三角形(计数)

题意:给定n*m个格点构造出的矩阵,问最多可以构造出多少个面积为1的三角形

题解:直接计数,讨论所有情况即可,注意乘法取模

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll mod = 1e9+7;int main(){ ll n,m; cin>>n>>m; ll s=(n-2)*(m-1)*4%mod+(n-1)*(m-2)*4%mod; s=(s+2*(n-1)*(m-2)%mod*(m-2)%mod+2*(m-1)*(n-2)%mod*(n-2)%mod)%mod; s=(s+2*(n-2)*(m-1)%mod*(m-2)%mod+2*(m-2)*(n-1)%mod*(n-2)%mod)%mod; cout<
<

B.kotori和bangdream(期望)

题意:每次有x%的概率获得a分,剩下的概率获得b分,一共进行n次,求得分期望

题解:结果是ans = (x%a+(1-(x%))b)*n

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ double n,x,a,b; cin>>n>>x>>a>>b; x/=100; double ans = n*(x*a+(1-x)*b); cout<
<

C.umi和弓道(双指针)

题意:给定一个起始坐标和一群坐标,这些坐标一定不在坐标轴上,现在需要在x轴或y轴设立一个挡板,这个挡板会遮蔽其他坐标和起始坐标的连线,要求遮蔽后最多只有k个点可以连通起始坐标,求这个挡板最短的长度

题解:分两种情况讨论,挡板在x轴上或在y轴上,将其他坐标与起始坐标的连线在x轴和y轴的交点分别记录下来,维护一个挡板长度的最小值,用双指针扫描

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ double x0,y0; int n,k; cin>>x0>>y0>>n>>k; k = n - k; vector
x,y; for(int i = 0; i < n; i++){ double x1,y1; cin>>x1>>y1; if(x1*x0<0){ y.push_back(y0-x0*(y1-y0)/(x1-x0)); } if(y1*y0<0){ x.push_back(x0-y0*(x1-x0)/(y1-y0)); } } sort(x.begin(),x.end()); sort(y.begin(),y.end()); double ans = 1e18; if(x.size()>=k){ int l = 0,r = k-1; while(r
=k){ int l = 0,r = k-1; while(r

D.hanayo和米饭(暴力)

题意:1,2,3...n这n个数会给你n-1个,让你把那个没给你的数输出

题解:直接暴力

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();bool vis[100005];int main(){ int n,x; cin>>n; for(int i = 0; i < n-1; i++) { cin>>x; vis[x] = true; } for(int i = 1; i <= n; i++) { if(!vis[i]){ cout<
<

E.rin和快速迭代(数论)

题意:给定一个数x,函数f(x)的值为x的因子个数,若当前的f(x)不为2,则继续进行f(f(x)),直到f(x)为2,求此时的计算次数

题解:本质上就是利用O(\(\sqrt{n}\))的积性函数\(\tau\)(n)暴力枚举出结果判断即可

\(\tau\)(n)函数表示的是正整数n的所有正因子个数,设n的质因子分解为n=\(p_1^{a_1}\)*\(p_2^{a_2}\)......\(p_s^{a_s}\),那么可以得出

\[\tau(n) = (a_1+1)*(a_2+1)*...*(a_s+1) = \prod_{j=1}^s(a_j+1)\]

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll count(ll n){ ll s = 1; for(ll i = 2;i*i<=n;i++){ if(n%i==0){ ll a = 0; do{ n/=i; a++; }while(n%i==0); s = s*(a+1); } } if(n>1)s*=2; return s;}int main(){ ll n; ll ans = 0; cin>>n; while(1){ ans++; if(count(n)==2)break; n = count(n); } cout<
<

F.maki和tree(并查集)

题意:给定一个n个点n-1条边的树,每个点为“W”白色或“B”黑色,问可以构成多少条两点之间只有一个黑色点的简单路径。、

题解:经过一个黑点的简单路径有两种,一种是路径两端都是白点,一种是有一端是黑点,我们统计每个白色连通块的权值,然后通过统计每个黑点相邻白点的权值和求出第二种的路径,对于第一种的路径,假设1个黑点有k个相邻白点,第一种路径就是从第1个白点开始,剩余的白点权值总和与当前白点的乘积,即

\(\sum_{i=1}^{k}\sum_{j=i+1}^kf(i)*f(j)\)

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 111111;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int f[N];ll knum[N];ll st[N];vector
g[N];ll n;string s;int find(int x){ if(f[x]==x)return x; else return find(f[x]);}void uni(int a,int b){ int p = find(a);int q = find(b); if(p!=q){ if(knum[p]>knum[q]){ f[q] = p; knum[p]+=knum[q]+1; }else { f[p] = q; knum[q]+=knum[p]+1; } }}ll get(vector
temp){ ll len = temp.size(); ll res = 0; if(len==0)return 0; vector
pre(len+10,0); pre[0] = temp.at(0); for(int i = 0; i < len; i++)//统计出以黑点为一端的种数 res+=temp[i]; for(int i = 1; i < len; i++)//前缀和维护每个点的权值合集 pre[i] += pre[i-1]+temp[i]; for(int i = 1; i < len; i++)//计算 res+=temp[i]*pre[i-1]; return res;}int main(){ cin>>n>>s; for(int i = 1;i <= n; i++)f[i] = i; for(int i = 1;i < n; i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); if(s[x-1]=='W'&&s[y-1]=='W')uni(x,y); } ll ans = 0; for(int i = 1; i <= n; i++)st[i] = knum[find(i)]+1; for(int i = 1; i <= n; i++) { if(s[i-1]=='B'){ vector
temp; for(int j = 0; j < g[i].size(); j++){ if(s[g[i][j]-1]=='W')temp.push_back(st[g[i][j]]); } ans+=get(temp); } } cout<
<

G.eli和字符串(字符串,双指针)

题意:给定一个字符串,要求截取一个最短的子串,这个子串至少包含k个相同的字符

题解:利用map存放每一个字符在字符串中的下标,当前字符数量满足k时调出区间长度维护最小值即可

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ int k,n; cin>>n>>k; map
> mp; string s; int ans = 2000000; cin>>s; for(int i = 0; i < s.size(); i++) { mp[s[i]].push_back(i); if(mp[s[i]].size()>=k){ int l = mp[s[i]][mp[s[i]].size()-k]; int len = i-l+1; ans = min(ans,len); } } if(ans==2000000) cout<<-1<

H.nozomi和字符串 (字符串,尺取法)

题意:给定一个01串,最多可以修改k次,仅限将0改为1,1改为0,问这个01串中最长连续子串是多长

题解:尺取维护k次修改区间

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();string s;int n,k;int deal(char x){ int L=0,R=0,change=0,ans=1; for (int i = 0; i < n; i++) { if(s[i]==x) { if(change
>n>>k>>s; cout<
<

I.nico和niconiconi(线性DP)

题意:给定长度为n的字符串,子串nico权值为a,子串niconi权值为b,子串niconiconi权值为c,求这个字符串的最大权值,子串不可重复使用

题解:dp即可,计dp[i]表示前i个字符的最大权值,那么有转移方程

if(substring(i-3,i))==nico,dp[i] = max(dp[i-4]+a.dp[i])

if(substring(i-5,i))==nico,dp[i] = max(dp[i-6]+b.dp[i])

if(substring(i-9,i))==nico,dp[i] = max(dp[i-10]+c.dp[i])

最后输出dp[n]即可

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ vector
dp(300005,0); int n,a,b,c; string s; cin>>n>>a>>b>>c; cin>>s; for(int i = 0; i < s.size(); i++){ if(i>0) dp[i] = dp[i-1]; if(i>=3&&s.substr(i-3,4)=="nico"){ dp[i] = max(dp[i-3]+a,dp[i]); } if(i>=5&&s.substr(i-5,6)=="niconi"){ dp[i] = max(dp[i-5]+b,dp[i]); } if(i>=9&&s.substr(i-9,10)=="niconiconi"){ dp[i] = max(dp[i-9]+c,dp[i]); } } cout<
<

J.u's的影响力(矩阵快速幂,费马小定理)

题意:给定n,x,y,a,b,设f(1) = x,f(2) = y,之后为f(i) = f(i-1) * f(i-2) *\(a^b\),让你求f(n)的值,结果%1e9+7。

题解:通过观察你会发现表达式由x,y,a三个因子组成,且x和y的幂数都构成斐波那契数列,而a的幂数则是斐波纳契数列的变种,这时候很容易就想到利用矩阵快速幂去解决这个问题。利用费马小定理进行降幂处理,因为%的1e9+7是一个质数,所以对于不等于1e9+7的数字a来说,\(a^{1e9+6} \equiv (1 mod 1e9+7)\),这样可以对x,y,a的系数进行降幂,而它们的系数则有矩阵快速幂递推公式求出。复杂度为O(logn)

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();const int MOD = 1e9+7;struct Mx{ ll mx[2][2]; void init(){ for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ mx[i][j] = (i==j?1:0); } } } void clear(){ for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ mx[i][j] = 0; } } }};Mx Mxmulti(Mx a, Mx b,int mod){ Mx res; res.clear(); for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ for(int k = 0; k < 2; k++){ res.mx[i][j]+=a.mx[i][k]*b.mx[k][j]%mod; res.mx[i][j]%=mod; } } } return res;}Mx Mxpow(Mx a,ll b,int mod){ Mx ans;ans.init(); while(b > 0){ if(b&1) ans = Mxmulti(ans,a,mod); b>>=1; a = Mxmulti(a,a,mod); } return ans;}ll quick_mod(ll a, ll b, ll mod){ if(b==0)return 1; ll ans = 1; a%=mod; while(b>0) { if(b&1) ans = (ans*a)%mod; b>>=1; a = (a*a)%mod; } return ans%mod;}int main(){ ll n,a,b,x,y; cin>>n>>x>>y>>a>>b; if(n==1){ cout<
<

转载地址:https://www.cnblogs.com/cloudplankroader/p/12266996.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:codeforces-1295D(欧拉函数)
下一篇:2020牛客寒假算法基础训练营2

发表评论

最新留言

很好
[***.229.124.182]2024年03月10日 12时57分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

html页面角落放动漫人物,L2Dwidget.js L2D网页动画人物添加 2019-04-21
html图片水平居中,CSS制作图片水平垂直居中 2019-04-21
水滴pin安卓版apk_财务报销管理系统 2019-04-21
平面设计师okr_设计团队的KPI/OKR如何制定? 2019-04-21
仪表盘故障图像识别_仪表显示的图像识别算法研究 2019-04-21
c#背单词小程序视频_C#用timer实现背单词小程序 2019-04-21
24v开关电源维修技巧_【电视技术】液晶电视电源板十个维修经验分享 2019-04-21
laravel comment显示到页面最上面了_使用 Laravel 快速开发API接口,新手必读 2019-04-21
echart实现3d地图_orbslam_2生成稀疏点云地图的保存与加载的实现 邹鹏程 2019.9.15... 2019-04-21
bash 不是内部或外部命令_python学习笔记6-pip命令不是内部命令问题 2019-04-21
管道的另一端上无任何进程。_别被忽悠入坑!信号贴贴上就能信号满格?对手机信号无任何改善... 2019-04-21
mysql无法写数据库_求助,为何我的数据不能写入数据库 2019-04-21
ssh 两个mysql数据库_ssh连接两个数据库(转) 2019-04-21
mysql 双向链表_23张图!万字详解「链表」,从小白到大佬! 2019-04-21
mysql 常量命名规则_详解Java编程规约(命名风格、常量定义、代码格式) 2019-04-21
pomelo mysql_全文索引 - Pomelo.EFCore.MySql 2019-04-21
如何打开git命令窗口_win10系统如何将右键菜单中“在此处打开powershell窗口”调整为“在此处打开命令窗口”?... 2019-04-21
rtsp 华为_华为多实例生成树RSTP配置详解 2019-04-21
ewb交通灯报告和文件_基于ewb平台的交通灯电路设计.doc 2019-04-21
mysql中$使用_在MySQL中使用序列的简单教程 2019-04-21