当前位置：网站首页>7/28-7/29 Expectation + thinking + suffix array + ST table
7/28-7/29 Expectation + thinking + suffix array + ST table
2022-07-31 07:59:00 【bell bell end】
期望的概念：
E(X+Y)=E(X)+E(Y) Therefore, the problem can be solved according to linear additivity
in the conditional probability,The probability of an event occurring is fixed
每日一题
Game (20上海ICPC热身赛)
类型：期望题,未与dp、Mathematical combination
思路：
1.长度为n的序列中,How many coprime combinations existcnt
2.将nDivided into parity judgment,若为奇数,则会产生（n-1）/2erasing,每次概率为cnt/C(n,2);
若为偶数,则会产生n/2erasing,每次概率为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 May Day training partyday2
类型：数学+desired combination
思路：
1.Process the probability of occurrence of any segment of events;Different lengths are being processedmThe value of the power.
2.Additivity according to time expectations,Enumerate the expected values that occur at different lengths and accumulate them.
#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++) //Probability of success for different interval segments
{
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]字符加密
思路：Double the string,Sorting the suffix array.The proof is equivalent to the problem-solving method：
1.abcab中ab在abcab前面,题意中ababc在abcab前面;If it is doubledabcababcab,则ababcab在abcababcab前面,The excess in the back doesn't matter
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.Make sure that a color is at least three adjacent and it has the same color,It is guaranteed that the color can be painted in at least two columns
2.若mfor the technical situation,You need to find at least one color to paint three columns
3.n和mThe value exchange of , should also be taken into account
#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.Solve the interval query for the specified operation
模板：
//ST表
int lg[N]; //记录log2N的整数值
int st[N][30]; //以i为左端点长度为2的jThe maximum value of the sequence of powers
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列的网格中,below each columna[i]grids are blocked,You can move up, down, left and right in four directions,Do not go out of bounds or hit blocking grids,不计次数,Can you just move to the point.
思路：
1.First determine whether the lines between the start and end points can be moved to the same line,Walk every time you movek步
2.同理,Whether the column grid can be moved to the same column
3.The maximum value of the blocking grid in each column cannot exceed the finally reached starting point value
#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的jThe maximum value of the sequence of powers
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 表
STTable static query,STTools for optimizing queries with table knowledge,Usually not taken alone,会结合LCAetc. Algorithm investigation
#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的jThe maximum value of the sequence of powers
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;
}
边栏推荐
猜你喜欢
【解决】mysql本地计算机上的MySQL服务启动后停止。某些服务在未由其他服务或程序使用时将自动停止
Leetcode952. Calculate maximum component size by common factor
![[Interview: Concurrency 38: Multithreading: Thread Pool] Basic concepts of the ThreadPoolExecutor class](/img/b2/c53b72a151b1277aee5aeb65c61cf7.png)
[Interview: Concurrency 38: Multithreading: Thread Pool] Basic concepts of the ThreadPoolExecutor class
我开发了一个利用 Bun 执行 .ts / .js 文件的 VS Code 插件
嵌入式系统驱动初级【2】——内核模块下_参数和依赖
2022.07.29_Daily Question
MySQL detailed explanation
正则表达式绕过
中软国际携手深开鸿发布（1+1) x N 战略，以数字化、智慧化改变人类生产和生活方式
Yu Mr Series 】 【 2022 July 022 - Go Go teaching course of container in the dictionary
随机推荐
第9章 异常try...except...else...finally
Environment_Variable_and_SetUID
2022.07.22 _ a day
【解决】npm ERR A complete log of this run can be found in npm ERR
Spark 在 Yarn 上运行 Spark 应用程序
【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习
van-uploader上传图片，使用base64回显无法预览的问题
初识NK-RTU980开发板
2022.07.18 _ a day
2022.07.15_每日一题
DAY18：Xss 靶场通关手册
把 VS Code 当游戏机
手把手教你开发微信小程序自定义底部导航栏
2022.07.13_Daily Question
MySql数据库优化查询工具
Super detailed mysql database installation guide
2022.07.15_每日一题
navicat 新建数据库
[Interview: Concurrency 38: Multithreading: Thread Pool] Basic concepts of the ThreadPoolExecutor class
Zabbix6.2惊喜发布！特别优化中大型环境部署的性能！