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

绝地灬酷狼 2021-09-30 02:02 285阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>Sloved</th> 
   <th align="center">A</th> 
   <th align="center">B</th> 
   <th align="center">C</th> 
   <th align="center">D</th> 
   <th align="center">E</th> 
   <th align="center">F</th> 
   <th align="center">G</th> 
   <th align="center">H</th> 
   <th align="center">I</th> 
   <th align="center">J</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>8/10</td> 
   <td align="center">O</td> 
   <td align="center">Ø</td> 
   <td align="center">Ø</td> 
   <td align="center">Ø</td> 
   <td align="center">Ø</td> 
   <td align="center">Ø</td> 
   <td align="center">.</td> 
   <td align="center">Ø</td> 
   <td align="center">!</td> 
   <td align="center">O</td> 
  </tr> 
 </tbody> 
</table>

*  O for passing during the contest
 *  Ø for passing after the contest
 *  ! for attempted but failed
 *  · for having not attempted yet

upsolve:I  
G题放弃

被A题卡太久了，期间想到几个正确的思路没写，反而一直在错误的试结论  
以及F题演了一波，用fabs导致精度爆炸

## A.Equivalent Prefixes ##

题意大概就是两个数组，找最大的p，使对于1到p的所有子区间都保证最小值的下标相同；  
这时我们就可以发现，如果 a \[ i \] < a \[ i + 1 \] a\[i\]<a\[i+1\] a\[i\]<a\[i\+1\]  a n d and and  b \[ i \] < b \[ i + 1 \] b\[i\]<b\[i+1\] b\[i\]<b\[i\+1\]，则 a \[ i + 1 \] a\[i+1\] a\[i\+1\]和 b \[ i + 1 \] b\[i+1\] b\[i\+1\]对之前所有子区间都不构成影响，因为总有 m i n ( a \[ 1 \] ， a \[ i \] ) min(a\[1\]，a\[i\]) min(a\[1\]，a\[i\])比 a \[ i + 1 \] a\[i+1\] a\[i\+1\]小

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define INF 0x3fffffff
    #define maxn 100005
    int n,m,k,t;
    int a[maxn],b[maxn],num1[maxn],num2[maxn];
    int main(){ 
        while(~scanf("%d",&n)){ 
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            for(int i=1;i<=n;i++)
                scanf("%d",&b[i]);
            a[0]=b[0]=0;
            num1[1]=num2[1]=0;
            for(int i=2;i<=n;i++){ 
                int k1=i-1,k2=i-1;
                while(a[i]<a[k1])
                    k1=num1[k1];
                num1[i]=k1;
                while(b[i]<b[k2])
                    k2=num2[k2];
                num2[i]=k2;
                if(num1[i]!=num2[i]){ 
                    printf("%d\n",i-1);
                    break;
                }
                if(i==n)
                    printf("%d\n",n);
            }
        }
    }

## B.Integration ##

建议搜其他题解

## C.Euclidean Distance ##

[题解][Link 1]

## D. Parity of Tuples ##

对于每个元组的子集计数，通过子集卷积fwt计算count(n)

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = (1 << 21) + 7;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
    int lcm(int a,int b){ return a / gcd(a,b) * b;}
    ll fpow(ll a,ll b)
    { 
        ll res = 1;
        while(b){ 
            if(b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    void fwt(int *a,int n)
    { 
        for(int d = 1;d < n;d <<= 1)
            for(int m = d << 1,i = 0;i < n;i += m)
                for(int j = 0;j < d;++j){ 
                    int x = a[i + j],y = a[i + j + d];
                    a[i + j] = x + y;
                    a[i + j + d] = x - y;
                    //and:a[i + j] = x + y;
                    //or:a[i + j + d] = x + y;
                }
    }
    int n,m,k,a[15],f[N];
    void dfs(int pos,int s,bool flag)
    { 
        if(pos == m){ 
            flag ? f[s]++ : f[s]--;
            return ;
        }
        dfs(pos + 1,s,flag);
        dfs(pos + 1,s ^ a[pos],!flag);
    }
    int main()
    { 
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        while(scanf("%d%d%d",&n,&m,&k) != EOF){ 
            for(int i = 0;i < (1 << k);++i) f[i] = 0;
            for(int i = 0;i < n;++i){ 
                for(int j = 0;j < m;++j) scanf("%d",&a[j]);
                dfs(0,0,true);//对所有可达的s的子集进行计数
            }
            fwt(f,1 << k);//求count(0)
            ll ans = 0;
            ll inv = fpow((1 << m),mod - 2);
            for(int i = 0;i < (1 << k);++i){ //计算题目的公式
                ans ^= ((ll)f[i] * inv) % mod;
                inv *= 3,inv %= mod;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

## E. ABBA ##

[详细题解][Link 2]

## F. Random Point in Triangle ##

关于abs和fabs，这是一个悲伤的故事  
[https://en.cppreference.com/w/cpp/numeric/math/fabs][https_en.cppreference.com_w_cpp_numeric_math_fabs]  
[http://www.cplusplus.com/reference/cmath/fabs/][http_www.cplusplus.com_reference_cmath_fabs]  
比赛中错误的原因是因为转成了double类型 ，而题目中的数据可以达到1e16  
建议以后直接判断是否小于0

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3fffffff
    #define maxn 100005
    int n,m,k,t;
    long long a[10];
    int main(){ 
        while(~scanf("%lld%lld%lld%lld%lld%lld",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])){ 
            long double s=abs((a[1]*a[4]-a[3]*a[2])+(a[3]*a[6]-a[5]*a[4])+(a[5]*a[2]-a[1]*a[6]));
            //cout<<typeid(abs((a[1]*a[4]-a[3]*a[2])+(a[3]*a[6]-a[5]*a[4])+(a[5]*a[2]-a[1]*a[6]))).name();
            printf("%lld\n",(long long)s*(long long)11);
        }
    }

随机程序

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(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())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    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;}
    
    
    #define y1 yy1
    #define nxt(i) ((i + 1) % s.size())
    typedef double LD;
    const LD PI = 3.14159265358979323846;
    const LD eps = 1E-10;
    int sgn(LD x) {  return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); }
    struct L;
    struct P;
    typedef P V;
    struct P { 
        LD x, y;
        explicit P(LD x = 0, LD y = 0): x(x), y(y) { }
        explicit P(const L& l);
    };
    struct L { 
        P s, t;
        L() { }
        L(P s, P t): s(s), t(t) { }
    };
    
    P operator + (const P& a, const P& b) {  return P(a.x + b.x, a.y + b.y); }
    P operator - (const P& a, const P& b) {  return P(a.x - b.x, a.y - b.y); }
    P operator * (const P& a, LD k) {  return P(a.x * k, a.y * k); }
    P operator / (const P& a, LD k) {  return P(a.x / k, a.y / k); }
    inline bool operator < (const P& a, const P& b) { 
        return sgn(a.x - b.x) < 0 || (sgn(a.x - b.x) == 0 && sgn(a.y - b.y) < 0);
    }
    bool operator == (const P& a, const P& b) {  return !sgn(a.x - b.x) && !sgn(a.y - b.y); }
    P::P(const L& l) {  *this = l.t - l.s; }
    ostream &operator << (ostream &os, const P &p) { 
        return (os << "(" << p.x << "," << p.y << ")");
    }
    istream &operator >> (istream &is, P &p) { 
        return (is >> p.x >> p.y);
    }
    
    LD dist(const P& p) {  return sqrt(p.x * p.x + p.y * p.y); }
    LD dot(const V& a, const V& b) {  return a.x * b.x + a.y * b.y; }
    LD det(const V& a, const V& b) {  return a.x * b.y - a.y * b.x; }
    LD cross(const P& s, const P& t, const P& o = P()) {  return det(s - o, t - o); }
    
    typedef vector<P> S;
    
    // 点是否在多边形中 0 = 在外部 1 = 在内部 -1 = 在边界上
    // int inside(const S& s, const P& p) { 
    // int cnt = 0;
    // rep (i, 0, s.size()) { 
    // P a = s[i], b = s[nxt(i)];
    // if (p_on_seg(p, L(a, b))) return -1;
    // if (sgn(a.y - b.y) <= 0) swap(a, b);
    // if (sgn(p.y - a.y) > 0) continue;
    // if (sgn(p.y - b.y) <= 0) continue;
    // cnt += sgn(cross(b, a, p)) > 0;
    // }
    // return bool(cnt & 1);
    // }
    // 多边形面积，有向面积可能为负
    LD polygon_area(const S& s) { 
        LD ret = 0;
        rep (i, 1, (int)s.size() - 1)
            ret += cross(s[i], s[i + 1], s[0]);
        return ret / 2;
    }
    
    int main(int argc, char const *argv[])
    { 
    	P p1(0,0),p2(0,100),p3(100,0);
    	P pp;
    	S ans;
    	ans.pb(p1);
    	ans.pb(p2);
    	ans.pb(p3);
    	cout << abs(polygon_area(ans)) << endl;
    
    	LD saa = abs(polygon_area(ans)) ;
    	LD sum = 0;
    	int t = 0;
    	rep(__,0,1000000)
    	{ 
    		pp.x = rnd(100);
    		pp.y = rnd(100);
    		if(pp.x + pp.y > 100)
    			continue;
    		t++;
    		S s1,s2,s3;
    		s1.pb(p1);
    		s1.pb(p2);
    		s1.pb(pp);
    		s2.pb(p1);
    		s2.pb(p3);
    		s2.pb(pp);
    		s3.pb(p3);
    		s3.pb(p2);
    		s3.pb(pp);
    		
    		LD ss1 = abs(polygon_area(s1));
    		LD ss2 = abs(polygon_area(s2));
    		LD ss3 = abs(polygon_area(s3));
    		sum += max(max(ss1,ss2),ss3);
    	}
    	LD sss = sum / (t*1.0);
    	cout << sum / t << endl;
    	cout << sss/ saa << endl;
    	cout << sss / saa * 36 << endl;
    	return 0;
    }

（因为水平问题） 正解建议搜其他博客

## G. Substrings 2 ##

串题 fail

## H. XOR ##

对于异或和问题联想线性基，先消元得到一组解，然后对剩下的未插入基底消元，每次的数量为2^(n - cnt + 1)

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 7;
    const int inf = 0x3f3f3f3f;
    const ll mod = 1e9 + 7;
    const double eps = 1e-10;
    int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
    int lcm(int a,int b){ return a / gcd(a,b) * b;}
    ll fpow(ll a,ll b)
    { 
        ll res = 1;
        while(b){ 
            if(b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    struct L_B{ 
        ll d[64],p[64];
        int cnt,num;
        void init(){ // 初始化
            memset(d,0,sizeof d);
            memset(p,0,sizeof p); // 单位基
            cnt = 0; // 单位基中1的数量
            num = 0; // 基底数量
        }
        bool insert(ll val){  // 插入 如果x的1数位不存在则插入val，存在则赋值为0
            for(int i = 63;i >= 0;--i)
                if(val & (1LL << i)){ 
                    if(!d[i]){ 
                        d[i] = val;
                        num++;
                        break;
                    }
                    val ^= d[i];
                }
            return val > 0;
        }
        ll query_max(){  // 查询最大异或和
            ll ret = 0;
            for(int i = 63;i >= 0;--i)
                if((ret ^ d[i]) > ret)
                    ret ^= d[i];
            return ret;
        }
        ll query_min(){  // 查询最小异或和
            for(int i = 0;i <= 63;++i)
                if(d[i]) return d[i];
            return 0;
        }
        void rebuild(){  // 使线性基每一个基底独立，即除了第i位每一位均为0
            for(int i = 63;i >= 0;--i)
                for(int j = i - 1;j >= 0;--j)
                    if(d[i] & (1LL << j)) d[i] ^= d[j];
            for(int i = 0;i <= 63;++i)
                if(d[i]) p[cnt++] = d[i];
        }
        ll kth_query(ll k){  // 查询第k小值
            int ret = 0;
            if(k >= (1LL << cnt))
                return -1;
            for(int i = 63;i >= 0;--i)
                if(k & (1LL << i)) ret ^= p[i];
            return ret;
        }
    }A,B;
    L_B merge(const L_B &n1,const L_B &n2) // 暴力合并两个线性基
    { 
        L_B ret = n1;
        for(int i = 63;i >= 0;--i)
            if(n2.d[i]) ret.insert(n1.d[i]);
        return ret;
    }
    vector<ll> vi;
    int main()
    { 
        int n;
        while(scanf("%d",&n) != EOF){ 
            A.init(),B.init();vi.clear();
            ll x,ans = 0;
            for(int i = 0;i < n;++i){ 
                scanf("%lld",&x);
                if(A.insert(x)) vi.push_back(x);
                else B.insert(x);
            }
            if(n != A.num) ans = (n - A.num) * fpow(2,n - A.num - 1) % mod;
            for(int i = 0;i < vi.size();++i){ 
                L_B C = B;
                for(int j = 0;j < vi.size();++j)
                    if(i != j) C.insert(vi[j]);
                if(!C.insert(vi[i])) ans += fpow(2,n - C.num - 1),ans %= mod;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

## I. Points Division ##

待更

## J. Fraction Comparision ##

while True:
        try:
            x,y,a,b = map(int,input().split())
            if b * x == a * y:
                print("=")
            elif b * x > a * y:
                print(">")
            else:
                print("<")
        except:
            break

这题如果 x , y , a , b x,y,a,b x,y,a,b均为质数，那么使用 x ∗ b 和 y ∗ a x\*b和y\*a x∗b和y∗a来判断超过了long long的位数，如果直接除会造成精度缺失；  
所以我们可以考虑把整数部分和小数部分分开求，用 a 1 a1 a1来代表 x / a x/a x/a（整数部分）， a 2 a2 a2来代表 x x%a x（小数部分）， y / b y/b y/b同理；  
对于整数部分相同的，我们可以让小数部分进行通分比大小（防止精度损失）

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll x,y,a,b;
    int main(){ 
        while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b))
        { 
            ll a1=x/a,b1=y/b;
            ll a2=x%a*b,b2=y%b*a;
            if(a1>b1||(a1==b1&&a2>b2))
                puts(">");
            else if(a1<b1||(a1==b1&&a2<b2))
                puts("<");
            else
                puts("=");
        }
    }

[Link 1]: https://blog.nowcoder.net/n/5f605e09321841e0b913009092268915
[Link 2]: https://blog.csdn.net/qq_39239844/article/details/96475068
[https_en.cppreference.com_w_cpp_numeric_math_fabs]: https://en.cppreference.com/w/cpp/numeric/math/fabs
[http_www.cplusplus.com_reference_cmath_fabs]: http://www.cplusplus.com/reference/cmath/fabs/