第二问思路

是否对配件检验：

1. 如果对配件检验：得到的配件一定是合格品，只需计算平均价值。

\(E = \frac{p*(w+c)}{p}\)

\(p\)表示合格品概率，\(w\)表示配件购买价格，\(c\)表示配件检验成本

2. 不对配件检验：会提高成品的不合格率

是否对成品检验：

1. 对成品检验：需要付出检验费用，但卖出的成品一定是合格品，所以不需要支付退还费用。

成本构成：1.合格品的成本（包括配件购买费用+配件检验费用） ；2.组装费用； 3.成品检验费用 ；4.不合格品的成本

2. 对成品不检验：不需要检验费用，但卖出的成品有一部分是不合格品，需要支付退还费用。

成本构成：

枚举所有做法（第二问）

首先考虑不拆解的情况

1. 不检验配件A，不检验配件B，不检验成品，不拆解成品。

成品为合格品概率：\(p(qualified) = p_a * p_b * p_c\)

不合格品概率：\(1 - p(qualified)\)

平均收益：\(E = p(qualified) * w - 1 * (cost) - (1-p(qualified))*(swap)\)

2. 检验配件A，不检验配件B，不检验成品，不拆解成品。

配件A的平均成本：\(\frac{cost + c}{p}\)

成品为合格品概率：\(p(qualified) = p_b * p_c\)

平均收益：\(E = p(qualified) * w - 1*cost - (1-qualified)*swap\)

组成一件成品的价格：\(cost = cost_a + cost_b + eval_a + assemble\)

3. 不检验配件A，检验配件B，不检验成品，不拆解成品。

原理同上

4. 检验配件A，检验配件B，不检验成品，不拆解成品。

合格品概率：\(p(qualified) = p_c\)

平均收益：\(E = p(qualified) * w - 1 * cost - (1-p(qualified))*swap\)

生产价格：\(cost = E(cost_A) + E(cost_B) + assemble\)

综上所述：当不检验成品，且不拆解成品时，卖出每件产品的期望收益为：

\(E = p(qualified) * w - 1*cost - p(unqualified) * swap\)

只是每种情况，计算生产成本的结果不同

5. 不检验配件A，不检验配件B，检验成品，不拆解成品。

合格品概率：\(p(qualified) = p_A * p_B * p_C\)

销售收益：\(p(qualified) * w\)

生产成本：\(cost_A + cost_B + assemble + eval_C\)

6. 检验配件A，不检验配件B，检验成品，不拆解成品。

合格品概率：\(p(qualified) = p_B * p_C\)

销售收益：\(p(qualified) * w\)

成产成本：\(E(cost_A) + cost_B + assemble + eval_C\)

平均收益：\(E = p(qualified) * w - 1*cost\)

7. 不检验配件A，检验配件B，检验成品，不拆解成品

同6

8. 检验配件A，检验配件B，检验成品，不拆解成品

\(cost = E(cost_A) + E(cost_B) + assemble + eval_C\)

综上所述：不拆解成品的情况下，所有方案 卖出一件的预期收益为：

\(E = p(qualified) * w - 1 * cost - p(unqualified)*swap\)

是否检验配件，影响\(cost\)的计算；

是否检验成品，决定了售出成品的不合格率是否为0，可以减少退还损失。

其次考虑拆解成品的情况

由于拆解的是检验不合格的成品，所以，当拆解成品时，必然伴随着检验成品。

1. 不检验配件A，不检验配件B，检验成品，且拆解成品，且不进行二次检验。

暂时认为，这是一种很糟糕的策略，只有在次品率极低的情况下适用。

2. 检验配件A，检验配件B，检验成品，且拆解成品，无需进行二次检验。

第i次合成成功的成本：\(cost(i) = E(cost_A) + E(cost_B) + i*assemble + (i-1)*melt\)

生产成本：$cost = _{i=1}^{} cost(i) $

成品的合格率：\(p(qualified) = p_c\)

卖出一件产品的预期收益同上。

3. 检验配件A，不检验配件B，检验成品，拆解成品，并对B进行二次检验

这里需要用到朴素贝叶斯公式！

成品合格率：\(p(qualified) = p_B * p_C\)

仅因为组装问题导致为次品的概率为：\((1-p_C)*p_B\) ，

配件B损坏导致为次品的概率（包括了B既为次品，还组装失败的情况）：\(1-p_B\)

模拟双端队列

初始化：

1

hh = 1 , tt = 0;

入队：

1
2

q[++tt] = i
q[--hh] = i

出队

1
2

tt--
hh++

判断是否队列非空

1

if(tt>=hh)

滑动窗口

题目描述：

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 \([1,3,-1,-3,5,3,6,7]\) 以及 \(k = 3\)，有如下过程：

\[\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} \]

输出共两行：

第一行为每次窗口滑动的最小值，第二行为每次窗口滑动的最大值。

思路：

例如针对最小值：队列中存放的是当前窗口可能最小值的下标，并且保证队列中下标对应的保持单调递增，这样队首的下标对应的值，即为当前窗口的最小值。

需要维护两个问题：

1. 当前下标与队首下标的差值大于等于\(k\)，则表示队首和队尾已经不在一个窗口当中，这时需要把队首弹出。
2. 当前数小于队列尾下标对应的数时，可以弹出队尾。因为从当前数a[i]进入窗口开始，到队列尾数a[q_tt]离开窗口为止，窗口始终包含a[i]，因此最小值一定不可能为比a[i]大的数a[q_tt]，因此将队列尾弹出可以减少时间复杂度。
3. 当前窗口的最小值始终为：\(a[q\_hh]\)

代码：

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

#include<iostream>
using namespace std;

const int N = 1000005;

int n,k;
int a[N],q[N];
int tt,hh;

void out_min_deque()
{
    hh = 1 , tt = 0;
    for(int i=1;i<=n;i++)
    {
        while(tt>=hh && i-q[hh]>=k) hh++;
        while(tt>=hh && a[i]<a[q[tt]]) tt--;
        q[++tt] = i;

        if(i>=k) cout<<a[q[hh]]<<" ";
    }
}

void out_max_deque()
{
    hh = 1 , tt = 0;
    for(int i=1;i<=n;i++)
    {
        while(tt>=hh && i-q[hh]>=k) hh++;
        while(tt>=hh && a[i]>a[q[tt]]) tt--;
        q[++tt] = i;

        if(i>=k) cout<<a[q[hh]]<<" ";
    }
}

int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++) cin>>a[i];

    out_min_deque();

    cout<<endl;

    out_max_deque();

    return 0;
}

寻找段落

题目描述

给定一个长度为 \(n\) 的序列 \(a\)，定义 \(a_i\) 为第 \(i\) 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 \([S, T]\) 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

思路

1. 找平均值最大的一个段落 可以转换为二分答案，\(s[i] = s[i-1] + a[i] - mid\)，若存在一段区间和大于0，则段落平均值的最大值一定大于\(mid\)。因此问题转化为寻找最大区间和问题，找到一个区间和大于0的区间，即可有效。
2. 对于一个区间\([l,r]\)来说，区间和为前缀和之差\(a[r]-a[l-1]\)。当我们确定右端点\(r\)时，只需在\([r-t+1,r-s+1]\)范围内选取一个\(l\)，找到\(a[l-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
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include<iostream>
using namespace std;

const int N = 1000005 , INF = 10000;

int n,s,t;
int a[N];
double b[N];
int q[N],tt,hh;

bool check(double x)
{
    hh = 1 , tt = 0;
    for(int i=1;i<=n;i++)
        b[i] = b[i-1] + a[i] - x;

    // for(int i=s,j=0;i<=n;i++,j++)
    // {
    //     //i为区间尾,这里找从1~j的最小区间和
    //     while(tt>=hh && b[j]<b[q[tt]]) tt--;
    //     q[++tt] = j;

    //     while(tt>=hh && i-q[hh]>t) hh++;

    //     if(b[i] - b[q[hh]] > 0.00001) return true;
    // }

    for(int i=1;i<=n;i++)
    {
        if(i>=s)
        {
            while(tt>=hh && b[i-s]<b[q[tt]]) tt--;
            q[++tt] = i-s;
        }

        while(tt>=hh && i-q[hh]>t) hh++;

        if(tt>=hh && b[i]-b[q[hh]]>0) return true;

    }

    return false;
}

int main()
{
    scanf("%d%d%d",&n,&s,&t);
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]);

    double l = -INF , r = INF;
    while(r-l > 1e-4)
    {
        double mid = (r+l) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    printf("%.3f",l);

    return 0;
}

ST表 || RMQ

该类问题为求：查询区间的最大值或最小值，思路用到了倍增思想。

设\(f[i][j]\)为从\(i\)开始的\(2^j\)个数中的最大值，可以从短到长合并，求得所有\(f[i][j]\)

最后查询区间，只需查询\(max(f[l1][k],f[l2][k])\)。

代码：

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

#include<iostream>
#include<math.h>
using namespace std;

const int N = 100005;

int n,m;
int a[N],f[N][20];
int l,r;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int query(int l,int r)
{
    int k = log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    n = read();
    m = read();

    for(int i=1;i<=n;i++) a[i] = read();
    for(int i=1;i<=n;i++) f[i][0] = a[i];

    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
        {
            int r2 = j + (1<<i) - 1;
            int l2 = j + (1<<(i-1));
            if(r2>n) break;

            f[j][i] = max(f[j][i-1],f[l2][i-1]);
        }

    for(int i=1;i<=m;i++)
    {
        l = read();
        r = read();
        printf("%d\n",query(l,r));
    }

    return 0;
}

良好的感觉

题目描述

kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 \(A_i\)，\(A_i\) 越大，表示人感觉越舒适。在一段时间 \(\left[i, j\right]\) 内，人的舒适程度定义为 \(\left[i, j\right]\) 中最不舒服的那一天的感受值 \(\times\) \(\left[i, j\right]\)中每一天感受值的和。现在给出 kkk 在连续 \(N\) 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

思路

单调栈：给定一个序列，求每个元素在其后第一个大于他的元素下标。可以从后往前跑一遍，将小于等于他的元素出栈，此时栈顶的下标即为第一个大于他的元素。

代码

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

#include<iostream>
using namespace std;

const int N = 1000005;
#define int long long

int n;
int a[N],s[N];
int l[N],r[N];
int stk[N],hh,tt;
int ans;

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i];

	tt = -1;
	for(int i=1;i<=n;i++)
	{
		while(tt>=0 && a[i]<=a[stk[tt]]) tt--;

		if(tt>=0) l[i] = stk[tt];
		else l[i] = 0;

		stk[++tt] = i;
	}

	tt = -1;
	for(int i=n;i>=1;i--)
	{
		while(tt>=0 && a[i]<=a[stk[tt]]) tt--;

		if(tt>=0) r[i] = stk[tt];
		else r[i] = n+1;

		stk[++tt] = i;
	}

	for(int i=1;i<=n;i++)
	{
		int sum = a[i] * (s[r[i]-1]-s[l[i]]);
		ans = max(ans,sum);
	}

	cout<<ans<<endl;

	return 0;
}

理论学习

通信协议基础

​ 通用异步收发传输器（Universal Asynchronous Receiver/Transmitter），通常称作UART。UART是一种通用的数据通信协议，也是异步串行通信口（串口）的总称，它在发送数据时将并行数据转换成串行数据来传输，在接收数据时将接收到的串行数据转换成并行数据。它包括了RS 232、RS499、RS423、RS422和RS485等接口标准规范和总线标准规范。

1.使用uart_rx模块作为图像接受模块

1. 波特率的计算

波特率：每秒钟通过信号传输的码元数称为码元的传输速率

使用时钟频率 除以 波特率 可以得到传输每个码源所占用的时钟周期数

$baud_cnt_max = $

理论基础

RS-485是双向、半双工通信协议，信号采用差分传输方式，允许多个驱动器和接收器挂接在总线上，其中每个驱动器都能够脱离总线。

RS-232是双向、全双工通信协议，信号采用单端传输方式。

Register Clustering Methodology for Low Power Clock Tree Synthesis

1.概要

背景

​ 一个时钟网络通常消耗整个芯片功率的40%。因此，许多研究者关注根据(1)中提出的参数对时钟网络进行功率优化。

KMR：基于k均值的寄存器聚类算法

KSR：基于k-分裂的寄存器聚类算法

GSR：基于贪婪搜索的寄存器聚类算法

1.SKEW-LATENCY-LOAD TREE CONSTRUCTION

首先提出了时钟延迟(latency)，时钟漂移(skew)，负载电容与线长的关系。

\(PL(s_i)\)denotes the path length from the source to \(s_i\)of \(T\) .

\(\begin{gathered} \text { skew } \propto \max _{s_i \in \mathcal{S}}\left\{P L\left(s_i\right)\right\}-\min _{s_i \in \mathcal{S}}\left\{P L\left(s_i\right)\right\}, \\ \text { latency } \max _{\max } \propto \max _{s_i \in \mathcal{S}}\left\{P L\left(s_i\right)\right\}, \\ \text { load } \propto W L(T), \end{gathered}\)

Sublime快捷键

查找替换

查找 ： Ctrl + F

查找替换 ：Ctrl + H

一.git基础

1. 初始化git仓库

   1

   git init

   阅读全文 »

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Clean buffer

1

$ hexo clean

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment

skyang

1.清除缓存可以帮助你重置主题，删除多余标签

1

hexo clean

2.快速生成并部署

1

hexo g -d

3. 书写markdown文档时题头用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---
title: Git基础
date: 2024-08-03 22:04:53
tags: 
  - git
  - linux
categories: 
  - 计算机基础
---

摘要内容 ......

<!--more-->
<!--more-->
      
正文内容 ......