上一次上线已经是两年前了，Rating居然还排在第四 怀旧
wuziyue的博客
博客
标签
怀旧
2025-12-05 19:18:21 By wuziyue
2023年4月月赛3 题解
2023-04-23 20:48:59 By wuziyue
Q1
简单题
k<=50，可以直接穷举
主代码：
if(n%10==0){
n/=10;
}
else n--;Q2
首先 每个数字最终要%m
所以：答案<m
做法：
1.a序列全部%m(无需解释)
2.a,b,sort排序
关键点： 将a数组同加一个数并%M，使其等于B数组
如：a=1,1,2,2,2，3,3
b=2,2,3,3,3，4,4
how？
1.找到b中最小数的个数（如：2,2个）
2.在a中找对应个数（如：1,4，都是2个）
3.一一测试正确性并打擂最小值上代码：
#include<bits/stdc++.h>
using namespace std;
int a[2005],b[2005];
int n,m;
bool check(int l){
int tmp[2005];
for(int i=1;i<=n;i++){
tmp[i]=a[i]+l;
tmp[i]%=m;
}
sort(tmp+1,tmp+n+1);
for(int i=1;i<=n;i++){
if(tmp[i]!=b[i]){
return 0;
}
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]%=m;
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
sort(b+1,b+n+1);
sort(a+1,a+n+1);
int sum=1;
while(b[sum+1]==b[sum]) sum++;
int q=n,ans=1000000005;
if(check(0)){
printf("%d",0);
return 0;
}
a[0]=-10000;
for(int i=n-1;i>=0;i--){
if(a[i]!=a[i+1]){
if(q-i==sum){
if(check((m+b[1]-a[i+1])%m)){
ans=min(ans,(m+b[1]-a[i+1])%m);
}
}
q=i;
}
}
printf("%d",ans);
return 0;
}Q3 若两个学校与A联通且不经过点B，则这两个学校无需同时经过点B
同理：若两个学校与B联通且不经过点A，则这两个学校无需同时经过点A
此时，剩下的学校组合即为必须同时经过A,B
废话不多说：
#include<bits/stdc++.h>
using namespace std;
long long int d[2],sum;
vector<int> aa[100005],aa2[100005];
bool f[100005];
void sss(int l){
sum++;
f[l]=1;
for(int i=0;i<aa[l].size();i++){
if(!f[aa[l][i]]) sss(aa[l][i]);
}
}
void sss2(int l){
sum++;
f[l]=1;
for(int i=0;i<aa2[l].size();i++){
if(!f[aa2[l][i]]) sss(aa2[l][i]);
}
}
int main(){
int n,m,a,b,x,y;
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if(x!=a&&y!=a){
aa[x].push_back(y);
aa[y].push_back(x);
}
if(x!=b&&y!=b){
aa2[x].push_back(y);
aa2[y].push_back(x);
}
}
f[a]=1;
sum=0;
sss(b);
d[0]=n-sum-1;
memset(f,0,sizeof(f));
f[b]=1;
sum=0;
sss2(a);
d[1]=n-sum-1;
printf("%lld",d[0]*d[1]);
return 0;
}2023年4月月赛2题解 整合版---by wuziyue
2023-04-16 18:02:59 By wuziyue
Q1（Markdown不太会用）
[题目]（http://go.helloworldroom.com:50080/contest/78/problem/12859）
分析一下：for example: 4出现于那些步骤？ 答：4，5，8,9,10,11,16,17,18,19,20,21,22,23,33......
分一下类：4.5 / 8 9 10 11 / 16,17,18,19,20,21,22,23,33
进一步发现：这些数字在（x1,y1） (x2,y2)这样的区间中（x2=x1乘（符号怎么打？）2,y2=y1乘2+1）
对于偶数n来说，x1=n,x2=n+1; 对于奇数n来说，x1=n乘2,x2=n乘2+1;（不要忘记n本身未算在内）
不要问我如何发现的
然后,将1至n分为奇数与偶数分别二分，比较奇偶数中大者输出
主要函数：
int se(int l){
if(l==0) return m+10;
int ans=0;
if(l%2==1){
ans++;
}
else l/=2;
int a1=l,a2=l;
while(1){
a1*=2;
a2*=2;
a2++;
if(a1>n){
return ans;
}
if(a2>n){
ans+=n-a1+1;
return ans;
}
else ans+=a2-a1+1;
}
}二分部分：
int l=1,r=(n+1)/2;
while(l<r){
int mid=(l+r)/2+1;
int sum=se(mid*2-1);
if(sum>=m){
l=mid;
}
else r=mid-1;
}//奇数
l=l*2-1;
int l2=0,r2=n/2;
while(l2<r2){
int mid=(l2+r2)/2+1;
int sum=se(mid*2);
if(sum>=m){
l2=mid;
}
else r2=mid-1;
}
l2=l2*2;//偶数Q2 简单题
上代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int a[n+1],sum=0,ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a[0]=-1;
for(int i=1;i<=n;i++){
if(a[i]==a[i-1]){
sum++;
}
if(a[i]!=a[i-1]){
sum=1;
}
ans=max(ans,sum);
}
printf("%d",ans);
return 0;
}Q3 从左至右，从上至下建立坐标，发现了什么？
数字1：横+纵=2;
数字2至3：横+纵=3;
数字4至6：横+纵=4;
懂了？
一号问：
1.先分组：如：样例19：1+2+3+4+5=15， 1+2+3+4+5+6=21， 所以19在第六组 所以横+纵=7
2.找出本组最小数，（如第六组为16）此数位于（1，横+纵-1）（如16位于（1,6））
3.算目标数-最小数=x(19-16=3),由于方正排列规则为向左下，所以目标数位于（1+x,横+纵-1-x）(如19位于（1+3,6-3）)
int n;
cin>>n;
int sum=0,d=0,sum2=1;
while(sum<n){
d++;
sum+=d;
sum2++;
}
sum-=d;
sum++;
sum2--;
int a1=1,a2=sum2;
while(sum!=n){
sum++;
a1++;
a2--;
}
cout<<a1<<' '<<a2;二号问倒推即可 1.得出目标所在组 2.所在组最小值+（横坐标-1）为目标
int x,y;
cin>>x>>y;
int sum2=x+y-1;
int sum=sum2*(sum2-1)/2;
sum+=x;
cout<<sum;2023年4月月赛2题解 第三题
2023-04-16 18:00:39 By wuziyue
从左至右，从上至下建立坐标，发现了什么？
数字1：横+纵=2;
数字2至3：横+纵=3;
数字4至6：横+纵=4;
懂了？
一号问：
1.先分组：如：样例19：1+2+3+4+5=15， 1+2+3+4+5+6=21， 所以19在第六组 所以横+纵=7
2.找出本组最小数，（如第六组为16）此数位于（1，横+纵-1）（如16位于（1,6））
3.算目标数-最小数=x(19-16=3),由于方正排列规则为向左下，所以目标数位于（1+x,横+纵-1-x）(如19位于（1+3,6-3）)
int n;
cin>>n;
int sum=0,d=0,sum2=1;
while(sum<n){
d++;
sum+=d;
sum2++;
}
sum-=d;
sum++;
sum2--;
int a1=1,a2=sum2;
while(sum!=n){
sum++;
a1++;
a2--;
}
cout<<a1<<' '<<a2;二号问倒推即可 1.得出目标所在组 2.所在组最小值+（横坐标-1）为目标
int x,y;
cin>>x>>y;
int sum2=x+y-1;
int sum=sum2*(sum2-1)/2;
sum+=x;
cout<<sum;2023年4月月赛2题解 第二题
2023-04-16 17:41:55 By wuziyue
简单题
上代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int a[n+1],sum=0,ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a[0]=-1;
for(int i=1;i<=n;i++){
if(a[i]==a[i-1]){
sum++;
}
if(a[i]!=a[i-1]){
sum=1;
}
ans=max(ans,sum);
}
printf("%d",ans);
return 0;
}2023年4月月赛2 题解 第一题
2023-04-16 14:48:25 By wuziyue
Q1（Markdown不太会用）
[题目]（http://go.helloworldroom.com:50080/contest/78/problem/12859）
分析一下：for example: 4出现于那些步骤？ 答：4，5，8,9,10,11,16,17,18,19,20,21,22,23,33......
分一下类：4.5 / 8 9 10 11 / 16,17,18,19,20,21,22,23,33
进一步发现：这些数字在（x1,y1） (x2,y2)这样的区间中（x2=x1乘（符号怎么打？）2,y2=y1乘2+1）
对于偶数n来说，x1=n,x2=n+1; 对于奇数n来说，x1=n乘2,x2=n乘2+1;（不要忘记n本身未算在内）
不要问我如何发现的
然后,将1至n分为奇数与偶数分别二分，比较奇偶数中大者输出
主要函数：
int se(int l){
if(l==0) return m+10;
int ans=0;
if(l%2==1){
ans++;
}
else l/=2;
int a1=l,a2=l;
while(1){
a1*=2;
a2*=2;
a2++;
if(a1>n){
return ans;
}
if(a2>n){
ans+=n-a1+1;
return ans;
}
else ans+=a2-a1+1;
}
}二分部分：
int l=1,r=(n+1)/2;
while(l<r){
int mid=(l+r)/2+1;
int sum=se(mid*2-1);
if(sum>=m){
l=mid;
}
else r=mid-1;
}//奇数
l=l*2-1;
int l2=0,r2=n/2;
while(l2<r2){
int mid=(l2+r2)/2+1;
int sum=se(mid*2);
if(sum>=m){
l2=mid;
}
else r2=mid-1;
}
l2=l2*2;//偶数#676题解
2022-10-17 21:03:51 By wuziyue
贪心，贪心，贪心！！！
初始化：a数组存目前各个物品最少价格
b次打擂，每次选出当前价格最少的物品，选择购买，然后更新a数组
over
#206 题解
2022-10-16 15:59:22 By wuziyue
前几天做了一道打卡题，205 做完了之后我就去了 www.luogu.com.cn 上面一搜，发现是2015年普及组复赛第三题，我又发现，前两题都是入门题……当时我就去挑战了一下第四题……没什么思路,用贪心干了60分出来.
这次又一想竟然想出来了
进入正题: 既然贪心会超时，不如用前缀和预处理，就能节省时间 我又想到既然距离只最大值有关系，那么就不用考虑太多的距离问题了
无非只有两种情况 第一种是挑疲劳值大的推销 另外一种情况就是挑最大的疲劳值n-1个及路径最远的那个 在这两个里面挑一个总疲劳值更大的 （由于距离所产生的疲劳只和最大的距离有关系，所以就不用考虑其他情况了，当时我没想到这点。）
首先，我们需要按照疲劳值大小排序 然后需要进行三个预处理，分别是疲劳值的前缀和 ，前i个的最大距离×2，以及后i个距离×2+疲劳值 程序就可以做出来了
具体程序略
比较公式略
共 8 篇博客