C++ 最多访问的人数
由于新的圣诞节规定，圣诞老人只能按照一定的顺序访问居住在每个城镇的儿童的家。
此外，他只能访问以他访问的上一个儿童的名字的字母结尾作为姓名开头的儿童。为了遵守这个规定，圣诞老人可能不得不遗漏一些儿童。
给定镇上儿童的名字和他需要遵循的顺序，你要找到他可以访问的最多数量的儿童。
输入包括
• 一行包含 n (1 ≤ n ≤ 10^4) – 儿童的数量
• n 行包含儿童的姓名（即长度≤15 的字符串）
按照圣诞老人需要遵循的顺序。如果一个名字出现多次，它指的是同名的不同儿童。
输出
输出单个数字，即圣诞老人可以访问的儿童的最大数量。
n = int(input('输入儿童的数量：'))
Names = []
print('请输入%d个儿童的名字'%n)
for i in range(n,0,-1):
Names.append(input())
#例子： Names = ['Marie', 'Elisabeth', 'Michael', 'Hans']
names = [n[0].lower()+n[-1] for n in Names]
res = []
for i,n in enumerate(names):
res.append([n])
for j in range(i+1,len(names)):
if names[j][0]==res[-1][-1][-1]:
res[-1].append(names[j])
print('圣诞老人可以访问的儿童的最大数量：',max(map(len,res)))
#include<iostream>
#include<vector>
std::vector<std::pair<std::string, bool>>s;
int func(char n, int t)
{
int max = t;
for (auto& str : s)
{
if (str.second && str.first.front() == n - 32)
{
str.second = false;
int res = func(str.first.back(), t + 1);
str.second = true;
if (res > max)
max = res;
}
}
return max;
}
int main()
{
int n;
std::cin >> n;
s.resize(n);
for (auto& str : s)
{
std::cin >> str.first;
str.second = true;
}
int max = 0;
for (char c = 'a'; c <= 'z'; c++)
{
int res = func(c, 0);
if (res > max)
max = res;
}
std::cout << max;
return 0;
}
试试这个，可能会超时
把名字首尾字母作为关系，形成图，最后就是求最大联通图的算法
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int main()
{
int n = 0; char name[N][M] = { 0 };
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int k = 0; int count = 1;
for (i = 0;i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if (name[k][sz - 1] != name[i + 1][0])
continue;
else
{
k = i+1;
count++;
}
}
printf("%d\n", count);
return 0;
}
如有帮住，望采纳已测试过，答案正确
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int main()
{
int n = 0; char name[N][M] = { 0 };
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int k = 0; int count = 1;
for (i = 0;i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if (name[k][sz - 1] != name[i + 1][0])
continue;
else
{
k = i+1;
count++;
}
}
printf("%d\n", count);
return 0;
}
已测试，没问题，希望对你有用
我提交个不一样解决方案吧，基于邻接表的图的并查集
using namespace std;
//基于邻接表的求最大连通分量--并查集
vector<int>parent;
int find(int x) {
if (parent[x] == -1) return x;
else {
int tmp = find(parent[x]);
parent[x] = tmp;
return tmp;
}
}
int main() {
vector<string>vexs;
vector<int>sum;
int i,j, n,a,b,maxLength=0;
char c,c1;
string str,str1;
cin >> n;
//O(n)
for (i = 0; i < n; i++) {
cin >> str;
c = str[str.length() - 1];
if ((int)c >= (int)'A' && (int)'Z' >= (int)c)
str[str.length() - 1] += 32;
c = str[0];
if ((int)c >= (int)'A' && (int)'Z' >= (int)c)
str[0] += 32;
vexs.push_back(str);
parent.push_back(-1);
sum.push_back(1);
}
//构造并查集O(n^2)
for (i = 0; i < n; i++) {
str = vexs[i];
c = str[str.length() - 1];
for (j = 0; j < n; j++) {
if (i == j) continue;
str1 = vexs[j];
c1 = str1[0];
if (c == c1) {
a = find(i);
b = find(j);
if (a != b) {
parent[a] = b;
sum[b] = sum[b] + sum[a];
}
}
}
}
for (i = 0; i < n; i++) {
if (parent[i] == -1 && sum[i] > maxLength) {
maxLength = sum[i];
}
}
cout << maxLength << endl;
}
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int main()
{
int n = 0; char name[N][M] = { 0 };
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int k = 0; int count = 1;
for (i = 0; i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32))
{
k = i + 1;
count++;
}
else
{
continue;
}
}
printf("%d\n", count);
return 0;
}
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int main()
{
int n = 0; char name[N][M] = { 0 };
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int k = 0; int count = 1;
for (i = 0; i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32)|| name[k][sz - 1] == (name[i + 1][0] +32)||( name[k][sz - 1]+32) == name[i + 1][0])
{
k = i + 1;
count++;
}
else
{
continue;
}
}
printf("%d\n", count);
return 0;
}
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int Count_num(char name[N][M],int n,int i,int j)
{
int k = j; int count = 1;
for (i; i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32))
{
k = i + 1;
count++;
}
}
return count;
}
int main()
{
int n = 0; char name[N][M] = { 0 }; int max = 0;
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int j = 0;
for (i = 0; i < n; i++)
{
int max_count = Count_num(name, n,i,j);
j++;
if(max_count>max)
max = max_count;
}
printf("%d\n", max);
return 0;
}
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int Count_num(char name[N][M],int n,int i,int j)
{
int k = j; int count = 1;
for (i; i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32))
{
k = i + 1;
count++;
}
}
return count;
}
int Screen(char name[N][M], int j, int n, int i)
{
int k = j;
int count = 1;
for (i; k<i+1; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
int sz1 = strlen(name[i+1]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32))
{
k = i + 1;
}
if ((name[k][sz - 1] - 32) == name[i + 1][sz1-1] || name[k][sz - 1] == name[i + 1][sz1-1] || name[k][sz - 1] == (name[i + 1][sz1-1] - 32))
{
count++;
}
}
if(count==1)
return 1 ;
else return 0;
}
int main()
{
int n = 0; char name[N][M] = { 0 }; int max = 0;
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int j = 0;
for (i = 0; i < n; i++)
{
int num = Screen(name,j,n ,i);
if (num)
{
int max_count = Count_num(name, n, i, j);
if (max_count>max)
max = max_count;
}
j++;
}
printf("%d\n", max);
return 0;
}
直接思路是逐个遍历儿童的名字找出遵循规则的所有名字，计算名字个数
#define N 10000
#define M 16
#include<stdio.h>
#include<string.h>
int Count_num(char name[N][M],int n,int i,int j)
{
int k = j; int count = 1;
for (i; i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32))
{
k = i + 1;
count++;
}
}
return count;
}
int Screen(char name[N][M], int j, int n, int i)
{
int k = j;
int count = 1;
for (i; i<n; i++)
{
if (i + 1 >= n) break;
int sz = strlen(name[k]);
int sz1 = strlen(name[i+1]);
if ((name[k][sz - 1] - 32) == name[i + 1][0] || name[k][sz - 1] == name[i + 1][0] || name[k][sz - 1] == (name[i + 1][0] - 32))
{
break;
}
if ((name[k][sz - 1] - 32) == name[i + 1][sz1-1] || name[k][sz - 1] == name[i + 1][sz1-1] || name[k][sz - 1] == (name[i + 1][sz1-1] - 32))
{
count++;
}
}
if(count==1)
return 1 ;
else return 0;
}
int main()
{
int n = 0; char name[N][M] = { 0 }; int max = 0;
scanf("%d", &n);
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%s", &name[i]);
}
int j = 0;
for (i = 0; i < n; i++)
{
int num = Screen(name,j,n ,i);
if (num)
{
int max_count = Count_num(name, n, i, j);
if (max_count>max)
max = max_count;
}
j++;
}
printf("%d\n", max);
return 0;
}