思维训练
T1
在 \([l,r]\) 区间中找两个不同的数\(x,y\) ，使得 \(l \le \gcd(x,y) \le r\)
\(solution\) ：
只需要判断 \(2 \times l\) 在不在这个区间里面就可以，可以证明出这个是最小的一组满足条件的数了。
T2 3533 KLO-Bricks
贪心和优先队列可以再洛谷上过去，但是 \(ACwing\) 上面过不去，会 \(TLE\) ，洛谷题解里面第一个可以过 \(ACwing\) 的题
\(solution\)：
首先先在一开始记录的时候就把起点和终点的数量给减掉，然后减掉之后要特判一下这个时候剩下的数量是否大于等于 \(0\) ，也就是说如果起点和终点是一个颜色然后这个颜色的数量只有 \(1\) 个的话是无解的。
然后把这些数量都加到一个优先队列里面去，每一次都取里面堆顶的数，也就是数量最多的数来分隔，如果当前数和前面一个数相同的话就再在堆里面取一个数出来。
最后遍历一遍看看能不能满足条件就可以了。
int k;
int p,qq;
int n;
int w[N];
struct node{
int cnt,id;
bool operator < (const node &t) const{
if (cnt == t.cnt) return id != qq;
return cnt < t.cnt;
}
};
int main(){
k = fr();
p = fr(),qq = fr();
priority_queue<node> q;
for (int i = 1; i <= k; i ++) {
w[i] = fr();
n += w[i];
if (i == p) w[i] --;
if (i == qq) w[i] --;
if (w[i]) q.push({w[i],i});
}
w[1] = p;
w[n] = qq;
if (q.top().cnt > n - q.top().cnt) {
cout << 0;
return 0;
}
int la = p;
bool flag;
for (int i = 2; i < n; i ++) {
flag = false;
auto t = q.top();
q.pop();
if (t.id == la) {
if (q.empty()) {
cout << 0;
return 0;
}
auto u = q.top();
q.pop();
w[i] = u.id;
la = w[i];
u.cnt --;
if (u.cnt) q.push(u);
q.push(t);
flag = true;
continue;
}
w[i] = t.id;
la = w[i];
t.cnt --;
if (t.cnt) q.push(t);
flag = true;
if (!flag) {
cout << 0;
return 0;
}
}
for (int i = 1; i <= n; i ++) {
fw(w[i]);
if (i != n) kg;
}
return 0;
}
T3
给定一个简单有向图，给每一条边染色，求没有一个环所有边的颜色都相同的方案，要求所用的颜色尽量少
\(n \le 2 \times 10^5\)
\(solution\)：
无环的话只要一种颜色，有环的话两种颜色即可。
考虑一个环，由树边和返祖边组成，树边标 \(0\)，返租边/横插边表 \(1\)
或者类似 \(tarjan\) 求 \(dfn\)，编号小的向编号大的边标 \(0\)，编号的大的向编号小的边标 \(1\)。因为一个环中肯定会有编号大到小的边和编号小到大的边，所以这样一定可以满足。
T4
给出 \(n\) 的排列，和所有相邻元素的大小关系，构造排列使 \(LIS\) 最短/长
\(n \leq 1e5\)
\(solution\)：
设连续上升段集合为 \(S_1\)，下降段集合为 \(S_2\)
最大是 \(\sum S_{1,i}\)，最小是 \(\max S_{1,i}\)
最大：不放考虑从后往前放，最后一段上升段从 \(n\) 倒着 开始放 \(n-k ...n\)，上升段放完，再把剩下的放到下降段即可
最小：让每一个上升的子段的终点都 \(\gt\) 后面的上升段的终点
我们从前往后放上升段，第一段 \(n-k....n\)，后面从 \(n-k\) 同理放
T5
给定无向图，每个点度数 \(\leq 7\)，四种颜色染色，每个点至多一个相邻的点和它颜色相同，求方案
\(n \leq 25000\)
\(solution\) ：
每个点随机染色，现在有非常多冲突
考虑局部优化调整算法
把每个点调整成和它相邻的点的颜色最少的那个颜色，记这个点为 \(t\)
这样调整，保证了 \(4--4\) 这种同色边数量单调下降
同时这个调整还要考虑对 \(t\) 的影响，然后算贡献最少的
我们这些调整丢到优先队列里面算就行了
T6
给定集合 \(S={d_1,d_2,...,d_n}\)，构造简单无向图 \(G\)，\(|V|=\max d_i+1\)，每个点的度数 \(d_i \in S\)，且所有点的度数完全覆盖 \(S\)
\(n \leq 300\)，\(\max S \leq 1000\)
\(solution\)：
考虑最先处理这个 \(d_n\)
我们选 \(k\) 个点让它的度数为 \(d_n\)，那么之后这些点就不能再次连边了
有一个递归的思路，如果我们能同时处理 \(d_1\) 的话，就可以转化成 \({d_2,...,d_{n-1}}\)
T7 P3069 Cow Lineup G
双指针（？），好像他们说有 \(O(n \log n)\) 的做法，但我没有听懂，故略过
双指针就是把右指针一直向右移动，然后左指针就保证这个区间里面最多只有 \(k + 1\) 种牛，如果不是就一直往左移，然后取一个 \(\max\) 就可以了。
int n,k;
int w[N];
map<int,int> flag;
int main(){
n = fr(),k = fr();
for (int i = 1; i <= n; i ++) {
w[i] = fr();
}
int cnt = 0;
int ans = 0;
for (int l = 1, r = 1; r <= n; r ++) {
if (!flag[w[r]]) {
cnt ++;
}
flag[w[r]] ++;
while (cnt == k + 2) {
flag[w[l]] --;
if (!flag[w[l]]) cnt --;
l ++;
}
ans = max(ans,flag[w[r]]);
}
fw(ans);
return 0;
}