1. 知识点总结
简单练手~
题目 | 难度 | 知识点 |
---|---|---|
Shortest Distance | 🎯 | 数组 |
Student List for Course | 🎯 | STL |
Find Coins | 🎯 | water |
Counting Ones | 🎯🎯 | 找规律 |
2. 分题题解
2.1 Shortest Distance
数组
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>dis;
vector<int>pre_dis;
int m,u,v;
int sum=0;
int main(){
scanf("%d",&n);
dis.resize(n+1);
pre_dis.resize(n+1);
pre_dis[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&dis[i]);//i与i+1的距离
pre_dis[i]=pre_dis[i-1]+dis[i];//1->i+1的距离
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
int temp=abs(pre_dis[(u-1)%n]-pre_dis[(v-1)%n]);
printf("%d\n",min(pre_dis[n]-temp,temp));
}
return 0;
}
2.2 Student List for Course
简单STL
#include<bits/stdc++.h>
using namespace std;
int N,K;
struct Student{
string name;
vector<int>course;
};
map<int,vector<string>>courseInfo;
string name;
int cid;
int num;
int main(){
scanf("%d%d",&N,&K);
vector<Student>stu(N);
for(int i=1;i<=K;i++){
courseInfo[i].clear();
}
for(int i=0;i<N;i++){
cin>>stu[i].name>>num;
for(int j=0;j<num;j++){
cin>>cid;
stu[i].course.push_back(cid);
}
}
for(int i=0;i<N;i++){
name=stu[i].name;
for(int j=0;j<stu[i].course.size();j++){
cid=stu[i].course[j];
courseInfo[cid].push_back(name);
}
}
for(int i=1;i<=K;i++){
int len=courseInfo[i].size();
printf("%d %d\n",i,len);
sort(courseInfo[i].begin(),courseInfo[i].end());
for(int j=0;j<len;j++){
printf("%s\n",courseInfo[i][j].c_str());
}
}
return 0;
}
2.3 Find Coins
简单题
#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<int>coins;
int num[1001]={0};
int a,b;
int main(){
scanf("%d%d",&N,&M);
coins.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&coins[i]);
num[coins[i]]++;
}
sort(coins.begin(),coins.end());
for(int i=0;i<N;i++){
a=coins[i];
b=M-a;
if(a==b&&num[a]>=2){
printf("%d %d",a,b);
return 0;
}else if(a!=b&&num[a]&&num[b]){
printf("%d %d",a,b);
return 0;
}
}
printf("No Solution");
return 0;
}
2.4 Counting Ones
暴力会超时,但是可以拿到22/30的分数;
实际上不是很难,属于找规律的题目
两种暴力方式:
1、除法
#include<bits/stdc++.h>
using namespace std;
//计数:1
int sum=0;
int n;
int Count(int num){
int temp=0;
while(num){
temp+=(num%10==1?1:0);
num/=10;
}
return temp;
}
int main(){
scanf("%d",&n);
//计算从1-n的1出现的次数
for(int i=1;i<=n;i++){
sum+=Count(i);
}
printf("%d",sum);
return 0;
}
2、字符串
#include<bits/stdc++.h>
using namespace std;
//计数:1
int sum=0;
int n;
int main(){
scanf("%d",&n);
//计算从1-n的1出现的次数
for(int i=1;i<=n;i++){
string str=to_string(i);
sum+=count(str.begin(),str.end(),'1');
}
printf("%d",sum);
return 0;
}
正确解答:
参考【CSDN】逐位计算出现1的个数,举几个数如515,504,526。
515:
计算个位的1出现个数有:001,011,021,…,501,511共52个;(不计算10位上的1)
计算十位的1出现个数有:010,011,…019,110,111…,210…,310…,…510,511,512,513,514,515共有5x10+5+1个1;
计算百位的1出现个数有:100,101,102…,199共有100个。
同理,计算504
个位上有50个,十位上有5x10个,百位上有100个
计算526
个位上有52个,十位上有(5+1)x10个,百位上有100个
发现有什么规律,当计算当前位的时候,1的个数与数左右两边有关
如数abc,计算10位的时候,左边的数为a,右边的数位c,那么
如果b=0,在十位就有a x 10个1;
如果b=1,在十位就有a x 10 + c+1 个1;
如果b>1,在十位就有(a+1) x 10个1;
#include <cstdio>
int main()
{
int n;
scanf("%d",&n);
int left=0,right=0,now=0,a=1,ans=0;
while(n/a){
left=n/(a*10);
right=n%a;
now=n/a%10;
if(now==0)ans+=left*a;
else if(now==1)ans+=left*a+right+1;
else ans+=(left+1)*a;
a*=10;
}
printf("%d\n",ans);
return 0;
}
3. 参考资料
无