wweiyiのblog

【全程NOIP计划】分治与倍增 分治 分治就是分而治之，化整为零的思想 分治的原理是把困难的大问题化解为简单的小问题 然后先解决小问题，然后根据小问题的答案解决大问题 它本质上不是一个算法，而是一个思想 比如快速幂，倍增求lca，归并排序，线段是cdq分治，甚至后缀数组FFT都利用了分治思想 分治虽然不经常出题，但是也非常有用 快速幂 快速幂可以在O(logb)O(logb)O(logb)的时间复杂度内计算aba^bab 方法很简单 注意到如果b是偶数，那么就可以先计算ab2a^{\frac{b}{2}}a2b​,这样问题的规模就减少了一半 如果b是奇数，那么我们就可以计算ab2a^{\frac{b}{2}}a2b​平方之后再乘a，问题规模同样以不大的代价减少了一般 这里的aba^bab就是大问题，而ab2a^{\frac b 2}a2b​就是小问题了 12345678910111213141516171819long long f(long long a,long long b,long long c){ long long temp=f(a,b/2) ...

【全程NOIP计划】动态规划及优化1 LIS 非常经典，最长上升子序列 设计状态 以f[x]f[x]f[x]表示序列a中以axa_xax​结尾的LIS长度 涉及转移 f[x]=maxi<x,ai≤ax(f[i]+1)f[x]=max_{i<x,a_i\le a_x}(f[i]+1)f[x]=maxi<x,ai​≤ax​​(f[i]+1) DP的状态和转移 一个问题可以DP，是因为这个问题可以从小问题的解推出大问题的解 我们可以从初始状态的解，推出最终状态的解，从而解决问题 本质 首先我们把LIS的问题中的每个状态作为点，放在图上 我们知道f[1]=1f[1]=1f[1]=1，因为单个字符的LIS长度只有1，现在想知道f[4]f[4]f[4]，这就需要转移来实现 如果状态x可以直接抵达y状态，我们就连上x→yx \rightarrow yx→y的有向边 如果我们按照上面的方式画图，我们就可以发现几个性质 1.DP的每一个状态对应着一个点 2.每种可能的转移方式，都对应着一条有向边 3.DP的求解顺序，等同于这张图的拓扑排序 4.必须是有向无环图DAG，否则无法找到...

【全程NOIP计划】初级数据结构2 树状数组 可以用于维护前缀信息（可合并） 优点：代码段，速度快 比如： 给定一个长n的数组，支持操作： 1.将第iii个数aia_iai​加vvv 2.询问区间[l,r][l,r][l,r]中的数的和 lowbit(i)lowbit(i)lowbit(i)：只保留iii的二进制表示中最低位的1 树状数组中，节点iii表示的区间为[i−lowbit(i)+1,i][i-lowbit(i)+1,i][i−lowbit(i)+1,i] 前缀查询 查询区间[1,i][1,i][1,i]的和的时候，由iii可以直接得到[i−lowbit(i)+1,i][i-lowbit(i)+1,i][i−lowbit(i)+1,i]的和，接下来查询[1,i−lowbit(i)][1,i-lowbit(i)][1,i−lowbit(i)]的区间和，重复上面的步骤就可以了 单点修改 修改iii的时候，寻找包含i的所有区间： 第一个包含iii且lowbitlowbitlowbit比iii大的节点是i+lowbit(i)i+lowbit(i)i+lowbit(i) 12345...

【全程NOIP计划】初级数据结构1 在线：每次询问之后，立马可以得到查询结果 离线：知道所有需要查询的值，然后一次输出查询结果 STL中set的用法 用迭代器 并查集 可以支持一些不相交集合的合并和查询 我们可以树形结构来组织数据 同一个集合的元素组成一棵树 因为集合没有交，所以最终构建得到的是一个森林 将树的根节点作为集合的代表元 开始的时候为n个孤立的点 查询一个点所属集合 1234int get(int x){ return fa[x]=(x==fa[x]? x:get(fa[x]));} 这里做了一个路径压缩，使这颗树变得扁平，大大减小了查找的时间 合并 1234void merge(int x,int y){ fa[get(x)]=get(y);} 如果是启发式合并的话，是把较小的树插到较大的树 用处 1.可以做最小生成树 也就是kruskal算法 2.还可以用来判环 P3958 奶酪 思路 实际上处理一个上界，处理一个下界，然后判断上面和下面能不能连通就可以了非常简单 123456789101112131415161...

【解题报告】CSP-S2020 从这一年开始NOIP和CSP正式变为四道题目，两天的考试已经成为历史了 T1 儒略日 思路 当年这道题目把我恶心死了，导致我没办法去NOIP2020 这道题目按理来说就是模拟，中间要处理一下格里高利历的空出的日期，以及公元前和公元后的一些闰年的处理，还有一些月份的处理 时至今日，我还是不想打模拟题 于是暗示了我的完美结局 实际上我们可以预处理四百年的信息，再来根据这个信息稍微改变以及推算一下就好了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define int long longu...

【解题报告】CSP-S2019 Day1 T1 格雷码 思路 一个模拟出来的搜索，当年我考场上得了个不知道多少分 当年找了个一个小时，结果是错的，也只有60pts 1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>#include <cstdio>#include <algorithm>#include <string>using namespace std;unsigned long long n,k;void dfs(unsigned long long n,unsigned long long k){ if(n==0) return ; long long x=(1<<(n-1));//表示有多少个 if(k==0)//如果k为0的话，没有好吧 { for(long long i=1;i<=n;i++) cout<<"0"...

【解题报告】NOIP2018 她开始变了…… Day1 T1 铺设道路 思路 CCF狠起来连自己都抄 就是2013年的积木大赛么 甚至都是春春幼儿园…… 1234567891011121314#include <iostream>using namespace std;int main(){ int n,a,last=0,ans=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a; if(a>last)ans+=(a-last); last=a; } cout<<ans<<endl;} T2 货币系统 思路 题意就是你有 nnn 个数字，然后你要将这些数字加起来，看有没有不能表示的数字 然后看能不能用 m≤nm \le nm≤n 个数字使这些数字的不能表示的数字和原来用 nnn 个数字不能表示数字的集合是同一个集合 我们考虑枚举 自己肯定是有的 我们对已有的...

【解题报告】NOIP2017 Day1 T1 小凯的疑惑 思路 这个是当年选手最后悔的也是大部分人能猜出来但是无法严格证明的题目 我来证明一下 好吧，我不会 但我们直接打表找规律，发现答案就是 ab−a−bab-a-bab−a−b 123456789#include <iostream>using namespace std;long long a,b;int main(){ cin>>a>>b; cout<<a*b-a-b<<endl; return 0;} T2 时间复杂度 思路 巨大模拟 字符串处理 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <iostream>#include ...

【解题报告】 NOIP2016 Day1 T1 玩具谜题 思路 快乐暴力模拟 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>int n,m;using namespace std;struct people{ int dir; char job[150];}a[100005];int b[100005],s[100005];int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i].dir; scanf("%s",a[i].job); } f...

【解题报告】NOIP2015 Day1 T1 神奇的幻方 思路 这不就是按照题目所给信息模拟一下咩？ 过了 12345678910111213141516171819202122232425#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int n;int s[50][50];int main(){ cin>>n; int x=1,y=(n+1)/2; for(int i=1;i<=n*n;i++) { s[x][y]=i; if(!s[(x-2+n)%n+1][y%n+1]) x=(x-2+n)%n+1,y=y%n+1; else x=x%n+1; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<s[i][j]<<" "; cout<<endl...