当前位置：网站首页>7/28-7/29 期望+思维+后缀数组+ST表
7/28-7/29 期望+思维+后缀数组+ST表
2022-07-31 06:41:00 【钟钟终】
期望的概念：
E(X+Y)=E(X)+E(Y) 因此可根据线性的可加性做题
在条件概率中，一个事件发生的概率固定
每日一题
Game (20上海ICPC热身赛)
类型：期望题，未与dp、数学结合
思路：
1.长度为n的序列中，存在多少互质的组合cnt
2.将n分成奇偶判断，若为奇数，则会产生（n-1）/2次消去，每次概率为cnt/C(n,2);
若为偶数，则会产生n/2次消去，每次概率为cnt/C(n,2)
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n;
int fac[N];
int fastpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int a) //求逆元
{
return fastpow(a,mod-2)%mod;
}
int C(int n,int m) //C(n,m)
{
return ((fac[n]*getinv(fac[m])%mod)*(getinv(fac[n-m])%mod))%mod;
}
signed main()
{
IOS;
cin>>n;
int cnt=0;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
if(__gcd(i,j)==1) cnt++;
}
if(n%2)
{
int g=__gcd(cnt,n);
cout<<cnt/g<<"/"<<n/g<<endl;
}
else
{
int g=__gcd(cnt,n-1);
cout<<cnt/g<<"/"<<(n-1)/g<<endl;
}
return 0;
}
Music Game 五一集训派对day2
类型：数学+期望的结合
思路：
1.处理出任意段事件发生的概率；在处理出不同长度m幂次方的值。
2.根据时间期望的可加性，枚举不同长度发生的期望值进行累加。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=5e3+5;
const int mod=1e9+7;
int n,m,p[N],mul[N],pre[N][N];
int fastpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int a) //求逆元
{
return fastpow(a,mod-2)%mod;
}
signed main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>p[i],mul[i]=fastpow(i,m);
int inv=getinv(100);
p[0]=p[n+1]=0;
for(int i=1;i<=n;i++) //不同区间段成功的概率
{
pre[i][i]=p[i]*inv%mod;
for(int j=i+1;j<=n;j++)
pre[i][j]=pre[i][j-1]*(p[j]*inv%mod)%mod;
}
int ans=0;
for(int i=0;i<=n;i++)
{
for(int j=i+2;j<=n+1;j++)
{
ans+=pre[i+1][j-1]*mul[j-i-1]%mod*(100-p[i])%mod*inv%mod*(100-p[j])%mod*inv%mod;
ans%=mod;
}
}
cout<<ans<<endl;
return 0;
}
后缀数组
P4051 [JSOI2007]字符加密
思路：将字符串扩大两倍，在进行后缀数组的排序。证明与题意处理方式等价：
1.abcab中ab在abcab前面，题意中ababc在abcab前面；若扩大两倍为abcababcab，则ababcab在abcababcab前面，后面多余并不影响
2.转为为了sa的裸题
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int n,k;
int rk[N],rk2[N]; //以i开头后缀的排名
char s[N];
int sa[N]; //表示sa[i]表示排名i的后缀的开头下标
//求解各个以i为起始下标的后缀字符串的排名
bool cmp(int i,int j)
{
if(rk[i]!=rk[j])
return rk[i]<rk[j];
int ri=(i+k<=n ? rk[i+k]:-1);
int rj=(j+k<=n ? rk[j+k]:-1);
return ri<rj;
}
void getsa(int n,char *str)
{
for(int i=1;i<=n;i++)
sa[i]=i,rk[i]=s[i]; //利用ASCLL码
for(k=1;k<=n;k*=2)
{
sort(sa+1,sa+1+n,cmp);
rk2[sa[1]]=1;
for(int i=2;i<=n;i++)
rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);
for(int i=1;i<=n;i++)
rk[i]=rk2[i];
}
}
int ht[N]; //维护数组rk相邻两个后缀的lcp(i-1和i的最长公共前缀)
void getht(int n,char *s)
{
for(int i=1;i<=n;i++)
rk[sa[i]]=i;
int h=0;
ht[1]=0;
for(int i=1;i<=n;i++)
{
int j=sa[rk[i]-1];
if(h>0)
h--;
for(;j+h<=n&&i+h<=n;h++)
if(s[j+h]!=s[i+h])
break;
ht[rk[i]]=h;
}
}
/* int top,ll[N],rr[N],sk[N],ans; int cal(int n,char *s) { getsa(n,s); getht(n,s); top=1,sk[1]=1; for(int i=2;i<=n;i++) { while(top&&ht[sk[top]]>ht[i]) rr[sk[top]]=i,top--; ll[i]=sk[top]; sk[++top]=i; } while(top) rr[sk[top]]=n+1,top--; int res=0; for(int i=2;i<=n;i++) res+=(i-ll[i])*(rr[i]-i)*ht[i]; return res; }*/
signed main()
{
cin>>(s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
s[i+n]=s[i];
n*=2;
getsa(n,s);
for(int i=1;i<=n;i++)
if(sa[i]<=n/2)
cout<<s[sa[i]+n/2-1];
cout<<endl;
return 0;
}
思维
A. Color the Picture
思路：
1.要保证一个颜色至少三个相邻和它有相同的颜色，则保证该颜色至少能涂两列
2.若m为技术的情况，则需找到至少一种颜色能涂三列
3.n和m的数值调换的情况也要考虑到
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n,m,k,a[N];
int f,f1,ans;
void check(int n,int m)
{
ans=0;
for(int i=1;i<=k;i++)
{
if(a[i]/n>=2)
{
if(a[i]/n>=3)
f1=1;
ans+=a[i]/n;
}
}
if(m%2)
{
if(ans>=m&&f1)
f=1;
}
else
if(ans>=m)
f=1;
}
signed main()
{
IOS;
int t;cin>>t;
while(t--)
{
f=f1=0;
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
cin>>a[i];
check(n,m);
swap(n,m);
check(n,m);
if(f)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
ST表
1.基于倍增思想，可做到O(n*logn)的预处理，O(1)的查询
2.解决指定运算的区间询问
模板：
//ST表
int lg[N]; //记录log2N的整数值
int st[N][30]; //以i为左端点长度为2的j次方的序列所求最值
void ST(int n)
{
lg[1]=0;
for(int i=2;i<=n;i++)
lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
for(int i=1;i<=n;i++)
st[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
int sch(int l,int r)
{
if(l>r)
return 0;
int k=lg[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
D. Rorororobot
题意：n行m列的网格中，每列下方中a[i]个格子被阻塞，可以往上下左右四个方向移动，不可出边界或碰到阻塞格子，不计次数，能否正好移动到重点。
思路：
1.先判断起点和终点间的行可否移动到同一行，每次移动需走k步
2.同理，列格子可否移动到同一列
3.每一列阻塞格子的最大值不可超过最终到达的起点值
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define y1 y11
using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n,m,a[N];
int x1,y1,x2,y2,k;
//ST表
int lg[N]; //记录log2N的整数值
int st[N][30]; //以i为左端点长度为2的j次方的序列所求最值
void ST(int n)
{
lg[1]=0;
for(int i=2;i<=n;i++)
lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
for(int i=1;i<=n;i++)
st[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
int sch(int l,int r)
{
if(l>r)
return 0;
int k=lg[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
signed main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i];
ST(m);
int q;cin>>q;
while(q--)
{
cin>>x1>>y1>>x2>>y2>>k;
x1+=(n-x1)/k*k;
x2+=(n-x2)/k*k;
if(y1>y2) swap(y1,y2);
if(x1==x2&&abs(y2-y1)%k==0&&sch(y1,y2)<x1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
P3865 【模板】ST 表
ST表静态查询，ST表知识优化查询的工具，一般不会单独考，会结合LCA等算法考察
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define y1 y11
using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n,m,a[N];
//ST表
int lg[N]; //记录log2N的整数值
int st[N][30]; //以i为左端点长度为2的j次方的序列所求最值
void ST(int n)
{
lg[1]=0;
for(int i=2;i<=n;i++)
lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
for(int i=1;i<=n;i++)
st[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
int sch(int l,int r)
{
if(l>r)
return 0;
int k=lg[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
signed main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
ST(n);
while(m--)
{
int l,r;cin>>l>>r;
cout<<sch(l,r)<<endl;
}
return 0;
}
边栏推荐
- [Interview: Concurrency 38: Multithreading: Thread Pool] Basic concepts of the ThreadPoolExecutor class
- 【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习
- 文件 - 02 上传文件：上传临时文件到服务器
- 2022.07.14_Daily Question
- SQLite数据库连接字符串
- 【科普向】5G核心网架构和关键技术
- 科普 | “大姨太”ETH 和 “小姨太”ETC的爱恨情仇
- The Ballad of Lushan Sends Lu's Servant to the Void Boat
- Yu Mr Series 】 【 2022 July 022 - Go Go teaching course of container in the dictionary
- 波士顿房价数据集 Boston house prices dataset
猜你喜欢
随机推荐
【微服务】 微服务学习笔记二：Eureka注册中心的介绍及搭建
Automatic translation software - batch batch automatic translation software recommendation
电脑开机密码怎么设置？如何给你的电脑加上“安全锁”
XSS靶场prompt.ml过关详解
Chapter 9 Exceptions try...except...else...finally
Chapter 17: go back to find the entrance to the specified traverse, "ma bu" or horse stance just look greedy, no back to search traversal, "ma bu" or horse stance just look recursive search NXM board
Core Tower Electronics won the championship in the Wuhu Division of the 11th China Innovation and Entrepreneurship Competition
Environment_Variable_and_SetUID
2022.07.22 _ a day
多进程全局变量失效、变量共享问题
uniapp 高度不自适应
《opencv学习笔记》-- 仿射变换
The Ballad of Lushan Sends Lu's Servant to the Void Boat
HighTec 的安装与配置
2022.07.20_每日一题
熟悉而陌生的新朋友——IAsyncDisposable
2022.07.13_Daily Question
【Go】Go 语言切片(Slice)
《白帽子说Web安全》思维导图
2022.07.18 _ a day