Little_sk

动态规划LIS（最长上升子序列）12345678910111213141516//复杂度O(nlogn)int n;cin>>n;vector<int> v(n+5);//原始数据int len = 0;for(int i= 1;i<=n;i++) scanf("%d",&v[i]);vector<int> stk;//stk[i]表示长度为i+1的上升子序列，末尾最小是多少。for(int i = 1;i<=n;i++){ if(stk.empty() || v[i] > stk.back()){//如果能接在后面 stk.push_back(v[i]); }else{//如果不能，就在stk中找第一个大于等于v[i]的stk[t],用v[i]替换 int t = lower_bound(stk.begin(),stk.end(),v[i]) - stk.begin(); stk[t] = v[i]; ...

Educational Codeforces Round 168 (Rated for Div. 2) A. Strong Password题意给你一个只含有小写字母的字符串S， 它的价值为： 第一个字母的价值为2。 之后每个字母，如果和上一个字母相同，价值为1，否则价值为2。 你现在需要向S中插入一个任意字符，使得插入后的字符的代价尽可能大。输出插入字符后的字符串。 思路如果存在两个相邻相同字母， 那么我们就在他们中间插入一个不同的字母，会使得总的代价加三。 如果上述条件不成立， 我们就在最后一个字符的后面加上一个不同的字母，使得总的代价加二。 代码 123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define int long long#define rep(i,l,r)...

Pinely Round 4 (Div. 1 + Div. 2) A. Maximize the Last Element题意给一个长度为$n$的数组 , (n为奇数) ， 每次你可以删除数组中相邻的两个数，直到数组剩下一个数，问数组最终剩下的那个数最大为多少。 思路可以发现， 我们最终只有可能留下奇数位的元素$a_1,a_3,…,a_n$ ，对其取max即可。 证明： 整个数组中有$\frac{n+1}{2}$ 个奇数数位， $\frac{n-1}{2}$ 个偶数数位， 即奇数下标一定比偶数多一个， 而对于每次删除操作，一定会删除一个奇数下标的元素和一个偶数下标的元素（因为二者相邻）， 并且不会改变其他下标的奇偶性， 因此进行$\frac{n-1}{2}$ 轮删除后， 奇数下标只剩$1$ 个，而偶数下标剩0个。 代码12345678910111213141516171819202122232425#include<bits/stdc++.h>using namespace std;#define IO...

题目链接https://codeforces.com/contest/1996 A. Legs题意一只鸡有两条腿，一只牛有四条腿，一共有$n$($n$是偶数)条腿，问最少多少只动物。 思路全是牛的时候动物数量最多， 所以$ans = \lceil \frac{n}{4} \rceil$ 代码123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define int long long#define rep(i,l,r) for(int i = l;i<=r;i++)#define per(i,r,l) for(int i = r;i>=l;i--)const int INF = 0x3f3f3f3f3f3f3f3f;typedef pair<int,int> PII;void solve(){ int n;...

比赛链接https://codeforces.com/contest/1995 A. Diagonals题意给定一个$n*n$ 的矩阵， 定义对角线为$i+j$ 相同的值，其中$i$为行号，$j$为列号 。 给你k个棋子要放在这么一个$n*n$ 的矩阵中， 问最少需要占据多少个对角线。 思路对角线的长度为 $n,n-1,n-1,n-2,n-2,…,1,1$ 。 我们按照对角线的长度从大到小按顺序填充棋子即可。 代码1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define int long long#define rep(i,l,r) for(int i = l;i<=r;i++)#define per(i,r,l) for(int i =...

比赛链接https://codeforces.com/contest/1988 A. Split the Multiset题意起初$S$中只有一个数字 $n$ , 你每次操作可以选择$S$中的一个任意一个数$x$，将他拆分成最多k个数，并且这k个数的和仍为$x$ ，问最少需要多少次拆分，能让$S$中只剩下$n$个$1$ 思路可以发现，每次拆分出$k-1$ 个 1 效率最高。 所以对于$n,k$ ,我们有总拆分次数为$\lceil \frac{n-1}{k-1} \rceil$ 。 代码123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define int long long#define rep(i,l,r) for(int i = l;i<=r;i++)#define per(i,r,l) for(int i =...

牛客周赛 Round 51比赛链接 A.小红的同余题意给一个奇数m，请你找出一个数`$x$ ($0 \le x < m$) 使得 $2x \equiv 1 (mod\ m)$ 思路$2x \equiv 1(mod \ m)$ 即 $2x$ 取余m等于1. 那么由于m是奇数， 很容易想到一个方案 $2x = m+1$ ， 即$x = \frac{m+1}{2}$ 代码123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define int long long#define rep(i,l,r) for(int i = l;i<=r;i++)#define per(i,r,l) for(int i = r;i>=l;i--)const int INF = 0x3f3f3f3f3f3f3f3f;typedef...

2024-7-4 虽然最终没有成功配置好qqbot，但是感觉这个过程还是值得记录的，所以写出了下文 最终因为登陆qq时的code45问题导致没有成功登录，据说更换qq号或者配置签名服务器是有可能可行的。 安装环境安装mcl（mirai的控制台）创建一个文件夹mcl 并进入文件夹 1mkdir mcl && cd mcl 寻找适合你的操作系统的的mcl安装包 (下载链接)，将安装包下载到刚刚创建的文件夹中 下面shell指令以mcl-installer-1.0.7-linux-amd64为例 1wget https://github.com/iTXTech/mcl-installer/releases/download/v1.0.7/mcl-installer-1.0.7-linux-amd64 赋予可运行权限，运行 1chmod +x...

搞了一天的mysql远程连接， 也算是踩过坑了，这里记录一下 如果你的mysql无法被远程连接，那么请依次检查如下条件： 1. 服务器的防火墙（安全组）放行端口如果mysql服务在云服务器上运行， 那么请检查云服务器是否将端口3306开放。 如果没有开放请设置为通行状态。。这里不同的云服务器厂商的截图不同，我这里给出华为云的安全组设置 华为云： 2. 启动mysql的远程连接服务在命令台中使用mysql -uroot 进入你的mysql数据库。1mysql -uroot 选择mysql库1use mysql检查user表中的host和User信息。1select host,User from user;如果你的root字段对应的host是localhost，那么代表root账户只能本地登录。123456789+-----------+------------------+| host | User |+-----------+------------------+| localhost | root ||...

题目链接 A. Card Exchange题意给你n个牌，每个牌都有一个数字。 每次你可以选择恰好k个相同数字的牌， 然后将他们替换为任意的k-1张牌。（这k-1张牌的上的数字任意） 问在经过一些操作后，最终能剩下的牌的数量最少是多少。 思路最终剩下牌的数量 = n - 最多执行的操作次数。 所以我们很明显地发现，如果起初不存在相同的k个数，那么就无法进行操作，直接输出n即可。 给出结论，如果可以进行第一次操作，那么就可以使得最终牌的数量变为k - 1。 下面是证明： 我们设当前有n张牌 ， 在满足”存在相同的k张牌“的前提下， 有如下两种情况： 只有k张牌，且全部相同。那么再进行一次操作就可以实现最终剩下k-1张牌。 除了这k张牌之外，还有其他的牌（设他的值为num），那么我们就可以选择k-1张num来替换起初的k张相同牌，...