洛谷12月写题1月末复盘
看来这些题还是值得细细品味滴
必须全都看一遍（对我自己说的）
P3741 honoka的键盘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
重点关注对象
只有四种排列情况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)
这个题看上去不难，但是令人棘手，不知道从哪里下手
方法一
#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)
#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)
正方形:
边长为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)
本质上就是判断点是否在圆里面
如果点在圆里面，就必须经过圆的边界
如果点在圆外面，可以绕过这个圆
🍔异或
#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;
}
P1914 小书童——凯撒密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目不难，但是有陷阱
P2705 小球 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目不难。就是有点迷惑人
P2907 [USACO08OPEN]Roads Around The Farm S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
列方程是个好方法
注意要求的是多少群，不是多少头
#include<iostream>
using namespace std;
int ans=1,n,k;
void fl(int a)//a为当前牛群所含牛的数目
{
int x,y;//x，y为分裂成两群之后的所含牛的数目
if((a+k)%2!=0)
{
return;//递归终止条件
}
else{
x=(a+k)/2;
y=a-x;
if(x<=0||x>=a||y<=0||y>=a)
{
return;
}
ans++;
fl(x);//分开的两群，分别判断
fl(y);
}
}
int main(){
cin>>n>>k;
fl(n);
cout<<ans;
return 0;
}P5725 【深基4.习8】求三角形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题，一定要自己写一遍
⭐⭐⭐如果不会，不要看题解 ，看我自己的提交记录
洛谷ID:OginoChihiro
P6443 [COCI2010-2011#1] TIMSKO - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
细节满满的一道题
剩余的人去实习
#include<iostream>
using namespace std;
int main()
{
int n,m,k,ans=0;
cin>>n>>m>>k;//n是女生人数，m是男生人数
for(int i=0;i<=(n+m-k)/3;i++)//组成队伍最大不超过剩余人数的三分之一
{
int boy=m-i;//组成i个队伍，剩下男生人数
int girl=n-2*i;//组成i个队伍，剩下女生人数
if(boy+girl>=k&&boy>=0&&girl>=0)
ans=i;//如果满足条件，则更新ans
}
cout<<ans;
return 0;
} P6685 可持久化动态仙人掌的直径问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
好（doge）一道签到题
注意数据范围，暴力枚举会爆掉
🍔方法一
#include<bits/stdc++.h>
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;;i++)
{
if(pow(i,m)>n)
{
printf("%d",i-1);
return 0;
}
}
return 0;
}🍔方法二（必对）
#include<bits/stdc++.h>
int n,m;
int main()
{
scanf("%d%d",&n,&m);
printf("%.0f",pow(n,1.0/m));
return 0;
}🍔 方法三（必对）
居然还能用二分写！！！
#include<bits/stdc++.h>
int n,m,l=1,r,mid;
int main()
{
scanf("%d%d",&n,&m);
r=n;
while(l<=r)
{
mid=(l+r)>>1;
if(pow(mid,m)<=n)l=mid+1; // 与上述同理，pow 函数的精度在 10^9 范围内可以接受
else r=mid-1;
}
printf("%d",r);
return 0;
} P6866 [COCI2019-2020#5] Emacs - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
要找长方形其实只用看顶点，如果一个点的上面和左边都是“.”，那么这个点就一定是某个长方形的左上顶点（妙）
同时把输入矩阵的周围都打成“.”，可以避免边界问题
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,j,n,m,cnt=0;
char a[105][105];
cin>>n>>m;
for(i=0;i<=n+1;i++)
{
for(j=0;j<=m+1;j++)
{
if(i==0||j==0||i==n+1||j==m+1){//围出边界
a[i][j]='.';
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i-1][j]=='.'&&a[i][j-1]=='.'&&a[i][j]=='*')
{
cnt++;//统计
}
}
}
cout<<cnt;
return 0;
}P8611 [蓝桥杯 2014 省 AB] 蚂蚁感冒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题y总有视频讲解
🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈
Code over!
276
264
到【灌水乐园】发言
