2022牛客蔚来杯第四场 N K D H A

2022牛客蔚来杯第四场 N K D H A
2022牛客蔚来杯第四场
文章目录
- 2022牛客蔚来杯第四场
- [N.Particle Arts](https://ac.nowcoder.com/acm/contest/33189/N)
  [K.NIO's Sword](https://ac.nowcoder.com/acm/contest/33189/K)
  [D.Jobs (Easy Version)](https://ac.nowcoder.com/acm/contest/33189/D)
  [H.Wall Builder II](https://ac.nowcoder.com/acm/contest/33189/H)
  [A.Task Computing](https://ac.nowcoder.com/acm/contest/33189/A)
N.Particle Arts
- 题意
  - n个粒子，每个粒子有能量ai。
  - 两两可以碰撞，碰撞后变成能量为a|b,a&b的两个粒子。
  - 求能量稳定后的方差
- 题解
  - 签到题
  - 观察变化的过程，得到结论：所有粒子的能量二进制表示时，同一位含有1的数量恒定
    
    a粒子能量 … 1(0) …
    
    b粒子能量 … 1(0) …
    
    同一位置不管是11,10,01,00哪一种情况，碰撞后|&运算不会使得此位的1的数量发生变化
    
    故，推得所有粒子能量的二进制任意位置1的数量恒定
  - 要求能量稳定时的方差，考虑什么时候稳定。
    
    当碰撞后得到的两个粒子能量还是原来的那两个时，处于稳定态。并且容易得到当二进制全是11111与任意粒子碰撞时都不会产生新的粒子能量。
    
    所以结合上一条结论，我们可以直接构造稳定态的各个粒子的能量。首先把各个二进制位的1数量记录，构造方法就是对于一个粒子让每一位尽量是1。
    
    二进制位 0 1 2 0 1 2
    
    a[0] 1 0 0 1 1 1 1
    
    a[1] 2 0 1 0 1 1 1
    
    a[2] 3 0 1 1 ------> 0 0 1
    
    a[3] 4 1 0 0 0 0 0
    
    a[4] 5 1 0 1 0 0 0
  - 得到稳定态所有粒子能量之后，直接计算方差即可。但是注意化简式子，否则精度会溢出。以下为long long 能过的化简。否则需要用__int128
    $\mu=\frac{sum}{n}\\ \sigma^2=\frac{\sum_{i=1}^{n}(x_i-\mu)^2}{n}\\ M=\sum_{i=1}^{n}(x_i-\mu)^2=\sum_{i=1}^{n}x_i^2+n*\frac{sum^2}{n^2}-\sum_{i=1}^{n}2*x_i*\frac{sum}{n}\\ n*M=\sum_{i=1}^{n}n*x_i^2+sum^2-\sum_{i=1}^{n}2*x_i*sum\\ \sigma^2=\frac{n*M}{n^2}(分子分母都在longlong以内)$
- 代码
```
#include 

using namespace std;
const int N=1e5+10,M=20;
typedef long long LL;

LL a[N],b[M];

LL gcd(LL a,LL b) {
    return b?gcd(b,a%b):a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    LL n;
    cin>>n;
    for(int i=0;i>a[i];
        for(int j=0;j<=15;j++)
            if(a[i]&(1<
```
- 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
K.NIO’s Sword
- 题意
  - 玩家有一把攻击力为0的剑，需要依次击杀n个敌人
  - 仅当攻击力膜n与i同余时才能击杀第i个敌人
  - 玩家可以任意升级剑，每次升级相当于在当前攻击力后面添加一个数字
  - 问最少升级几次可以把敌人全部击杀
- 题解
  - 杀完敌人i后，设剑攻击力为A；那么A%n同余于i，但不同余于i+1；所以剑每杀一个敌人至少需要升级一次；但次数又不会超过6，因为6次升级后攻击力为A*10^6+y,(0，此时y是n的范围，而i+1小于n，所以一定可以在6步选数中找到同余i+1的攻击力
  - 上述可得，我们不需要知道确切的剑攻击力，只需要枚举升级次数（最多枚举升级6次）所带来的攻击力提升的范围是否能凑出同余即可
  - 每次枚举如何判断：杀完i攻击力A，设需要升级k次能杀i+1 $A\equiv i(\% n)\\ A\not\equiv i+1(\%n)\\ 假设A*10^k+x\equiv i+1(\%n),即(0A≡i(%n)A≡i+1(%n)假设A∗10k+x≡i+1(%n),即(0<x<10k)移项x≡(i+1)−i∗10k验证x的范围，即可确定这个次数k是否正确$
  - 每次击杀互不影响，每次取最小，答案一定是全局最小值
  - 注意n=1时，不需要升级
- 代码
#include using namespace std; #define int long long int n,pow_10[15]; int domod(int x,int mod) {//可能负数，所以这样取模 return (x%mod + mod) % mod; } signed main() { cin>>n; if(n==1) {puts("0");return 0;}//特判 pow_10[0]=1;//预处理pow打大小，减少运算时间复杂度 for(int i=1;i<=10;i++) pow_10[i]=pow_10[i-1]*10; int ans=0; for(int i=1;i<=n;i++) {//枚举每一个怪物 int k=1;//记录杀死每一个怪物的升级次数 while(domod(i-(i-1)*pow_10[k],n)>=pow_10[k]) k++; ans+=k; } cout<
- 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
D.Jobs (Easy Version) 题意有n个公司，i公司有mi个工作，每个工作有三个能力的要求，三个能力都达标才能胜任这个工作一个人只要胜任了一个公司的任意一份工作即可得到这个公司的offer 询问q次，每次随机数给出三个能力后求可以得到几家公司的offer，之后根据题目式子用快速幂算一下题解注意seed要在输入之后再随机，因为每次获得的输入都和上一次的答案有关 **做法：**直接暴力，超时法一：O(n*400^3)，预处理出f[id,i,j,k]，表示第id公司是否存在三商不超过i,j,k的工作，那么只需要在每个询问中查询n个公司即可。数组爆空间，可以用bitset优化法二：O(n*400^2)，预处理出f[id,i,j]，表示第id公司前两个能力不超过i,j，的最小的第三个能力，同样的每个人只需查询n次即可。代码法一，三维前缀或 #include using namespace std; typedef long long ll; const int N=2e6+10,mod=998244353; ll n,q,m,a,b,c,seed; ll pw[N];//直接预处理指数，不用快速幂，优化一点点 bitset<402> f[11][402][402];//实则四维数组 int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>q; for(int id=1;id<=n;id++) { cin>>m; while(m--) { cin>>a>>b>>c; f[id][a][b][c]=1; } //维护三维前缀或 for(int i=1;i<=400;i++) for(int j=1;j<=400;j++) for(int k=1;k<=400;k++) f[id][i][j][k]=f[id][i][j][k] | f[id][i-1][j][k] | f[id][i][j-1][k] | f[id][i][j][k-1]; } cin>>seed; std::mt19937 rng(seed); std::uniform_int_distribution<> u(1,400); ll lastans=0,res=0; pw[0]=1; for(int i=1;i<=q;i++) pw[i]=pw[i-1]*seed % mod; 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=0; for(int j=1;j<=n;j++) if(f[j][IQ][EQ][AQ]) lastans++; res=(res + lastans*pw[q-i]%mod) % mod; } cout<

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

 
法二，二维偏序集 
#include 
#include 
#include 

using namespace std;
#define int long long
const int mod=998244353;
int n,q,seed,f[15][405][405];

int solve(int a,int b,int c) {
    int res=0;
    for(int id=1;id<=n;id++)
        if(f[id][a][b]<=c) res++;
    return res;
}

int qmi(int a,int b,int p){
    int res=1%p;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

signed main() {
    cin>>n>>q;
    memset(f,0x3f,sizeof f);
    for(int id=1;id<=n;id++) {
        int m;
        cin>>m;
        while(m--) {
            int a,b,c;
            cin>>a>>b>>c;
            f[id][a][b]=min(f[id][a][b],c);
        }
        //维护二维偏序集
        for(int i=1;i<=400;i++)
            for(int j=1;j<=400;j++) {
                f[id][i][j]=min(f[id][i][j],f[id][i-1][j]);
                f[id][i][j]=min(f[id][i][j],f[id][i][j-1]);
            }
    }
    
    cin>>seed;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1,400);

    int lastans=0,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*qmi(seed,q-i,mod)%mod) % mod;
    }
    cout<

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

 
H.Wall Builder II 
 题意 
  给n个1✖️1的矩形，n-1个1✖️2的矩形，n-2个1✖️3的矩形…
把这些矩形拼接成一个大矩形，问此大矩形的最小周长
 
 题解 
  由题可得面积固定，那么用不等式可以证明，当大矩形最接近于正方形时大矩形的周长最小
并且可以发现上述最接近的长和宽一定能构造成一个大矩形，不会证明
确定了长宽之后，只需要贪心去摆放矩形即可。每一层先放长的再放小的
 
 代码
  
#include 

using namespace std;
#define int long long
const int N=110;
int n,a[N];//长度为i的木板数量为a[i]

void solve() {
    cin>>n;
    int s=0;
    for(int i=1;i<=n;i++) a[i]=n-i+1,s+=i*a[i];//计算面积
    
    int y,x;
    for(int i=1;i<=s/i;i++)//找出最接近的正方形的一对长和宽
        if(s%i==0) y=i;
    x=s/y;
    cout<<2*x+2*y<<'\n';//输出周长
  
    for(int i=1;i<=y;i++) {//枚举每一层怎么铺
        int pos=0;//指针指向铺到横坐标的哪了
        for(int k=n;k>=1;k--)//贪心的从长木板开始放置
            while(a[k] && x-pos>=k){//如果还有这个长度的木板以及位置够用
                cout<>t;
    while(t--) solve();
    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 
A.Task Computing 
 题意 
   有n个物品，每个物品都有两个性质(wi,pi)
 
 从中选出m个物品，并且把m个物品排序使得下列式子最大。只选一个物品时价值为wi
  $\sum_{i=1}^{m}w_{i}*\prod_{j=0}^{i-1}p_j$ 
 
 
 题解 
   由于影响答案的因素有两个，一个是选哪m个物品，另一个是这m个物品的顺序，考虑固定一个因素来简化题目。
 因为从n个物品中选m个物品使得总价值最大可以用背包，所以考虑把n个物品的最优顺序排出来
 
 研究两个物品的顺序关系对于答案的影响之前，我们需要先知道每加入一个物品对答案的贡献是多少（比较的衡量），之后才能两两比较。
 加一个物品对答案的贡献：假设原先的答案为pre，假设新加入的物品放在最前面，因为这样假设可以确切的计算出这个物品对于答案的贡献，贡献是w+ pre*p，最优顺序取决于自己
 假设物品x放在前面对y优于y，那么满足下式
  $w_x+p_x*(w_y+p_y*pre)>w_y+p_y*(w_x+p_x*pre) \\ 化简w_x+p_x*w_y>w_y+p_y*w_x\\ 移项\frac{w_x}{1-p_x}>\frac{w_y}{1-p_y}$ 
 
 所以通过这个式子把最优顺序固定。最后只需要背包即可，f[i,j]表示从i个物品中选择j个物品的最大价值
 
 
 代码
  
#include 
#include 

using namespace std;
#define int long long 
const int N=1e5+10;
double f[N][25];

int n,m;
struct obj{
    double w,q;
    bool operator<(const obj &W)const {//排序
        return w+W.w*q>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i].w;
    for(int i=1;i<=n;i++) cin>>a[i].q,a[i].q/=10000;
    sort(a+1,a+n+1);
    
    for(int i=1;i<=n;i++)//01背包
        for(int j=1;j<=m;j++)
            f[i][j]=max(f[i-1][j],f[i-1][j-1]*a[i].q+a[i].w);
    printf("%.15lf\n",f[n][m]);
    
    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

2022牛客蔚来杯第四场

文章目录

N.Particle Arts

K.NIO’s Sword

D.Jobs (Easy Version)

H.Wall Builder II

A.Task Computing