A
(1) 输入格式说明：
以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
(2) 输出格式说明：
以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。
(3) 样例输入与输出：
输入1：
3 4 -5 2 6 1 -2 0
输出1：
12 3 -10 1 6 0
输入2：
-1000 1000 999 0
输出2：
-1000000 999
输入3：
1000 0
输出3：
0 0代码：
#include <iostream>
#include <chrono>
#include <math.h>
#include <ctime>
#include <stack>
#include <sstream>
#include <string>
#define SIZE 1000
#define ADDSIZE 100
using namespace std;
typedef struct
{
int* base;
int* top;
int stacksize;
}Stack;
void initstack(Stack* S)
{
S->base = (int*)malloc(SIZE * sizeof(int));
if (!S->base) exit(EOVERFLOW);
S->top = S->base;
S->stacksize = SIZE;
}
int isEmpty(Stack* S)
{
return S->base == S->top;
}
int gettop(Stack* S)
{
if (S->base == S->top) exit(0);
else
return *(--S->top);
}
void push(Stack* S, int e)
{
if (S->top - S->base >= S->stacksize)
{
exit(EOVERFLOW);
}
*S->top++ = e;
}
void Num(string& input, Stack* numstack) {
istringstream iss(input);
int num;
while (iss >> num) {
push(numstack,num);
iss.ignore();
}
}
int main()
{
int count = 0;
int coe, ind;
string s;
getline(cin, s);
Stack T1;
initstack(&T1);
Stack T2;
initstack(&T2);
Num(s, &T1);
while (!isEmpty(&T1))
{
push(&T2, gettop(&T1));
++count;
}
while (!isEmpty(&T2))
{
coe = gettop(&T2);
ind = gettop(&T2);
if (coe != 0 && ind != 0)
{
cout << coe * ind << " " << ind - 1 << " ";
}
else if (coe != 0 && count == 2)
{
cout << 0 << " " << 0;
}
else
{
cout << "";
}
}
return 0;
}B
设二叉树的结点的数据域的类型为char，给定一棵二叉树的先序遍历序列和中序遍历序列，还原该二叉树，并输出二叉树的深度和叶子节点的数量。
用例1
-*+abc/de
a+b*c-d/e
4
5
用例2
ab
ba
2
1
用例3
*c-ab
c*a-b
3
3
用例4
A
A
1
1
说明：用例的前两行分别为输入的先序和中序序列，这两个序列中不能有重复的字符，后两行分别为计算得出的二叉树的深度和叶子数量。
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <iomanip>
#include <unordered_map>
using namespace std;
struct TreeNode {
char data;
TreeNode* left;
TreeNode* right;
};
TreeNode* buildTree(string preorder, string inorder, int start, int end, int& index) {
if (start > end) {
return nullptr;
}
TreeNode* root = new TreeNode;
root->data = preorder[index++];
root->left = root->right = nullptr;
int i;
for (i = start; i <= end; i++) {
if (inorder[i] == root->data) {
break;
}
}
root->left = buildTree(preorder, inorder, start, i - 1, index);
root->right = buildTree(preorder, inorder, i + 1, end, index);
return root;
}
int getDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return 1 + max(leftDepth, rightDepth);
}
int getLeafCount(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
int leftCount = getLeafCount(root->left);
int rightCount = getLeafCount(root->right);
return leftCount + rightCount;
}
int main() {
string preorder, inorder;
cin >> preorder;
cin >> inorder;
int index = 0;
int n = inorder.size() - 1;
TreeNode* root = buildTree(preorder, inorder, 0, n, index);
int depth = getDepth(root);
int leafCount = getLeafCount(root);
cout << depth << endl;
cout << leafCount << endl;
return 0;
}
C
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如下图所示。
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。 假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
(1) 输入格式说明：
输入第1行给出两个正整数，分别表示社交网络图的结点数N （1<N<=104，表示人数）、边数M（<=33*N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号），表示两个人互相认识。
(2) 输出格式说明：
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。自身到自身的距离为0，故计算的时候也把自身算入。
输入用例1
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出用例1
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%
输入用例2
10 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
9 10
输出用例2
1: 70.00%
2: 80.00%
3: 80.00%
4: 80.00%
5: 80.00%
6: 80.00%
7: 80.00%
8: 70.00%
9: 20.00%
10: 20.00%
输入用例3
11 10
1 2
1 3
1 4
4 5
6 5
6 7
6 8
8 9
8 10
10 11
输出用例3
1: 100.00%
2: 90.91%
3: 90.91%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 100.00%
9: 100.00%
10: 100.00%
11: 81.82%代码：
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <iomanip>
#include <queue>
using namespace std;
vector<vector<int>> graph;
int N, M;
void calculateSixDegrees() {
for (int node = 1; node <= N; node++) {
vector<bool> visited(N + 1, false);
queue<int> q;
visited[node] = true;
q.push(node);
int level = 0;
int total = 1;
while (!q.empty() && level < 6) {
int nodesAtCurrentLevel = q.size();
for (int i = 0; i < nodesAtCurrentLevel; i++) {
int currentNode = q.front();
q.pop();
for (int neighbor : graph[currentNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
total++;
}
}
}
level++;
}
double percentage = (static_cast<double>(total) / N) * 100;
cout << node << ": " << fixed << setprecision(2) << percentage << "%" << endl;
}
}
int main() {
cin >> N >> M;
graph.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
calculateSixDegrees();
return 0;
}
D
实现一种简单原始的文件相似度计算，即以两文件的公共词汇占总词汇的比例来定义相似度。为简化问题，这里不考虑中文（因为分词太难了），只考虑长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。
(1) 输入格式说明：
输入首先给出正整数N（<=100），为文件总数。随后按以下格式给出每个文件的内容：首先给出文件正文，最后在一行中只给出一个字符“#”，表示文件结束。在N个文件内容结束之后，给出查询总数M（<=10000），随后M行，每行给出一对文件编号，其间以空格分隔。这里假设文件按给出的顺序从1到N编号。
(2) 输出格式说明：
针对每一条查询，在一行中输出两文件的相似度，即两文件的公共词汇量占两文件总词汇量的百分比，精确到小数点后1位。注意这里的一个“单词”只包括仅由英文字母组成的、长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。单词间以任何非英文字母隔开。另外，大小写不同的同一单词被认为是相同的单词，例如“You”和“you”是同一个单词。
输入用例1
3
Aaa Bbb Ccc
#
Bbb Ccc Ddd
#
Aaa2 ccc Eee
is at Ddd@Fff
#
2
1 2
1 3
输出用例1
50.0%
33.3%
输入用例2
2
This is a test for repeated repeated words.
#
All repeated words shall be counted only once. A longlongword is the same as this longlongwo.
#
1
1 2
输出用例2
23.1%
输入用例3
2
This is a test to show ...
#
Not similar at all
#
1
1 2
输出用例3
0.0%
输入用例4
4 2
These two files are the same
#
these.two_files are the SAME
#
1
1 2
输出用例4
100.0%代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXS 10
#define MINS 3
#define MAXB 5
#define MAXTable 500009
typedef char ElementType[MAXS + 1];
typedef struct FileEntry {
int words;
struct FileEntry* Next;
}WList;
typedef struct WordEntry {
int FileNo;
struct WordEntry* Next;
}FList;
struct HashEntry {
ElementType Element;
int FileNo;
FList* InvIndex;
};
typedef struct HashTbl {
int TableSize;
struct HashEntry* TheCells;
}HashTable;
HashTable* Table_Init(int TableSize) {
HashTable* H = malloc(sizeof(HashTable));
H->TableSize = TableSize;
H->TheCells = malloc(sizeof(struct HashEntry) * H->TableSize);
while (TableSize) {
H->TheCells[--TableSize].FileNo = 0;
H->TheCells[TableSize].InvIndex = NULL;
}
return H;
}
WList* FileIndex_Init(int Size) {
WList* F = malloc(sizeof(FList) * Size);
while (Size) {
F[--Size].words = 0;
F[Size].Next = NULL;
}
return F;
}
int GetWord(ElementType Word) {
char c;
int p = 0;
scanf("%c", &c);
while (!isalpha(c) && (c != '#'))
scanf("%c", &c);
if (c == '#')
return 0;
while (isalpha(c) && (p < MAXS)) {
Word[p++] = tolower(c);
scanf("%c", &c);
}
while (isalpha(c))
scanf("%c", &c);
if (p < MINS)
return GetWord(Word);
else {
Word[p] = '\0';
return 1;
}
}
int Hash(char* key, int p) {
unsigned int h = 0;
while (*key != '\0')
h = (h << MAXB) + (*key++ - 'a');
return h % p;
}
int Find(ElementType key, HashTable* H) {
int pos = Hash(key, H->TableSize);
while (H->TheCells[pos].FileNo && strcmp(H->TheCells[pos].Element, key)) {
pos++;
if (pos == H->TableSize)
pos -= H->TableSize;
}
return pos;
}
int InsertAndIndex(int FileNo, ElementType key, HashTable* H) {
FList* F;
int pos = Find(key, H);
if (H->TheCells[pos].FileNo != FileNo) {
if (!H->TheCells[pos].FileNo)
strcpy(H->TheCells[pos].Element, key);
H->TheCells[pos].FileNo = FileNo;
F = malloc(sizeof(FList));
F->FileNo = FileNo;
F->Next = H->TheCells[pos].InvIndex;
H->TheCells[pos].InvIndex = F;
return pos;
}
else
return -1;
}
void FileIndex(WList* File, int FileNo, int pos) {
WList* W;
if (pos < 0)
return;
W = malloc(sizeof(WList));
W->words = pos;
W->Next = File[FileNo - 1].Next;
File[FileNo - 1].Next = W;
File[FileNo - 1].words++;
}
double work(WList* File, int F1, int F2, HashTable* H) {
int temp;
WList* W;
FList* F;
if (File[F1 - 1].words > File[F2 - 1].words) {
temp = F1;
F1 = F2;
F2 = temp;
}
temp = 0;
W = File[F1 - 1].Next;
while (W) {
F = H->TheCells[W->words].InvIndex;
while (F) {
if (F->FileNo == F2)
break;
F = F->Next;
}
if (F)
temp++;
W = W->Next;
}
return ((double)(temp * 100) / (double)(File[F1 - 1].words + File[F2 - 1].words - temp));
}
struct Find {
int x, y;
};
int main() {
int n, m, x = 0;
ElementType word;
HashTable* H;
WList* File;
struct Find FIND[100];
scanf("%d", &n);
if (getchar() != '\n')
{
scanf("%d", &n);
}
File = FileIndex_Init(n);
H = Table_Init(MAXTable);
for (int i = 0; i < n; i++)
while (GetWord(word))
FileIndex(File, i + 1, InsertAndIndex(i + 1, word, H));
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &FIND[i].x, &FIND[i].y);
}
for (int i = 0; i < m - 1; i++)
{
printf("%.1f%c\n", work(File, FIND[i].x, FIND[i].y, H), '%');
}
printf("%.1f%c", work(File, FIND[m - 1].x, FIND[m - 1].y, H), '%');
return 0;
}E
Excel可以对一组纪录按任意指定列排序。现请编写程序实现类似功能。
(1) 输入格式说明：
输入的第1行包含两个正整数 N (<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。之后有 N 行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，保证没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（[0, 100]内的整数）组成，相邻属性用1个空格隔开。
(2) 输出格式说明：
在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
输入用例1
3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
输出用例1
000001 Zoe 60
000007 James 85
000010 Amy 90
输入用例2
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
输出用例2
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
输入用例3
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
输出用例3
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90
输入用例4
1 2
999999 Williams 100
输出用例4
999999 Williams 100代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Student {
string id;
string name;
int score;
};
bool compare(const Student& s1, const Student& s2) {
return s1.id < s2.id;
}
bool compareName(const Student& s1, const Student& s2) {
if (s1.name != s2.name)
return s1.name < s2.name;
return s1.id < s2.id;
}
bool compareScore(const Student& s1, const Student& s2) {
if (s1.score != s2.score)
return s1.score < s2.score;
return s1.id < s2.id;
}
int main() {
int N, C;
cin >> N >> C;
vector<Student> records(N);
for (int i = 0; i < N; i++) {
cin >> records[i].id >> records[i].name >> records[i].score;
}
if (C == 1)
sort(records.begin(), records.end(), compare);
else if (C == 2)
sort(records.begin(), records.end(), compareName);
else if (C == 3)
sort(records.begin(), records.end(), compareScore);
for (int i = 0; i < N; i++) {
cout << records[i].id << " " << records[i].name << " " << records[i].score << endl;
}
return 0;
}
![[NeurIPS-23] GOHA: Generalizable One-shot 3D Neural Head Avatar](https://img-blog.csdnimg.cn/direct/09eaf0f8743d4a339a2e61f83194003b.png)
