牛客网暑期ACM多校训练营(第九场
C Gambling
一开始感觉这个题似乎没什么逻辑,博主只是跟着题解AC了一遍。。等写博客的时候大概想了想概率与此时应加的钱的关系,才觉得有点道理。
我们要明白两件事情。
第一,一开始的概率为1/2。
第二,题解上写的概率的转换。也就是设当前胜率为p,那么如果下一场赢了,胜率会变成p+q,输了胜率会变成p-q。
总之只需要明白胜率会进行加加减减知道最后变成1或者0。所以这也就说明了为什么**的钱为什么为,因为胜率的变化只是线性变化,那么你的胜率从1/2到1与钱从0到 的变化量应该成正相关的,所以你只要算出前面一次函数前面的系数就ok了,那么显然前面的系数就为。
可能说的不是很清楚,大家可以自己理解理解。。
那么现在关注点就在如何求胜率啦,这个参考题解就行了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int mod=1000000007;
//***************************************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extgcd(long long a,long long b,long long &x,long long &y)
{
if(a==0&&b==0)return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
long long d=extgcd(b,a%b,y,x);
y-=a/b*x;
return d;//返回gcd(a,b)
}
//****************求逆元******************************
//ax=1(mod n)
long long mod_reverse(long long a,long long n)
{
long long x,y;
long long d=extgcd(a,n,x,y);
if(d==1)return (x%n+n)%n;
return -1;
}
long long tab1[maxn],tab2[maxn];
long long two[maxn];
void init()
{
two[0]=1;
for(int i=1;i<maxn;i++)
two[i]=two[i-1]*2%mod;
tab1[0]=1;
for(int i=1;i<maxn;i++)
tab1[i]=tab1[i-1]*i%mod;
tab2[maxn-1]=mod_reverse(tab1[maxn-1],mod);
for(int i=maxn-2;i>=0;i--)
tab2[i]=tab2[i+1]*(i+1)%mod;
}
long long C(int a,int b)
{
if(a<b)return 0;
return tab1[a]*tab2[b]%mod*tab2[a-b]%mod;
}
long long gett(int a)
{
return two[a];
}
int main()
{
init();
int n;
scanf("%d",&n);
int i=0,j=0;
//printf("%lld\n",gett(1)*C(2*n-2,n-1)%mod);
int tmp;
while(1)
{
printf("%lld\n",gett(1+i+j)*C(2*n-2-i-j,n-i-1)%mod);
scanf("%d",&tmp);
if(tmp==0)i++;
else j++;
if(i==n||j==n)break;
}
return 0;
}
F Typing practice
第一次见trie图,没做出来。。赛后补题觉得这个思路十分正确啊,也没有什么拐弯的地方,属于套路题,这里mark一下。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct Trie
{
int next[maxn][30],fail[maxn],End[maxn];
int root,L;
int newnode()
{
for(int i=0;i<26;i++)
next[L][i]=-1;
End[L++]=0;
return L-1;
}
void init()
{
L=0;
root=newnode();
}
void insert(char buf[],int idx)
{
int len=strlen(buf);
int now=root;
for(int i=0;i<len;i++)
{
if(next[now][buf[i]-'a']==-1)
next[now][buf[i]-'a']=newnode();
now=next[now][buf[i]-'a'];
}
End[now]=End[now]|(1<<idx);
}
void build()
{
queue<int>Q;
fail[root]=root;
for(int i=0;i<26;i++)
{
if(next[root][i]==-1)
next[root][i]=root;
else
{
fail[next[root][i]]=root;
Q.push(next[root][i]);
}
}
while(!Q.empty())
{
int now=Q.front();Q.pop();
End[now]|=End[fail[now]];
for(int i=0;i<26;i++)
{
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
void debug()
{
for(int i=0;i<L;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],End[i]);
for(int j=0;j<26;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
}
}ac;
char s[maxn];
int d[maxn];
vector<int>V[maxn];
stack<int>S;
void solve()
{
memset(d,-1,sizeof(d));
for(int i=0;i<ac.L;i++)
{
for(int j=0;j<26;j++)
if(ac.next[i][j]!=-1)
V[ac.next[i][j]].push_back(i);
}
queue<int>Q;
for(int i=0;i<ac.L;i++)
if(ac.End[i]!=0)
Q.push(i),d[i]=0;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int v:V[x])
{
if(d[v]==-1)
d[v]=d[x]+1,Q.push(v);
}
}
int now=ac.root;
printf("%d\n",d[now]);
S.push(now);
int len=strlen(s);
for(int i=0;i<len;i++)
{
if(s[i]=='-')
{
S.pop();
if(S.size())
{
now=S.top();
}
else S.push(0),now=0;
printf("%d\n",d[now]);
}
else
{
now=ac.next[now][s[i]-'a'];
printf("%d\n",d[now]);
S.push(now);
}
}
}
int main()
{
ac.init();
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",s);
ac.insert(s,i);
}
ac.build();
//ac.debug();
scanf("%s",s);
solve();
}
H Prefix Sum
首先呢,你需要推出第k行的每个数与第一项的关系(化繁为简)。也就是题解中的式子。
然后在按照题解一步步的推,似乎没什么逻辑上的问题啊。。
总之就是推推推。。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1000000007;
//***************************************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extgcd(long long a,long long b,long long &x,long long &y)
{
if(a==0&&b==0)return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
long long d=extgcd(b,a%b,y,x);
y-=a/b*x;
return d;//返回gcd(a,b)
}
//****************求逆元******************************
//ax=1(mod n)
long long mod_reverse(long long a,long long n)
{
long long x,y;
long long d=extgcd(a,n,x,y);
if(d==1)return (x%n+n)%n;
return -1;
}
long long tab1[maxn],tab2[maxn];
void init()
{
tab1[0]=1;
for(int i=1;i<maxn;i++)
tab1[i]=tab1[i-1]*i%mod;
tab2[maxn-1]=mod_reverse(tab1[maxn-1],mod);
for(int i=maxn-2;i>=0;i--)
tab2[i]=tab2[i+1]*(i+1)%mod;
}
long long C(int a,int b)
{
if(a<0)
{
if(b%2)return C(-a+b-1,b)*-1;
return C(-a+b-1,b);
}
else
{
if(a<b)return 0;
return tab1[a]*tab2[b]%mod*tab2[a-b]%mod;
}
}
long long sum[45][maxn];
#define lowbit(x) x&(-x)
void add(int x,long long val,long long sum[])
{
while(x<maxn)
{
sum[x]=(sum[x]+val)%mod;
x+=lowbit(x);
}
}
long long query(int x,long long sum[])
{
long long res=0;
while(x)
{
res=(res+sum[x])%mod;
x-=lowbit(x);
}
return res;
}
//
int n,m,k;
long long a[maxn];
void update(long long x,long long y)
{
for(int j=0;j<=k;j++)
{
long long tmp=(y*C(k-x,k-j)%mod+mod)%mod;
add(x,tmp,sum[j]);
}
}
void Query(long long x)
{
long long ans=0;
for(int j=0;j<=k;j++)
{
long long tmp=C(x,j);
long long tmp2=query(x,sum[j]);
ans=(ans+tmp*tmp2%mod)%mod;
}
printf("%lld\n",ans);
}
void solve()
{
int opt;
long long x,y;
while(m--)
{
scanf("%d",&opt);
if(opt==0)
{
scanf("%lld %lld",&x,&y);
update(x,y);
}
else
{
scanf("%lld",&x);
Query(x);
}
}
}
int main()
{
init();
scanf("%d %d %d",&n,&m,&k);
k--;
solve();
}
G Longest Common Subsequence
这题是整套题研究时间最长的题了,因为博主不知道怎么分治求四维偏序。所以特意去学了下cdq分治。
第一步你首先可以记录每个数组中的每个数所在的位置,然后依题解所说建立一个四维的点,找到一个最长上升子序列即可。
所以学会四维偏序后,因为这不是求点的偏序个数,而是求最长上升子序列,所以你分治的顺序和树状数组维护的东西需要改变。因为你要保证求左边对右边的影响时,左边必须已经被处理。所以分治的顺序应该把处理右边的放在合并后面。
而求最长上升子序列,那么树状数组只需要维护前缀最大值即可了。
详细见代码吧。
如果不清楚cdq分治的同学请戳此链接
#include<bits/stdc++.h>
using namespace std;
const int maxn=8e4+5;
struct Item
{
int d1,d2,d3,d4,part;
int idx;
Item(int tmp[])
{
d1=tmp[1];
d2=tmp[2];
d3=tmp[3];
d4=tmp[4];
}
Item() {}
} a[maxn];
int acnt;
const int LEFT=0;
const int RIGHT=1;
//
int arr[maxn];
inline int lowbit(int num)
{
return num&(-num);
}
void add(int idx,int val)
{
while(idx<maxn)
{
arr[idx]=max(arr[idx],val);
idx+=lowbit(idx);
}
}
int query(int idx)
{
int ans=0;
while(idx)
{
ans=max(ans,arr[idx]);
idx-=lowbit(idx);
}
return ans;
}
void clear(int idx)
{
while(idx<maxn)
{
if(arr[idx]==0)break;
arr[idx]=0;
idx+=lowbit(idx);
}
}
//
Item tmp3d[maxn];
Item tmp2d[maxn];
int dp[maxn];
bool cmpb(const Item &a,const Item &b)
{
return a.d2<b.d2;
}
bool cmpc(const Item &a,const Item &b)
{
return a.d3<b.d3;
}
bool cmpa(const Item &a,const Item &b)
{
return a.d1<b.d1;
}
Item tmp4[maxn];
void cdq3d(int L,int R)
{
if(R-L<=1)return;
int M=(L+R>>1);
cdq3d(L,M);
sort(tmp2d+L,tmp2d+M,cmpc);
for(int i=M;i<R;i++)
tmp4[i]=tmp2d[i];
sort(tmp2d+M,tmp2d+R,cmpc);
int p=L,q=M,o=L;
while(p<M&&q<R)
{
if(tmp2d[p].d3<tmp2d[q].d3)
{
if(tmp2d[p].part==LEFT)add(tmp2d[p].d4,dp[tmp2d[p].idx]);
tmp3d[o++]=tmp2d[p++];
}
else
{
if(tmp2d[q].part==RIGHT)dp[tmp2d[q].idx]=max(dp[tmp2d[q].idx],query(tmp2d[q].d4-1)+1);
tmp3d[o++]=tmp2d[q++];
}
}
while(p<M)tmp3d[o++]=tmp2d[p++];
while(q<R)
{
if(tmp2d[q].part==RIGHT)dp[tmp2d[q].idx]=max(dp[tmp2d[q].idx],query(tmp2d[q].d4-1)+1);
tmp3d[o++]=tmp2d[q++];
}
for(int i=L; i<R; i++)
{
if(tmp3d[i].part==LEFT)clear(tmp3d[i].d4);
//tmp2d[i]=tmp3d[i];
}
for(int i=M;i<R;i++)
tmp2d[i]=tmp4[i];
cdq3d(M,R);
}
Item tmp3[maxn];
void cdq2d(int L,int R)
{
if(R-L<=1)return;
int M=L+R>>1;
cdq2d(L,M);
sort(a+L,a+M,cmpb);
for(int i=M; i<R; i++)
tmp3[i]=a[i];
sort(a+M,a+R,cmpb);
int p=L,q=M,o=L;
while(p<M&&q<R)
{
if(a[p].d2<a[q].d2)
{
a[p].part=LEFT;
tmp2d[o++]=a[p++];
}
else
{
a[q].part=RIGHT;
tmp2d[o++]=a[q++];
}
}
while(p<M)
{
a[p].part=LEFT;
tmp2d[o++]=a[p++];
}
while(q<R)
{
a[q].part=RIGHT;
tmp2d[o++]=a[q++];
}
//for(int i=L;i<R;i++)a[i]=tmp2d[i];
cdq3d(L,R);
for(int i=M; i<R; i++)
a[i]=tmp3[i];
cdq2d(M,R);
}
vector<int>p[5][10005];
int tmp[5];
void dfs(int x,int d)
{
if(d==5)
{
a[acnt]=Item(tmp);
a[acnt].idx=acnt;
acnt++;
return;
}
for(int u:p[d][x])
{
tmp[d]=u;
dfs(x,d+1);
}
}
int main()
{
int n;
scanf("%d",&n);
int aa;
for(int i=1; i<=4; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&aa);
p[i][aa].push_back(j);
}
}
for(int i=1; i<=n; i++)
dfs(i,1);
for(int i=0; i<acnt; i++)
dp[i]=1;
sort(a,a+acnt,cmpa);
cdq2d(0,acnt);
int ans=0;
for(int i=0; i<acnt; i++)
ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}
上一篇: 腾讯2018笔试模拟题之判断正方形
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
牛客多校第九场 Groundhog and 2-Power Representation(大整数,java)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第一场)H-Minimum-cost Flow
-
2020牛客暑期多校 第一场 F Infinite String Comparision(字符串)
-
Harmony Pairs 2020牛客暑期多校训练营(第六场)