首页 > 系统相关 >2024-02-22-物联网系统编程(3-进程)

2024-02-22-物联网系统编程(3-进程)

时间:2024-02-23 14:12:03浏览次数:20  
标签:02 22 process pid 2024 exit printf 进程 include

3.进程

3.1 进程概述

3.1.1 进程的定义

程序:存放在存储介质上的可执行文件

进程:程序的执行实例,包括程序计数器、寄存器和变量的当前值

程序是静态的,进程是动态的。程序是一些执行的有序集合,而进程是程序执行的过程;进程状态是变化的,有创建、调度和消亡。

在linux系统中,进程是管理事务的基本单元;进程拥有自己独立的处理环境和资源系统(处理器、存储器、IO等)

3.1.2 进程的状态和转换

进程整个生命周期可以划分为三个状态

就绪态:进程已经具备执行的一切条件,正在等待分配CPU的处理时间

执行态:进程正在占用CPU运行

等待态:进程因不具备某些执行条件而暂时无法运行的状态

image-20240222142421948

进程调度机制:时间片轮转、上下文切换

系统通过时间片轮转和上下文切换,实现多进程工作。

3.1.3 进程控制块

进程控制块(Process Control Block)是用于保存一个进程信息的结构体

OS通过PCB对并发执行的进程进行控制和管理。

系统在创建一个进程的时候会开辟一段内存空间存放与此进程相关的PCB数据结构。PCB是操作系统中最重要的记录型数据结构。PCB中记录了用于描述进程进展情况及控制进程运行所需的全部信息。

PCB是进程存在的唯一标志,在Linux中PCB存放在task struct结构体中。

task struct结构体保存在/usr/src/linux-headers-4.4.0-176-generic/include/inux/sched.h 一般在1500或者1300行左右

3.2 进程控制

3.2.1 进程号

每个进程都有一个进程号来标识,其类型为pid_t,进程号范围:0~32767

进程号总是唯一的,但进程号可以重用。当一个进程终止后,其进程号就可以再次使用了。

  1. 在 linux 系统中进程号由0开始,进程号为01的进程由内核创建,

  2. 进程号为0的进程通常是调度进程,常被称为交换进程(swapper)。进程号为1的进程通常是 init 进程。

    除调度进程外,在 linux下面所有的进程都由 init 进程直接或者间接创建。

进程号(PID): 标识进程的一个非负整型数
父进程号(PPID):任何进程(除 init 进程)都是由另一个进程创建,该进程称为被创建进程的父进程,对应的进程号称为父进程号(PPID)
进程组号(PGID):进程组是一个或多个进程的集合。他们之间相互关联,进程组可以接收同一终端的各种信号,关联的进程有一个进程组号(PGID)

Linux 操作系统提供了三个获得进程号的函数 getpid()、geippid()、getpgid()

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main(int argc, char const *argv[])
{
    printf("pid = %d\n", getpid());

    printf("ppid = %d\n", getppid());

    printf("pgid = %d\n", getpgid(getpid()));

    return 0;
}

输出结果

$ ./a.out 
pid = 12169
ppid = 3527
pgid = 12169

3.2.2 进程的创建 - fork函数

在 linux,环境下,创建进程的主要方法是调用以下两个函数:

#include <sys/types.h>
#include <unistd.h>

pid_t fork(void); 
pid_t vfork(void);
创建一个新进程
	pid_t fork(void)
功能:
	fork()函数用于从一个已存在的进程中创建一个新进程,新进程称为子进程,原进程称为父进程
返回值:
	成功: 子进程中返回0,父进程中返回子进程ID
	失败: 返回-1。

地址空间:包括进程上下文、进程堆栈、打开的文件描述符、信号控制设定、进程优先级、进程组号等。
子进程所独有的只有它的进程号,计时器等,因此,使用fork函数的代价是很大的。

image-20240222162301346
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
int main()
{
	// 通过fork函数的返回值来区分父子进程的独立代码区
	// 父子进程是来回交替执行的,谁先谁后不确定
	pid_t pid;
	pid = fork();
	if (pid < 0)
	{
		printf("fail to fork");
		return -1;
	}
	else if (pid > 0) // 父进程的代码区,返回值为子进程的进程号
	{
		while (1)
		{
			printf("parent:pid = %d,ppid = %d\n", getpid(), getppid());
			printf("this is a parent process\n");
			sleep(1);
			printf("***********************\n");
		}
	}
	else // 子进程代码区,返回值为0,因为子进程复制fork前父进程的所有信息
	{
		while (1)
		{
			printf("son:pid = %d,ppid = %d\n", getpid(), getppid());
			printf("this is a son  process\n");
			sleep(1);
			printf("------------------------\n");
		}
	}

	return 0;
}

输出结果

spider@ubuntu:~/C/output$ ./"01_fork"
parent:pid = 3600,ppid = 3349
this is a parent process
son:pid = 3601,ppid = 3600
this is a son  process
***********************
parent:pid = 3600,ppid = 3349
this is a parent process
------------------------
son:pid = 3601,ppid = 3600
this is a son  process
***********************
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
int a = 666;
int main()
{
	// 通过fork函数的返回值来区分父子进程的独立代码区
	// 父子进程是来回交替执行的,谁先谁后不确定
	pid_t pid;
	static int b = 777;
	int c = 888;
	pid = fork();
	if (pid < 0)
	{
		printf("fail to fork");
		return -1;
	}
	else if (pid > 0)
	{
		while (1) // 父进程代码区
		{

			a++;
			b++;
			c++;
			printf("this is a parent process a = %d ,b = %d, c=%d\n", a, b, c);
		}
	}
	else
	{
		while (1) // 子进程代码区
		{

			printf("this is a son  process a = %d ,b = %d, c=%d\n", a, b, c);
		}
	}

	return 0;
}

输出结果

// 子进程只是复制fork之前的变量,所以子进程的值不会发生改变(堆区、栈区、数据区)
this is a son  process a = 666 ,b = 777, c=888
this is a parent process a = 40855 ,b = 40966, c=41077
this is a son  process a = 666 ,b = 777, c=888
this is a parent process a = 40856 ,b = 40967, c=41078
this is a son  process a = 666 ,b = 777, c=888
this is a parent process a = 40857 ,b = 40968, c=41079
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int main()
{
    // 子进程会继承父进程一些公有的区域,比如磁盘空间、内核空间
    // 文件描述符的偏移量保存在内核空间,所以父进程改变偏移量,则子进程获取的偏移量是父进程改变之后的
	int fd;
	if ((fd = open("file.txt", O_RDONLY)) == -1)
	{
		perror("fail to read");
		return -1;
	}

	pid_t pid;
	pid = fork();
	if (pid < 0)
	{
		printf("fail to fork");
		return -1;
	}
	else if (pid > 0)
	{
		while (1) // 父进程代码区
		{

			char buf[32] = "";
			if (read(fd, buf, 10) == -1)
			{
				perror("fail to read");
				return -1;
			}
			printf("this is a parent process:%s\n", buf);
			break;
		}
	}
	else
	{
		while (1) // 子进程代码区
		{

			char buf[32] = "";
			if (read(fd, buf, 32) == -1)
			{
				perror("fail to read");
				return -1;
			}
			printf("this is a son  process: %s\n", buf);
			break;
		}
	}

	return 0;
}

输出结果

// 子进程会继承父进程一些公有的区域,比如磁盘空间、内核空间
// 文件描述符的偏移量保存在内核空间,所以父进程改变偏移量,则子进程获取的偏移量是父进程改变之后的
spider@ubuntu:~/C/output$ ./"03_fork"
this is a parent process:hello worl
this is a son  process: d welcome to beijing
spider@ubuntu:~/C/output$ 

3.2.3 进程挂起 - sleep函数

进程在一定的时间内没有任何操作,即进程的挂起

#include <unistd.h>
  unsigned int sleep(unsigned in sec);
功能:
	进程挂起指定的秒数,直到指定的时间用完或收到信号才解除挂起;
返回值:
	若进程挂起到 sec 指定的时间则返回 0,若有信号中断则返回剩余秒数;
注意:
	进程挂起指定的秒数后程序并不会立即执行,系统只是将此进程切换到就绪态;
#include <unistd.h>
#include <stdio.h>
int main(int argc, char const *argv[])
{
    while (1)
    {
        // 当运行到sleep函数后,程序会在此位置等待设定的秒数,当到达后,代码会接着执行
        // sleep运行时进程为等待态,时间到达后会切换到就绪态,如果代码继续执行,再切换到运行态
        printf("hello world\n");
        sleep(2);
    }

    return 0;
}

输出结果

spider@ubuntu:~/C/output$ ./"04_sleep"
hello world
hello world
hello world

3.2.4 进程的等待 - wait函数、waitpid函数

wait函数

pid t wait(int *status);

功能:  等待子进程终止,如果子进程终止了,此函数会回收子进程的资源。调用 wait 函数的进程会挂起,直到它的一个子进程退出或收到一		  个不能被忽视的信号时才被唤醒若调用进程没有子进程或它的子进程已经结束,该函数立即返回;
参数:
	函数返回时,参数 status 中包含子进程退出时的状态信息。子进程的退出信息在一个 int 中包含了多个字段, 用宏定义可以取出其中的每个字段;
返回值:
        执行成功,返回子进程的进程号
        执行错误,返回-1,失败原因存放在error中

取出子进程的退出信息

WIFEXITED(status)
	如果子进程是正常终止的,取出的字段值非零W
EXITSTATUS(status)
	返回子进程的退出状态,退出状态保存在 status 变量的 8~16 位。在用此宏前应先用宏 WIFEXITED 判断子进程是否正常退出,正常退出才可以使用此宏。
注意:
	此 status 是个 wait 的参数指向的整型变量
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/wait.h>


int main()
{

    pid_t pid;
    pid = fork();
    if (pid < 0)
    {
        printf("fail to fork");
        return -1;
    }
    else if (pid > 0)
    {
        // 父进程代码区
        // 使用wait等待子进程的退出
        // wait(NULL);
        // 也可以接受子进程的退出状态,子进程中必须使用exit或者_exit函数,在退出进程时发出退出状态
        int status = 0;
        wait(&status);
        if(WIFEXITED(status) !=0){
            printf("The son process return statsu :%d \n",WEXITSTATUS(status));
        }
        printf("this is a parent process\n");
        
    }
    else
    {
        // 子进程代码区

        int i;
        for (i = 0; i < 5; i++)
        {
            printf("this is a son  process\n");
        }
        // 使用exit退出进程
    }

    return 0;
}

输出结果

this is a son  process
this is a son  process
this is a son  process
this is a son  process
this is a son  process
The son process return statsu :0 
this is a parent process

waitpid函数

pid_t waitpid(pid_t pid, int *status,int options)
功能: 等待子进程终止,如果子进程终止了,此函数会回收子进程的资源

参数pid 的值有以下几种类型:
	pid>0: 等待进程 ID 等于 pid 的子进程
	pid=0: 等待同一个进程组中的任何子进程,如果子进程已经加入了别的进程组,waitpid,不会等待它。
    pid=-1: 等待任一子进程,此时 waitpid 和 wait 作用一样。
    pid<-1:等待指定进程组中的任何子进程,这个进程组的 ID 等于 pid的绝对值
        
status 参数中包含子进程退出时的状态信息。
options 参数能进一步控制 waitpid 的操作:
    0 : 同 wait,阻塞父进程,等待子进程退出;
	WNOHANG : 没有任何已经结束的子进程,则立即返回;
    WUNTRACED : 如果子进程暂停了则此函数马上返回,并且不予以理会子进程的结束状态。(跟踪调试,很少用到)
返回值:
	成功: 返回状态改变了的子进程的进程号;如果设置了选项 WNOHANG 并且 pid 指定的进程存在则返回 0;
	出错: 返回-1。当 pid所指示的子进程不存在,或此进程存在,但不是调用进程的子进程,waitpid 就会出错返回,这时 crrno 被设置为 ECHILD。

特殊进程

  1. 僵尸进程(Zombie Process)

    进程已运行结束,但进程的占用的资源未被回收,这样的进程称为僵尸进程。子进程已运行结束,父进程未调 wait 或 waitpid 函数回收子进程的资源是子进程变为僵尸进程的原因。

  2. 孤儿进程(0rphan Process)
    父进程运行结束,但子进程未运行结束的子进程。

  3. 守护进程(精灵进程)(Daemon process)
    守护进程是个特殊的孤儿进程,这种进程脱离终端,在后台运行。

3.2.5 进程终止 - exit函数 、_exit函数

exit函数

#include <stdlib.h>
void exit(int value)  //结束进程执行
参数:返回给父进程的参数

_exit函数

#include<stdlib.h)
void exit(int status);
功能: 退出当前进程
参数:
    status:退出状态,由父进程通过wait函数接收这个状态
        一般失败退出设置为非0
        一般成功退出设置为0
返回值:无

exit_exit函数的区别:

  1. exit为库函数,而_exit为系统调用
  2. exit会刷新缓冲区,但是_exit不会刷新缓冲区,一般会使用exit
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>

void myfunc()
{
    printf("nihao beijing");
    // 使用return,在子函数中使用,退出当前函数;在主函数中使用退出当前进程
    // return;
    
    // 使用exit
    // exit(0);

    // 使用_exit ,验证是否刷新缓冲区,去掉一个输出中的\n
    // _exit不会刷新缓冲区
    _exit(0);
    printf("welcome to shanghai\n");
}

int main(int argc, char const *argv[])
{
    printf("hello world\n");
    myfunc();
    printf("hello kitty\n");
    return 0;
}

使用return 输出

hello world
nihao beijing
hello kitty

使用exit输出

hello world
nihao beijing

使用_exit输出

hello world

3.2.6 进程退出清理 - atexit函数

进程在退出前可以用 atexit ,函数注册退出处理函数

#include <stdlib.h>
int atexit(void (*function)(void));
功能:
	注册进程正常结束前调用的函数,进程退出执行注册函数;
参数:
	function:进程结束前,调用函数的入口地址。一个进程中可以多次调用atexit函数注册清理函数,正常结束前调用函数的顺序和注册时的顺序相反;
返回值:
    成功 : 0 
    失败 : 非0 
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

void clear_fun1()
{
    printf("perform clear fun1\n");
}

void clear_fun2()
{
    printf("perform clear fun2\n");
}

void clear_fun3()
{
    printf("perform clear fun3\n");
}

int main(int argc, char const *argv[])
{
    // atexit在进程结束时才会执行参数对应的回调函数
    // atexit在多次
    atexit(clear_fun1);
    atexit(clear_fun2);
    atexit(clear_fun3);
    printf("process exit 3 sec later\n");
    sleep(3);
    return 0;
}

输出结果

process exit 3 sec later
perform clear fun3
perform clear fun2
perform clear fun1

3.2.7 进程的创建 - vfork函数

pid_t vfork(void)
功能:
	vfork,函数和 fork函数一样都是在已有的进程中创建一个新的进程,但它们创建的子进程是有区别的。返回值:
创建子进程成功,则在子进程中返回0,父进程中返回子进程 ID。出错则返回-1。

fork 和 yfork 函数的区别:
vfork保证子进程先运行,在它调用 execexit 之后,父进程才可能被调度运行。

vfork fork 一样都创建一个子进程,但它并不将父进程的地址空间完全复制到子进程中,因为子进程会立即调用 exec(或 exit),于是也就不访问该地址空间。相反,在子进程中调用 exec 或 exit之前,它在父进程的地址空间中运行,在 exec之后子进程会有自己的进程空间。

1.子进程在父进程之前完成

使用vfork函数创建完子进程后,子进程会先执行,直到子进程执行exit或者exec后,父进程才会执行

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
int main()
{
    // 使用vfork函数创建完子进程后,子进程会先执行
    // 直到子进程执行exit或者exec后,父进程才会执行

    pid_t pid;
    pid = vfork();
    if (pid < 0)
    {
        printf("fail to fork");
        exit(1);
    }
    else if (pid == 0)
    {
        int i;
        for (i = 0; i < 5; i++)
        {
            printf("this is son process\n");
            sleep(1);
        }
        exit(0);
    }
    else
    {
        while (1)
        {

            printf("this is a father  process\n");
            break;
        }
    }

    return 0;
}

输出结果

this is son process
this is son process
this is son process
this is son process
this is son process
this is a father  process

2.子进程和父进程共享同一空间

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
int a = 10;
int main(int argc, char const *argv[])
{
    pid_t pid;
    int b = 9;

    // 使用vfork创建完子进程
    // 在子进程执行exit或者exec之前,父子进程共用同一地址空间
    pid = vfork();
    if (pid < 0)
    {
        perror("fail to vfork\n");
        exit(1);
    }
    if (pid == 0)
    {
        a++;
        b++;
        printf("in son process a = %d, b = %d\n", a, b);
        exit(0);
    }

    if (pid > 0)
    {
        printf("in father process a = %d, b = %d\n", a, b);
    }
    return 0;
}

输出结果

in son process a = 11, b = 10
in father process a = 11, b = 10

3.2.8 进程的替换 - exec函数族

进程的替换
exec 函数族,是由六个exec 函数组成的。

  1. exec 函数族提供了六种在进程中启动另一个程序的方法。
  2. exec 函数族可以根据指定的文件名或目录名找到可执行文件。
  3. 调用 exec 函数的进程并不创建新的进程,故调用 exec 前后,进程的进程号并不会改变,其执行的程序完全由新的程序替换,而新程序则从其 main 函数开始执行。

exec函数族取代调用进程的数据段、代码段和堆栈段。

#include <unistd. h)
int execl(const char *pathname, const char *arg0, NULL)
int execlp(const char *filename, const char *arg0,..NULL);
int execle(const char *pathname, const char *arg0,…, NULL,char *const enyp[]);
int execv(const char *pathname,  char *const argy[]);
int execvp(const char *filename, char *const argy[]);
int execve(const char *pathname, char *const argy[], char *const enyp[]));

六个exec函数中只有 execve,是真正意义的系统调用(内核提供的接口),其它函数都是在此基础上经过封装的库函数。
l (list): 参数地址列表,以空指针结尾;
    参数地址列表: char *arg0, char *argl, ..., char *argn, NULL
v (vector): 存有各参数地址的指针数组的地址;
	使用时先构造一个指针数组,指针数组存各参数的地址,然后将该指针数组地址作为函数的参数;
p (path): 按 PATH 环境变量指定的目录搜索可执行文件。
    以p结尾的 exec 函数取文件名做为参数。当指定filename 作为参数时,若 filename 中包含/,则将其视为路径名,并直接到指定的路径中执行程序;
e (environment): 存有环境变量字符串地址的指针数组的地址。
    execle和execve改变的是exec启动的程序的环境变量 [新的环境变量完全由 environment 指定],其他四个函数启动的程序则使用默认系统环境变量。

注意:
exec 函数族与一般的函数不同,exec 函数族中的函数执行成功后不会返回。只有调用失败了,它们才会返回失败后从原程序的调用点接着往下执行。
在平时的编程中,如果用到了 exec 函数族,一定要记得加错误判断语句

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main(int argc, char const *argv[])
{
    pid_t pid;
    if (((pid = fork()) < 0))
    {
        perror("fail to fork");
        exit(1);
    }
    else if (pid > 0)
    { // 父进程
        printf("this is a parent process\n");
        wait(NULL);
        printf("the child process has quited\n");
    }
    else
    { // 子进程
        printf("this is a son process\n");
        printf("hello world\n");
    }

    return 0;
}

输出结果

this is a son process
this is a parent process
hello world
the child process has quited
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main(int argc, char const *argv[])
{
    pid_t pid;
    if (((pid = fork()) < 0))
    {
        perror("fail to fork");
        exit(1);
    }
    else if (pid > 0)
    { // 父进程
        printf("this is a parent process\n");
        wait(NULL);
        printf("the child process has quited\n");
    }
    else
    { // 子进程
        printf("this is a son process\n");
/* exec 函数族用来调用shell命令 */
#if 1
        // 不带p的函数,命令的路径一定要用绝对路径,如/bin/ls
        if (execl("/bin/ls", "ls", "-l", NULL) == -1)
        {
            perror("fail to execl");
            exit(1);
        }
#endif

#if 1
        // 带p的函数,命令的路径可以是相对路径,也可以是绝对路径
        if (execlp("ls", "ls", "-l", NULL) == -1)
        {
            perror("fail to execl");
            exit(1);
        }
#endif

#if 1
        // 带v用来传入指针数组
        char *str[] = {"ls", "-l", NULL};
        if (execv("/bin/ls", str) == -1)
        {
            perror("fail to execv");
            exit(1);
        }
#endif

#if 1
        /* exec函数族调用可执行文件*/
        if (execl("./hello", "./hello", NULL) == -1)
        {
            perror("fail to execl");
            exit(1);
        }
#endif

#if 1
        /* exec函数族调用shell脚本*/
        if (execlp("./myshell.sh", "./myshell.sh", NULL) == -1)
        {
            perror("fail to execl");
            exit(1);
        }
#endif

        // exec函数族取代调用进程的数据段、代码段和堆栈段
        // 所以当exec函数执行完毕后,当前进程就结束,所以进程后的代码就不会执行
        printf("hello world\n");
    }

    return 0;
}

输出结果(只输出了第一个案例的结果,其他的需要注释执行,因为执行完毕后,进程结束,就跳出了,无法执行后面的内容)

this is a parent process
this is a son process
总用量 680
-rwxrwxr-x 1 spider spider 67464 2月  22 17:20 01_fork
-rwxrwxr-x 1 spider spider 67408 2月  22 17:40 02_fork
-rwxrwxr-x 1 spider spider 72136 2月  22 17:51 03_fork
-rwxrwxr-x 1 spider spider 59576 2月  22 17:58 04_sleep
-rwxrwxr-x 1 spider spider 76344 2月  23 09:58 05_wait
-rwxrwxr-x 1 spider spider 49512 2月  23 10:29 06_waitpid
-rwxrwxr-x 1 spider spider 67552 2月  23 10:39 07_atexit
-rwxrwxr-x 1 spider spider 67440 2月  23 11:00 08_vfork
-rwxrwxr-x 1 spider spider 67504 2月  23 11:07 09_vfork2
-rwxrwxr-x 1 spider spider 73920 2月  23 11:50 10_exec
-rw-rw-r-- 1 spider spider    30 2月  22 17:44 file.txt
the child process has quited

标签:02,22,process,pid,2024,exit,printf,进程,include
From: https://www.cnblogs.com/hasaki-yasuo/p/18029371

相关文章

  • AtCoder WTF 2019 B Multiple of Nine/南外集训 2024.2.23 T1
    给定\(q\)个区间\(\{[l_i,r_i]\}\),计算满足条件的长度为\(n\)的十进制数码串\(S\)的个数\(\bmod10^9+7\):\(\foralli\in[1,q],num(S[l_i,r_i])\equiv0\pmod9\)。其中\(num(T)\)表示数码串\(T\)代表的整数,\(T[a,b]\)表示子串\(T_aT_{a+1}\dotsT_b\)......
  • 02. 安装 Unity 引擎和代码编辑器
    下载并安装Unity访问网站unity.cn,在右边点击下载Unity。如果没有Unity账号,先注册账号,然后登陆账号。首先下载UnityHub,安装UnityHub,获取个人免费许可,再安装编辑器代码编辑器有VisualStudio、VisualStudioCode、Rider具体怎么用见下面的链接https://learn.microso......
  • 【2024-02-12】连岳摘抄
    23:59明月高悬夜空,眼下是春天。我想起了你,内心是完整的。                                                 ——费尔南多·佩索阿当世上没有一个人爱我们,周边全是陌......
  • 【2024-02-11】连岳摘抄
    23:59春何曾说话呢?但她那伟大潜隐的力量,已这般的温柔了世界了!                                                 ——冰心爱的一个重要体现是“爱屋及乌”。一个人爱......
  • 2024.2.22 初三集训模拟测试4
    终于挽回了一点颜面。(模拟赛最水的一集)排名T1打赌不得语,暗相思,两心之外无人知。一直记录这骰子的上面、正面和右面。先把暴力打出来,然后优化一下就行。同一行翻转的时候一直是四个状态循环,随便处理一下就行。一顾倾城,再顾倾国。#include<bits/stdc++.h>#definein......
  • P6646 [CCO2020] Shopping Plans 题解
    好好玩的题。思路对于前\(K\)小方案问题。我们可以考虑当前方案对下一个方案的转移。重点在于转移的最优化与不重不漏。只有一种种类假设没有\(l,r\)的限制怎么做。我们不妨把所有价格排序。发现一种状态转移到另一种状态,无异与将其中已选择的一个物品不选,选择他后面......
  • 信息之路计划(2024.3——2024.5)
    写在前面:马上就要退役了,真的要为\(HNMFS\)\(2024\)选拔考试做好准备了。cy推荐博客:Alex_Wei(%%%)。Part1———针对思维思维能力远远不够,需要训练思维能力。最近在比赛打得比较多,但是\(AT\)总是只打到\(C\)或\(D\),CF打得最好的一次就是切掉了\(D\)(\(Div3\)),总的来说......
  • 2024省选模拟26联测23
    T1首先,存在一个显然的事情:若集合\(S\)满足要求,那么\(S\)的任何子集也满足要求。还有一个比较显然的事实:对于一个合法的集合,其每个元素的位置一定在范围的交内。难道要用奇怪的容斥???但是好像根本容斥不了。。。。哈哈。能不能考虑减去不合法的状态?也许可以连边找完全图???好......
  • 2.22前总结
    2.1[CQOI2011]动态逆序对[HEOI2016/TJOI2016]序列2.2[BZOJ3730]点分树|震波(模板)2.3[ZJOI2015]幻想乡战略游戏2.42.5[HNOI2015]开店[SDOI2011]消耗战2.6考试(270pts,rk1)2.7-2.17替罪羊树2.18-2.19考试+题解2.20[SDOI2015]寻宝游戏2.21-2.22考试+题解总结:做题......
  • 2024.2.22 梦想 在什么地方 总是那么令人向往
    字符串太难了。今天早上起来牙又疼了,很难受。UOJ461考虑当前已经把整张图分成了\(L,R\)两个点集,考虑extend一个点进来。可以使用二分的方式,具体的将未加入的点按任意顺序排列,二分一个前缀并断掉\(L,R\)与这个前缀的所有边,找到一个最小的前缀满足此时不连通,此时对于这个......