每日思维题
Graph and String
题目大意：
给出一个由字符串ss建图的过程。
- 字符仅有$a,b,c$三种，建出的图中第$i$个顶点表示原来的第$i$个字符。
- $i$与$j$有连边，当且仅当$s[i]$与$s[j]$相同或$s[i]$和$s[j]$是相邻的字符（$a$与$b$相邻，$b$与$c$相邻）
现给出由某个字符串$s$建出的图，构造一个字符串使其符合上面的要求要求，或者回答不存在这样的字符串。
解题思路：首先分析题目可以发现这样一件事情，对于出现的$b$来说他是需要连接所有点的，$a$只需要连接相邻的$a$以及$b$即可，$c$的话和$a$同理，那么其实这样子的话我们可以在刚开始的时候处理以下所有和其他点连接的点，赋值为$b$，然后我们可以考虑一件事情，对于$a$和$c$来说相对应的边是不相连的，那么对于原图的补图来说一定是一张二分图，然后我们可以判断二分图并且染色之后再去根据颜色判断，如果两个相邻的边是$a$以及$c$那么就是不行的
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 10;
int mp[maxn][maxn],n,m;
int deg[maxn],col[maxn];
char ans[maxn];
vector<int> edge[maxn];
int flag = 1;
void dfs(int s,int fa)
{
for(auto to:edge[s])
{
if(to == fa) continue;
if(col[to] == -1)
{
col[to] = col[s] ^ 1;
dfs(to,s);
}
else if(col[to] == col[s]) flag = 0;
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;++i) mp[i][i] = 1,col[i] = -1;
for(int i = 1,u,v;i <= m;++i)
{
cin >> u >> v;
mp[u][v] = mp[v][u] = 1;
deg[u]++;
deg[v]++;
}
for(int i = 1;i <= n;++i)
{
for(int j = i + 1;j <= n;++j)
{
if(mp[i][j]) continue;
edge[i].emplace_back(j);
edge[j].emplace_back(i);
}
}
for(int i = 1;i <= n;++i)
{
if(deg[i] == n - 1) ans[i] = 'b';
else
{
if(col[i] == -1) col[i] = 0,dfs(i,0);
}
}
if(!flag)
{
cout << "No\n";
return 0;
}
for(int i = 1;i <= n;++i)
{
for(int j = i + 1;j <= n;++j)
{
if(mp[i][j] && col[i] + col[j] == 1)
{
cout << "No\n";
return 0;
}
}
}
cout << "Yes\n";
for(int i = 1;i <= n;++i)
{
if(deg[i] == n - 1)
{
cout << "b";
}
else if(col[i] == 0) cout << "a";
else cout << "c";
}
return 0;
}Carousel
CF1328D Carousel - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意: 有$q$组询问,每组询问如下:
已知一个有$n(3\le n\le 210^5)$个点的*环,点$i$的类型为$a_i$,现在需要给每个点进行染色,要求相邻不同类型的点的颜色不同且所用颜色数最小.输出颜色数及一种染色方案即可.(颜色从1开始)
注意: $n ≤2*10^5$
解题思路:
其实很容易想到环的颜色种类不多，至多只有$3$
那么我们可以进行这样子的讨论，首先我们可以把这个环分成奇环和偶环，对于偶环来说他有比较好的性质我们直接赋值$1$ $2$交替即可
那奇环呢？分析样例我们可以得出对于两两之间不一样的都是$3$种，反之就是$2$种
同时我们需要特判以下情况，在这个序列中只存在$1$种或者$2$种数字的情况
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn],num[maxn],n;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
int cnt = 0;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
num[a[i]]++;
if(num[a[i]] == 1) cnt++;
}
if(cnt == 1)
{
cout << "1\n";
for(int i = 1;i <= n;++i)
{
cout << "1 ";
}
cout << "\n";
}
else if(cnt == 2)
{
cout << 2 << "\n";
for(int i = 1;i <= n;++i)
{
if(a[i] == a[1]) cout << "1 ";
else cout << "2 ";
}
cout << "\n";
}
else if(n % 2 == 0)
{
cout << 2 << "\n";
for(int i = 1;i <= n;++i)
{
cout << (i & 1) + 1<< " ";
}
cout << "\n";
}
else
{
int flag = -1;
for(int i = 1;i <= n - 1;++i)
{
if(a[i] == a[i + 1]) flag = i;
}
if(a[n] == a[1]) flag = n;
if(flag == -1)
{
cout << "3\n";
for(int i = 1;i <= n - 1;++i)
{
cout << (i & 1) + 1 << " ";
}
cout << "3\n";
}
else
{
cout << "2\n";
for(int i = 1;i <= flag;++i)
{
if(i % 2) cout << 1 << " ";
else cout << 2 << " ";
}
for(int i = flag + 1;i <= n;++i)
{
if(i % 2) cout << 2 << " ";
else cout << 1 << " ";
}
cout << "\n";
}
}
for(int i = 1;i <= n;++i) num[a[i]] = 0;
}
return 0;
}What a Colorful Wall
题目大意: 给定$n$个矩形，每个矩形有一定的颜色，矩形之间可以相互覆盖，问在$n$个矩形覆盖之后整个坐标系中最多存在着多少种颜色
解题思路: 首先先思考这样子的一件事情，因为矩形具有覆盖性，因此我们可以从后往前去放置矩形，因为后面的矩形总是不会被前面的矩形所覆盖，首先对于相同的$x$坐标的一个区域来说，如果一个矩形的高度小于另外一个的高度并且它的，那么它在这个$x$轴影响的$y$上面是被覆盖的，那么对于其他的$x$呢？我们可以利用一个类似于扫描线的做法，遍历相对应的$x$轴遍历过去即可，然后用并查集维护相对应的$y$是否已经是在同一条线上面
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e3 + 10;
int fa[maxn * 2],n,ans[maxn];
vector<int> posx,posy;
vector<array<int,5>> pos;
void init()
{
for(int i = 0;i <= 8010;++i) fa[i] = i;
}
int getf(int x)
{
if(x == fa[x]) return x;
fa[x] = getf(fa[x]);
return fa[x];
}
void merge(int x,int y)
{
x = getf(x);
y = getf(y);
fa[x] = y;
}
int getx(int x)
{
int px = lower_bound(posx.begin(),posx.end(),x) - posx.begin();
return px;
}
int gety(int y)
{
int py = lower_bound(posy.begin(),posy.end(),y) - posy.begin();
return py;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1,x1,y1,x2,y2,col;i <= n;++i)
{
cin >> x1 >> y1 >> x2 >> y2 >> col;
posx.push_back(x1),posx.push_back(x2);
posy.push_back(y1),posy.push_back(y2);
pos.push_back({x1,y1,x2,y2,col});
}
sort(posx.begin(),posx.end());
sort(posy.begin(),posy.end());
posx.erase(unique(posx.begin(),posx.end()),posx.end());
posy.erase(unique(posy.begin(),posy.end()),posy.end());
for(auto &now:pos)
{
now[0] = getx(now[0]),now[2] = getx(now[2]);
now[1] = gety(now[1]),now[3] = gety(now[3]);
// cout << now[0] << " "
}
int tot = posx.size();
for(int i = 0;i <= tot;++i)
{
init();
for(int j = n - 1;j >= 0;--j)
{
auto now = pos[j];
if(now[0] <= i && now[2] > i)
{
int ny = getf(now[1]);
while(ny > now[3])
{
merge(ny,ny - 1);
ans[now[4]] = 1;
ny = getf(ny);
}
}
}
}
int res = 0;
for(int i = 1;i <= n;++i) res += ans[i];
cout << res << "\n";
return 0;
}Chemical table
题意: 给定一个$n * m$的棋盘，给定$q$个元素，这些元素在棋盘的上面，如果对于一个$2 * 2$的矩形来说，这个矩形中的三个值都存在但是还有一个值不存在，那么这个值也会自动生成，问最多要加多少个值才能使得这个棋盘最后是满的
解题思路: 首先我们先分析最后的棋盘的状态，最后棋盘的状态是一个满的形式，对于棋盘来说我们可以把它看成一个二分图的形式，左边是列右边是行，然后我们去分析最终态，最终态是行和列的点都在一个连通块中；然后我们分析题目给定的条件，每次对于一个行和列连边，然后对于生成那个新点来说，实际上并不会影响当前连通块的情况，那么我们只需要连接所有的边，然后找出连通块的数量是多少，最后再加上相对应的边即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
int f[maxn],n,m,q;
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
x = getf(x);
y = getf(y);
f[x] = y;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m >> q;
for(int i = 1;i <= n + m;++i)
{
f[i] = i;
}
for(int i = 1,x,y;i <= q;++i)
{
cin >> x >> y;
merge(x,y + n);
}
int ans = 0;
for(int i = 1;i <= n + m;++i)
{
if(getf(i) == i)
{
ans++;
}
}
cout << ans - 1 << "\n";
return 0;
}Cross Swapping
题意: 给定一个$n * n$的矩阵，可以选定一个$k$，交换所有的$mp[i][k]$和$mp[k][i]$，可以进行这样子的操作若干次，问在进行操作
之后这个矩阵字典序最小是什么样子的
解题思路: 模拟每一次交换的过程，我们发现实际上$mp[i][j]$只会和$mp[j][i]$交换，既然这样那么实际上我们就很好去操作了
如果我们要交换$mp[i][j]$和$mp[j][i]$，我们只需要选定$k = i$ $or$ $k = j$,如果不交换我们可以两个都不选或者两个都选偶数次
然后的话我们可以用并查集来维护相对应的关系，用类似于敌人朋友的并查集来维护这个东西。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
int mp[maxn][maxn],n;
int f[maxn];
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
x = getf(x);
y = getf(y);
f[x] = y;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
{
cin >> mp[i][j];
}
}
for(int i = 1;i <= 2 * n;++i) f[i] = i;
for(int i = 1;i <= n;++i)
{
for(int j = i;j <= n;++j)
{
if(mp[i][j] < mp[j][i])
{
//not change
if(getf(i) == getf(j + n)) continue;
merge(i,j),merge(i + n,j + n);
}
else if(mp[i][j] > mp[j][i])
{
//change
if(getf(i) == getf(j)) continue;
merge(i,j + n),merge(i + n,j);
}
}
}
for(int k = 1;k <= n;++k)
{
if(getf(k) > n) continue;
for(int i = 1;i <= n;++i)
{
swap(mp[i][k],mp[k][i]);
}
}
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
{
cout << mp[i][j] << " \n"[j == n];
}
}
}
return 0;
}
Mikasa
题意: 给定$T$组数据，每组数据有一个$n$和$m$,给定一个序列从$n \bigoplus 0,n \bigoplus 1,…,n \bigoplus m$问这个序列中没有出现过的最小数字是多少
解题思路: 考虑再这个序列中出现过的数字$k$,那么存在$x$使得式子$n \bigoplus x = k,x ∈ [0,m]$成立,那么对于上面的式子其实可以等价于$n \bigoplus k = x, 0 \leq n \bigoplus k \leq m$，那么我们要求的答案也就是去找一个最小的$k$使得$n \bigoplus k \geq m + 1$，那么这样子的话我们就可以进行按位考虑，假设$p = m + 1$,我们从高位开始考虑，如果这个位置上面$n_i = 1,p_i = 0$,那么直接break掉，如果$n_i = 0,p_i = 1$,则需要加上这一位的贡献
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
int p = m + 1;
int ans = 0;
for(int i = 30;i >= 0;--i)
{
int ni = (n >> i & 1);
int pi = (p >> i & 1);
if(ni == 1 && pi == 0) break;
if(ni == 0 && pi == 1) ans += (1 << i);
}
cout << ans << "\n";
}
return 0;
}Count Triangles
题意: 给定四个数字$A,B,C,D$使得三角形的三个边$a,b,c$分别满足$A \leq a \leq B, B\leq b \leq C,C \leq c \leq D$,问这样子的三元组$a,b,c$有多少
解题思路: 其实拿到题目的时候我们可以直接考虑枚举，但是直接分别枚举$a,b$是否在区间里面时间肯定是有点问题的，但是既然是三角形我们其实如果知道$a + b$是多少我们就能找到对应的第三条边是多少，既然这样的话那么我们只需要枚举$a + b$中有多少个就可以了，然后通过差分数组去维护相对应的数量，那么对应的$a + b$在数据范围中对应的第三条边可能是啥呢？其实是在一个范围中，我们在$a + b - C$和$D + C - 1$中取小的就可以了，当然需要特判一下$a + b - C$小于$0$的情况
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
vector<int> pa,pb,pc;
int A,B,C,D;
const int maxn = 2e6 + 10;
int sum[maxn];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> A >> B >> C >> D;
for(int i = A;i <= B;++i) sum[i + B]++,sum[i + C + 1]--;
for(int i = 1;i <= 3 * D;++i) sum[i] += sum[i - 1];
int ans = 0;
for(int i = 1;i <= 3 * D;++i)
{
ans += sum[i] * max(0ll,min(i - C,D - C + 1));
}
cout << ans << "\n";
return 0;
}Integers Have Friends
题意: 给定一个长度为$n$的序列，序列中每个元素的数值各不相同，找一个最长的子序列使得这个子序列中$mod $ $m$都是相同的数字
解题思路: 因为题目中需要找到$a[i]$ $mod$ $m$ $=$ $a[j]$ $mod$ $m$,那么对于这样子的式子我们可以先进行一个化简，那么就是$(a[i] - a[j]) $ $ mod $
$m = 0$,然后我们可以对这个序列进行一个处理，处理之后二分找最长的即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn],n;
int b[maxn],tree[maxn << 2];
inline void build(int k,int l,int r)
{
if(l == r)
{
tree[k] = b[l];
return;
}
int mid = (l + r) >> 1;
build(k << 1,l,mid);
build(k << 1 | 1,mid + 1,r);
tree[k] = __gcd(tree[k << 1],tree[k << 1 | 1]);
return;
}
inline int query(int k,int l,int r,int lx,int rx)
{
if(l == lx && r == rx)
{
return tree[k];
}
int mid = (l + r) >> 1;
int ans = 0;
if(rx <= mid) ans = __gcd(ans,query(k << 1,l,mid,lx,rx));
else
{
if(lx > mid) ans = __gcd(ans,query(k << 1 | 1,mid + 1,r,lx,rx));
else ans =__gcd(ans,__gcd(query(k << 1,l,mid,lx,mid),query(k << 1 | 1,mid + 1,r,mid + 1,rx)));
}
return ans;
}
int check(int x)
{
for(int i = 1;i <= n;++i)
{
if(i + x - 1 > n) break;
if(abs(query(1,1,n,i + 1,i + x - 1)) != 1)
{
return 1;
}
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
}
for(int i = 1;i <= n;++i)
{
b[i] = a[i] - a[i - 1];
}
build(1,1,n);
int ans = 1;
int L = 2;
int R = n;
while(L <= R)
{
int mid = (L + R) >> 1;
if(check(mid))
{
L = mid + 1;
ans = max(ans,mid);
}
else
{
R = mid - 1;
}
}
cout << ans<< "\n";
}
return 0;
}Distance in Tree
题意: 给定一棵$n$个结点的树，需要找出这个树上面距离严格为$k$的点对有多少个
解题思路: 拿到题目之后看$k$的范围实际上不大，有$500$左右，那么其实$nk$时间复杂度的算法是可以过的
那么接下来去思考如何用$nk$的时间复杂度去求
那么我们可以考虑这样子的一件事情，假设我们已经知道当前这里的一个点距离它距离为$x$的点都已知道
那么对于答案的贡献实际上可以是$ans += dp[now][i] * dp[to][k - i - 1]$
然后我们再更新相对应的数量即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e4 + 10;
int dp[maxn][520];
int n,ans,k;
vector<int> edge[maxn];
void dfs(int s,int fa)
{
dp[s][0] = 1;
for(auto to:edge[s])
{
if(to == fa) continue;
dfs(to,s);
for(int i = 0;i < k;++i) ans += dp[s][i] * dp[to][k - i - 1];
for(int i = 0;i < k;++i) dp[s][i + 1] += dp[to][i];
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> k;
for(int i = 1,u,v;i <= n - 1;++i)
{
cin >> u >> v;
edge[u].emplace_back(v);
edge[v].emplace_back(u);
}
dfs(1,0);
cout << ans << "\n";
return 0;
}
The Sports Festival
Three Bags
题目大意: 给定$3$个集合，可以选定任意两个集合中的元素$a,b$,移走$b$并且让$a$变成$a - b$
问最后剩下的元素最大值是多少
解题思路: 首先考虑如果在没有集合限制的情况下，其实我们进行这样子的操作就会使得一个数字没有取到，那么其实对应到集合来说，就是两个不同集合的数字的最小值没有取到是最优的；还有一种取法，就是另外两个集合全部取完，还有一个集合全部不取
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int n,m,k;
int sum;
int a[maxn],b[maxn],c[maxn],sa,sb,sc;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m >> k;
int ma,mb,mc;
ma = mb = mc = 1e9 + 7;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
sum += a[i];
sa += a[i];
ma = min(ma,a[i]);
}
for(int i = 1;i <= m;++i)
{
cin >> b[i];
sum += b[i];
sb += b[i];
mb = min(mb,b[i]);
}
for(int i = 1;i <= k;++i)
{
cin >> c[i];
sum += c[i];
sc += c[i];
mc = min(mc,c[i]);
}
int ans = max({sum - 2 * (ma + mb),sum - 2 * (mb + mc),sum - 2 * (mc + ma),sum - 2 * sa,sum - 2 * sb,sum - 2 * sc});
cout << ans << "\n";
return 0;
}Dr. Evil Underscores
题意: 给定$n$个数字，需要找到一个数字$x$使得这些数字$\bigoplus x$的最大值最小
解题思路: 拿到题目之后我们可以想到拆位去思考，首先我们考虑这样子的一件事情，对于高位来说肯定是能消掉尽可能消掉，不能消掉再看接下来这个高位所带来的影响，然后对于一位来说，如果这一位在所有数字上面都是相同的，那么其实它就可以最后消掉；如果有存在不相同的，对于最终答案来说这一位肯定是取$1$的，但是对于后面的位数还是不确定什么是更优的，因此还是需要找下去
所以我们可以建立一棵$tire$树，在$tire$树上面跑$dfs$即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
int tire[maxn][2],cnt,n;
void insert(int x)
{
int root = 0;
for(int i = 30;i >= 0;--i)
{
int id = (x >> i & 1);
if(!tire[root][id]) tire[root][id] = ++cnt;
root = tire[root][id];
}
}
int dfs(int pos,int now)
{
if(now < 0) return 0;
int ans = 0;
if(tire[pos][0] && tire[pos][1])
{
ans += (1 << now);
ans += min(dfs(tire[pos][0],now - 1),dfs(tire[pos][1],now - 1));
}
else if(tire[pos][0])
{
ans += dfs(tire[pos][0],now - 1);
}
else if(tire[pos][1])
{
ans += dfs(tire[pos][1],now - 1);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1,x;i <= n;++i)
{
cin >> x;
insert(x);
}
cout << dfs(0,30) << "\n";
return 0;
}New Year’s Problem
题目大意: 给定$m$个商店，有$n$个人，最多可以在$n - 1$个商店中买东西，第$i$个人收到第$j$个物品的数值是$A{i,j}$
问如何选择能够让所有人的最小开心值最高
解题思路: 其实题目有两个$trick$点，一个是最小的开心值最大，对于这一个点我们可以使用二分来解决，还有一个就是$n - 1$个商店，那么对于$n - 1$来说我们可以思考的一个点也就是鸽巢原理。那么我们在写二分$check$的时候可以这样子，因为我们是选定$n - 1$个，如果对于当前选定的$x$来说，存在对应的人的最大值没有，那么就直接返回$0$，然后对于第二个部分的话我们可以考虑这样子的一个东西，至少要有一个商店带来两个人的贡献，否则就无法使用$n - 1$个
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n,m;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
vector<vector<int>> mp(n + 1,vector<int>(m + 1));
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
cin >> mp[i][j];
}
}
auto check = [](int x,vector<vector<int>> &mp)
{
for(int i = 1;i <= m;++i)
{
int f = 0;
for(int j = 1;j <= n;++j)
{
if(mp[j][i] >= x) f = 1;
}
if(!f) return 0;
}
for(int i = 1;i <= n;++i)
{
int ct = 0;
for(int j = 1;j <= m;++j)
{
ct += (mp[i][j] >= x);
}
if(ct >= 2) return 1;
}
return 0;
};
int L = 0;
int R = 1000000000;
int ans = 0;
while(L <= R)
{
int mid = (L + R) >> 1;
if(check(mid,mp))
{
L = mid + 1;
ans = max(ans,mid);
}
else R = mid - 1;
}
cout << ans << "\n";
}
}Left Right Operation
D - Left Right Operation (atcoder.jp)
Zuma
题目大意: 给定$n$个东西，每个东西有一个颜色，每次可以消除颜色是回文串的一个字串，消除一个字串之后会自动拼接回去，问最少需要几次可以消除完
解题思路: 数据很小只有$500$，考虑区间$dp$
然后接下来我们来思考转移过程，因为每次消去的都是一个回文串，那么对于我们枚举的$l$和$r$来说可以放到上一个回文串中一起删除掉，如果$l == r$
那么$dp[l][r] = dp[l - 1][r + 1]$
否则我们需要考虑一个断点，在这个断点的两边进行$dp$
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 5e2 + 10;
int dp[maxn][maxn];
int a[maxn],n;
int check(int l,int r)
{
string s = "";
for(int i = l;i <= r;++i)
{
char id = '0' + a[i];
s.push_back(id);
}
string ss = s;
reverse(ss.begin(),ss.end());
return ss == s;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
dp[i][i] = 1;
}
for(int i = 1;i <= n;++i)
{
int r = i + 2 - 1;
if(r > n) break;
if(a[i] != a[r])
{
dp[i][r] = 2;
}
else dp[i][r] = 1;
}
for(int len = 3;len <= n;++len)
{
for(int l = 1;l <= n;++l)
{
int r = l + len - 1;
if(r > n) break;
if(a[l] == a[r]) dp[l][r] = dp[l + 1][r - 1];
else dp[l][r] = min(dp[l + 1][r],dp[l][r - 1]) + 1;
for(int mid = l;mid <= r;++mid)
{
chkmin(dp[l][r],dp[l][mid] + dp[mid + 1][r]);
}
}
}
cout << dp[1][n] << "\n";
return 0;
}Book of Evil
Empty Graph
https://codeforces.com/problemset/problem/1712/D
题目大意: 给定一个长度为$n(1\leq n \leq 2e5)$的序列,对于任意的$(l,r),1 \leq l < r \leq n$存在一条边连接$l$以及$r$，边权是$min(a_l,a_{l + 1},…,a_r)$
我们有$k$次操作机会可以将一个位置上的数字变成任意数字$x(1\leq x \leq 1e9)$,问这张图的直径是多少
一张图的直径定义如下所示: $max_{1 \leq u < v \leq n}d(u,v)$,$d(u,v)$是从$u$到$v$的最短路
解题思路: 首先我们先分析一下$d(u,v)$在这种情况下可能由什么组成，要么我是走两条最小的从$u$到$v$，如果是两个相邻的情况，那么我实际上$u$到$v$是只需要取$min(a_u,a_v)$
然后考虑这$k$次操作我们怎么使用，因为次数肯定是使用越多我最后的答案趋向于越大，具有一定的单调性，因此我们可以使用二分来写
我们去遍历整个序列，对于我们当前$check$的$x$来说，如果当前的数字小于$\frac{x}{2}$，那么我们需要一次机会将其变大
如果当前所需要的次数大于$k$的话，那么是不行的，我们就不要这一种情况
如果相同的话，我们看一下整个序列最大的$d$是多少，看看是否大于等于$x$即可
如果小于$k$次的话，找序列中最大的数字即可
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 2e5 + 10;
int a[maxn],n,k,use[maxn];
int cal()
{
int now1 = min(use[1],use[2]);
for(int i = 1;i <= n - 1;++i)
{
now1 = max(now1,min(use[i],use[i + 1]));
}
int mi = use[1];
for(int i = 1;i <= n;++i)
{
chkmin(mi,use[i]);
}
return min(2 * mi,now1);
}
int check(int x)
{
int cs = 0;
for(int i = 1;i <= n;++i) use[i] = a[i];
for(int i = 1;i <= n;++i)
{
if(use[i] * 2 < x)
{
cs++;
use[i] = 1e9;
}
}
if(cs > k) return 0;
else if(cs == k)
{
int now = cal();
// cout << "??? " << now << "\n";
if(now >= x) return 1;
return 0;
}
else
{
// cout << 33 << "\n";
if(k == 1)
{
int now = use[1];
for(int i = 1;i <= n;++i)
{
chkmax(now,use[i]);
}
// cout << "now -> " << now << " x -> " << x << "\n";
if(now >= x) return 1;
return 0;
}
return 1;
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n >> k;
for(int i = 1;i <= n;++i) cin >> a[i];
int L = 1,R = 1e9;
int ans = 0;
// cout << "?? " << check(4) << "\n";
while(L <= R)
{
int mid = (L + R) >> 1;
if(check(mid))
{
L = mid + 1;
ans = mid;
}
else R = mid - 1;
}
cout << ans << "\n";
}
return 0;
}小结
- 在异或运算中，若$x \bigoplus y = z$则有$x \bigoplus z = y$
- 在两个数字取余需要相等的时候，可以转移一下位置变成一个等式
- 注意模拟样例的时候样例给定的特殊性质
- 对于$n - 1$这个数字我们要特殊考虑一下$trick$点
- 边着色考虑特殊情况比如有一些情况只需要两种颜色即可$(CF1217D)$
