山東大學計算機科學與技術(shù)學院程序設計思維與實踐作業(yè)
山大程序設計思維與實踐作業(yè)
sdu程序設計思維與實踐
山東大學程序設計思維實踐作業(yè)H8
山大程序設計思維實踐作業(yè)H8
山東大學程序設計思維與實踐
week8-圖和樹的性質(zhì)與應用(下)
相關(guān)資料：GitHub
A : 元音回文
問題描述
現(xiàn)在有一個長度為 n 的字符串，都有小寫字母組成。
現(xiàn)在所有元音字母都可以看作相同的字符
輸出最長回文子串的長度
一個與自身的逆序相同的字符串即為回文串
比如 aba,aabbaa,asdffdsa 都為回文串
輸入格式
第一行一個整數(shù) n , 1≤n≤5000，表示字符串長度
接下來一行表示字符串
輸出格式
輸出一行，一個數(shù)，代表答案
樣例輸入
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 : 模測成績單
問題描述
模測結(jié)束了，小 L 拿到了一些形如 A 比 B 得分高 的信息，現(xiàn)在小 L 想要輸出一份成績排名表，使得排名表滿足得到的信息，并且學號小的盡可能排在前面。
輸入格式
第一行有兩個整數(shù)，n,m 表示有 n 個同學，第 i 個同學學號為 i ，有 m 條信息。
接下來有 m 行，每行有兩個整數(shù) A,B ，表示學號為 A 的同學得分比學號為 B 的同學得分高。
1≤n,m≤10
6
1≤A,B≤n
數(shù)據(jù)保證有解
輸出格式
輸出一行 n 個數(shù)，表示按照學號給出的排名。
樣例輸入
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 最多種多少瓶酸奶
輸入格式
第一行兩個整數(shù) n,m ，表示有 n 個坑，有 m 條限制。
1≤n,m≤1000
接下來 m 行，每行四個整數(shù) k,a,b,c
1≤k≤5 ， 1≤a≤b≤n , ∣c∣<=2000
輸出格式
輸出一行，若有解則輸出一個整數(shù)，表示答案
否則輸出 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最短路所走的邊數(shù)
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;//表示當前節(jié)點是否在隊列中
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 。
問最少把消息告訴幾個人，能讓所有人得知這個消息。
輸入格式
第一行兩個整數(shù) n,m , 1≤n,m≤10
6
，表示有 n 個人
接下來 m 行，每行給出一個關(guān)系形如 A,B ，表示如果 A 得知一個消息，那么他一定會告訴 B 。
輸出格式
輸出一行，一個數(shù)，代表答案
樣例輸入
10 10
1 3
2 4
4 5
2 8
5 2
5 9
6 8
9 2
10 5
5 8文章來源：http://www.zghlxwxcb.cn/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文章來源地址http://www.zghlxwxcb.cn/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;
}
到了這里，關(guān)于山東大學計算機科學與技術(shù)學院程序設計思維與實踐作業(yè) week8-圖和樹的性質(zhì)與應用(下)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
