山东大学计算机科学与技术学院程序设计思维与实践作业
山大程序设计思维与实践作业
sdu程序设计思维与实践
山东大学程序设计思维实践作业H8
山大程序设计思维实践作业H8
山东大学程序设计思维与实践
week8-图和树的性质与应用(下)
相关资料：GitHub
A : 元音回文
问题描述
现在有一个长度为 n 的字符串，都有小写字母组成。
现在所有元音字母都可以看作相同的字符
输出最长回文子串的长度
一个与自身的逆序相同的字符串即为回文串
比如 aba,aabbaa,asdffdsa 都为回文串
输入格式
第一行一个整数 n , 1≤n≤5000，表示字符串长度
接下来一行表示字符串
输出格式
输出一行，一个数，代表答案
样例输入
10
aeioubaeio
样例输出
9
#include<bits/stdc++.h>
using namespace std;
string str;
int expandAroundCenter(string s, int zuo, int you) {
while (zuo >= 0 && you < s.length() && s[zuo] == s[you]) {
--zuo;
++you;
}
return you - zuo - 1;
}
int main()
{
int n;
cin>>n;
if(n==1) {
cout<<1;
return 0;
}
char c;
for (int i = 0; i <n ; ++i) {
cin>>c;
if(c=='e'||c=='i'||c=='o'||c=='u')
c='a';
str+=c;
}
int start = 0, end = 0;
int res=0;
for (int i = 0; i < str.length(); i++) {
int len1 = expandAroundCenter(str, i, i);
int len2 = expandAroundCenter(str, i, i + 1);
int len = max(len1, len2);
if (len >res) {
res=len;
}
}
cout<<res;
return 0;
}
B : 模测成绩单
问题描述
模测结束了，小 L 拿到了一些形如 A 比 B 得分高 的信息，现在小 L 想要输出一份成绩排名表，使得排名表满足得到的信息，并且学号小的尽可能排在前面。
输入格式
第一行有两个整数，n,m 表示有 n 个同学，第 i 个同学学号为 i ，有 m 条信息。
接下来有 m 行，每行有两个整数 A,B ，表示学号为 A 的同学得分比学号为 B 的同学得分高。
1≤n,m≤10
6
1≤A,B≤n
数据保证有解
输出格式
输出一行 n 个数，表示按照学号给出的排名。
样例输入
5 3
4 5
2 3
1 5
样例输出
1 2 3 4 5
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m;
int A, B;
int nd_before[1000100] = { 0 };
vector<int> eage[1000100];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> A >> B;
nd_before[B] ++;
eage[A].push_back(B);
}
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 1; i <= n; i++) {
if (nd_before[i] == 0)
q.push(i);
}
vector<int> result;
while (!q.empty()) {
int tempu = q.top();
q.pop();
result.push_back(tempu);
for (int i = 0; i < eage[tempu].size(); i++) {
if (--nd_before[eage[tempu][i]] == 0)
q.push(eage[tempu][i]);
}
}
for (int i = 0; i < n; i++) {
cout << result[i] <<" ";
}
return 0;
}
C : 种酸奶
问题描述
小 L 喜欢喝酸奶，春天来了，小 L 想把酸奶种在地里，等到来年春暖花开，就能长出好多好多酸奶了
有 n 个坑，小 L 给坑都编上号，从 1 号到 n 号，每个坑最多种一瓶酸奶。
但是有一些限制形如 k,a,b,c 。
若 k 等于 1 ，则第 a 号坑到第 b 号坑最多种 c 瓶酸奶。
若 k 等于 2 ，则第 a 号坑到第 b 号坑最少种 c 瓶酸奶。
若 k 等于 3 ，则第 a 号坑到第 b 号坑必须种少于 c 瓶酸奶。
若 k 等于 4 ，则第 a 号坑到第 b 号坑必须种多于 c 瓶酸奶。
若 k 等于 5 ，则第 a 号坑到第 b 号坑必须种等于 c 瓶酸奶。
问小 L 最多种多少瓶酸奶
输入格式
第一行两个整数 n,m ，表示有 n 个坑，有 m 条限制。
1≤n,m≤1000
接下来 m 行，每行四个整数 k,a,b,c
1≤k≤5 ， 1≤a≤b≤n , ∣c∣<=2000
输出格式
输出一行，若有解则输出一个整数，表示答案
否则输出 impossible
样例输入
5 5
1 1 4 4
2 2 5 1
3 2 4 2
4 1 5 2
5 1 3 2
样例输出
3
#include <bits/stdc++.h>
using namespace std;
const int maximumm= 1e7;
const int maximumn= 1e7;
const int INF = 1e8;
int n,m;
int dist[maximumn];
int mis[maximumn];
struct EdgeData{
int m;
int n;
int next;
}E[maximumm];
int head[maximumn],total;
void init()
{
for(int i=0;i<=n;i++)
head[i] = -1;
total=0;
}
void addEdge(int u,int m,int n)
{
E[total].m = m;
E[total].n = n;
E[total].next = head[u];
head[u] = total;
total++;
}
int cnt[maximumn];//记录从源点到i最短路所走的边数
bool Spfa(int s)
{
for(int i =0;i<=n;i++)dist[i] = INF,mis[i] = 0,cnt[i] = 0;
queue<int> q;
dist[s] = 0;
q.push(s);
mis[s]=1;//表示当前节点是否在队列中
while(!q.empty())
{
int u = q.front();
q.pop();
mis[u] = 0;
//u点出了队列，那么一个点就可以多次入队
for(int i = head[u];i!=-1;i =E[i].next)
{
int m = E[i].m;
int t = E[i].n;
if(dist[m]>dist[u]+t)
{
dist[m] = dist[u]+t;
cnt[m] = cnt[u]+1;
if(cnt[m]>=n)
return false;
if(!mis[m])
q.push(m);
}
}
}
return true;
}
int main()
{
cin>>n>>m;
init();
for(int i = 1;i<=m;i++)
{
int k,a,b,c;
cin>>k>>a>>b>>c;
a=a-1;
if(k==1)
addEdge(a,b,c);
if(k==2)
addEdge(b,a,-c);
if(k==3)
addEdge(a,b,c-1);
if(k==4)
addEdge(b,a,-c-1);
if(k==5)
{
addEdge(a,b,c);
addEdge(b,a,-c);
}
}
for(int i = 0;i<=n-1;i++)
{
addEdge(i,i+1,1);
addEdge(i+1,i,0);
}
bool res = Spfa(0);
if(res)
cout<<dist[n]<<endl;
else
cout<<"impossible\n"<<endl;
return 0;
}
D : 信息传递
问题描述
有 n 个人，每个人都有一个编号，从 1 到 n 。
如果 A 得知一个消息，那么他一定会告诉 B 。
问最少把消息告诉几个人，能让所有人得知这个消息。
输入格式
第一行两个整数 n,m , 1≤n,m≤10
6
，表示有 n 个人
接下来 m 行，每行给出一个关系形如 A,B ，表示如果 A 得知一个消息，那么他一定会告诉 B 。
输出格式
输出一行，一个数，代表答案
样例输入
10 10
1 3
2 4
4 5
2 8
5 2
5 9
6 8
9 2
10 5
5 8文章来源：https://www.toymoban.com/news/detail-425161.html
10 10
1 3
2 4
4 5
2 8
5 2
5 9
6 8
9 2
10 5
5 8
样例输出
4文章来源地址https://www.toymoban.com/news/detail-425161.html
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000100;
int n,m;
int A,B;
int vis[maxn],c[maxn],dfn[maxn],dcount,scount; //Dcount DFS sequence count, scout SCC count, the i-th point in the sequence after DFN [i] - DFS, and the SCC number of point C [i] - I
bool flag[maxn]; //Record whether the penetration of each connected component is 0
vector<int> G1[maxn];
vector<int> G2[maxn]; //反图
int indegree[maxn] = {0};
void dfs1(int x){
vis[x] = 1;
for(int i = 0; i < G1[x].size(); i++){
if(!vis[G1[x][i]])
dfs1(G1[x][i]);
}
dfn[++dcount] = x;//dfn[i]-dfs后序列中第i个点
}
void dfs2(int x){
c[x] = scount;
for(int i = 0; i < G2[x].size(); i++){
if(!c[G2[x][i]])
dfs2(G2[x][i]);
}
}
void kosaraju(){
//初始化
dcount = scount = 0;
memset(c,0,sizeof c);
memset(vis, 0, sizeof vis);
//第一遍dfs 记录每个点是dfs之后 dfs中的第几个点
for(int i = 1; i <= n; i++)
if(!vis[i]) dfs1(i);
//第二遍dfs 记录所在的SCC编号
for(int i = n; i >= 1; i--)
if(!c[dfn[i]]) ++scount,dfs2(dfn[i]);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i = 0; i < m; i++){
cin>>A>>B;
G1[A].push_back(B);
G2[B].push_back(A);
}
kosaraju();
for(int i = 1; i <= scount; i++)
flag[i] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < G1[i].size(); j++){
if(c[i] != c[G1[i][j]])
flag[c[G1[i][j]]] = 1;
}
}
int result = 0;
for(int i = 1; i <= scount; i++)
if(!flag[i])
result++;
cout<<result;
return 0;
}
到了这里，关于山东大学计算机科学与技术学院程序设计思维与实践作业 week8-图和树的性质与应用(下)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
