1、猜数字-交互版
你需要编写一个“猜数字”的程序。跟你做过的大部分题目不一样，你需要通过不断地询问另外一个程序（以下称之为“交互程序”）来猜到最终的数字。
在你的程序刚运行时，交互程序会通过标准输入给你提供一个数字 N，表示你需要猜的数字在 1 到 N 范围里。
接下来你可以开始发起你的询问。你可以直接通过输出到标准输出来询问；每次询问为一个数字，表示你猜测的结果。每次询问后，你需要刷新输出流，否则可能会有输出内容停留在缓冲区不被输出。例如 C++ 你可以使用 fflush(stdout)，Java 你可以使用 System.out.flush() ，Pascal 你可以使用 flush(output) ，Python 则可以使用 stdout.flush()。
交互程序会根据你的询问返回你的猜测与正确答案的比较情况。具体而言：
- 如果正确答案小于你的猜测，则会返回
<； - 如果正确答案大于等于你的猜测，则会返回
>=
一旦你确定你找到了正确的答案，则输出 ! x（x 是你猜测的数字，注意与感叹号用空格隔开），并立刻结束你的程序（否则判题系统可能不能返回正确的判题结果）。
最后，总的询问次数不能大于等于 25 次。
请你尝试猜对正确的数字吧！
输入样例:
20
>=
<
>=
<
>=
<输出样例:
5
18
10
13
12
11
! 12样例程序
以下程序用于你理解如何与交互程序进行交互，并不是正确的程序。
#include <cstdio>
int main() {
int n;
scanf("%d", &n);
printf("%d\n", n / 2);
fflush(stdout);
char ans[10];
scanf("%s", ans);
if(ans[0] == '>') {
printf("! %d\n", n / 2 + 1);
fflush(stdout);
} else {
printf("! %d\n", n / 2 - 1);
fflush(stdout);
}
}答案
#include<bits/stdc++.h>
using namespace std;
int main(){
int last=1,maxnumber;
char c[3];
cin>>maxnumber;
while(last != maxnumber){
int midnumber=(last + maxnumber + 1) >> 1;//随机数
printf("%d\n", midnumber);
fflush(stdout);
scanf("%s",c);
if(strcmp(c,"<")) last=midnumber;
else maxnumber= midnumber - 1;
}
printf("! %d\n", last);
fflush(stdout);
return 0;
}2、两个有序序列的中位数
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。
输入格式:
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
5
1 3 5 7 9
2 3 4 5 6输出样例1:
4输入样例2:
6
-100 -10 1 1 1 1
-50 0 2 3 4 5输出样例2:
1答案
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
n=2*n;
vector<int>a;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
a.push_back(temp);
}
sort(a.begin(), a.end()); //排序
int cnt=0;
for(vector<int>::iterator it=a.begin(); it!=a.end(); it++){
cnt+=1;
}
cnt=(cnt-1)/2;
cout<<a[cnt];
return 0;
}3、数组循环左移
本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据由（a0a1⋯an−1）变换为（am⋯an−1a0a1⋯am−1）（最前面的m个数循环移至最后面的m个位置）。如果还需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
输入格式:
输入第1行给出正整数n（≤100）和整数m（≥0）；第2行给出n个整数，其间以空格分隔。
输出格式:
在一行中输出循环左移m位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。
输入样例：
8 3
1 2 3 4 5 6 7 8输出样例：
4 5 6 7 8 1 2 3答案
#include<stdio.h>
int main(){
int x,y,i,m;
scanf("%d %d",&x,&y);
int a[x+y];
for(i=0;i<x;i++)
{
scanf("%d",&a[i]);
}
for(i=x;i<x+y;i++)
{
a[i]=0;
}
for(i=0;i<y;i++)
{
a[x]=a[i];
x++;
}
m=y;
for(i=0;i<x-y;i++)
{
a[i]=a[m];
m++;
if(i!=x-y-1)
{
printf("%d ",a[i]);
}
else
{
printf("%d",a[i]);
}
}
return 0;
}4、Merging Linked Lists
Given two singly linked lists L1=a1→a2→⋯→an−1→an and L2=b1→b2→⋯→bm−1→bm. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1→a2→bm→a3→a4→bm−1⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.
Input Specification:
Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1 and L2, plus a positive N (≤105) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Nextwhere Address is the position of the node, Data is a positive integer no more than 105, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.
Output Specification:
For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1Sample Output:
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1答案
#include <iostream>
#include <vector>
#include <map>
using namespace std;
inline void output(pair<int, int> &p)
{
static bool flag = false;
if (flag) printf(" %05d\n", p.first);
printf("%05d %d", p.first, p.second);
flag = true;
}
int main()
{
int sa, sb, n, a, v, nxt, j;
cin >> sa >> sb >> n;
map<int, pair<int, int>> node;
for (int i = 0; i < n; ++i)
{
cin >> a >> v >> nxt;
node[a] = make_pair(v, nxt);
}
vector<pair<int, int>> l1, l2;
while (sa != -1)
l1.emplace_back(sa, node[sa].first), sa = node[sa].second;
while (sb != -1)
l2.emplace_back(sb, node[sb].first), sb = node[sb].second;
if (l1.size() < l2.size()) swap(l1, l2);
for (j = 0; j < 2 * l2.size(); j += 2)
output(l1[j]), output(l1[j + 1]), output(l2[l2.size() - j / 2 - 1]);
for (; j < l1.size(); ++j) output(l1[j]);
printf(" -1");
}5、统计工龄
给定公司N名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。
输入格式:
输入首先给出正整数N（≤105），即员工总人数；随后给出N个整数，即每个员工的工龄，范围在[0, 50]。
输出格式:
按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为0则不输出该项。
输入样例:
8
10 2 0 5 7 2 5 2输出样例:
0:1
2:3
5:2
7:1
10:1答案
#include <stdio.h>
void countAges(int* ages, int size) {
int ageCounts[51] = {0}; // 初始化一个长度为51的数组，下标表示工龄，初始值为0
for (int i = 0; i < size; i++) {
ageCounts[ages[i]]++; // 统计每个工龄出现的次数
}
for (int i = 0; i < 51; i++) {
if (ageCounts[i] != 0) {
printf("%d:%d\n", i, ageCounts[i]); // 输出每个工龄的员工个数
}
}
}
int main() {
int n;
scanf("%d", &n);
int ages[n];
for (int i = 0; i < n; i++) {
scanf("%d", &ages[i]);
}
countAges(ages, n);
return 0;
}6、冒泡法排序
将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。
本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。
输入格式：
输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。
输出格式：
在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。
输入样例：
6 2
2 3 5 1 6 4输出样例：
2 1 3 4 5 6答案
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
}
//冒泡排序：两两比较，满足条件，交换位置
//外层循环控制几轮比较 几轮比较是数组的长度减1
for (int i = 0; i < k; i++) {
//内层循环是每轮有几次比较
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int t = array[j];
array[j] = array[j + 1];
array[j + 1] = t;
}
}
}
for (int i = 0; i < n; i++) {
if (i < n - 1) {
System.out.print(array[i] + " ");
} else {
System.out.print(array[i]);
}
}
}
}7、整数分解为若干项之和**
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。
输入格式：
每个输入包含一个测试用例，即正整数N (0<N≤30)。
输出格式：
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1<mi+1,则N1序列必定在N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
输入样例：
7输出样例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7答案
import java.util.Scanner;
public class Main {
public static int N;
public static int[] numbers = new int[35];
public static int interval = 0;
public static String printItem(int[] array, int pos) {
String result = N + "=";
for (int i = 0; i <= pos; i++) {
result += array[i];
if (i < pos) result += "+";
}
if (interval % 4 == 0 || pos == 0) result += "\n";
else result += ";";
return result;
}
public static void dfs(int pos, int sum, int next) {
if (sum + next > N) return;
else {
numbers[pos] = next;
if (sum + next == N) {
interval++;
System.out.print(printItem(numbers, pos));
} else if (sum + next < N) {
sum += next;
pos++;
for (int i = next; i <= N - sum; i++) {
dfs(pos, sum, i);
}
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
for (int i = 1; i <= N / 2; i++) {
dfs(0, 0, i);
}
dfs(0, 0, N);
}
}
8、输出全排列
请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。
输入格式:
输入给出正整数n（<10）。
输出格式:
输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a1,a2,⋯,an排在序列b1,b2,⋯,bn之前，如果存在k使得a1=b1,⋯,ak=bk 并且 ak+1<bk+1。
输入样例：
3输出样例：
123
132
213
231
312
321答案
#include <stdio.h>
#include <stdlib.h>
int a[11],b[11];
//数组a用于判读数字是否选过 数组b用来存储符合条件的数字，即（未被选过，a[x]=0）
int n;
void find(int a[],int b[],int x)
{
if(x==n+1)
//当所有位置都遍历之后，输出
{
for(int i=1; i<=n; i++)
printf("%d",b[i]);
printf("\n");
}
for(int i=1; i<=n; i++)
{
if(a[i]==0)
//判断该数字是否被选择过，未被选择过的加入数组b中
{
a[i]=1;
b[x]=i;
find(a,b,x+1);
a[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
find(a,b,1);
return 0;
}
9、哪两个点之间的距离最近
设P={(x1,y1),(x2,y2),⋯,(xn,yn)}是平面上散列的n个点的集合。请编写程序找出集合中距离最近的点对。严格地说，相同距离的最近点对可能不止一对，为了简单期间只找出第一对最近点对即可。
输入格式:
输入第一行给出一个正整数n，表示平面上的点数。随后n行，每行给出一个实数对，每个实数对表示一个点的纵横坐标值，其中第1数表示横坐标，第2数表示纵坐标。
输出格式:
输出最近点对中两个点的坐标和它们之间的距离。如果 x1+y1<=x2+y2则按
(x1,y1),(x2,y2),miniDist=Distance
输出结果，否则按
(x2,y2),(x1,y1),miniDist=Distance
输出结果。
其中x1,y1,x2,y2是保留两位小数的实数，Distance是保留3位小数的实数
输入样例:
5
1.00 1.00
2.00 0.00
0.00 2.00
0.50 0.60
-1.00 2.00输出样例:
(0.50,0.60),(1.00,1.00),miniDist=0.640答案
#include <stdio.h>
#include <math.h>
int main()
{
int n;
scanf("%d", &n);
double x[n], y[n];
for (int i = 0; i < n; i++)
{
scanf("%lf %lf", &x[i], &y[i]);
}
int dx, dy;
double nmin = 1e9;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
double sum = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); // 计算两点之间的距离
if (sum < nmin)
{
nmin = sum;
dx = i;
dy = j;
}
}
}
if ((x[dx] + y[dx]) <= (x[dy] + y[dy]))
{
printf("(%.2lf,%.2lf),(%.2lf,%.2lf),miniDist=%.3lf", x[dx], y[dx], x[dy], y[dy], nmin);
}
else
{
printf("(%.2lf,%.2lf),(%.2lf,%.2lf),miniDist=%.3lf", x[dy], y[dy], x[dx], y[dx], nmin);
}
return 0;
}10、士兵排队
在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一行。
编程计算使所有士兵排成一行需要的最少移动步数。
题目引自POJ
输入格式:
第1行是士兵数n，1≤n≤10000。接下来n行是士兵的初始位置，每行有2个整数x和y，-10000≤x，y≤10000。
输出格式:
一个数据，即士兵排成一行需要的最少移动步数。
输入样例:
5
1 2
2 2
1 3
3 -2
3 3输出样例:
8答案
#include<stdio.h>
int cmp(const void* a, const void* b)
{
return (*(int*)a) - (*(int*)b);
}
int sub(int a, int b)
{
if (a > b)
return a - b;
else
return b - a;
}
int main()
{
int n, i;
long long a = 0, b = 0;
scanf("%d", &n);
int *x = (int*)malloc(n * sizeof(int));
int *y = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; ++i)
scanf("%d %d", &x[i], &y[i]);
qsort(x, n, sizeof(int), cmp);
qsort(y, n, sizeof(int), cmp);
for (i = 0; i < n; ++i)
x[i] -= i;
qsort(x, n, sizeof(int), cmp);
for (i = 0; i < n; ++i)
{
a += sub(x[n / 2], x[i]);
b += sub(y[n / 2], y[i]);
}
printf("%lld\n", a + b);
free(x);
free(y);
return 0;
}11、词频统计
请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。
所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。
输入格式:
输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。
输出格式:
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。
随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。
输入样例：
This is a test.
The word "this" is the word with the highest frequency.
Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this...#
this line should be ignored.
输出样例：（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）
23
5:this
4:isimport sys
s = sys.stdin.read()
s = s[:s.find('#')] #读写所有内容，输入 ctrl+d 结束
for i in s: #将所有非字母、非数字、非下划线的字符均用空格替换
if i.isalnum() == False and i != '_':
s = s.replace(i, ' ')
words1 = s.lower().split(' ') #以空格分隔各个单词并存储它们的小写
words2 = {}
for i in words1:
if i == '': #上一步分隔后，可能存在分隔了两个空格存留的空字符，将其略过
continue
else:
i = i[:15] #保留所有单词的前十五位
#如果字典中有这个键，则值加一，若没有，则创建一个并令值等于零
words2[i] = words2.get(i, 0) + 1
#将字典先按“值”倒序排列，大的在前，最大的数前面加个符号就变的最小，这样排得越前
#然后再按“键”排列，即相同数量时，按字母顺序排列
words3 = sorted(words2.items(), key=lambda x:(-x[1],x[0]))
print(len(words3))
num = int(len(words3) / 10) #输出前10%的单词
for i in range(num):
print(str(words3[i][1]) + ':' + str(words3[i][0]))12、打印学生选课清单
假设全校有最多40000名学生和最多2500门课程。现给出每门课的选课学生名单，要求输出每个前来查询的学生的选课清单。注意：每门课程的选课人数不可超过 200 人。
输入格式:
输入的第一行是两个正整数：N（≤40000），为前来查询课表的学生总数；K（≤2500），为总课程数。此后顺序给出课程1到K的选课学生名单。格式为：对每一门课，首先在一行中输出课程编号（简单起见，课程从1到K编号）和选课学生总数（之间用空格分隔），之后在第二行给出学生名单，相邻两个学生名字用1个空格分隔。学生姓名由3个大写英文字母+1位数字组成。选课信息之后，在一行内给出了N个前来查询课表的学生的名字，相邻两个学生名字用1个空格分隔。
输出格式:
对每位前来查询课表的学生，首先输出其名字，随后在同一行中输出一个正整数C，代表该生所选的课程门数，随后按递增顺序输出C个课程的编号。相邻数据用1个空格分隔，注意行末不能输出多余空格。
输入样例:
10 5
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6
输出样例:
ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5#include<bits/stdc++.h>
using namespace std;
int main(){
int N,K;
map<string,vector<int> >m;
map<string,vector<int> >::iterator t;
scanf("%d%d",&N,&K);
for(int i = 1; i <= K; i++){
int nums,a;
scanf("%d%d",&a,&nums);
for(int j = 0; j < nums; j++){
char ch[6];
scanf("%s",ch);
m[ch].push_back(a);
}
}
for(int i = 0; i < N; i++){
char name[6];
scanf("%s",name);
printf("%s %d",name,m[name].size());
sort(m[name].begin(),m[name].end());
for(int j = 0; j < m[name].size(); j++){
cout << ' ' << m[name][j];
}
printf("\n");
}
}13、深入虎穴
著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。
输入格式：
输入首先在一行中给出正整数 N（<10
5
），是门的数量。最后 N 行，第 i 行（1≤i≤N）按以下格式描述编号为 i 的那扇门背后能通向的门：
K D[1] D[2] ... D[K]
其中 K 是通道的数量，其后是每扇门的编号。
输出格式：
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。
输入样例：
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0
输出样例：
12#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
void solve() {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
vector<int> inDeg(n + 1, 0);
int x = -1;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
cin >> x;
g[i].push_back(x);
inDeg[x]++;
}
}
int s = 0;
for (int i = 1; i <= n; i++) {
if (inDeg[i] == 0) {
s = i;
break;
}
}
queue<int> q;
q.push(s);
while (!q.empty()) {
x = q.front();
q.pop();
for (int y : g[x]) {
q.push(y);
}
}
cout << x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T-- > 0) {
solve();
}
return 0;
}14、六度空间
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:
输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤10
3
，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。
输出格式:
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。
输入样例:
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例:
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
vector<vector<int>> g;
int n;
int bfs(int e) {
queue<int> q;
vector<bool> vis(n + 1, false);
q.push(e);
vis[e] = true;
int cnt = 1, dis = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int x = q.front();
q.pop();
for (int y : g[x]) {
if (!vis[y]) {
vis[y] = true;
cnt++;
q.push(y);
}
}
}
dis++;
if (dis > 6) break;
}
return cnt;
}
int main() {
int T = 1;
// T = in.nextInt();
while (T-- > 0) {
cin >> n;
int m;
cin >> m;
g.resize(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<double> ans(n + 1);
for (int i = 1; i <= n; i++) {
ans[i] = 100.0 * bfs(i) / n;
}
for (int i = 1; i <= n; i++) {
cout << i << ": " << fixed << setprecision(2) << ans[i] << "%" << endl;
}
}
return 0;
}
15、功夫传人
一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。
这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。
输入格式：
输入在第一行给出3个正整数，分别是：N（≤10
5
）——整个师门的总人数（于是每个人从0到N−1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r ——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N行，第i行（i=0,⋯,N−1）描述编号为i的人所传的徒弟，格式为：
K
i
ID[1] ID[2] ⋯ ID[K
i
]
其中K
i
是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。K
i
为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。
输出格式：
在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过10
10
。
输入样例：
10 18.0 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
输出样例：
404from collections import deque
MAX = 100005
winners = [0] * MAX
peoples = [[] for _ in range(MAX)]
def main():
global winners, peoples
global MAX
N, Z, r = map(float, input().split())
N = int(N)
for i in range(N):
info = list(map(int, input().split()))
k = info[0]
for j in range(1, k + 1):
id = info[j]
peoples[i].append(id)
if k == 0:
x = info[-1]
winners[i] = x
if N == 1:
print(int(winners[0] * Z))
return
q = deque([0])
level = 0
total_power = 0.0
while q:
t = len(q)
level += 1
for _ in range(t):
top = q.popleft()
for j in range(len(peoples[top])):
q.append(peoples[top][j])
temp = Z * winners[peoples[top][j]] * (1 - r * 0.01) ** level
total_power += temp
print(int(total_power))
if __name__ == "__main__":
main()
16、列出连通性
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照"{ v
1
v
2
... v
k
}"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
void dfs(int x, vector<vector<int>>& g, vector<bool>& vis, ostream& out) {
out << x << " ";
vis[x] = true;
for (int y : g[x]) {
if (!vis[y]) {
vis[y] = true;
dfs(y, g, vis, out);
}
}
}
void bfs(int x, vector<vector<int>>& g, vector<bool>& vis, ostream& out) {
out << x << " ";
vis[x] = true;
queue<int> q;
q.push(x);
while (!q.empty()) {
x = q.front();
q.pop();
for (int y : g[x]) {
if (!vis[y]) {
out << y << " ";
vis[y] = true;
q.push(y);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (auto& i : g)
sort(i.begin(), i.end());
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
cout << "{ ";
dfs(i, g, vis, cout);
cout << "}\n";
}
}
fill(vis.begin(), vis.end(), false);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
cout << "{ ";
bfs(i, g, vis, cout);
cout << "}\n";
}
}
return 0;
}
17、哈利波特的考试
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例:
4 70#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> dis(n, vector<int>(n, INF));
for (int i = 0; i < n; i++)
dis[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
dis[u][v] = dis[v][u] = w;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
int pos = 0, distance = INF;
for (int i = 0; i < n; i++) {
int mx = 0;
for (int j : dis[i]) {
if (j != INF) mx = max(mx, j);
else {
cout << 0;
return 0;
}
}
if (mx < distance) {
distance = mx;
pos = i + 1;
}
}
cout << pos << " " << distance;
return 0;
}
18、装箱问题
假设有N项物品，大小分别为s
1
、s
2
、…、s
i
、…、s
N
，其中s
i
为满足1≤s
i
≤100的整数。要把这些物品装入到容量为100的一批箱子（序号1-N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。
输入格式：
输入第一行给出物品个数N（≤1000）；第二行给出N个正整数s
i
（1≤s
i
≤100，表示第i项物品的大小）。
输出格式：
按照输入顺序输出每个物品的大小及其所在的箱子序号，每个物品占1行，最后一行输出所需的箱子数目。
输入样例：
8
60 70 80 90 30 40 10 20
输出样例：
60 1
70 2
80 3
90 4
30 1
40 5
10 1
20 2
5#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> box;
vector<int> ans;
for (int i = 0; i < n; i++) {
int v;
cin >> v;
int idx = -1;
bool found = false;
for (int j = 0; j < box.size(); j++) {
if (box[j] >= v) {
box[j] -= v;
idx = j + 1;
found = true;
break;
}
}
if (!found) {
box.push_back(100 - v);
idx = box.size();
}
cout << v << " " << idx << endl;
ans.push_back(idx);
}
cout << box.size() << endl;
return 0;
}
19、月饼
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。
输入格式：
每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。
输出格式：
对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。
输入样例：
3 20
18 15 10
75 72 45
输出样例：
94.50#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct mk {
double storage, sale;
double unit_price;
};
void solve() {
int n;
double D;
cin >> n >> D;
vector<mk> cake(n);
for (int i = 0; i < n; i++) {
cin >> cake[i].storage;
}
for (int i = 0; i < n; i++) {
cin >> cake[i].sale;
cake[i].unit_price = cake[i].sale / cake[i].storage;
}
sort(cake.begin(), cake.end(), [](const mk &a, const mk &b) {
return a.unit_price > b.unit_price;
});
double sum = 0;
for (const mk &i : cake) {
if (i.storage < D) {
D -= i.storage;
sum += i.sale;
} else {
sum += D * i.unit_price;
break;
}
}
cout << fixed << setprecision(2) << sum << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while (T-- > 0) {
solve();
}
return 0;
}
