924普及组——提高-模拟赛题解

wflengxuenong · 2023-09-24 10:10:49 · 个人记录

T1幸运字符:

考察点：字符串。入门题目。

方法： 两种情况： 找出连续的"vv",把第二个v替换为k即可。 找出连续的"KK",把第一个k替换为v即可。

有同学用了o(n^2)的算法。 参考代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

int n;
string s; 

int ans = -1;

char change(char ch){
    if(ch == 'V') return 'K';
    if(ch == 'K') return 'V';
}
int sum(){
    int res = 0;
    for(int i = 0; i < n-1; i ++){
        if(s[i] == 'V' && s[i+1] == 'K'){
            res++;
        }
    }
    return res;
}

signed main(void){
    cin >> n;
    cin >> s;
    int cnt = sum();
    ans = max(ans, cnt);
    for(int i = 0; i < n; i ++){
        s[i] = change(s[i]);
        int cnt = sum();
        ans = max(ans, cnt);
        s[i] = change(s[i]);
    }
    cout << ans << endl;
    return 0;
}

实际这个题目o(n)的算法即可以解决。 第一遍先找VK,找到的打标记。，第二遍找没打标记的连续“VV”或“KK”。

参考代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

int n,ans;
string a;

signed main(void){
    cin >> n;
    cin >> a;
    for(int i=0;i<n-1;i++)
        if(a[i]=='V'&&a[i+1]=='K')ans++,a[i]=a[i+1]='.';
    for(int i=0;i<n-1;i++){
        if(a[i]!='.'&&a[i]==a[i+1]){
            ans++;break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

T2 慢跑

考察点：模拟、数学。 在这个超长跑道上。起始坐标大、速度慢的会挡住起始坐标小速度快的人。

有同学贪心，先计算出T时刻后的最终速度。看坐标小的会不会被下一个坐标大的挡住，这样的方法是错的，因为下一个坐标大的速度也可能被前面的挡住，直接计算的最终坐标点并不是其真正的坐标点。例如新增加的第二组样例数据。

• 方法一：根据坐标的大小逆序来，记录逆序的最小真正终点。 参考代码：

  // liqianzuo
  #include<iostream>
  #include<cstring>
  using namespace std;
  const int N=1e6;
  long long n,t;
  long long lo[N+3],loc,v;
  int main()
  {
  scanf("%d%d",&n,&t);
  for(int i=0;i<n;i++)
  {
      scanf("%d%d",&loc,&v);
      lo[i]=loc+v*t;
  }
  long long ans=1;
  for(int i=n-1;i>0;i--)
  {
      if(lo[i-1]>=lo[i])
      {
          lo[i-1]=lo[i];
      }
      else
      {
          ans++;
      }
  }
  cout<<ans;
  return 0;
  }

• 方法二： 也可以正序做，但是要把前面挡住的作为并查集来处理 例如A-B,B-C，那么他们就组成一个集合。 参考代码：

  
  //刘chenkai
  #include<bits/stdc++.h>
  #include<unistd.h>
  #define ll long long
  #define ull unsigned long long
  #define uint unsigned int
  #define pii pair<int,int>
  #define mp(a,b) make_pair(a,b)
  #define endl '\n'
  using namespace std;
  const int N=1e5+1;
  const ull INF=0x7f7f7f7f7f7f7f7f;
  int fa[N];
  bool b[N];
  void init(int n)
  {
  for(int i=1;i<=n;i++) fa[i]=i;
  }
  int find(int i)
  {
  return fa[i]==i?i:fa[i]=find(fa[i]);
  }
  void unionn(int i,int j)
  {
  fa[find(i)]=find(j);
  }
  struct node
  {
  ll x,v;
  bool operator < (node b)
  {
      return x<b.x;
  }
  }a[N];
  inline ll read()
  {
  ll x=0;
  char ch=getchar();
  while(ch<'0'||ch>'9')
  {
      ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  {
      x=(x<<1)+(x<<3)+(ch^48);
      ch=getchar();
  }
  return x;
  }

int main() { ll n=read(),T=read(),ans=0; ull num1=INF,num2=INF; init(n); for(int i=1;i<=n;i++) { a[i].x=read();a[i].v=read(); } for(int i=n;i>=1;i--) { if(i%2==0) { num2=a[i].x+a[i].vT; num2=min(num1,num2); if(num2>=num1) unionn(i,i+1); } else { num1=a[i].x+a[i].vT; num1=min(num1,num2); if(num1>=num2) unionn(i,i+1); } } for(int i=1;i<=n;i++) { if(!b[find(i)]) { b[find(i)]=1; ans++; } } cout<<ans<<endl; return 0; }

## T3 子段和

枚举子段区间$[l,r]$,再计算修改，有$o(n^3)$暴力算法。

不带修改：枚举子段区间$[l,r]$,利用前缀和，有$o(n^2)$算法。

最大子段和：
    动态规划：当前点和前面的连接更优秀吗？更优秀和前面连，否则就自己开始。

- 设$f[i]$为以$i$为结束点的最大子段和长度。
- 那么 $f[i]=max(f[i-1]+a[i],a[i])$
- 最终的结果为： $ans=max(f[i]),1\leq i \leq n$;
- 时间复杂度为$o(n)$

最大子段和再变形，只有一次修改机会，调用$n$次最大子段和算法即可。

参考代码：
```cpp
//zhou zu hao
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],x,dp[1006],maxx=-0x3f3f3f3f;
signed main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=n;j++){
        int kun=a[j];
        a[j]=x;
        for(int i=1;i<=n;i++){
            dp[i]=max(dp[i-1]+a[i],a[i]);
            maxx=max(maxx,dp[i]);
        } 
        a[j]=kun;
    } 
    cout<<maxx;
    return 0;
} 

• 如果数据范围更大，比如n=10^5怎么解决？

还有o(n)的算法 设dp[i][0/1]为打当前点是否用了这次修改机会的最大值。

 \\liu xi
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,begin,end) for(ll i=(begin);i<=(end);++i)
const ll maxn=1e6+5;
inline ll read(){
    ll f=0, k=1; char ch=getchar();
    while(ch<'0' || ch>'9'){ if(ch=='-') k=-1; ch=getchar();}
    while(ch>='0' && ch<='9'){ f=(f<<1)+(f<<3)+(ch-'0'); ch=getchar();}
    return f*k;
}
ll n, x, a[maxn], dp[maxn][2], ans;
int main(){
    n=read();
    x=read();
    FOR(i,1,n){
        a[i]=read();
    }
    dp[0][0]=0;
    FOR(i,1,n){
        dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
        dp[i][1]=max(dp[i-1][0]+x,max(dp[i-1][1]+a[i],x));
        ans=max(dp[i][1],ans);
    }
    cout << ans;

    return 0;
}

T4修栅栏

数学知识：

在长度确定的情况下，如何构成的长方形面积最大？

长宽越接近，面积越大？你会证明吗？

结论

按照长度排序，用长度尽可能接近的木棍来修栅栏。 要找相同数目的，数据范围10^6首选桶排序。

桶内数值为偶数的直接使用。 用不上的只能是奇数中的1个，就把这1个就削去1，放入下一个桶，因为木棍只可以被削1次，因此还要做一个削后木棍数量的标记，防止重复。

参考代码：

//李jinhan
#include<iostream>
using namespace std;
long long a[1000050],mp1[1000050],mp2[1000050];
long long b[1000050],cnt=0;
int main()
{
    int n;
    long long maxx=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp1[a[i]]++;
        maxx=max(maxx,a[i]);
    }
    for(int i=maxx;i>=1;i--)
    {
        if((mp1[i]+mp2[i])%2==1&&mp1[i]>0) mp1[i]--,mp2[i-1]++;
        //for(int j=1;j<=((mp1[i]+mp2[i])/2);j++) b[++cnt]=i;
        while((mp1[i]+mp2[i])>=2)
        {
            if(mp1[i]) mp1[i]--;
            else mp2[i]--;
            if(mp1[i]) mp1[i]--;
            else mp2[i]--;
            b[++cnt]=i;
        }
    }
    long long ans=0;
    //cout<<cnt<<'\n';
    //for(int i=1;i<=cnt;i++) cout<<b[i]<<' ';
    for(int i=1;i<cnt;i+=2)
    {
        long long x=b[i];
        long long y=b[i+1];
        ans+=x*y;
        //cout<<"ans+="<<x<<'*'<<y<<'\n';
    }
    cout<<ans;
    return 0;
}

T5 飞行

图论题目。最短路，而且是边权为固定值的最短路，可以用BFS。 可以跑从n到其他所有点的最短路。 然后枚举中转点计算。设其AB单独走到C点,再从C点到N点。