A-切蛋糕的贝贝
题解:分成1:1:4:5:1:4份,每次都要沿着两点连线切割,所以n要是16的倍数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=5e5+5;
const ll inf=1e18;
const ll mod=9901;
ll a[N],sum[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n;cin>>n;
if(n&&n%16==0) cout<<5;
else cout<<-1;
}
B-抱歉,这没有集美
题解:gcd(x,y)为偶数,那么就说明x,y都是偶数。反向思考,考虑概率为0的情况,就是把所有的偶数都付给奇数点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=5e5+5;
const ll inf=1e18;
const ll mod=1e9+7;
ll a[N],sum[N],fact[N],infact[N],res[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n;cin>>n;
ll p=n/2;
ll q=n-p;
ll ans=1;
ll sum=1;
for(ll i=1;i<=n;i++){
sum=(sum*i)%mod;
}
for(ll i=1;i<=p;i++){
ans=(ans*i)%mod;
}
if(n&1) ans=(ans*q)%mod;//在奇数点中选择p个偶数点
for(ll i=1;i<=q;i++){
ans=(ans*i)%mod;
}
ans=(sum-ans+mod)%mod;
cout<<ans;
}
C-打牌的贝贝
题解:贝贝赢得方式必须是出一张牌大于宁宁手上所有牌,所以可以先分配给贝贝n-1张牌,然后将这剩下得n+1张牌中最大的呢张牌给贝贝,那么贝贝一定赢,然后再通过总的减去求出宁宁即可,数目很大,用逆元求组合数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=2e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll fact[N],infact[N];
ll ksm(ll x,ll y){
ll ans=1;
while(y){
if(y&1) ans=(ans*x)%mod;
x=(x*x)%mod;y>>=1;
}
return ans;
}
void init(){
fact[0]=1;
for(ll i=1;i<=2000000;i++){
fact[i]=fact[i-1]*i%mod;
}
infact[2000000]=ksm(fact[2000000],mod-2)%mod;
for(ll i=2000000;i>=1;i--){
infact[i-1]=infact[i]*i%mod;
}
}
ll solve(int a,int b){
return fact[a]*infact[b]%mod*infact[a-b]%mod;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
init();
ll t;cin>>t;
while(t--){
int n;cin>>n;
cout<<solve(2*n,n-1)<<" "<<(solve(2*n,n)-solve(2*n,n-1)+mod)%mod<<"\n";
}
}
D-点分治分点
题解:将所有路径按照权值从大到小排序,然后每次将边加到图中,这样每次选出的权值,对于能达到的点而言,都一样是最小值中的最大值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=2e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,s;
ll dis[N],vis[N],ans[N];
vector<ll> e[N];
struct sp{
ll x,y,w;
}a[N];
bool cmp(sp x,sp y){
return x.w>y.w;
}
void dfs(ll x,ll w){
vis[x]=1;ans[x]=w;
for(auto it:e[x]){
if(!vis[it]){
dfs(it,w);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
for(ll i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].w;
}
sort(a+1,a+1+m,cmp);
fill(ans,ans+N,-1);
vis[s]=1;
for(ll i=1;i<=m;i++){
ll x=a[i].x;
ll y=a[i].y;
e[x].push_back(y);
if(vis[x]&&!vis[y]){
dfs(y,a[i].w);
}
}
for(ll i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
}
标签:typedef,练习赛,const,ll,cin,牛客,ans,105,mod
From: https://www.cnblogs.com/hhzp/p/16864121.html