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;
}