2019牛客暑期多校训练营第一场

 2019-07-26 /  Luo Jinrong

进度

A	B	C	D	E	F	G	H	I	J
√	Δ	Δ		√	√		Δ	Δ	√

A. Equivalent Prefixes

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define M 100010
#define MAXN 500
#define MAXM 500
int dpp[M][20],dp1[M][20];
int a[M],c[M],n;
void makeRmqIndex(int n,int b[]) //返回最小值对应的下标
{
    int i,j;
    for(i=0;i<n;i++)
        dpp[i][0]=i;
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dpp[i][j]=b[dpp[i][j-1]] < b[dpp[i+(1<<(j-1))][j-1]]? dpp[i][j-1]:dpp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return b[dpp[s][k]]<b[dpp[v-(1<<k)+1][k]]? dpp[s][k]:dpp[v-(1<<k)+1][k];
}
void makeRmqIndex2(int n,int b[]) //返回最小值对应的下标
{
    int i,j;
    for(i=0;i<n;i++)
        dp1[i][0]=i;
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dp1[i][j]=b[dp1[i][j-1]] < b[dp1[i+(1<<(j-1))][j-1]]? dp1[i][j-1]:dp1[i+(1<<(j-1))][j-1];
}
int rmqIndex2(int s,int v,int b[])
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return b[dp1[s][k]]<b[dp1[v-(1<<k)+1][k]]? dp1[s][k]:dp1[v-(1<<k)+1][k];
}
bool solve(int l,int r){
    if(l>r)
        return true;
    int pos1=rmqIndex(l,r,a);
    int pos2=rmqIndex2(l,r,c);
    if(pos1==pos2){
        if(solve(l,pos1-1)&&solve(pos1+1,r))
            return true;
        else
            return false;
    }else{
        return false;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
            cin>>c[i];
        }
        makeRmqIndex(n,a);
        makeRmqIndex2(n,c);
        int l=0,r=n-1;
        int ans;
        while(l<=r){
            int mid=(l+r)/2;
            if(solve(0,mid)){
                l=mid+1;
                ans=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        cout<<ans<<"\n";
    }
}

B. Integration

#include <bits/stdc++.h>
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pI;
typedef vector<ll> vI;
const ll mod(1e9 + 7);
const ll INF(0x3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// head
 
ll a[1005];
 
int main(){
    int n;
    while(cin>>n){
        ll sgn=n&1?1:-1;
        per(i,1,n+1)
            cin>>a[i];
        ll summ=0;
            per(i,1,n+1){
                ll tmp=1;
                per(j,1,n+1){
                    if(i!=j){
                        tmp*=((a[i]*a[i]-a[j]*a[j])%mod);
                        tmp%=mod;
                    }
                }
                 
                tmp=tmp%mod;
                tmp=powmod(tmp,mod-2);
                ll tmm=2*a[i];
                tmm=powmod(tmm,mod-2);
                summ+=(tmp*tmm%mod)%mod;
                summ%=mod;
                //cout<<tmp<<"       ";
            }
            summ*=sgn;
         
         
        while(summ<0) {
            summ+=mod;
        }
        summ %=mod;
        //cout<<endl;
        cout<<summ<<endl;
    }
}

C. Euclidean Distance

#include<bits/stdc++.h>
using namespace std;
#define FIN freopen("./C.in","r",stdin)
typedef long long ll;
const ll maxn(1e4+5);
const double pi=acos(-1);
ll n,m,a[maxn];
bool cmp(ll a,ll b){
    return a>b;
}
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n>>m){
        for(ll i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+n+1,cmp);
        ll idx=n,left=m;
        for(ll i=1;i<n;i++){
            if(left>=abs(a[i+1]-a[i])*i){
                left-=abs(a[i+1]-a[i])*i;
            }else{
                idx=i;
                break;
            }
        }
        ll n1=(a[idx]*idx-left)*(a[idx]*idx-left),n2=idx*m*m;
        for(ll i=idx+1;i<=n;i++){
            n1+=a[i]*a[i]*idx;
        }
        ll g=__gcd(n1,n2);
        if(g==n2){
            cout<<n1/n2<<endl;
        }else{
            cout<<n1/g<<"/"<<n2/g<<endl;
        }
    }
}

E. ABBA

#include <bits/stdc++.h>
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pI;
typedef vector<ll> vI;
const ll mod(1e9 + 7);
const ll INF(0x3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// head
 
const int MAXN(1e3+7);
ll Cn2n[MAXN];
ll Inv[MAXN];
ll n, m, sumnm;
ll outt;
 
inline ll C(ll nn,ll mm)
{
    if(mm<0)return 0;
    if(nn<mm)return 0;
    if(mm>nn-mm)mm=nn-mm;
    ll up=1,down=1;
    for(ll i=0;i<mm;i++)
    {
        up=up*(nn-i)%mod;
        down=down*(i+1)%mod;
    }
    return up*Inv[down]%mod;
}
 
ll dfs(ll pos, ll s, ll xnm, ll ynm) {
    if(s>m || s<-n) {
        return C(2*sumnm-pos, sumnm-xnm);
    }
    if(xnm==sumnm || ynm==sumnm) {return 0;}
    ll summ1;
    summ1 = dfs(pos+1, s+1, xnm+1, ynm);
    summ1 += dfs(pos+1, s-1, xnm, ynm+1);
    return summ1;
}
 
ll dp[5*MAXN][MAXN*20];
ll dpp[MAXN][MAXN];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    dpp[0][0] = 1;
    while(cin >> n >> m) {
        ll tmp = min(n, m), tmp1=max(n, m);
        n = tmp; m=tmp1;
        if(dpp[n][m]) {
            cout << dpp[n][m] << endl;
            continue;
        }
        sumnm = n+m;
        dp[0][10*MAXN] = 1;
        per(i, 1, sumnm*2+1) {
            per(j, 0, m+2) {
                dp[i][10*MAXN+j] = 0;
            }
            per(j, 1, n+2) {
                dp[i][10*MAXN-j] = 0;
            }
            per(j, 0, m+1) {
                if (dp[i - 1][10 * MAXN + j]) {
                    dp[i][10*MAXN+j+1] = (dp[i][10*MAXN+j+1]+dp[i-1][10*MAXN+j])%mod;
                    dp[i][10*MAXN+j-1] = (dp[i][10*MAXN+j-1]+dp[i-1][10*MAXN+j])%mod;
                }
            }
            per(j, 1, n+1) {
                if(dp[i-1][10*MAXN-j]) {
                    dp[i][10*MAXN-j+1] = (dp[i][10*MAXN-j+1]+dp[i-1][10*MAXN-j])%mod;
                    dp[i][10*MAXN-j-1] = (dp[i][10*MAXN-j-1]+dp[i-1][10*MAXN-j])%mod;
                }
            }
        }
        dpp[n][m] = dp[sumnm*2][10*MAXN]%mod;
        cout << dpp[n][m] << endl;
    }
 
    return 0;
}

F. Random Point in Triangle

#include <bits/stdc++.h>
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pI;
typedef vector<ll> vI;
const ll mod(1e9 + 7);
const ll INF(0x3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// head
 
const int MAXN(50);
ll x[MAXN], y[MAXN];
 
inline ll CTA(int p1, int p2, int p3) {
    return 11*(x[p1]*y[p2]+x[p2]*y[p3]+x[p3]*y[p1]-x[p3]*y[p2]-x[p2]*y[p1]-x[p1]*y[p3]);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
     
    while(cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2]) {
        cout << abs(CTA(0, 1, 2)) << '\n';
    }
     
    return 0;
}

return 0;

本文链接：
https://luojinrong.github.io/2019/07/26/2019牛客暑期多校训练营第一场/