洛谷12月写题1月末复盘（一）-阿里云开发者社区

洛谷12月写题1月末复盘（一）

2023-05-08 109

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 洛谷12月写题1月末复盘

看来这些题还是值得细细品味滴

必须全都看一遍（对我自己说的）

P3741 honoka的键盘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

20.1.png

重点关注对象

只有四种排列情况VK KV KK VV

其中，VK是符合要求的，KK和VV都能改一个字符成为VK，只有KV不可以改

先从头到尾跑一遍，把正确的VK都改为X

然后再找VV KK 的

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int n,ans=0;
    cin>>n;
    string str;
    cin>>str;
    for(int i=0;i<n;i++)
    {
        if(str[i]=='V' && str[i+1]=='K')//先统计是VK的
        {
            ans++;
            str[i]='X';
            str[i+1]='X';
        }
    }
    for(int i=0;i<n;i++)
    {
        if(str[i]!='X' && str[i]==str[i+1])//统计是VV或KK的
        {
            ans++;
            break;
        }
    }
    cout<<ans;
    return 0;
}

P1147 连续自然数和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

20.2.png

这个题看上去不难，但是令人棘手，不知道从哪里下手

方法一

#include<iostream>
using namespace std;
int n,sum,j;
int main()
{
    cin>>n;     
    for(int i=1;i<=n/2;i++)//为什么是n/2,因为如果只有两个数，那么这两个数最小都是n/2
    {
        sum=0;     //sum归零
        for(j=i;j<n;j++)   //枚举每一个i对应的j，这个j是最小的，从i加到j总和大于等于n的自然数
        {
            sum+=j;            //sum记录从i加到j的总和
            if(sum>=n)break;    //当sum>=n时，跳出循环
        }
        if(sum==n)cout<<i<<' '<<j<<endl;   //输出
    }
    return 0;
}

方法二

#include<iostream>
int m;
int main()
{
  scanf("%d",&m);
  int sum=3;
  for(int i=1,j=2;i<=m/2;)//为什么是m/2，因为如果只有两个数，那么这两个数最小都是m/2
  {
    if(sum==m)
    {
      printf("%d %d\n",i,j);
      sum-=i;
      i++;
    }
    else if(sum<m)
    {
      j++;
      sum+=j;
    }
    else 
    {
      sum-=i;
      i++;
    } 
  }
  return 0;
}

P6832 [Cnoi2020]子弦 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

20.4.png

20.5.png

#include<iostream>
#include<cstring>
using namespace std;
const int N=10010;
int a[N],b[N];
int main()
{
  string str;
  cin>>str;
  int max=0;
  for(int i=0;i<str.size();i++)
  {
    a[str[i]-'a']++;//存的是位置 a—0 b—1 …………
  }
  for(int i=0;i<26;i++)
  {
    if(a[i]>max) max=a[i];
  }
  cout<<max;
}

P1548 [NOIP1997 普及组] 棋盘问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

20.6.png

正方形:

边长为1的正方形个数为n*m

边长为2的正方形个数为(n-1)*(m-1) （自己动手想想）

边长为3的正方形为个数(n-2)*(m-2)

边长为min(n,m)的正方形为个数s1=(n-min(n,m)+1)*(m-min(n,m)+1)

然后从边长为1到min（m，m）的正方形个数全部加起来；

长方形:

长为1的长方形（包括正方形）有n个

长为2的长方形（包括正方形）有n-1个

长为n的长方形（包括正方形）有1个

长为1到n的长方形1+2+...+n个

同理宽为1的长方形（包括正方形）有m个

宽为2的长方形（包括正方形）有m-1个

宽为m的长方形（包括正方形）有1个

宽为1-m的长方形1+2+...+m个

然后把它们乘起来，根据求和公式，总数s2=((1+n)*n*(1+m)*m)/4;

题目要求的是“非正方形的长方形”，因此要减去s1;

#include<iostream>
using namespace std;
int main()
{
  int n,m,s1=0,s2;
  cin>>n>>m;
  s2=((m+1)*m*(n+1)*n)/4;
  for(;m>=1&&n>=1;m--,n--)
  {
    s1+=m*n;   
  }                  
  cout<<s1<<" "<<s2-s1;
  return 0;
}

P1652 圆 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

20.7.png

本质上就是判断点是否在圆里面

如果点在圆里面，就必须经过圆的边界

如果点在圆外面，可以绕过这个圆

🍔异或

#include<iostream>
#include<cmath>
using namespace std;
const int N=100010;
int x[N],y[N],r[N];
double dist(int x1,int y1,int x2,int y2)
{
  return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
  int n,x1,y1,x2,y2,ans=0;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>x[i];
  }
  for(int i=1;i<=n;i++)
  {
    cin>>y[i];
  }
  for(int i=1;i<=n;i++)
  {
    cin>>r[i];
  }
  cin>>x1>>y1>>x2>>y2;
  for(int i=1;i<=n;i++)//每个圆都搜一遍
  {
    if( (dist(x1,y1,x[i],y[i])<r[i]) ^ (dist(x2,y2,x[i],y[i])<r[i]) )
    ans++;
    //异或，相同为0，不同为1
    //如果两个点恰有一个在圆内，就累加上
  }
  cout<<ans;
  return 0;
}