吴凡的题库——快快编程1601-1800

博主： WinRTAS
发布时间：2022 年 08 月 11 日
364 次浏览
暂无评论
389字数
分类：默认分类

## 1617. 墨提斯
```
题目描述
墨提斯(Metis)，是希腊神话中第一代智慧女神，她非常关心人们的智商。墨提斯有独特的神力：每年可以挑选一个人让其智商加k。同时，没有被选中的人，智商每年会加1。目前你的智商为q。要让你在m年后智商达到100，请问墨提斯至少需要对你使用几次神力? 如果无法让你在m年后智商达到100，请输出-1。

```
```
输入输出格式
输入格式
输入文件metis.in 输入第一行为正整数q,k,m。1<=q<=1000，1<=k<=100，1<=m<=100。
输出格式
输出文件metis.out输出一个整数。
```
```
输入输出样例
输入样例#1:
90 4 3
输出样例#1:
3
输入样例#2:
91 4 3
输出样例#2:
2
输入样例#3:
91 2 4
输出样例#3:
-1
```
```
#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("metis.in","r",stdin);
	freopen("metis.out","w",stdout);
	int q,k,m,ans;
	cin>>q>>k>>m;
	if(q+k*m<100)
	    ans=-1;
	else if(q+m>=100)
	    ans=0;
	else if(k==1)
	    ans=0;
	else
	    ans=ceil(1.0*(100-q-m)/(k-1));
	cout<<ans;
	return 0;
}
```

## 1618. 阿斯克勒庇俄斯
```
题目描述
阿斯克勒庇俄斯(Asclepius)，是希腊神话中的医神，他非常关心人们的健康。眼前有n个人，编号1到n，其中i号的伤病值为f[i]。阿斯克勒庇俄斯有独特的神力：每一 天可以挑选一人使其伤病值减k。同时，其他没有被选中的人也有恢复，伤病值每天会减1。伤病值降为0以后就不再变化。请问m天后，能否让n人伤病值都降为0?

```
```
输入输出格式
输入格式
输入文件asclepius.in输入第一行为正整数n,k,m。n<=200000，1<=k<=1000，1<=m<=1000000。第二行为n个正整数代表每个人的初始伤病值。均不超过100000000。     
输出格式
输出文件asclepius.out输出Yes或No。
```
```
输入输出样例
输入样例#1:
3 2 1
1 1 2
输出样例#1:
Yes
输入样例#2:
4 3 2
3 4 2 3
输出样例#2:
No
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
#define N 200009
using namespace std;
int main(){
	freopen("asclepius.in","r",stdin);
	freopen("asclepius.out","w",stdout);
	int n,k,m,f[N];
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)cin>>f[i];
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(f[i]>k*m){
			cout<<"No";
			return 0;
		}
		if(f[i]<=m)continue;
		if(k>1)
		    cnt+=ceil(1.0*(f[i]-m)/(k-1));
	}
	if(cnt>m)cout<<"No";
	else cout<<"Yes";
	return 0;
}
```

## 1619. 栖息地
```
题目描述
你是一个外星领导人，你原本的外星家园遭到破坏已经不再适宜居住，所以你带着手下的n艘光速飞船(编号1到n)飞向地球，希望在地球能找到你们新的栖息地。此时， 
第i号飞船距离地球的距离为d[i]光年，速度最高为光速。突然你发现：所有飞船所携带的燃料都只够飞m年了。为了让更多飞船能够到达地球，你每年可以使用一次空间跃魔法：每年挑选一艘飞船前进最多k光年。请问m年后最多能让多少艘飞船到达地球？

```
```
输入输出格式
输入格式
输入文件habitat.in输入第一行为正整数n,k,m。n<=200000，1<=k<=1000，1<=m<=1000000。第二行为n个正整数代表每艘飞船此时到地球的距离。均不超过100000000。 
输出格式
输出文件habitat.out输出一个整数。
```
```
输入输出样例
输入样例#1:
3 2 1
1 5 2
输出样例#1:
2
输入样例#2:
4 3 2
3 5 2 4
输出样例#2:
3
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
const int N=200009;
int n,k,m,d[N];
int main(){
	freopen("habitat.in","r",stdin);
	freopen("habitat.out","w",stdout);
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)cin>>d[i];
	sort(d+1,d+1+n);
	int cnt=0,ans=0;
	for(int i=1;i<=n;i++){
		if(d[i]>k*m)break;
		if(d[i]<=m){ans++;continue;}
		if(k>1)
		    cnt+=ceil(1.0*(d[i]-m)/(k-1));
		if(cnt<=m)ans++;
		else break;
	}
	cout<<ans;
    return 0;
}
```

## 1628. 球盒问题:相同球相同盒不能空
```
题目描述
将n个相同的球放入m个相同盒子里，要求盒子都不能空。请问有多少种方案?

```
```
输入输出格式
输入格式
输入文件qiuhe1.in
输入共一行，包含正整数n和m，n<=15,m<=15。
输出格式
输出文件qiuhe1.out
输出一个整数。
```
```
输入输出样例
输入样例#1:
5 2
输出样例#1:
2
说明：4+1,2+3
输入样例#2:
7 3
输出样例#2:
4
说明：5+1+1,4+2+1,3+3+1,3+2+2
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=16;
int n,m,f[N][N];
int main(){
	freopen("qiuhe1.in", "r", stdin);
	freopen("qiuhe1.out", "w", stdout);
	cin>>n>>m;
	if(n<m){
		cout<<0;
		return 0;
	}
	for(ll i=1;i<=n;i++)f[i][1]=1;
	for(ll j=2;j<=m;j++)
	    for(ll i=j;i<=n;i++)
	        f[i][j]=f[i-1][j-1]+f[i-j][j];
	cout<<f[n][m];
	return 0;
}
```

## 1629. 球盒问题:相同球不同盒不能空
```
题目描述
将n个相同的球放入m个不同盒子里，要求盒子都不能空。请问有多少种方案?

```
```
输入输出格式
输入格式
输入文件qiuhe2.in
输入共一行，包含正整数n和m，n<=15,m<=15。
输出格式
输出文件qiuhe2.out
输出一个整数。
```
```
输入输出样例
输入样例#1:
5 2
输出样例#1:
4
说明：
4+1,3+2,2+3,1+4
输入样例#2:
7 3
输出样例#2:
15
说明：
5+1+1,
4+2+1,4+1+2,
3+3+1,3+2+2,3+1+3
2+4+1,2+3+2,2+2+3,2+1+4
1+5+1,1+4+2,1+3+3,1+2+4,1+1+5
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=16;
ll n,m;
int main(){
	freopen("qiuhe2.in", "r", stdin);
	freopen("qiuhe2.out", "w", stdout);
	cin>>n>>m;
	if(n<m){
		cout<<0;
		return 0;
	}
	ll ans=1;
	for(ll i=1;i<=m-1;i++){
		ans*=n-i;
		ans/=i; 
	}
	cout<<ans;
	return 0;
}
```

## 1630. 球盒问题:不同球相同盒不能空
```
题目描述
将n个不同的球放入m个相同盒子里，要求盒子都不能空。请问有多少种方案?

```
```
输入输出格式
输入格式
输入文件qiuhe3.in
输入共一行，包含正整数n和m，n<=15,m<=15。
输出格式
输出文件qiuhe3.out
输出一个整数。
```
```
输入输出样例
输入样例#1:
3 2
输出样例#1:
3
说明：{1,2,3}共三个小球放入2个相同的盒子里共有3种方案：
1和2放一起，3独立放。1和3放一起，2独立放。2和3放一起，1独立放
输入样例#2:
4 2
输出样例#2:
7
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=16;
int n,m,S[N][N];
int main(){
	freopen("qiuhe3.in", "r", stdin);
	freopen("qiuhe3.out", "w", stdout);
	cin>>n>>m;
	if(n<m){
		cout<<0;
		return 0;
	}
	for(ll i=1;i<=n;i++)S[i][1]=1;
	for(ll j=2;j<=m;j++)
	    for(ll i=j;i<=n;i++)
	        S[i][j]=S[i-1][j-1]+j*S[i-1][j];
	cout<<S[n][m];
	return 0;
}
```

## 1631. 球盒问题:不同球不同盒不能空
```
题目描述
将n个不同的球放入m个不同盒子里，要求盒子都不能空。请问有多少种方案?

```
```
输入输出格式
输入格式
输入文件qiuhe4.in
输入共一行，包含正整数n和m，n<=15,m<=15。
输出格式
输出文件qiuhe4.out
输出一个整数。
```
```
输入输出样例
输入样例#1:
3 2
输出样例#1:
6
说明：{1,2,3}共三个小球放入2个不同的盒子里共有6种方案：
1和2放第一个盒子，3独立放第二个盒子；
1和3放第一个盒子，2独立放第二个盒子；
2和3放第一个盒子，1独立放第二个盒子；
3独立放第一个盒子，1和2放第二个盒子；
2独立放第一个盒子，1和3放第二个盒子；
1独立放第一个盒子，2和3放第二个盒子；
输入样例#2:
8 3
输出样例#2:
5796
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=16;
int n,m,S[N][N];
int main(){
	freopen("qiuhe4.in", "r", stdin);
	freopen("qiuhe4.out", "w", stdout);
	cin>>n>>m;
	if(n<m){
		cout<<0;
		return 0;
	}
	for(ll i=1;i<=n;i++)S[i][1]=1;
	for(ll j=2;j<=m;j++)
	    for(ll i=j;i<=n;i++)
	        S[i][j]=S[i-1][j-1]+j*S[i-1][j];
	ll ml=1;
	for(ll i=1;i<=m;i++)ml*=i;
	cout<<S[n][m]*ml;
	return 0;
}
```

## 1645. 树上基本统计（模板题）
```
题目描述
输入一棵树，1是根节点。求每个节点的父节点、深度、子树大小、子树高度
```
```
输入输出格式
输入格式
第1行一个正整数n（<=100000）
后面n-1行每行2个正整数u,v，表示u,v之间有一条边（1<=u,v<=n，保证全图连通）
输出格式
n行每行4个整数，第i行依次表示节点i的父节点编号、深度、子树大小（节点数）、子树高度
规定根节点的父节点输出0，根节点深度为1，叶节点高度为1
```
```
输入输出样例
输入样例#1:
6
2 1
3 2
4 2
5 4
6 2
输出样例#1:
0 1 6 4
1 2 5 3
2 3 1 1
2 3 2 2
4 4 1 1
2 3 1 1
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int n,h[N],sz[N],p[N],d[N];
vector<int> to[N];
void add(int u,int v){
	to[u].push_back(v);
	to[v].push_back(u);
}
void input(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
}
void dfs(int u,int fa){
	p[u]=fa;
	d[u]=d[fa]+1;
	sz[u]=1;
	h[u]=1;
	for(int i=0;i<to[u].size();i++){
		int v=to[u][i];
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		h[u]=max(h[u],h[v]+1);
	}
}
int main(){
	input();
	dfs(1,0);
	for(int i=1;i<=n;i++)cout<<p[i]<<" "<<d[i]<<" "<<sz[i]<<" "<<h[i]<<endl; 
	return 0;
}
```

## 1646. 二进制转十进制
```
题目描述
将一个二进制数转换成十进制数。
```
```
输入输出格式
输入格式
输入一行01串，长度不超过60。
输出格式
输出一个整数。
```
```
输入输出样例
输入样例#1:
111
输出样例#1:
7
输入样例#2:
1111
输出样例#2:
15
输入样例#3:

输出样例#3:

```
```
#include<iostream>
#include<string>
#include<cmath> 
using namespace std;
int main(){
	long long result=0;
	string s;
	cin>>s;
	for(int i=0; i<s.size(); i++){ 
		result *= 2;
		if(s[i]=='1')result++; 
	}
	cout<<result; 
	return 0; 
}
```

## 1655. 站岗放哨2
```
题目描述
一条直线上，你安排了n个哨兵站岗放哨，编号从1到n。其中i号哨兵的坐标位置是x[i]。不会有哨兵站在相同的位置。作为指挥官，你需要知道3个信息：
1.从左到右，每个哨兵的坐标依次是几?
2.从左到右，每个哨兵依次是几号哨兵?
3.哨兵编号从1到n，每个哨兵依次站在从左到右的第几个?
```
```
输入输出格式
输入格式
输入文件guard.in
输入第一行包含正整数n。1<=n<=100000。第二行共n个正整数，代表每个哨兵的坐标，均不超过1000000000。
输出格式
输出文件guard.out
输出共3行，每行n个正整数。
```
```
输入输出样例
输入样例#1:
5
7 8 10 6 9
输出样例#1:
6 7 8 9 10
4 1 2 5 3
2 3 5 1 4
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
struct guard{
	int x, id;
};
bool cmp(const guard&u,const guard&v){
	return u.x<v.x;
}
int main(){
	freopen("guard.in","r",stdin);
	freopen("guard.out","w",stdout);
	int n, rk[100000];
	guard g[100000];
	cin>>n;
	for(int i=1;i<=n;i++) cin>>g[i].x;
	for(int i=1;i<=n;i++) g[i].id=i;
	sort(g+1,g+1+n,cmp);
	for(int i=1;i<=n;i++) rk[g[i].id]=i;
	for(int i=1;i<=n;i++) cout<<g[i].x<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<g[i].id<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<rk[i]<<" ";
	cout<<endl;
	return 0;
} 
```

## 1656. 并列排名2
```
题目描述
你作为教务老师，手上有一份n名学生的成绩，你需要计算每个学生排第几名，注意会出现并列名次。
```
```
输入输出格式
输入格式
输入文件rank.in
输入第一行为正整数n，n<=100000。第二行是n个正整数分数,在0到1000000000之间。
输出格式
输出文件rank.out
输出共一行，有n个正整数依次代表每人的名次，由空格隔开。
```
```
输入输出样例
输入样例#1:
4
59 100 99 100
输出样例#1:
4 1 3 1
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
int n;
int x[100008];
int id[100008];
int rk[100008];
bool cmp(const int&a,const int&b){
	return x[a]>x[b];
}
int main(){
	freopen("rank.in", "r", stdin);
	freopen("rank.out", "w", stdout);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+1+n,cmp);
	for(int i=1;i<=n;i++) rk[id[i]]=i;
	
	for(int i=1;i<=n-1;i++)
		if(x[id[i]]==x[id[i+1]])
		    rk[id[i+1]]=rk[id[i]];
	for(int i=1;i<=n;i++) cout<<rk[i]<<" ";
	return 0;
}
```
## 1657. 枚举子集
```
题目描述
有n个数字组成的集合，{1,2,3,...,n}。请枚举所有非空子集。

输出的先后顺序遵循以下规则：

1.每行输出一个子集，每个子集的元素从小到大输出，由空格隔开，行末不能有空格。

2.较小数字开头的子集比较大数字开头的子集先输出。

3.开头数字一样的话，再依次比较后续数字。后续有数字的子集先输出，后续没有数字的子集后输出。

输入输出格式
输入格式
输入文件subsets.in
输入第一行包含正整数n。1<=n<=15。
输出格式
输出文件subsets.out
输出共n行，每行若干个正整数。
```
```
输入输出样例
输入样例#1:
3
输出样例#1:
1 2 3
1 2
1 3
1
2 3
2
3
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
int n,ok[20],p[20];
void print(){
	int m=-1;
	for(int i=0;i<=n;i++)
	    if(ok[i])p[++m]=i;
	if(m==-1)return;
	for(int i=0;i<m;i++)
	    cout<<p[i]<<" ";
	cout<<p[m]<<endl;
}
void dfs(int x){
	if(x==n+1){
		print();
		return;
	}
	ok[x]=1;
	dfs(x+1);
	ok[x]=0;
	dfs(x+1);
}
int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout); 
	cin>>n;
	dfs(1);
	return 0;
}
```
## 1658. 枚举组合
```
题目描述
有n个数字组成的集合，{1,2,3,...,n}。给定一个m，1<=m<=n。对于从n个数里选m个数的组合情况，请枚举所有可能方案。

输出的先后顺序遵循以下规则：

1.每行输出一个组合，每个组合的元素从小到大输出，由空格隔开，行末不能有空格。

2.较小数字开头的组合大数字开头的组合先输出。

3.开头数字一样的话，再依次比较后续数字。

输入输出格式
输入格式
输入文件combinations.in
输入第一行包含正整数n和m。1<=m<=n<=15。
输出格式
输出文件combinations.out
输出共C(n,m)行，每行若干个正整数。
```
```
输入输出样例
输入样例#1:
3 2
输出样例#1:
1 2
1 3
2 3
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
int n,m,p[20];
void print(){
	for(int i=1;i<m;i++)
	    cout<<p[i]<<" ";
	cout<<p[m]<<endl;
}
void dfs(int x,int c){
	if(c==m){
		print();
		return;
	}
	if(c+n+1-x<m)return;
	if(x==n+1)return;
	p[c+1]=x;
	dfs(x+1,c+1);
	dfs(x+1,c);
}
int main(){
	freopen("combinations.in","r",stdin);
	freopen("combinations.out","w",stdout); 
	cin>>n>>m;
	dfs(1,0);
	return 0;
}
```

## 1720. 俄狄浦斯
```
题目描述
传说有一个大家族里共n名男性成员，编号1到n。其中共有n-1条父子关系。现在他们要挑选若干人组成家族护卫队抵抗外族入侵。i号成员的战斗力为z[i], 大家当然希 望挑选最强护卫队。但是为了防止“父子矛盾”的魔咒应验，大家决定不会让父子两人同时入选。请问护卫队选出的队员总战斗力最大是多少?

```
```
输入输出格式
输入格式
输入文件oedipus.in 输入第一行为正整数n，n<=100000. 第二行共n个正整数，依次为成员们的战斗力，均不超过10000。再接着n-1行，每行输入父子关系，由两个正整a,b代表b是a的父亲。
输出格式
输出文件oedipus.out 输出一个整数。
```
```
输入输出样例
输入样例#1:
3
5 2 2
2 1
3 1
输出样例#1:
5
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
const int N=100009;
long long n,f[N][2],z[N];
vector<long long> es[N];
void dfs(int u,int fa){
	f[u][1]=z[u];
	f[u][0]=0;
	for(int i=0;i<es[u].size();i++){
		int v=es[u][i];
		if(v==fa)continue;
		dfs(v,u);
		f[u][1]+=f[v][0];
		f[u][0]+=max(f[v][0],f[v][1]);
	}
}
int main(){
	freopen("oedipus.in","r",stdin);
	freopen("oedipus.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>z[i];
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		es[x].push_back(y);
		es[y].push_back(x);
	}
	dfs(1,0);
	cout<<max(f[1][0],f[1][1])<<endl;
	return 0;
}
```

## 1721. 非常棒
```
题目描述
请写一个程序，使用一句Very good界面，具体形状请参考下文中的输出样例。
注意：
一共3行，每一行都有一个换行，行之间不能有多余空行；
行末不应该出现多余空格。
```
```
输入输出格式
输入格式
无
输出格式
无
```
```
输入输出样例
输入样例#1:
无
输出样例#1:
**********
Very good!
**********

输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

```
```
#include<iostream>
using namespace std;
int main(){
	cout<<"**********"<<endl;
	cout<<"Very good!"<<endl;
	cout<<"**********"<<endl;
	return 0;
}
```

## 1722. 美丽的等边三角形
```
题目描述
请写一个程序，输出一个等边三角形，具体形状请参考下文中的输出样例。
注意：
一共3行，每一行都有一个换行，行之间不能有多余空行。
行末不应该出现多余空格。
第3行开头没有空格。
同一行的*号之间可能需要空格。
```
```
输入输出格式
输入格式
无
输出格式
无
```
```
输入输出样例
输入样例#1:
无
输出样例#1:
  *
 * *
* * *
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<iostream>
using namespace std;
int main(){
	cout<<"  *"<<endl;
	cout<<" * *"<<endl;
	cout<<"* * *"<<endl;
	return 0;
}
```

## 1725. 口算王子
```
题目描述
口算王子就是你，两个数字间的运算对你来说就是小菜一碟。已知一条计算式子，请你回答出计算结果。
```
```
输入输出格式
输入格式
输入文件calculation.in  输入一行包含一条算式，包含两个正整数a,b，均不超过10^9。这两个数中间有一个运算符号c，可能是加号+ ，或者减号-，或者乘号*。这一行内没有空格。
输出格式
输出文件calculation.out 输出一个整数。
```
```
输入输出样例
输入样例#1:
3+6
输出样例#1:
9
输入样例#2:
6*16
输出样例#2:
96
输入样例#3:
12345*54321
输出样例#3:
670592745
```
```
#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("calculation.in", "r", stdin);
	freopen("calculation.out", "w", stdout);
	long long a, b, ans;
	char c;
	cin>>a>>c>>b;
	if(c == '+')
	    ans=a+b;
	else if (c == '-')
	    ans=a-b;
	else
	    ans=a*b;
	cout<<ans<<endl;
	return 0;
}
```

## 1730. 恢复通车
```
题目描述
不久前爆发了一种新型病毒，传染性极强。为了阻断传染病病毒的传播，全国各大城市都采取了封城措施：城市间的所有交通全部中断，以保证隔离的效果。经过一年的
离，全国已经没有新增确诊病例了，于是城市间的高速公路会逐步恢复。已知共有m个城市，编号1到m。共有n条双向高速公路按照顺序依次恢复，每天恢复一条高速公公。按照给定顺序逐步恢复，请问在第几天时全国所有城市都能连通。

```
```
输入输出格式
输入格式
输入文件transportation.in 输入第一行包含正整数m和n，m<=10000,n<=100000。接着n行每行两个正整数u,v，代表高速公路链接的两个城市，1<=u<v<=n。按照输入顺 序恢复各个高速公路。
输出格式
输出文件transportation.out 输出一个整数代表天数。若无解输出-1。
```
```
输入输出样例
输入样例#1:
3 4
1 2
1 2
1 3
2 3
输出样例#1:
3
输入样例#2:
4 5
1 2
2 3
1 3
3 4
1 4
输出样例#2:
4
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100009;
int n,m,id[N];
ll root(ll x){
	if(id[x]==x)return x;
	return id[x]=root(id[x]);
}
void unite(ll x,ll y){
	ll rx=root(x),ry=root(y);
	id[rx]=ry;
}
int main(){
	freopen("transportation.in", "r", stdin);
	freopen("transportation.out", "w", stdout);
	cin>>m>>n;
	int cnt=m;
	for(ll i=0;i<N;i++)id[i]=i;
	for(ll t=1;t<=n;t++){
		int u,v;
		cin>>u>>v;
		int ru=root(u);
		int rv=root(v);
		if(ru==rv)continue;
		unite(ru,rv);
		cnt--;
		if(cnt==1){
			cout<<t<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}
```

## 1744. 友谊号渡船
```
题目描述
有 n 个人要过河，第i人重w[i]。每艘小船只有2个位置，最大载重为c。求最少要几艘船?

```
```
输入输出格式
输入格式
输入文件friendship.in 输入第一行为正整数n和c，代表人数和载重，n,c<=10^5。第二行共n个正整数，代表体重，均不超过c。
输出格式
输出文件friendship.out 输出一个整数。
```
```
输入输出样例
输入样例#1:
3 10
7 6 5
输出样例#1:
3
输入样例#2:
5 10
7 6 2 2 5
输出样例#2:
3
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
int n,c,w[N];
int main(){
	freopen("friendship.in", "r", stdin);
	freopen("friendship.out", "w", stdout);
	cin>>n>>c;
	for(ll i=1;i<=n;i++)cin>>w[i];
	sort(w+1,w+1+n);
	ll ans=0;
	ll i=1,j=n;
	while(i<=j){
		ans++;
		ll r=c-w[j];
		j--;
		if(w[i]<=r)
		    i++;
	}
	cout<<ans;
	return 0;
}
```

## 1776. 建大桥
```
题目描述
你拥有n个小岛，编号1到n。作为岛主，你找人设计了m座桥，第i座桥连接ai号和bi号岛，颜值为yi。你希望所有岛之间都能通过桥直接或间接连通，所以你会选择恰好n-1座桥。同时你希望选中的桥的颜值总和尽量大，请问最大颜值总和是多少？

保证能找到连通方案。

输入输出格式
输入格式
输入文件bridge.in 输入n,m，n<=100,m<=5000。接着m行为桥的信息，每一行包含正整数ai,bi,yi，其中ai<=n,bi<=n，ai和bi不同，yi<=1000.
输出格式
输出文件bridge.out输出一个整数。
```
```
输入输出样例
输入样例#1:
3 3
1 2 2
2 3 3
3 1 4
输出样例#1:
7
输入样例#2:
4 5
1 2 4
1 3 5
2 3 3
2 4 2
3 4 1
输出样例#2:
11
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
#define N 109
#define M 5009
using namespace std;
struct edge{int u,v,w;};
edge e[M];
int n,m,id[N];
int root(int u){
	return id[u] == u?u:id[u]=root(id[u]);
}
bool cmp(const edge&a,const edge&b){
	return a.w<b.w;
}
void Kruskal(){
	sort(e,e+m,cmp);
	reverse(e,e+m);
	for(int u=1;u<=n;u++)id[u]=u;
	int ans=0,cnt=0;
	for(int k=0;k<m;k++){
		int ru=root(e[k].u);
		int rv=root(e[k].v);
		if(ru==rv)continue;
		id[ru]=rv;
		ans+=e[k].w;
		cnt++;
		if(cnt==n-1)break;
	}
	cout<<ans<<endl;
}
int main(){
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	    cin>>e[i].u>>e[i].v>>e[i].w;
	Kruskal();
	return 0;
}
```

## 1780. 闰年统计
```
题目描述
给定两个年份a,b ，请统计从a到b的年份里有几个闰年。
注意：统计时包含a，b两年本身在内。
```
```
输入输出格式
输入格式
输入文件leapyear.in 输入一行为正整数a，b，1<=a<=b<=9999。
输出格式
输出文件leapyear.out 输出一个整数。
```
```
输入输出样例
输入样例#1:
2000 2020
输出样例#1:
6
输入样例#2:
21 23
输出样例#2:
0
输入样例#3:

输出样例#3:

```
```
#include<bits/stdc++.h>
using namespace std;
bool isLeap(int y){
	return y%400==0||y%4==0&&y%100!=0;
}
int main(){
	freopen("leapyear.in", "r", stdin);
	freopen("leapyear.out", "w", stdout);
	int a,b,cnt;
	cin>>a>>b;
	for(int i = a;i <= b; i++){
		if(isLeap(i))
		    cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}
```

## 1781. 回文数统计
```
题目描述
输入n个正整数，判断每个数是否为回文数。
```
```
输入输出格式
输入格式
输入文件palindrome.in  输入第一行为正整数n，n<=100。第二行为n个正整数，由空格隔开，均不超过10^18。
输出格式
输出文件palindrome.out 输出一行，共n个结果，每个结果为Yes或No，由空格隔开。
```
```
输入输出样例
输入样例#1:
5
2020 12321 567765 1991 2000000
输出样例#1:
No Yes Yes Yes No
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

```
```
#include<bits/stdc++.h>
using namespace std;
bool isHW(string s){
    int l=0;
    int r=s.size()-1;
    while(l<r){
        if(s[l]!=s[r])
            return 0;
        l++;
        r--;
    }
    return 1;
}
int main(){
    freopen("palindrome.in", "r", stdin);
    freopen("palindrome.out", "w", stdout);
    int n;
    cin>>n;
    for(int i = 0; i < n;++i){
    	string s;
    	cin>>s;
    	if(isHW(s))
    	    cout<<"Yes"<<" ";
    	else
    	    cout<<"No"<<" ";
	}
	return 0;
}
```

## 1796. 最大子段和
```
题目描述
"段"是连续段的缩写，也叫作区间，都蕴含着"连续"的含义。

有n个整数的序列，编号1到n。第i个数值为x[i]，当然x[i]可能是负数。你可以挑选一段任意连续段求和（但不能不选），请计算结果最大是多少？并输出总和最大这段结尾是第几个数。若有多个解输出编号最小的

输入输出格式
输入格式
输入文件subsequence.in 输入第1行为正整数n，n<=100000。第2行为n个整数，均不超过10000。
输出格式
输出文件subsequence.out 输出一行包含两个整数。
```
```
输入输出样例
输入样例#1:
5
3 -1 -2 3 -2
输出样例#1:
3 1
输入样例#2:
3
-1 1 3
输出样例#2:
4 3
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int s,n,x[N],f[N];
int main(){
    freopen("subsequence.in", "r", stdin);
    freopen("subsequence.out", "w", stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>x[i];
	
	f[0]=0;
	for(int i=1;i<=n;++i)
	    f[i]=max(f[i-1],0)+x[i];
	int ans=*max_element(f+1,f+1+n);
	s=max_element(f+1,f+1+n)-f;
	cout<<ans<<" "<<s;
	return 0;
}
```

## 1797. 西佳佳偶像天团0
```
题目描述
西佳佳偶像天团共k人，编号1到k。第i人的颜值为x[i]，团内颜值最低者成为团长，若有多人一样丑，就选编号最小的那人。求团长是几号，颜值是多 少。
```
```
输入输出格式
输入格式
输入文件idol.in 输入第一行为k，1<=k<=200000。第二行为k个正整数，每个数都不超过100000。
输出格式
输出文件idol.out 输出共2个数字，由空格隔开。
```
```
输入输出样例
输入样例#1:
10
4 3 2 1 2 3 4 5 4 6
输出样例#1:
4 1
输入样例#2:
5
7 6 9 7 6
输出样例#2:
2 6
输入样例#3:

输出样例#3:

```
```
#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("idol.in", "r", stdin);
	freopen("idol.out", "w", stdout);
	int n,idols[200001];
	cin>>n;
	for(int i = 0; i < n; i ++){
		cin>>idols[i];
	}
	cout<<min_element(idols, idols+n) - idols + 1<<" "<<*min_element(idols, idols + n);
	return 0;
}
```

最后修改：2022 年 08 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

吴凡的题库——快快编程1601-1800

WinRTAS • 2022 年 08 月 11 日

## 1628. 球盒问题:相同球相同盒不能空
```
题目描述
将n个相同的球放入m个相同盒子里，要求盒子都不能空。请问有多少种方案?

## 1629. 球盒问题:相同球不同盒不能空
```
题目描述
将n个相同的球放入m个不同盒子里，要求盒子都不能空。请问有多少种方案?

## 1630. 球盒问题:不同球相同盒不能空
```
题目描述
将n个不同的球放入m个相同盒子里，要求盒子都不能空。请问有多少种方案?

## 1631. 球盒问题:不同球不同盒不能空
```
题目描述
将n个不同的球放入m个不同盒子里，要求盒子都不能空。请问有多少种方案?

输出样例#3:

输出的先后顺序遵循以下规则：

1.每行输出一个子集，每个子集的元素从小到大输出，由空格隔开，行末不能有空格。

2.较小数字开头的子集比较大数字开头的子集先输出。

3.开头数字一样的话，再依次比较后续数字。后续有数字的子集先输出，后续没有数字的子集后输出。

输出的先后顺序遵循以下规则：

1.每行输出一个组合，每个组合的元素从小到大输出，由空格隔开，行末不能有空格。

2.较小数字开头的组合大数字开头的组合先输出。

3.开头数字一样的话，再依次比较后续数字。

输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

```
```
#include<iostream>
using namespace std;
int main(){
	cout<<"**********"<<endl;
	cout<<"Very good!"<<endl;
	cout<<"**********"<<endl;
	return 0;
}
```

## 1744. 友谊号渡船
```
题目描述
有 n 个人要过河，第i人重w[i]。每艘小船只有2个位置，最大载重为c。求最少要几艘船?

保证能找到连通方案。

输出样例#3:

输出样例#2:

输入样例#3:

输出样例#3:

## 1796. 最大子段和
```
题目描述
"段"是连续段的缩写，也叫作区间，都蕴含着"连续"的含义。

输出样例#3:

吴凡的题库——快快编程1601-1800

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

吴凡的题库——快快编程801-1000

吴凡的题库——快快编程1001-1200

宝塔面板设置反代并添加ssl

使用 Python 来自动回微信

VS Code 和 Python：数据科学的天作之合

Docker 火了！外部网络可直接访问映射到 127.0.0.1 的服务。。。

神器！轻松用 Python 写个 APP！

狂揽两千星，速度百倍提升，高性能 Python 编译器 Codon 火了！

好用API分享

吴凡的题库——快快编程601-800

吴凡的题库——快快编程1601-1800

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

吴凡的题库——快快编程1601-1800

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款