山东大学计算机科学与技术学院程序设计思维与实践作业
山大程序设计思维与实践作业
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

10 10
1 3
2 4
4 5
2 8
5 2
5 9
6 8
9 2
10 5
5 8
样例输出
4

#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;
}