集训队 题解2019 day

首先发现后缀和前缀比较不好看，所以翻转第二个字符串，记为 $T'$。 这样就变成了操作两个字符串的前缀。 观察发现，操作 $k$ 等价于交换 $S[1\sim k]$ 和 $T'[1\sim k]$，然后翻转 $S[1\sim k]$ 和 $T'[1\sim k]$。 结论 1：同一个下标上的字符对 ......

## Description 给定 $n,k$，求： $$\displaystyle\sum_{i=1}^{n}{\binom{n}{i}\times i^k}$$ $1\leq k\leq 5000,1\leq n\leq 10^9$。 ## Solution 看到那个 $i^k$ 很不爽，但是 ......

首先我们考虑第一种情况怎么处理，显然我们可以给原数列的每个数开一个$vector$，每加一个数丢到对应的$vector$后面就行了。 再看第二个操作，你考虑新加一个数会有什么影响。 原来的两个$vector$是这样的： ![image](https://img2023.cnblogs.com/blo ......

## 题目：[235. 二叉搜索树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/) ### 思路： BST和普通二叉树不同的一点是可以根据特性来找最近公共祖先，只要找到第一个值 ......

[传送门](https://www.luogu.com.cn/problem/AT_arc158_c) ## 题目分析 我们可以先从简单一点的情况开始分析，如果现在 $a_{[i]},a_{[j]}$ 都**不会进位**，那么最后的 $f(a_{[i]}+a_{[j]})=f(a_{[i]})+f( ......

#### 线程管理 ##### 基本概念 1、线程是进程的执行路线，它是进程内部的控制序列，线程是进程的一部分，进程是一个资源单位，而线程是执行单位，线程是进程执行的实体，负责真正的执行 2、线程是轻量级的，没有自己的代码段、数据段、bss段、堆、环境变量、命令行参数、文件描述符、信号处理函数、当前 ......

#### TCP服务端处理多客户端任务： 原来是通过开启子进程来服务不同的客户端，当客户端退出时就关闭该子进程 #### 多路复用： 使用一个进程(有且只有一个主进程)同时若干个文件描述符，这种读写模式称为多路复用 多用于TCP的服务端，用于监控客户端的连接和数据的收发 优点：不需要频繁地创建、销毁 ......

##### 封装socket网络通信模块-network 原因：TCP、UDP客户端、服务端的操作流程固定，所以为了后期使用方便，把socket网络通信封装成网络模块 任务：生成libnw.so共享库 笔试、面试问题：回答原始函数 讲项目：聊封装过程 ##### FTP协议 FTP 的独特的优势同时 ......

A 题解：不会 #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include ......

##### 进程间通信-socket套接字 基本特征：socket是一种接口技术，被抽象了一种文件操作，可以让同一计算机中的不同进程之间通信，也可以让不同计算机中的进程之间通信（网络通信） ###### 本地进程间通信编程模型： 进程A 进程B 创建socket对象 创建socket对象 准备通信地 ......

用的书：《Java从入门到精通》 day1(3.1-3.3): [【Java】从头开始的Java复健day1](https://www.cnblogs.com/ryukirin/p/17610317.html) day2(3.4-3.8): [【Java】从头开始的Java复健day2](https ......

344. 反转字符串 详解 class Solution { public: void reverseString(vector<char>& s) { int left = 0; int right = s.size() - 1; while(left <= right){ // char tmp ......

今天在b站跟学了黑马的前端js课程，因为是第一天学习都对于我们这种学过了的来说其实挺简单的，不过今天一边做公司的项目一边学习多少是有点时间不够的感觉，看样子明天要开二倍看了，下面是今天的笔记 什么是js:javascript是人机交互的一种编程语言js由哪几部分组成:ECMAScript和webap ......

把应用系统比作是保险柜，假如保险柜破了一个洞，这个洞只有少数人知道，没有传播开来，也暂时没有补救的措施，那这个洞就是0day漏洞。 也就是说，这个漏洞处于相对“未知”的状态，一旦被用来发起攻击的话，就会面临“没有补丁”的情况。 而1day呢，就是有洞的问题已经被公开了，保险柜主人也正在组织人来补洞， ......

链接：[P2073 送花](https://www.luogu.com.cn/problem/P2073 "P2073 送花") ## 题意： 有若干朵花，每个有两个属性（美丽值和价格）。你需要维护 $3$ 种操作： - 1.添加一朵花（如果之前有价格相同的忽略此操作） - 2.删除最贵的花 - 3 ......

### 二叉树 #### [114. 二叉树展开为链表](https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/) 给你二叉树的根结点 `root` ，请你将它展开为一个单链表： - 展开后的单链表应该同样使用 `TreeNo ......

在 $S=[1,n]\cap \mathbb Z$ 中选出一个最大子集 $T$ 使得其任意两元素差不为 $x$ 且不为 $y$，求 $|T|$。$n\le 10^9,x,y\le 22$。 通项，打表找规律套结论，或者矩乘。都是错的。考虑一个周期性。 注意到有 $n=x+y$ 的包。上结论，将对于 ......

就是 $m$ 组询问**补图的最小生成树**上的树链最大值。有两种基本思路求这棵树。 第一种，Kruskal，基于找到最小的边使两端点不连通。考虑补图中 $(x,y)$ 的边权，它是原图最小生成树上的树链最大值。从小到大枚举补图的边，相当于从小到大枚举原图最小生成树的边 $(u,v,w)$，然后： ......

一棵树，点权 $a_i(a_i\le n)$，无边权，求 $$\sum_{i\ne j}\varphi(a_ia_j)\text{dis}(i,j)$$ 首先，你没有任何手段求 $10^{10}$ 级别的一堆离散的 $\varphi$。于是 $$\varphi(xy)=\frac{\varphi(x ......

454. 四数相加 II 讲解 class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { //map unor ......

## [题面](https://www.luogu.com.cn/problem/AT_agc064_a) # 题目大意 给定一个正整数 $N$，要求构造一个序列。对于每一个在 $1$ 到 $N$ 之间的整数 $i$，序列中包含了 $i$ 个，并且将该序列首尾相接拼成环后，相邻两项之差大于等于 $1 ......

>作为惩罚，GY被遣送去帮助某神牛给女生送礼物貌,~~~~似是个好差事~~~~ 但是在GY看到礼物之后，他就不这么认为了。 某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)， 他一次可以搬动重量和在w(w题目概述 有N件物品，每件物品有自己的重量，每件物品只能选一次。 选取任意件物 ......

# CF1854D Michael and Hotel 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1854D) [Codeforces](https://codeforces.com/problemset/problem/1854/D) ......

# P2034题解 ## 题目描述 给定一行 $n$ 个非负整数 $a_1 \cdots a_n$。现在你可以选择其中若干个数，但不能有超过 $k$ 个连续的数字被选择。你的任务是使得选出的数字的和最大。 ## 题解 正难则反，考虑将原问题转化为从 $a$ 中选若干数使得，任意两数差不大于 $k$, ......

# ZS Shuffles Cards 题解 我们把每一次抽一些数字牌再抽到 joker 视作一局游戏。 ## 每局期望轮数 首先考虑 $f_i$ 表示每一局游戏抽出 $i$ 张牌的概率。 那么就是先抽出 $i - 1$ 张数字牌，再抽出一张 joker 。 概率就是 ： $$ f_i = \fra ......

## 思路 这个题是一个简单的构造题。~~竟然比 T2 简单，也是少见~~ 我们可以首先从 $1$ 开始不断乘以 $2$，像这样：$1, 2, 4, 8, 16\cdots,2^x$，直到什么时候超过 $n$ 就停止。 这样相邻两个数字就可以凑出 $1, 2, 4, 6, \cdots,2^{x- ......

## 上午/一维数组排序 - 排序：sort，冒泡，选择，插入，计数 复杂度：$O(nlogn),O(n^2),O(n^2),O(n^2),O(n)$ 点击查看代码 ``` #include #include using namespace std; const int N=1e5+10; int ......

## 思路 我们可以让两人先拿 $c$ 里面的，因为 $a$ 和 $b$ 肯定是自己的，那么公共的“我”也要抢的越多越好，所以我们都要先拿 $c$ 里面的。 如果 $c$ 是奇数，那么先手一定多拿 $1$ 个 $c$ 里面的，相当于先手可以拿 $a + 1$ 个，后手可以拿 $b$ 个； 如果 $c ......

[860. 柠檬水找零](https://leetcode.cn/problems/lemonade-change/description/) 数组中只有5,10,20三种数字， * 如果是5，不需要找零 * 如果是10，需要至少有一张5的 * 如果是20，需要一张10的，一张5的，或者3张5的找零 ......

[题面](https://codeforces.com/problemset/problem/1060/E) 由题意可知，在原图中经过边数为 $2$ 的一对点，在新图中经过边数为 $1$。所以每对点在新图中的距离为： $$ \begin{aligned} \lceil \frac{dis(i,j)} ......