比赛报告
比赛名称：模拟赛 \(3\)
比赛时间：2023.8.2 2:00~5:00
比赛过程
今天再做题时，第一题明明很简单，但是因为没看清题目导致 \([2~n-1]\) 写成了 for(int i=2;i<=n;i++)应该是 for(int i=2;i<n;i++),导致扣除了 \(80\) 分；
第二题因为自己读题不明白，导致运行错误就成为了 \(0\) 分，但应该这道题做对的，
第三题因为自己的知识掌握不到位，并且在 \(dfs\) 这一部分没有学的透彻，成了\(0\) 分；
第四题还可以，成功 \(\texttt {AC}\)；
正解
\(flower\)
注意不等号的取值范围的细节，按题意模拟即可。这道题的数据范围 \([2~n-1]\),应该注意
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
#define c const
#define endl '\n'
#define ft first
#define sd second
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+5;
ll a[N],cnt;
int main()
{ fst;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<n;i++)
{
if(a[i-1]<=a[i]&&a[i]>=a[i+1])//根据公式判断if结果
{
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
\(sunset\)
注意到读⼊可以写成⼀个 的矩形，其实就是需要判断这个矩阵的哪两列相等,并且输出最小字典序，如果找到了就cout<<i<<" "<<j没找到就cout<<-1<<endl
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define TRASE 1
#define tcout TRASE&&cout
#define endl '\n'
#define ft first
#define sd second
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e4+500;
int n,k;
int a[N][N];
string s[N];
signed main()
{
cin>>n>>k;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
int x;
cin>>x;
if(x)//x是1
{
s[j]=s[j]+"1";
}
else//x是0
{
s[j]=s[j]+"0";
}
}
}
for(int i=1;i<=n;i++)//枚举每一列的的字母数
{
for(int j=i+1;j<=n;j++)//枚举下一列的字母，每次都比外层循环多一个
{
if(s[i]==s[j])//如果相等，那么++
{
cout<<i<<" "<<j;
return 0;//只输出最小的
}
}
}
cout<<-1<<endl;
return 0;
}
\(sky\)
第一种可能：\(s1,s2\) 中分别最深的叶⼦最为端点，这条路径的⻓度就是 \(m_s1+m_s2-2*d_p\),用它去更新 \(x=ms2-1\) 的答案;
第二种可能：\(s1\) 中最深的叶⼦和p作为端点,⻓度为\(d_p-m_s1\),对应询问 \(x=m_s1\) 的答案。实际实现的时候，可以只维护当前遍历过的⼉⼦中最⼤的深度，每遍历⼀个⼉⼦就更新答案。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,q;
vector<int> g[maxn];
int dep[maxn],down[maxn],fa[maxn];
int ask,num;
int ans[maxn];
void init(int x,int f){
dep[x]=dep[f]+1;
fa[x]=f;
int maxx=-1;
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
if(y==f){
continue;
}
init(y,x);
maxx=max(maxx,down[y]);
}
down[x]=maxx+1;
}
void get(int x){
if(x==1&&g[x].size()<=0){
return;
}
if(x!=1&&g[x].size()<=1){
return;
}
int res=0;
priority_queue<int> q;
q.push(0);
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
if(y==fa[x]){
continue;
}
q.push(down[y]+1);
}
for(int i=1;i<=2;i++){
int tmp=q.top();
q.pop();
res+=tmp;
if(i==2){
ans[dep[x]+tmp]=max(ans[dep[x]+tmp],res);
}
}
}
void dfs(int x){
get(x);
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
if(y==fa[x]){
continue;
}
dfs(y);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>ask;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dep[1]=-1;
init(1,1);
dfs(1);
for(int i=n-1;i>=1;i--){
ans[i]=max(ans[i],ans[i+1]);
}
for(int i=1;i<=ask;i++){
cin>>num;
if(ans[num+1]==0){
cout<<-1<<'\n';
}
else{
cout<<ans[num+1]<<'\n';
}
}
return 0;
}
\(resurrection\)
这道题因为数据范围大，所以我们可以用双指针加上前缀和的思想来做最后求出最大值进行比较即可
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
#define c const
#define endl '\n'
#define ft first
#define sd second
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
c int N=1e6+5;
ll a[N],maxx,sum[N],cnt,b[N],max1;
int main()
{ fst;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
maxx=max(a[i],maxx);//求出最大值
}
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];//前缀和计算
}
int l=1,r=n;//双指针扫描
while(l<r)
{
ll maxn=maxx*(r-l+1)-(sum[r]-sum[l-1])-(r-l+1);//代入公式计算
b[++cnt]=maxn;//式子求出的和放到b[]
l++,r--;//双指针遍历
}
for(int i=1;i<=cnt;i++)
{
max1=max(b[i],max1);//求出最大值
}
cout<<max1<<endl;
return 0;
}