2022牛客暑期多校训练营4(总结+补题)

总结：

打的很难受的一把，前期做签到题N的时候完全没想到会被卡long long，wa了整整四发，中期队友切掉H和K后来和我一起看D，我因为bitset没有正确开数组又MLE了三发，最后队友想到了优化才过的D。四题超高罚时结束。很难受的一把多校。

题解：

D - Jobs (Easy Version)

题意：

有 $n(1\le n\le 10)$ 个公司，每个公司有 $m_i(1\le m_i\le 10^5)$ 个岗位，每个岗位需要员工的 IQ、EQ、AQ均不低于 $a_i,b_i,c_i$ ，其中$1\le a_i,b_i,c_i\le 400$ ，现给你 $q$ 个查询，每次查询告诉你求职者的 IQ、EQ、AQ，问该求职者能够获得多少个公司的 offer（求职者只需要满足一个公司的任何一个岗位的条件，即可获得该公司的offer）。

做法：

对于公司每个岗位进行预处理，维护求职者如果IQ、EQ为 $i,j$ 时获得offer最小需要有多少AQ，这个操作只需要用类似于二维前缀 $min$ 的操作来维护即可，而查询则可以在 $O(n)$ 的复杂度里查到结果。

代码：

/*
 author:wuzx
 */

#include
#define int long long
#define endl "\n"
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int t;
int n,m;
#define tp3 tuple<int,int,int>
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int q;
    cin>>n>>q;
    vector<vector<vector<int>>> dp(n,vector<vector<int>> (401,vector<int>(401,inf)));
    for(int i=0;i<n;i++)
    {
        cin>>m;
        for(int j=0;j<m;j++)
        {
            int iq,eq,aq;
            cin>>iq>>eq>>aq;
            dp[i][iq][eq]=min(dp[i][iq][eq],aq);//输入员工的数据
        }
    }
    int seed;
    cin>>seed;
    auto init = [&]()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<=400;j++)
            {
                for(int k=1;k<=400;k++)
                    dp[i][j][k]=min({dp[i][j][k],dp[i][j-1][k],dp[i][j][k-1]});
            		//维护iq，eq所需要的最小aq
            }
        }
    };
    init();
    auto solve = [&](int IQ,int EQ,int AQ)
    {
        int res=0;
        for(int i=0;i<n;i++)
            if(dp[i][IQ][EQ]<=AQ)//若求职者aq大于等于该公司iq，eq岗位所需的最小aq，获得该公司offer
                res++;
        return res;
    };
    mt19937 rng(seed);
    uniform_int_distribution<> u(1,400);
    int lastans=0;
    auto poww = [&](int a,int b)
    {
        a%=mod;
        int res=1;
        while(b){
        if(b&1)
            res=res*a%mod;
            a=a*a%mod;
            b=b>>1;
        }
        return res%mod;
    };
    int res = 0;
    for (int i=1;i<=q;i++)
    {
        int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
        int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
        int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
        lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend  
        res = (res + lastans * poww(seed,q-i) %mod ) % mod;
    }
    cout<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

N - Particle Arts

题意：

有一对粒子 $a_i(1\le i\le n)$ $(0\le a_i\le 2^{15})$ 粒子会随机碰撞，$a_i$ 为粒子的能量，粒子每次碰撞时，他们将湮灭并产生两个新的粒子，新粒子的能量和分别为 KaTeX parse error: Undefined control sequence: \and at position 4: a_i\̲a̲n̲d̲ ̲a_j 和 $a_i|a_j$ ，经过足够的时间后，这些粒子的能量方差会收敛到一个稳定值，求稳定值后粒子能量的方差。

做法：

通过模拟碰撞我们可以知道，这些粒子能量中二进制的1最终会归到同一个数中，例如

001—>>000

010—>>000

011—>>001

100—>>111

101—>>111

我们也可以看作是上面数字二进制的1会随着碰撞往下掉到下面空白的0中，因此我们可以将输入中每个数的二进制位存起来，然后对 $n$ 个数贪心地构造出最大的数列。对其求方差，由于题目要求输出分数，我们可以用int128手写分数类。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
inline int gcd1(__int128 a,__int128 b){return b ? gcd1(b , a % b) : a ;}
struct P{
    __int128 f,s;
    P(__int128 ff,__int128 ss):f(ff),s(ss){};
};
P jf(P aa,P bb)
{
    __int128 fm=aa.s*bb.s;
    __int128 fz1=aa.f*bb.s;
    __int128 fz2=bb.f*aa.s;
    __int128 fz=fz1-fz2;
    __int128 cd=gcd1(fm,fz);
    fm/=cd;
    fz/=cd;
    fm=fm*fm;
    fz=fz*fz;
    cd=gcd1(fm,fz);
    fm/=cd;
    fz/=cd;
    return P(fz,fm);
}
P jiaf(P aa,P bb)
{
    __int128 fm=aa.s*bb.s;
    __int128 fz1=aa.f*bb.s;
    __int128 fz2=bb.f*aa.s;
    __int128 fz=fz1+fz2;
    __int128 cd=gcd1(fm,fz);
    fm/=cd;
    fz/=cd;
    return P(fz,fm);
}
inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    cin>>n;
    vector<int> a;
    vector<int> vis(20,0);//用于存输入数据中二进制第i位为1
    for(int i=0;i<n;i++)
    {
        cin>>m;
        for(int j=0;j<20;j++)
        {
            if(m%2)
                vis[j]++;
            m/=2;
        }
    }    
    vector<int> er(20,1);
    for(int i=1;i<20;i++)
        er[i]=er[i-1]*2;
    for(int i=0;i<n;i++)
    {
        int nb=0;
        for(int j=0;j<20;j++)//构造碰撞后数组
        {
            if(vis[j]>0)//该二进制有1，则将该为的1加到当前数中
            {
                nb+=er[j];
                vis[j]--;
            }
        }
        a.push_back(nb);
    }
    P mu(0,1);
    // mu.f=0,mu.s=1;
    int cd;
    for(int x:a)//求均值
    {
        mu=jiaf(mu,P(x,n));
        cd=gcd1(mu.f,mu.s);
        mu.f/=cd;
        mu.s/=cd;
    }
    P zero(0,1);
    for(int x:a)//求方差
    {
        // cout<
        P jh=jf(P(x,1),mu);
        zero=jiaf(zero,jh);
        // cout<
    }
    // cout<
    __int n1=n;
    cd=gcd1(zero.f,n1);
    zero.f/=cd;
    n/=cd;
    zero.s*=n;
    cd=gcd1(zero.f,zero.s);
    zero.f/=cd;
    zero.s/=cd;
    print(zero.f);
    cout<<"/";
    print(zero.s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118