A.简单计算
题目描述
键盘输入两个数，打印它们的和。
输入
共1行，有两个数（中间用空格隔开），分别表示两个加数。
输出
共1行，输出两个数的和。
样例输入
3 5
样例输出
8
解题思路：
签到题a+b，但是要注意数据范围，这个题用int可能会爆，注意用long long输入
A.cpp
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
LL a,b;
cin >> a >> b;
cout << a + b;
return 0;
}
A.java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
System.out.println(cin.nextLong() + cin.nextLong());
cin.close();
}
}
B.排序
题目描述
将四个整数进行从小到大的顺序排列, 每一个数 范围[0,10000]
输入
四个整数
输出
从小到大输出这四个数，每两个数用一个空格隔开，行末没有空格。
样例输入
5 3 4 2
样例输出
2 3 4 5
解题思路：
简单的排序，可以直接调用排序函数轻松AC
B.cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int a[4];
for(int i=0;i<4;i++)cin >> a[i];
sort(a,a+4);
for(int i=0;i<4;i++)cout << a[i] << " ";
return 0;
}
B.java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int []a = new int[4];
for(int i=0;i<4;i++){
a[i] = cin.nextInt();
}
Arrays.sort(a);
for(Integer i:a){
System.out.print(i + " ");
}
cin.close();
}
}
C.后缀排序
题目描述
对于一个字符串，将其后缀子串进行排序，例如grain
其子串有：
grain
rain
ain
in
n
然后对各子串按字典顺序排序，即：
ain,grain,in,n,rain
输入
多组输入，每组输入为一行字符串。
输出
将子串排序输出，每行一个字符串
样例输入
grain
banana
样例输出
ain
grain
in
n
rain
a
ana
anana
banana
na
nana
解题思路：
这个题可以遍历，一个字符串的子串个数就是这个字符串的长度，先将字符串分解为若干个子串，然后调用sort函数进行排序就能顺利AC。
C.cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string s;
while(cin >> s){
string a[s.length()];
int i = 0;
for(int i=0;i<s.length();i++){
a[i] = s.substr(i,s.length() - i);//分解成s.length()个子串
}
sort(a,a+s.length());
for(auto &i:a){
cout << i << "\n";
}
}
return 0;
}
C.java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
String s = cin.next();
String [] a = new String[s.length()];
for(int i=0;i<s.length();i++){
a[i] = s.substring(i,s.length());
}
Arrays.sort(a);
for(String i:a){
System.out.println(i);
}
}
cin.close();
}
}
D. 数学猜想
题目描述
著名的哥德巴赫猜想可以表述为：一个不小于6的偶数总可以写成两个素数和，比如8=5+3;爱好思考数学的老赵，发现了一个新的的数学猜想：
对任何一个不小于6的整数 n 似乎都可以拆成 三个素数 p,q,r的和 ,比如6=2+2+2,7=2+2+3,15=3+5+7=5+5+5,输出的三个素数 p,q,r 满足 p+q+r=n
输入
一个不小于6的整数n, 6≤n≤2∗109
输出
输出的三个素数 p,q,r 满足 p+q+r=n
样例输入
15
样例输出
5 5 5
解题思路：
最简单的方法就是构造法，可以直接构造出2,p,q和3,p,q的组合，然后直接遍历求出符合题目要求的p和q即可。
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int maxn = 1e8;
bool prime(int n){
if(n < 2)return false;
if(n == 2)return true;
if(n % 2 == 0)return false;
for(int i=3;i*i<=n;i+=2){
if(n % i == 0)return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
LL n;
cin >> n;
if(n % 2 == 0){
n -= 2;
cout << 2 << " ";
} else {
n -= 3;
cout << 3 << " ";
}
for(int i=2;i<=n;i++){
if(prime(i) && prime(n-i)){
cout << i << " " << n - i;
break;
}
}
return 0;
}
D.java
import java.util.Scanner;
public class Main{
static boolean isprime(int n){
if(n < 2)return false;
if(n == 2)return true;
if(n % 2 == 0)return false;
for(int i=3;i*i<=n;i+=2){
if(n % i == 0)return false;
}
return true;
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int n = cin.nextInt();
if(n % 2 == 0){
System.out.print(2 + " ");
n -= 2;
} else {
System.out.print(3 + " ");
n -= 3;
}
for(int i=2;i<=n;i++){
if(isprime(i) && isprime(n-i)){
System.out.print(i + " ");
System.out.println(n - i);
break;
}
}
cin.close();
}
}
E.方格取数
题目描述
设有N*N的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。
某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出
只需输出一个整数，表示2条路径上取得的最大的和。
样例输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
样例输出
67
解题思路：
这个题我们的dp[i][j][h][k]:表示两条路同时走，第一条路径走到(i,j)时，第二条走到（h,k）时的最大数字和；
一个位置的值只能被取一次，那么当两次走到同一个位置时，只需要加格子上的值即可。当在不同位置，那两个位置的值都得加上。
E.cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100][100];
int sum;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
memset(a,0,sizeof(a));
int x,y,z;
while(cin >> x >> y >> z){
if(x == 0 && y == 0 && z == 0)break;
a[x][y] = z;
}
int dp[n+2][n+2][n+2][n+2];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int h=1;h<=n;h++){
for(int k=1;k<=n;k++){
int max1 = max(dp[i-1][j][h-1][k],dp[i][j-1][h][k-1]);
int max2 = max(dp[i-1][j][h][k-1],dp[i][j-1][h-1][k]);
dp[i][j][h][k] = max(max1,max2) + a[i][j];
if(i!=h && j!=k){
dp[i][j][h][k] += a[h][k];
}
}
}
}
}
cout << dp[n][n][n][n];
return 0;
}
E.java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int [][]a = new int[n+10][n+10];
while(cin.hasNext()){
int x = cin.nextInt();
int y = cin.nextInt();
int z = cin.nextInt();
if(x == 0 && y == 0 && z == 0)break;
a[x][y] = z;
}
int [][][][]dp = new int[n+2][n+2][n+2][n+2];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int h=1;h<=n;h++){
for(int k=1;k<=n;k++){
int max1 = Math.max(dp[i-1][j][h-1][k],dp[i][j-1][h][k-1]);
int max2 = Math.max(dp[i][j-1][h-1][k],dp[i-1][j][h][k-1]);
dp[i][j][h][k] = Math.max(max1,max2) + a[i][j];
if(i != h && j != k){
dp[i][j][h][k] += a[h][k];
}
}
}
}
}
System.out.println(dp[n][n][n][n]);
cin.close();
}
}
F.拼接
题目描述
有一天阳阳摆弄着他最钟爱的木棒，他突发奇想，如果从中任意选取确定数量木棒，然后拼接成一根，可以得到多少长度不一的木棒呢？
输入
两行。
第 1 行，2 个正整数 N 和 M，分别表示阳阳共拥有木棒数和选出木棒的数量。
第 2 行，N 个 500 以内的正整数，表示各木棒的长度。
输出
一个整数，表示可以拼接出不同长度木棒的数量
样例输入
4 3
1 3 5 7
样例输出
4
解题思路：
一道深搜题，我们可以从n根小木棍中搜索出m条小木棍拼接出来的所有长度，然后利用set进行去重，最终set的长度就是答案。
F.cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
set <int> s;
int a[1000];
void dfs(int k,int sum,int cnt){
if(cnt == m){
s.insert(sum);
return;
}
if(k == n)return;
dfs(k+1,sum + a[k],cnt+1);
dfs(k+1,sum,cnt);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i=0;i<n;i++)cin >> a[i];
dfs(0,0,0);
// for(auto &i:s){
// cout << i << " ";
// }
cout << s.size();
return 0;
}
F.java
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main {
static int n,m;
static Set<Integer> s = new TreeSet<>();
static int [] a = new int[100];
static void dfs(int k,int cnt,int sum){
if(cnt == m){
s.add(sum);
return;
}
if(k == n)return;
dfs(k+1,cnt+1,sum + a[k]);
dfs(k+1,cnt,sum);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
for(int i=0;i<n;i++)a[i] = cin.nextInt();
dfs(0,0,0);
System.out.println(s.size());
cin.close();
}
}
G.采购大米
题目描述
目前全国都在饱受新型冠状病毒疫情的困扰，疫情当前我们最大的贡献就是闭门不出。同时各个社区也有社区志愿者战斗在”防疫一线”，帮助居民采购生活物资，在社区门口管理和登记车辆和行人的出口等。小创的妈妈就是社区志愿者中的一员，负责物资的采购，而今天要采购的物资是大米，小创的妈妈一共需要采买M斤大米，小创的妈妈已经拿到了N名大米供应商的信息，每个供应商的价格不同，每个供应商的供应量也不一定相同，小创的妈妈需要挑选出一些供应商来满足采买需求。
但是小创的妈妈比较头疼，若要采购足够量的大米(如果总的供应量不足，那么尽可能的购买最多)，如何采购才能使得花费最小呢？请你帮助小创的妈妈来解决这个问题吧。
输入
第一行，两个整数N和M，N表示的是大米供应商的数量，M表示需要采买的大米总量。
1≤N≤1000，0≤M≤10^6
接下来N行，是用空格隔开的一个小数和一个整数，分别表示第i个供应商的单价xi和这个供应商的供应量yi
1≤Xi≤10，0≤yi≤10^6
输出
一行，一个小数，表示小创妈妈要采购M斤大米所需要的最小花费，小数点后保留一位小数。
样例输入
5 1000
1.9 100
2.1 200
1.8 300
2.2 800
2.5 400
样例输出
2030.0
提示
需要采购的代码是1000斤，1.8元的供应商采购300斤，1.9元的供应商采购100斤，2.1元的供应商采购200斤，2.2元的供应商采购400斤，总花费是2030.0元
解题思路：
贪心思想，价格便宜的大米优先购买，结构体排序，用最少的价格把米尽可能的买到最多。
G.cpp
#include<bits/stdc++.h>
using namespace std;
struct rice{
double price;
int sum;
}a[1000005];
bool mycmp(rice &m,rice &n){
return m.price < n.price;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m;
cin >> n >> m;
double ans = 0;
for(int i=0;i<n;i++){
cin >> a[i].price >> a[i].sum;
}
sort(a,a+n,mycmp);
for(int i=0;i<n;i++){
if(m <= 0)break;
ans += a[i].price * min(m,a[i].sum);
m -= a[i].sum;
}
cout << fixed << setprecision(1) << ans;
return 0;
}
G.java
import java.util.*;
class rice{
double price;
int sum;
rice(double price,int sum){
this.price = price;
this.sum = sum;
}
}
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
rice []a = new rice[n];
for(int i=0;i<n;i++){
a[i] = new rice(cin.nextDouble(),cin.nextInt());
}
Arrays.sort(a, new Comparator<rice>() {
@Override
public int compare(rice o1, rice o2) {
return (int)(o1.price*100) - (int)(o2.price*100);
}
});
double ans = 0;
for(int i=0;i<n;i++){
if(m <= 0)break;
ans += a[i].price * Math.min(m,a[i].sum);
m -= a[i].sum;
}
System.out.printf("%.1f",ans);
cin.close();
}
}
H.连通图
题目描述
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。
输入
第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。
随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。
输出
对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。
样例输入
5 4
1 2
1 3
1 4
2 5
样例输出
YES
解题思路：
这道题我们可以利用并查集，通过并查集最终找根节点，若只有一个根节点说明图是连通的，否则是不连通的。
H.cpp
#include<bits/stdc++.h>
using namespace std;
int f[10000];
void init(int n) {
for (int i = 1; i <= n; i++) {
f[i] = i;
}
}
int find(int x) {
if (x == f[x]) {
return x;
}
else {
return f[x] = find(f[x]);
}
}
/*
int find(int x){
x==f[x]?return x:return find(f[x]);
}
*/
void merge(int x, int y) {
int tx = find(x);
int ty = find(y);
if (ty != tx) {
f[tx] = ty;
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
init(n);
while (m--) {
int a, b;
cin >> a >> b;
merge(a, b);
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (f[i] == i) {
cnt++;
}
}
if (cnt == 1) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}
I.畅通工程
题目描述
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
输入
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
输出
对每个测试用例，在1行里输出最少还需要建设的道路数目。
样例输入
5 3
1 2
3 2
4 5
0
样例输出
1
解题思路：
并查集板子题
I.cpp
#include<bits/stdc++.h>
using namespace std;
int f[1000];
void init(int n) {
for (int i = 1; i <= n; i++) {
f[i] = i;
}
}
int find(int x) {
if (x == f[x]) {
return x;
}
else {
return f[x] = find(f[x]);//路径压缩
}
}
/*
int find(int x){
x==f[x]?return x:return find(f[x]);
}
*/
void merge(int x, int y) {
int tx = find(x);
int ty = find(y);
if (ty != tx) {
f[tx] = ty;//合并
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
while (cin >> n) {
if (n == 0) {
break;
}
cin >> m;
init(n);
while (m--) {
int a, b;
cin >> a >> b;
merge(a, b);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (f[i] == i) {
ans++;
}
}
cout << ans - 1 << endl;
}
return 0;
}
I.java
import java.util.*;
public class Main {
static int []f = new int[10000];
static void init(int n) {
for (int i = 1; i <= n; i++) {
f[i] = i;
}
}
static int find(int x) {
if (x == f[x]) {
return x;
}
else {
return f[x] = find(f[x]);
}
}
static void merge(int x, int y) {
int tx = find(x);
int ty = find(y);
if (ty != tx) {
f[tx] = ty;
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
int n = cin.nextInt();
if(n == 0)break;
int m = cin.nextInt();
init(n);
while (m-- != 0) {
int a = cin.nextInt();
int b = cin.nextInt();
merge(a, b);
}
int ans = 0;
for(int i=1;i<=n;i++){
if(f[i] == i)ans++;
}
System.out.println(ans - 1);
}
cin.close();
}
}