河南萌新联赛2024第（一）场：河南农业大学 题目讲解c++【3】
河南萌新联赛2024第（一）场：河南农业大学 题目讲解c++【3】
链接：https://ac.nowcoder.com/acm/contest/86639/I
来源：牛客网
题目I描述
现在有长度为 nnn 的数组 aaa，式子 SSS 定义为 S=a1÷a2÷a3…÷anS=a_1\div a_2\div a_3…\div a_nS=a1÷a2÷a3…÷an，最多对数组 aaa 进行 ttt 次循环右移 操作**。
**
请问，进行第几次操作时使得 SSS 最大？若存在多种答案，请输出最小值。
**
**
循环右移：一次操作使数组从 a1,a2,a3,…,ana_1,a_2,a_3,…,a_na1,a2,a3,…,an 形式转换为 an,a1,a2,…,an−1a_n,a_1,a_2,…,a_{n-1}an,a1,a2,…,an−1 形式。
输入描述:
输入包含两行.
第一行一个正整数 n,tn,tn,t (1≤n≤2×105,0≤t≤109)(1\leq n\leq 2\times10^5,0\leq t\leq 10^9)(1≤n≤2×105,0≤t≤109) 表示数组 aaa 的长度和最多的操作次数。
第二行 nnn 个正整数 aia_iai (1≤ai≤109)(1\leq a_i \leq10^9)(1≤ai≤109) 表示数组 aaa 的元素。
输出描述:
输出包含一行一个整数，表示使得 SSS 最大的最小操作次数。
想要得到最大值，显然是让开头的数字最大，我们在避免循环时，最多只能操作n-1次。由此我们最多能操作min(t,n-1)次；我们找出每次操作后得到的开头的数字最大的，即为所求
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,t;
cin>>n>>t;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
int va=0;
int v_=0;
//构造一个执行顺序为 1,n,n-1,...2的 循环。->a索引 使得我们能判断初始状态是否即为所求
for(int i=0;i<=min(t,n-1);i++){
if (a[(n - i) % n + 1] > va) {
va = a[(n - i) % n + 1];
v_= i;
}
}
cout<<v_;
}
链接：https://ac.nowcoder.com/acm/contest/86639/J
来源：牛客网
题目J描述
定义一个 k×kk\times kk×k 的01矩阵，若该矩阵的副对角线（从右上角到左下角的对角线）全由1组成，左侧的边全由1组成，下侧的边全由1组成，且该矩阵的其余元素全为0，则称该矩阵为一个 k×kk\times kk×k 的箭头矩阵。现在给你一个 n×mn\times mn×m 的01矩阵，请你在这个矩阵中找到一个最大的箭头矩阵，并输出其边长的大小。
输入描述:
输入共 n+1n+1n+1 行。
第一行两个正整数 n，m(1≤n，m≤5000)n，m (1≤n，m≤5000)n，m(1≤n，m≤5000) 代表所给矩阵是一个 nnn 行 mmm 列的矩阵。
接下来 nnn 行，每行 mmm 个整数，中间没有空格，仅由0和1组成。
输出描述:
输出一行一个数，表示该 n×mn\times mn×m 的矩阵中的最大箭头矩阵的边长的大小。
做这个题的关键点，在于我们如何能做到高效的找到匹配，由这个组成箭头矩阵的规律，发现边长为1的有1个1，边长为2的有4个1，边长为3的有7个1，发现是3的等差数列，得到A(变成为n) = 3 n - 2，如果以这个边构建一个n*n的正方形，如果这个正方形构成了箭头举证，那么必然，它会有3 n - 2个1。我们可以尝试着，从一个点，探索他能满足最大箭头矩阵的前提条件，它三个方向上（向上，向右，向右上）的1数量，当发现满足这一条件时，在观察这个构成的正方形是否满足3n-2，即可判断能否构成箭头矩阵。为了高效的拿到这个矩阵的1的数量，可以用前缀和的方式，帮助快速拿到。
假设从1，1开始遍历，就是黑框那里.
我们从左上开始得到每个i,j与左上角（0，0）围成的矩阵中1的数量。显然0，0，和1,1所构成的矩阵中，1的数量，为它上面0，0和0，1构成的红色矩阵，和左边0，0和1，0 构成的红色矩阵再减去它们重叠的部分，即为0，0和0，0构成的矩阵中，1的数量。可得到推导式
a[i][j] = a[i-1][j]+a[i][j-1] -a[i-1][j-1]+(它自身的1的数量);
#include<bits/stdc++.h>
using namespace std;
int n,m;
int Get(int i,int j,vector<vector<int>> &a,vector<vector<bool>> &s) {
//从箭头边长从1，到n依次遍历
int max=0;
for(int x=1;x<=n;x++){
//探索的最大边长越界了
if(i-x+1<0||j+x-1>m) {
return max;
}
//探索的最大边长不为1
if(!s[i-x+1][j]||!s[i][j+x-1]||!s[i-x+1][j+x-1]) {
return max;
}
//探索的矩阵1数量不为3*n-2
if((a[i][j+x-1]-a[i][j-1]-a[i-x][j+x-1]+a[i-x][j-1])!=3*x-2)
{
return max;
}
max++;
}
return max;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
//记录当前的数据
vector<vector<bool>> s(n+1,vector<bool>(m+1,0));
vector<vector<int>> a(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
string st;
cin>>st;
for(int j=1;j<=m;j++){
s[i][j] = st[j-1]-'0';
a[i][j] = a[i-1][j]+a[i][j-1] -a[i-1][j-1]+s[i][j];
}
}
int max=0;
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=m;j++) cout<<a[i][j]<<" ";
// cout<<endl;
// }
//以每个坐标点，作为箭头矩阵的出发点，尝试探索得到最大的箭头矩阵。
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
int nc=Get(i,j,a,s);
if(nc>max) max=nc;
}
cout<<max;
}
链接：https://ac.nowcoder.com/acm/contest/86639/K
来源：牛客网
题目K描述
EasyEasyEasy 版本和 HardHardHard 版本唯一的区别是 HardHardHard 版本删除的是桥，而 EasyEasyEasy 版本删除的是任意边。
你有一张 nnn 个点 mmm 条边的无向图，你有无数次删除操作来删除任意条边以获得若干个联通块。定义联通块的大小为其所包含点个数。定义这个图的代价是：你有任意次操作，每次操作合并两个联通块，合并后联通块大小为二者之和，最后剩下两个联通块大小的乘积为此图的代价，若只有一个则代价为0。你需要最大化此图代价。
输入描述:
第一行包含两个整数 nnn 和 mmm ,图中顶点的数量和边的数量。
接下来的每 mmm 行包含两个整数 uuu 和 vvv ,表示图中顶点 uuu 和 vvv 之间有一条无向边。
(0<n≤106)\left ( 0< n\leq 10^{6} \right )(0<n≤106)
(0≤m≤106)\left ( 0\leq m\leq 10^{6} \right )(0≤m≤106)
(0<u,v≤n)\left ( 0< u,v\leq n \right )(0<u,v≤n)
输出描述:
输出一个整数表示最大代价。
做这题我们发现，其实可以把这些节点，任意合并大小，但为了最大化代价，显然希望的是，最后得到的两个连通图的大小是相似的，那么根据总共有大小n,我们只可能相似成两种情况，它两相等，或它两相差1
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
cin>>n;
n = n>>1;
if(n&1){
cout<<n*(n|1);
}
else
cout<<n*n;
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/86639/L
来源：牛客网
题目L描述
EasyEasyEasy 版本和 HardHardHard 版本唯一的区别是 HardHardHard 版本删除的是桥，而 EasyEasyEasy 版本删除的是任意边。
你有一张 nnn 个点 mmm 条边的无向图，你有无数次删除操作来删除任意条桥 以获得若干个联通块。定义联通块的大小为其所包含点个数。定义这个图的代价是：你有任意次操作，每次操作合并两个联通块，合并后联通块大小为二者之和，最后剩下两个联通块大小的乘积为此图的代价，若只有一个则代价为0。你需要最大化此图代价。
对于桥的定义 ：对于一个无向图，如果删掉一条边后图中的连通块数增加了，则称这条边为桥或者割边。
输入描述:
第一行包含两个整数 nnn 和 mmm ,图中顶点的数量和边的数量。
接下来的每 mmm 行包含两个整数 uuu 和 vvv ,表示图中顶点 uuu 和 vvv 之间有一条无向边。
(0<n≤4×105)\left ( 0< n\leq 4\times10^{5} \right )(0<n≤4×105)
(0≤m≤106)\left ( 0\leq m\leq 10^{6} \right )(0≤m≤106)
(0<u,v≤n)\left ( 0< u,v\leq n \right )(0<u,v≤n)
输出描述:
输出一个整数表示最大代价。
这题的思路主要考察tarjan算法,用于求图中所有的强联通分量的大小，这些大小最后组成2个，符合题意的题。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 +10;
struct edge{
int to,ne;
}eds[N];
int idx;
int h[N];
void add(int x,int y){
eds[++idx]={
y, h[x]
};
h[x] = idx;
}
int dfn[N],low[N],cnt,cntc;
int st[N],top;
int type[N],sz[N];
bool inst[N];
void tarjan(int x,int fa) {
// cout<<"到达了"<<x<<endl;
low[x] = dfn[x] = ++cnt;
st[++top] = x; inst[x] = true;
for(int i=h[x];i;i=eds[i].ne){
int son = eds[i].to;
if(son==fa)continue;
if(!dfn[son]){
tarjan(son,x);
// cout<<"打算去往"<<son<<endl;
low[x] = min(low[son],low[x]);
}
else
{
// cout<<"决定更新"<<son<<endl;
low[x] = min(low[x],dfn[son]);
}
}
if(dfn[x]==low[x]){
// cout<<"发现组成连通图"<<x<<endl;
int y;
cntc++;
do {
y = st[top--];
type[y] = cntc;
sz[cntc]++;
} while (x != y);
}
}
signed main() {
int n,m;
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++){
cin>>a>>b;
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++){
if(dfn[i]) continue;
tarjan(i,0);
}
// for(int i=1;i<=n;i++) {
// cout<<i<<":"<<low[i]<<endl;
// }
//根据拿到的大小进行融合。
sort(sz+1,sz+1+cntc,greater<int>());
int x=0,y=0;
for(int i=1;i<=cntc;i++){
if(x<=y) x+=sz[i] ;
else y+=sz[i];
}
cout<< x*y;
}