# 牛客白月赛28【题解】

https://ac.nowcoder.com/acm/contest/7412

# 牛牛和牛可乐的赌约【概率】

``````#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int mod=1e9+7;
//1-x;
LL qsm(LL a,LL b,LL p)
{
LL sum=1;
while(b)
{
if(b&1) sum=sum*a%p;
b>>=1;
a=a*a%p;
}
return sum%p;
}
int main(void)
{
int t; cin>>t;
while(t--)
{
LL n,m; scanf("%lld%lld",&n,&m);
LL sum=qsm(qsm(n,mod-2,mod),m,mod);
printf("%lldn",(1-sum+mod)%mod);
}
return 0;
}
``````

# 牛牛和牛可乐的赌约2【博弈论】

``````#include<bits/stdc++.h>
using namespace std;

int main(void)
{
int t; cin>>t;
while(t--)
{
int x,y; cin>>x>>y;
x=x%3,y=y%3;
if(x^y) puts("yyds");
else puts("awsl");
}
return 0;
}
``````

# 单词记忆方法【栈模拟】

``````#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
string s;
stack<LL>st;
int main()
{
cin>>s;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(') st.push(-1);
else if(s[i]==')')
{
LL j=i,sum=0;
while(j+1<s.size()&&(s[j+1]>='0'&&s[j+1]<='9'))
{
j++;
sum=sum*10+s[j]-'0';
}
sum=max(sum,1ll);
LL ans=0;
while(st.size())
{
if(st.top()==-1)
{
st.pop();
break;
}
ans+=st.top(); st.pop();
}
st.push(ans*sum);
i=j;
}else if(s[i]>='A'&&s[i]<='Z')
{
LL j=i,sum=0;
while(j+1<s.size()&&(s[j+1]>='0'&&s[j+1]<='9'))
{
j++;
sum=sum*10+s[j]-'0';
}
sum=max(sum,1ll);
st.push(sum*(s[i]-'A'+1));
i=j;
}
}
LL ans=0;
while(st.size()) ans+=st.top(),st.pop();
cout<<ans;
}
//((A2B2)2(A3B4)2)2
//68
``````

# 位运算之谜【思维】

``````#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(void)
{
//std::ios::sync_with_stdio(false);
//std::cin.tie(nullptr);
int t; cin>>t;
while(t--)
{
LL x,y; cin>>x>>y;
LL temp=y;
bool flag=1;
vector<int>s1,s2;
while(temp)
{
s1.push_back(temp%2);
temp/=2;
}
while(s1.size()<63) s1.push_back(0);
LL sum=x-y*2,ans=0;
if(sum<0) flag=0;
if(flag)
{
while(sum)
{
s2.push_back(sum%2);
sum/=2;
}
while(s2.size()<63) s2.push_back(0);
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
for(int i=0;i<s1.size();i++)
{
if(s1[i]==1&&s2[i]==1) flag=0;
if(s2[i]==1) ans=ans*2+1;
else ans=ans*2;
}
}
if(flag) cout<<ans<<'n';
else cout<<-1<<'n';
}
return 0;
}
``````

# 牛牛和字符串的日常【KMP】

``````#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const double e=2.7182818284590452353602874713527;
typedef pair<int,int> PII;
typedef long long int LL;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL qsm(LL a,LL b,LL p)
{
LL sum=1;
while(b)
{
if(b&1) sum=sum*a%p;
a=a*a%p; b=b>>1;
}
return sum%p;
}

/*
#pragma GCC optimize(2)
exp(n) e的n次方
priority_queue<int,vector<int>,greater<int>>q;

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
*/

const int N=1e5+10;
int n,m,t;
int ne[N];
string a,b;
int main(void)
{
cin>>a;
n=a.size();
a="0"+a;
for(int i=2,j=0;i<=n;i++)
{
while(j&&a[i]!=a[j+1]) j=ne[j];
if(a[i]==a[j+1]) j++;
ne[i]=j;
}
int t; cin>>t;
LL ans=0;
while(t--)
{
cin>>b;
m=b.size();
b="0"+b;
int temp=0;
for(int i=1,j=0;i<=m;i++)
{
while(j&&b[i]!=a[j+1]) j=ne[j];
if(b[i]==a[j+1]) j++;
temp=max(temp,j);
}
ans+=temp;
}
cout<<ans;
return 0;
}
``````

# 上学要迟到了【建图 最短路】

``````#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long int LL;
typedef pair<LL,int> PII;
int h[N],e[N],ne[N],w[N],idx;
LL st[N],dist[N];
LL n,m,stx,edx,t;
int a[N],b[N];
vector<int>ve[N];
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void Dijkstra(int u)
{
memset(dist,0x3f,sizeof dist);
priority_queue<PII,vector<PII>,greater<PII> > q; q.push({0,u});
dist[u]=0;
while(q.size())
{
auto temp=q.top(); q.pop();
u=temp.second;
if(st[u]) continue;
st[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[u]+w[i])
{
dist[j]=dist[u]+w[i];
q.push({dist[j],j});
}
}
}
}
int main(void)
{
cin>>n>>m>>stx>>edx>>t;
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i],ve[b[i]].push_back(i);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
Dijkstra(stx);
cout<<dist[edx];
return 0;
}
``````

# 迷宫【DP】

``````#include<bits/stdc++.h>
using namespace std;
const int N=105;
const int M=10007;
const int mod=1e4+7;
bool f[N][N][M];
int n,m,a[N][N];
int main(void)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>a[i][j],a[i][j]=a[i][j]%mod;
f[1][1][a[1][1]]=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i == 1 && j == 1) continue;
for(int k=0;k<mod;k++)
{
int temp=(k+a[i][j])%mod;
if(f[i-1][j][k]) f[i][j][temp]=true;
if(f[i][j-1][k]) f[i][j][temp]=true;
}
}
}
int cnt=0;
for(int i=0;i<10007;i++) if(f[n][m][i]) cnt++;
cout<<cnt;
return 0;
}
``````

# 树上行走【并查集】

``````#include<bits/stdc++.h>
using namespace std;
const int N=1e5*4+10;
int n,w[N];
int p[N],cnt[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i],p[i]=i,cnt[i]=1;
for(int i=1;i<=n-1;i++)
{
int a,b; cin>>a>>b;
if(w[a]==w[b]&&find(a)!=find(b))
{
cnt[find(a)]+=cnt[find(b)];
p[find(b)]=find(a);
}
}
int ans=0,t=1;
for(int i=1;i<=n;i++)
{
if(ans<cnt[find(i)]) ans=cnt[find(i)],t=1;
else if(ans==cnt[find(i)]) t++;
}
cout<<t<<endl;
for(int i=1;i<=n;i++) if(ans==cnt[find(i)]) cout<<i<<" ";
return 0;
}
``````

THE END

)">