问题 A: 1的个数
题目描述
输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。
输入
输入一个整数（int类型）。
输出
这个数转换成2进制后，输出1的个数。
样例输入 Copy
5样例输出 Copy
2
#include<stdio.h>
int main()
{
int n,s=0;
scanf("%d",&n);
while(n!=0)
{
if(n%2==1)
s++;
n/=2;
}
printf("%d\n",s);
return 0;
}问题 B: 又一道简单题
题目描述
输入一个四个数字组成的整数 n，你的任务是数一数有多少种方法，恰好修改一个数字，把它 变成一个完全平方数（不能把首位修改成 0）。比如 n=7844，有两种方法：3844=622 和 7744=882。
输入
输入第一行为整数 T (1<=T<=1000)，即测试数据的组数，以后每行包含一个整数 n (1000<=n<=9999)。
输出
对于每组数据，输出恰好修改一个数字，把 n变成完全平方数的方案数
样例输入 Copy
2 7844 9121样例输出 Copy
Case 1: 2 Case 2: 0
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =5e2 +5;
const int M =1e5 +7;
const int inf =0x3fffffff;
const double pi = acos(-1.0);
int m=1;
bool fun(int n){
int nn=sqrt(n);
return (nn*nn==n);
}
void solve(){
int n;
cin>>n;
string s=to_string(n);
int sum=0;
for(int i=0;i<4;i++){
for(char j='0';j<='9';j++){
if(i==0&&j=='0'){
continue;
}
if(s[i]==j){
continue;
}
string ss=s;
ss[i]=j;
int num=stoi(ss);
if(fun(num)){
sum++;
}
}
}
cout<<"Case "<<m++<<": "<<sum<<"\n";
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int t;cin>>t;while(t--)
solve();
return 0;
}问题 C: 安置路灯
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数 接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。 第二行一个字符串s表示道路的构造,只包含'.'和'X'。输出
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。样例输入 Copy
2 3 .X. 11 ...XX....XX样例输出 Copy
1 3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
void solve(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
int sum=0;
for(int i=0;i<s.size();){
if(s[i]=='X'){
i++;
}
else {
sum++;
i+=3;
}
}
cout<<sum<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
return 0;
}问题 D: 单源最短路径问题
编程实现Dijkstra算法，求一个有向加权图中，从源点出发到其他各个顶点的最短路径。
输入
第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边（两个顶点，边的起点和终点）及权重。
输出
顶点0到每一个顶点的最短路径长度。
样例输入 Copy
5 7 0 1 10 0 3 30 0 4 100 1 2 50 2 4 10 3 2 20 3 4 60样例输出 Copy
0 10 50 30 60
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5 +5;
const int M =1e9 +7;
const int inf =0x3fffffff;
const double pi = acos(-1.0);
struct node{
int id,dis;
bool operator<(const node& other) const {
return dis > other.dis;
}
}x;
priority_queue<node> q;
vector<node> a[N];
int n,m,w[N];
bool b[N];
void bfs(){
q.push({0,0});
while(!q.empty()){
x=q.top();
q.pop();
if(b[x.id]){
continue;
}
b[x.id]=1;
w[x.id]=x.dis;
for(int i=0;i<a[x.id].size();i++){
if(!b[a[x.id][i].id]){
q.push({a[x.id][i].id,x.dis+a[x.id][i].dis});
}
}
}
}
void solve(){
int u,v,d;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>d;
a[u].push_back({v,d});
}
bfs();
for(int i=0;i<n;i++){
cout<<w[i]<<" \n"[i==n];
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
solve();
return 0;
}问题 E: ABC + DEF = GHI
用1, 2, 3...9 这九个数字组成一个数学公式，满足：ABC + DEF = GHI，每个数字只能出现一次，编写程序输出所有的组合。
输入
无
输出
输出所有的 ABC + DEF = GHI，
每行一条数据，格式为ABC+DEF=GHI
输出结果按照ABC升序排列，如果ABC相同，则按照DEF升序排列。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =5e2 +5;
const int M =1e5 +7;
const int inf =0x3fffffff;
const double PI = acos(-1.0);
int a[9]= {1,2,3,4,5,6,7,8,9};
int abc,def,ghi;
void solve()
{
do
{
abc=a[0]*100+a[1]*10+a[2];
def=a[3]*100+a[4]*10+a[5];
ghi=a[6]*100+a[7]*10+a[8];
if(abc+def==ghi) cout<<abc<<"+"<<def<<"="<<ghi<<'\n';
} while(next_permutation(a,a+9));
}
int main() {
cin.tie(0)->sync_with_stdio(false);
solve();
return 0;
}问题 F: 油田问题
题目描述
输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），即属于同一个八连块。
输入
多组输入
输入行数m，以及列数n。
然后输入*和@
1<=n,m<=100输出
联通块个数样例输入 Copy
5 5 ****@ *@@*@ *@**@ @@@*@ @@**@样例输出 Copy
2
#include <bits/stdc++.h>
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int m, n;
char a[105][105];
bool b[105][105];
using namespace std;
void dfs(int x, int y)
{
b[x][y] = true;
for (int i = 0; i < 8; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && a[nx][ny] == '@' && !b[nx][ny])
dfs(nx, ny);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> m >> n)
{
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
cin >> a[i][j];
int s = 0;
memset(b, 0, sizeof(b));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (a[i][j] == '@' && !b[i][j])
{
dfs(i, j);
s++;
}
cout << s << '\n';
}
return 0;
}问题 G: 迷宫问题（回溯法求解）
输入一个n×n的迷宫，定义左上角为起点，右下角为终点，寻找一条从起点到终点的路径
输入
多组输入
每组输入第一行有两个整数n，m表示迷宫尺寸
后跟n行，每行m个字符0表示道路，1表示墙壁
1<=n,m<=10输出
输出地图，用2表示路径
多个答案输出任意一种即可样例输入 Copy
5 5 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0样例输出 Copy
2 1 1 1 1 2 2 2 2 1 1 1 1 2 1 0 0 0 2 1 0 1 1 2 2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 +5;
const int M = 1e9 +7;
const int inf = 0x3fffffff;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int a[15][15];
bool b[15][15];
int n,m;
bool t;
bool check(int x,int y){
if(x>=0&&x<n&&y>=0&&y<m&&!b[x][y]&&a[x][y]==0){
return true;
}
return false;
}
void dfs(int x,int y){
if(x==n-1&&y==m-1){
b[x][y]=true;
t=true;
return;
}
for(int i=0;i<4;i++){
int xx=dx[i]+x;
int yy=dy[i]+y;
if(check(xx,yy)){
b[xx][yy]=true;
dfs(xx,yy);
if(t){
a[xx][yy]=2;
return;
}
b[xx][yy]=false;
}
}
}
void solve(){
while(cin>>n>>m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
b[0][0]=true;
dfs(0,0);
a[0][0]=2;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
memset(b,false,sizeof b);
t=false;
}
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
return 0;
}问题 H: 低碳出行
题目描述
为了做一项关于“爱护环境，从小做起”的公益调查，新司机小明决定开老爸的车从家中前往X市第一小学。从小明家到X市第一小学的交通网络图一共有n个顶点（包括起点小明家和终点X市第一小学）和m条无向边。每条边都有一个碳排放量和一个行驶时间（单位：分钟）。
现在需要你编写一个程序帮助小明实现低碳出行，即寻找一条碳排放量最少的路径，一条路径的碳排放量等于该路径上所有边的碳排放量之和。如果存在两条碳排放量相同的路径，则找出总的行驶时间最少的路径，并输出该路径的总碳排放量和总的时间（分钟）。输入
单组输入。
在每组输入中，第1行包含两个正整数n和m，分别表示顶点数和边数（n<=1000且m<=1000）。其中，第1号顶点为起点（小明家），第n号顶点为终点（X市第一小学）。两个正整数之间用空格隔开。
第2行到第m+1行表示m条边的信息，每一行包含四个正整数。第1个正整数和第2个正整数表示一条边所对应的两个顶点的编号，第3个正整数表示该边对应的碳排放量，第4个正整数表示该边所对应的行驶时间（单位：分钟）。四个正整数两两之间用空格隔开。输出
对于每组输入，输出碳排放量最少的路径的总碳排放量和总时间（分钟），如果存在两条碳排放量相同的路径，则输出总的行驶时间最少的路径的总碳排放量和总时间。
样例输入 Copy
3 3 1 2 5 5 1 3 8 11 2 3 3 5样例输出 Copy
8 10
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e3 +5;
const int M =1e9 +7;
const int inf =0x3fffffff;
const double pi = acos(-1.0);
struct node{
int id,dis,time;
bool operator<(const node& other) const {
if(dis==other.dis){
return time>other.time;
}
return dis>other.dis;
}
}x;
priority_queue<node> q;
vector<node> a[N];
int n,m,dis[N],t[N];
bool b[N];
void dijkstra(){
q.push({1,0,0});
while(!q.empty()){
x=q.top();
q.pop();
if(b[x.id]){
continue;
}
b[x.id]=true;
dis[x.id]=x.dis;
t[x.id]=x.time;
for(int i=0;i<a[x.id].size();i++){
if(!b[a[x.id][i].id]){
q.push({a[x.id][i].id,x.dis+a[x.id][i].dis,x.time+a[x.id][i].time});
}
}
}
}
void solve(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,c,t;
cin>>u>>v>>c>>t;
a[u].push_back({v,c,t});
a[v].push_back({u,c,t});
}
dijkstra();
cout<<dis[n]<<" "<<t[n]<<"\n";
}
int main() {
cin.tie(0)->sync_with_stdio(false);
solve();
return 0;
}