单调队列

发表于 2024-08-31 更新于 2024-09-02 分类于算法竞赛

模拟双端队列

初始化：

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} \]

输出共两行：

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

思路：

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

需要维护两个问题：

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

代码：

#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]$ 之间的连续序列。最有价值段落是指平均值最大的段落。

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

思路

找平均值最大的一个段落可以转换为二分答案，$s[i] = s[i-1] + a[i] - mid$，若存在一段区间和大于0，则段落平均值的最大值一定大于$mid$。因此问题转化为寻找最大区间和问题，找到一个区间和大于0的区间，即可有效。
对于一个区间$[l,r]$来说，区间和为前缀和之差$a[r]-a[l-1]$。当我们确定右端点$r$时，只需在$[r-t+1,r-s+1]$范围内选取一个$l$，找到$a[l-1]$最小值，即可找到区间最大值。

代码

#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])$。

代码：

#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 感觉最舒适？

思路

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

代码

#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;
}

rs232

发表于 2024-08-05 更新于 2024-08-27 分类于 fpga ，通信协议

理论学习

通信协议基础

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

阅读全文 »

基于rs232的lcd图像显示

发表于 2024-08-05 更新于 2024-08-27 分类于 fpga ，通信协议

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

波特率的计算

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

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

$baud_cnt_max = $

阅读全文 »

rs485

发表于 2024-08-05 更新于 2024-08-27 分类于 fpga ，通信协议

理论基础

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

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

阅读全文 »

Register Clustering Methodology for Low Power Clock Tree Synthesis

发表于 2024-08-03 更新于 2024-08-27 分类于 EDA

Register Clustering Methodology for Low Power Clock Tree Synthesis

1.概要

背景

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

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

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

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

阅读全文 »

Toward Controllable Hierarchical Clock Tree Synthesis with Skew-Latency-Load Tree

发表于 2024-08-03 更新于 2024-09-02 分类于 EDA

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快捷键

发表于 2024-08-03 更新于 2024-08-13 分类于计算机基础

Sublime快捷键

查找替换

查找： Ctrl + F

查找替换：Ctrl + H

Git基础

发表于 2024-08-03 更新于 2024-08-04 分类于计算机基础， git

一.git基础

初始化git仓库
1
git init
阅读全文 »

Hello World

发表于 2023-12-14 更新于 2024-08-03

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.快速生成并部署

hexo g -d

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

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

摘要内容 ......

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