[SCOI2011]棘手的操作 前言 不得不说，这题得劲。因为这几天复习数据结构都疯了QwQ，一来就想码并查集+线段树，但是想了一想(wtcl)，似乎不太容易维护每个块。emmm，然后去网上看看题解，发现竟然可以用堆合并与删除解决，以简单方法吊打难题 分析 纵观全局，可以先确定能用并查集。每一个都需要维护。而需要维护的则是每一个块的最大值，每一个块有哪些节点 维护方法：因为既要求所有节点中的最大值，也要求各个块中的，那就对全局以及每一个块都建立一个堆，同时维护一个容器 c [ i ] 表示在块 i 中的有哪些节点。因为每次对一个点进行修改时，不能直接提出来进行修改(即先进行pop找到节...

Perfect Security 题意 给出一个n，两个长度为n的数组（分别记为 a , p ），问如何排列p数组使得a [ i ] ^ p [ i ]的 最后的结果排列字典序最小 分析 贪心的想，因为要结果排列字典序最小，那第一个结果得最小，第二个类似....那就可以对每一个a [ i ] 都进行查询操作，求得与他异或结果最小的 p[ i ] ,同时标记 p [ i ] 表示他已经被用过了 代码 #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX usi...

Vitya and Strange Lesson 题意 n个数，m个操作，对于每一个操作 首先给出一个数 x , 每一个 a [ i ] 更新为与 x 按位异或的结果 求出这 n 个数的 Mex 分析 首先这 m 个操作的 x 是可以重合在一起的，也就是说，并不用每输入一次 x 就将数组更新 求Mex：这个Mex是在数组中最小的没有出现过的数，联想我们已经建立的trie树，如果没有异或操作，只询问 Mex那其实就是在 trie 上找最靠左的一个空位。那这个呢？不就是带了个x呗。尽量走一条与x按位异或结果相同的道路。很明显，因为这个数要不存在，说明节点下方的子节点不能将空位全部占满，否则只...

奶牛异或 分析 先假设s [ i ] = a [ 1 ] ^ a [ 2 ] ^ ... ^ a [ i ]，那么 在每次将 a [ i ] 加入树的时候，记录它的尾节点对应的是哪一个下标 代码 /* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=1e5+10; int n,tot,sum; int a[N],tr[2][N*20],be[20*N...

The XOR Largest Pair 分析 一道模板题，先将所有的数按数位从高到低加入到字典树中，从最高位到最低位贪心 代码 /* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=1e5+10; int n,tot; int a[N],tr[2][N*20]; inline void insert(int x) { int rt=0; f...

前言 自己还是好菜啊qwq B Hyperdrome 题意：给一个整数n以及一串长度为n的字符串。求他有多少个子区间中的字符能够通过重新排列形成一个回文串。 分析： 因为能够重新排列，所以不能直接用manacher(这是一个悲伤的故事)。那我们就考虑一个区间能够通过重新排列形成回文串的条件 回文串： “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。 即镜像对称。那么他们每一个字符的出现次数只有两种情况：1.全部都是偶数次 2.一个是奇数次，其余全部是偶数次。考虑他们的次数对二取模，状态压缩每一个字符的出现次数。 对于情况一：因...

前言 好题很多 A Fractions 题意：给出一个n，构造两个数组满足 分析：让我们推导一下，假设存在两个数x/a,y/b使得上式成立(为最简式)那么可以得知 a * b = n,枚举n的因数，然后可以得到b，因为是分数，再通过枚举x来计算出y的结果，即for (ll i=2;i<=sqrt(n);i++) if(n%i==0)//枚举因子a for (ll j=1;j<i;j++) if((n-1-j*n/i)%i==0)//枚举分子x，求出y的值 { print...

前言 从23号26号，终归还是找了时间来补了几道题，确实还是太菜了。只勉强A了6道，只要涉及到一些数论或是高级数据结构or 算法，基本上就没思路了。但总归还是得总结一下，也希望能对补题的同学尽绵薄之力 A Laminar Family 题意：有n个点组成的树，有n-1条边。给出m条树上的路径，判断他们是否相互包含。如果任意两条路径要么不相交，要么包含，则输出“yes”，反之，输出“no” 简要思考： 先明确是什么意思这是两条的情况，那么多条边怎么去判断呢？如果要去判断这几条边是否相交，只需要判断他所在的位置是否只有一种颜色的边(由图)，这就是为什么许多题解称之为区间染色类的原因。 解法...

The Battle of Chibi 分析 这题不用优化?状态设计：设f [ i ] [ j ] ：长度为 i ，以 a [ j ] 为结尾的严格上升子序列如果要优化的用树状数组+离散化，可以减少一重循环 代码(普通) int T;scanf("%d",&T); for (int u=1;u<=T;u++) { memset(f,0,sizeof(f)); scanf("%lld%lld",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&amp...

Cleaning Shifts 分析 此类问题似被统称为——最小区间覆盖问题。首先考虑最简单的转移方程表示覆盖[1,b[i]]的区间的最小代价。考虑优化——快速找到区间最小值。只需要建立一棵线段树，每次查询对应区间，更新。 代码 //#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* 区间最小覆盖问题 ...

起床困难综合症 分析 为什么有人说他是dp呢可以发现直接枚举m可以得到30分的好成绩ヽ(￣▽￣)ﾉ虽然m不能枚举完，但是把其表示成二进制枚举每一位还是可以做到的。因为每一位只有0|1的情况，根据贪心，从高位开始，判定每一位为0|1能否造成伤害，肯定是先判定0能否使这一位最终答案为1，否则去判断1能否使这一位为1 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m; char s[10]; int id[N],a[N],f[31][N]; int main() { ...

Book of Evil 分析 如果想要作为一个放置点，那么一个点距离一个魔鬼的最大值不能超过 d 。考虑到最大距离的产生方式——子树内部以及外部。那么可以分两步做 求出一个节点距离子树内部的鬼的最远距离从叶子结点更新到根节点 开始更新子树外的最远距离，dfs一遍，从上往下更新。 更新方式：记录一个最大值(f)与次大值(g)，一个点要么从父节点的最远距离(dis)更新过来，要么从父节点的f或g数组更新过来。 注意：dis数组：以i为根节点的子树外的鬼到i最最远距离。所以在统计答案的时候要dis与f都不大于d 代码 #include<iostream> #include&...

飞扬的小鸟 分析 直接进入正题 单取一个位置来看，假设当前为第 i 列，高度为 j ，这个高度要么是从位置 i - 1 落下来，要么则是点击屏幕飞上来的，这难道不是一个状态转移方程？即枚举当前位置和高度，设为f [ i ] [ j ]，则 但是注意，这个空间是有限的——高度不可能低于1或高于m，所以得单独列出考虑。 scanf("%d%d%d",&n,&m,&k);//输入 for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),bird[i].l=0,bird[i].h=m+1; //每一个位置的...

[ZJOI2006]物流运输 分析 方法一：这是我一开始想到的一种方法。我可以先预处理出所有的可行路径，因为m范围较小。一个dfs深搜过去，加一个状态压缩，就能得到路径上所有的节点以及路径的花费。剩下的就是dp的事情了。选出每一天的可行路径，然后枚举前一天走的路径。似乎是2^18*2^18，复杂度略大，可以优化一下。代码没来得及码。。。 方法二：这是小菜鸡发现自己的状压要爆炸，于是点开题解开始厚颜无耻学习的结果。主要是要通过spfa预处理出一个co [ i ] [ j ] : 第 i 天到第 j 天走的最短路长度，然后就可以直接dp了 代码(方法二) #include<bits/...