题解 | D、Jobs (Easy Version)

Task Computing

https://ac.nowcoder.com/acm/contest/33189/A

PS：之前图有误，已更新

D、Jobs (Easy Version)

前置知识：二维前缀min，快速幂

题意

题目是说给你n个公司的求职岗位，每个岗位有三个要求：EQ、IQ、AQ，当你的这三项质数都大于等于这个职位的标准时，这个公司就会邀请你入职。现在你有q个朋友，你要算出他们分别会被多少个公司邀请，再根据公司的数量算出： alt 其中ans是第i个朋友收到公司邀请的数目，seed是题目给我们的随机数种子。

问题解析

先说一下题目给的这一段代码：

#include <random>
std::mt19937 rng(seed);
std::uniform_int_distribution<> u(1,400);

int lastans=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
}

这个是让我们来算出每个朋友的IQ、EQ、AQ的，我们直接把它加入到我们的代码里即可（看不懂没关系，不用看懂）。

solve(IQ,EQ,AQ):求得的是第i个朋友被公司邀请的数量。

这一题的主要问题就是，我们怎么能够知道对于第i家公司，我们当前朋友的三商是否能完全满足某个职位的需求。

暴力解法就是我们直接for循环用朋友的三商对比当前公司的所有职位，来看当前公司是否能邀请我们。

但这样的时间复杂度是:n * q * mi，显然是不行。

提示1：查看数据范围我们发现除了职位数mi和朋友数q是常见的1e5、1e6级别。公司数n和三商的上限都是很小的，我们可以试着从这里想办法。
提示2：我们并不用知道一个公司有多少职位是我们朋友可以满足的，只要有一个职位满足就可以了。

我们可以采用类似二维前缀和的方式，我们准备一个二维数组，把IQ看成i，EQ看成j，AQ为a[i][j]，那么对于朋友的三商bcd来说，只要a[b][c]小于等于d，那么这个公司就是能够邀请我们的。

假如一个公司有三个职位z1,z2,z3，他们要求的三商为（2，2，4），（3，3，3），（4，4，2），转化成我们的二维数组就是：（左上角为（0，0））

alt

如果我们朋友的坐标（IQ，EQ）：

在红色区域内，那么他的AQ至少为4才可以胜任至少一个职位。
在黄色区域内，那么他的AQ至少为3才可以胜任至少一个职位。
在蓝色区域内，那么他的AQ至少为2才可以胜任至少一个职位。
在白色区域内，那么他的AQ为多少都不能胜任至少一个职位（因为它的EQ或IQ太低了）。

这样子，我们就可以在O1的时间复杂度内判断这个公司是否能邀请我们的朋友。

因为有n个公司，所以我们开的其实是一个11 * 401 * 401的三维数组，但做法实际和二维数组一样。（当成三维来看也行，但实际从二维角度来看更方便）

至于计算结果，我们用快速幂求出seed的q-i次幂再乘上ans，把n个朋友的运算结果加起来即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e5 + 50, MOD = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}


int gcd(int a, int b)
{
    return a == 0 ? b : gcd(b % a, a);
}

uniform_int_distribution<> u(1, 400);
int n, q, res=0, seed=0;
int a[11][401][401];

int solve(int IQ, int EQ, int AQ, int x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
    	//第i个公司判断是否有职位是我们能胜任的
        if (a[i][IQ][EQ] <= AQ)cnt++;
    }
    //计算结果
    res = (res + cnt * qpow(seed, q - x) % MOD) % MOD;
    //cout<<cnt<<" "<<res<<endl;
    return cnt;
}



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int  x, b, c, d;
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        //初始把第i个公司的职位全设置成一个很大的数（即我们图上的白色区域）
        memset(a[i], 0x3f, sizeof a[i]);
        for (int j = 0; j < x; j++)
        {
            cin >> b >> c >> d;
            //把这公司的职位存入三维数组中
            a[i][b][c] = min(a[i][b][c], d);
        }
        //递推
        for (int j = 1; j <= 400; j++)
        {
            for (int k = 1; k <= 400; k++)
            {
            	//取最小值
                a[i][j][k] = min(a[i][j][k], a[i][j][k - 1]);
                a[i][j][k] = min(a[i][j][k], a[i][j - 1][k]);
            }
        }
    }
    cin >> seed;
    
    //题目给的代码
    mt19937 rng(seed);
	
    int lastans=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
        //加上了个i，好知道现在是第几个朋友
        lastans=solve(IQ,EQ,AQ,i);  // The answer to the i-th friend
    }
    cout << res;
    return 0;
}