A?:?賣菜
問題描述
在一條街上有 n 個(gè)賣菜的商店，按 1 至 n 的順序排成一排，這些商店都賣一種蔬菜。
第一天，每個(gè)商店都自己定了一個(gè)價(jià)格。店主們希望自己的菜價(jià)和其他商店的一致，第二天，每一家商店都會(huì)根據(jù)他自己和相鄰商店的價(jià)格調(diào)整自己的價(jià)格。具體的，每家商店都會(huì)將第二天的菜價(jià)設(shè)置為自己和相鄰商店第一天菜價(jià)的平均值（用去尾法取整）。
注意，編號為 1 的商店只有一個(gè)相鄰的商店 2，編號為 n 的商店只有一個(gè)相鄰的商店 n-1，其他編號為 i 的商店有兩個(gè)相鄰的商店 i-1 和 i+1。
給定第一天各個(gè)商店的菜價(jià)，請計(jì)算第二天每個(gè)商店的菜價(jià)。
輸入格式
輸入的第一行包含一個(gè)整數(shù) n，表示商店的數(shù)量。
第二行包含 n 個(gè)整數(shù)，依次表示每個(gè)商店第一天的菜價(jià)。
輸出格式
輸出一行，包含 n 個(gè)正整數(shù)，依次表示每個(gè)商店第二天的菜價(jià)。
樣例輸入
8
4 1 3 1 6 5 17 9
樣例輸出
2 2 1 3 4 9 10 13
數(shù)據(jù)規(guī)模和約定
對于所有評測用例，2 ≤ n ≤ 1000，第一天每個(gè)商店的菜價(jià)為不超過 10000 的正整數(shù)。
解答
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n + 1] = {0};
int b[n + 1] = {0};
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
if (i == 1)
{
b[i] = (a[i] + a[i + 1]) / 2;
}
else if (i == n)
{
b[i] = (a[i] + a[i - 1]) / 2;
}
else
{
b[i] = (a[i] + a[i + 1] + a[i - 1]) / 3;
}
cout << b[i] << " ";
}
cout << endl;
return 0;
}B?:?買菜
問題描述
小 H 和小 W 來到了一條街上，兩人分開買菜，他們買菜的過程可以描述為，去店里買一些菜然后去旁邊的一個(gè)廣場把菜裝上車，兩人都要買 n 種菜，所以也都要裝 n 次車。具體的，對于小 H 來說有 n 個(gè)不相交的時(shí)間段[a1?,b1?],[a2?,b2?]...[an?,bn?]在裝車，對于小 W 來說有 n 個(gè)不相交的時(shí)間段[c1?,d1?],[c2?,d2?]...[cn?,dn?]在裝車。其中，一個(gè)時(shí)間段[s, t]表示的是從時(shí)刻 s 到時(shí)刻 t 這段時(shí)間，時(shí)長為 t-s。
由于他們是好朋友，他們都在廣場上裝車的時(shí)候會(huì)聊天，他們想知道他們可以聊多長時(shí)間。
輸入格式
輸入的第一行包含一個(gè)正整數(shù) n，表示時(shí)間段的數(shù)量。
接下來 n 行每行兩個(gè)數(shù)ai?，bi?，描述小 H 的各個(gè)裝車的時(shí)間段。
接下來 n 行每行兩個(gè)數(shù)ci?，di?，描述小 W 的各個(gè)裝車的時(shí)間段。
輸出格式
輸出一行，一個(gè)正整數(shù)，表示兩人可以聊多長時(shí)間。
樣例輸入
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
樣例輸出
3
數(shù)據(jù)規(guī)模和約定
對于所有的評測用例，1 ≤ n ≤ 2000,?ai?<bi?<ai+1?，ci?<di?<ci+1?,對于所有的 i(1 ≤ i ≤ n)有，1 ≤?ai?,bi?,ci?,di??≤ 1000000。
解答
#include<bits/stdc++.h>
using namespace std;
int a[1000001] = {0};
int main(){
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n;i++){
int x, y;
cin >> x >> y;
for (int j = x; j < y;j++){
a[j] = 1;
}
a[y] = 2;
}
for (int i = 1; i <= n;i++){
int x, y;
cin >> x >> y;
for (int j = x; j <= y;j++){
if(a[j]==1 and j!=y){
sum++;
}
// if(a[j] == 2){
// sum--;
// }
}
}
cout << sum << '\n';
return 0;
}C?:?穿越蟲洞
問題描述
小 H 有n個(gè)秘密基地（編號?1?到?n?）,n?個(gè)秘密基地之間有?m?條雙向路徑和?w?個(gè)單向時(shí)空隧道，通過路徑需要消耗一定的時(shí)間Ti?，而通過時(shí)空隧道可以使時(shí)光倒流Tj?,現(xiàn)在小 H 想知道他能否從某一秘密基地出發(fā)，通過路徑和時(shí)空隧道回到過去（即回到出發(fā)的秘密基地且該時(shí)刻要早于出發(fā)時(shí)間）。
輸入格式
第1行，一個(gè)整數(shù)?F,表示測試用例的數(shù)量
接下來對于每一個(gè)測試用例，輸入格式如下
第1行，三個(gè)空格分隔的整數(shù)n,m,w
第2到?m+1?行，三個(gè)空格分隔的數(shù)字?s,e,t，表示?s,e?之間存在雙向道路，通行需要消耗t，允許兩點(diǎn)間存在多條路徑
第m+2到m+w+1行三個(gè)空間分隔的數(shù)字?s,e,t,表示存在從?s?到?e?的單向時(shí)空隧道，穿過時(shí)空隧道時(shí)光倒流?t
輸出格式
對于每個(gè)測試用例，如果小 H 能回到過去則輸出?YES，否則輸出?NO
每個(gè)測試用例的輸出占一行
樣例輸入
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
樣例輸出
NO
YES
數(shù)據(jù)規(guī)模和約定
1≤n≤500,1≤m≤4×104,1≤w≤200
1≤Ti?,Tj?≤104
解答
#include <bits/stdc++.h>
using namespace std;
int dis[510][510];
#define inf 1e8
void FF(int n)
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
int main()
{
int F;
cin >> F;
for (int ii = 1; ii <= F; ii++)
{
int n, m, w;
cin >> n >> m >> w;
int s, e, t;
// 初始化
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == j)
{
dis[i][j] = 0;
}
else
{
dis[i][j] = inf;
}
}
}
for (int x = 0; x < m; x++)
{
cin >> s >> e >> t;
dis[s][e] = t;
dis[e][s] = t;
}
for (int x = 0; x < w; x++)
{
cin >> s >> e >> t;
dis[s][e] = -t;
}
FF(n);
int u = 0;
for (; u <= n; u++)
{
if (dis[u][u] < 0)
{
cout << "YES" << endl;
break;
}
}
if (u > n)
{
cout << "NO" << endl;
}
}
return 0;
}D?:?差旅花費(fèi)
問題描述
有 n 個(gè)車站，其中 1 號車站為始發(fā)站，現(xiàn)有 n-1 個(gè)人，你需要安排他們分別去往除始發(fā)站以外的 n-1 個(gè)車站，然后返回始發(fā)站。交通系統(tǒng)的所有路徑均為單向路徑，連接兩個(gè)不同的車站，每經(jīng)過一條路徑需要交納一定的費(fèi)用，你能求出總花費(fèi)的最低金額嘛
輸入格式
第一行一個(gè)整數(shù) T，表示測試用例的個(gè)數(shù)。
對于每個(gè)測試用例，輸入格式如下
第一行兩個(gè)整數(shù) n,m,分別表示車站的數(shù)量和車站之間的單向路徑數(shù)。
接下來 m 行，每行三個(gè)數(shù) s,e,c,表示存在從 s 到 e 的單向路徑，花費(fèi)為 c
輸出格式
對于每個(gè)測試用例，輸出其總花費(fèi)的最低金額，每個(gè)測試用例的輸出占一行。
樣例輸入
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
樣例輸出
46
210
數(shù)據(jù)規(guī)模和約定
1<=n,m<=1000000
價(jià)格 c 為正整數(shù)，且保證其總和小于 1000000000
解答
#include <bits/stdc++.h>
using namespace std;
#define N 1000000
#define pa pair<int, int>
#define inf 1e8
int tot, tot2;
int dis[N], vis[N];
int point[N], V[N], W[N], nxt[N];
int dis2[N], vis2[N];
int point2[N], V2[N], W2[N], nxt2[N];
void add(int x, int y, int z)
{
tot++;
nxt[tot] = point[x];
point[x] = tot;
V[tot] = y;
W[tot] = z;
tot2++;
nxt2[tot2] = point2[y];
point2[y] = tot2;
V2[tot2] = x;
W2[tot2] = z;
}
void init()
{
for (int i = 0; i < N; i++)
{
point[i] = 0;
point2[i] = 0;
W[i] = 0;
W2[i] = 0;
V[i] = 0;
V2[i] = 0;
nxt[i] = 0;
nxt2[i] = 0;
dis[i] = 0;
dis2[i] = 0;
vis[i] = 0;
vis2[i] = 0;
tot = 0;
tot2 = 0;
}
}
void dj(int s, int n)
{
priority_queue<pa, vector<pa>, greater<pa>> q;
for (int i = 1; i <= n; i++)
{
dis[i] = inf;
vis[i] = 0;
}
dis[s] = 0;
q.push(make_pair(0, s));
while (!q.empty())
{
int x = q.top().second;
q.pop();
if (vis[x])
{
continue;
}
vis[x] = 1;
for (int i = point[x]; i; i = nxt[i])
{
if (dis[V[i]] > dis[x] + W[i])
{
dis[V[i]] = dis[x] + W[i];
q.push(make_pair(dis[V[i]], V[i]));
}
}
}
}
void dj2(int s, int n)
{
priority_queue<pa, vector<pa>, greater<pa>> q2;
for (int i = 1; i <= n; i++)
{
dis2[i] = inf;
vis2[i] = 0;
}
dis2[s] = 0;
q2.push(make_pair(0, s));
while (!q2.empty())
{
int x = q2.top().second;
q2.pop();
if (vis2[x])
{
continue;
}
vis2[x] = 1;
for (int i = point2[x]; i; i = nxt2[i])
{
if (dis2[V2[i]] > dis2[x] + W2[i])
{
dis2[V2[i]] = dis2[x] + W2[i];
q2.push(make_pair(dis2[V2[i]], V2[i]));
}
}
}
}
int main()
{
int T;
cin >> T;
for (int ss = 1; ss <= T; ss++)
{
int sum = 0;
int m, n;
cin >> n >> m;
int s, e, c;
init();
for (int i = 1; i <= m; i++)
{
cin >> s >> e >> c;
add(s, e, c);
}
dj(1, n);
// dj2(1, n);
dj2(1, n);
for (int i = 2; i <= n; i++)
{
sum = sum + dis[i] + dis2[i];
}
cout << sum << endl;
}
return 0;
}E?:?運(yùn)輸貨物
問題描述
考慮一個(gè)具有 N 個(gè)頂點(diǎn)，M 條邊的無向圖。編號為 1 的頂點(diǎn)對應(yīng)于一個(gè)礦山，從中提取一些珍貴的礦物。編號為 N 的頂點(diǎn)對應(yīng)于一家礦物加工廠。每條邊連接兩個(gè)不同的頂點(diǎn)并擁有有兩個(gè)參數(shù)，分別為最大承重量 C 和通行時(shí)間 D?，F(xiàn)在將從礦山中提取的礦物并選擇一條路徑將提取的礦物運(yùn)送至工廠。該路徑應(yīng)具有最大的承重量，以便能夠同時(shí)運(yùn)輸盡可能多的礦物。路徑的承重量等于路徑中經(jīng)過的邊的最大承重量的最小值。但是，這些礦物非常敏感，一旦從礦山中提取出來，它們將在 T 時(shí)間單位后開始分解，除非他們在此時(shí)間間隔內(nèi)到達(dá)工廠。因此，所選路徑的總行進(jìn)時(shí)間（其路徑的通行時(shí)間之和）應(yīng)小于或等于 T。
輸入格式
輸入的第一行包含一個(gè)整數(shù) X，表示測試用例的數(shù)量。
每個(gè)測試用例的第一行包含 3 個(gè)整數(shù)，并用空格分隔：N，M，T。接下來的 M 行中的每行將包含四個(gè)整數(shù)，每個(gè)數(shù)字用空格分隔：A，B，C 和 D，這意味著頂點(diǎn) A 和 B 之間存在一條邊，最大承重量為 C，通行時(shí)間為 D。A 和 B 是 1 和 N 之間的不同整數(shù)。任何兩個(gè)頂點(diǎn)之間最多存在一個(gè)邊。
輸出格式
對于 X 個(gè)測試用例，請輸出在滿足通行時(shí)間限制下的路徑最大承重量，每個(gè)測試用例對應(yīng)一行。
數(shù)據(jù)保證圖中至少存在一條 1 到 n 通行總時(shí)間小于等于 T 的路徑，即一定有解。文章來源：http://www.zghlxwxcb.cn/news/detail-426077.html
樣例輸入
2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4
樣例輸出
13
99
數(shù)據(jù)規(guī)模和約定
1≤??≤10000， 1≤m≤50000，1≤??≤500000
1≤??≤10000000， 1≤??≤50000文章來源地址http://www.zghlxwxcb.cn/news/detail-426077.html
解答
#include <bits/stdc++.h>
using namespace std;
#define MEM 100000
#define INF 10000000
// typedef long unsigned int;
typedef pair<int, int> par;
int dis[MEM], point[MEM], next1[MEM], wl[MEM], ct[MEM], v[MEM];
int mrkd[MEM];
int n, m;
int t, w;
int tot;
void init()
{
tot = MEM - 1;
while (1)
{
dis[tot] = INF;
point[tot] = 0;
next1[tot] = 0;
wl[tot] = 0;
ct[tot] = 0;
v[tot] = 0;
mrkd[tot] = 0;
if (tot == 0)
break;
tot--;
}
}
void add(int x, int y, int ww, int tt)
{
tot++; // 獲得新的內(nèi)存地址（為新邊節(jié)點(diǎn)申請內(nèi)存）
next1[tot] = point[x]; // 新邊節(jié)點(diǎn)的下一個(gè)指向舊邊節(jié)點(diǎn)
point[x] = tot; // 點(diǎn)x的指針更新指向新邊節(jié)點(diǎn)
v[tot] = y; // 新邊節(jié)點(diǎn)設(shè)置第二個(gè)連接點(diǎn)
wl[tot] = ww; // 為新邊設(shè)置參數(shù)
ct[tot] = tt;
}
void dijkstra(int s, int wwb)
{
priority_queue<par, vector<par>, greater<par>> q;
for (int i = 1; i <= n; i++)
{
dis[i] = INF;
mrkd[i] = 0;
}
dis[s] = 0;
q.push(make_pair(dis[s], s));
while (!q.empty())
{
int x = q.top().second;
q.pop();
if (!mrkd[x])
{
mrkd[x] = 1;
for (int p = point[x]; p; p = next1[p])
{
if (wl[p] >= wwb && dis[v[p]] > dis[x] + ct[p])
{
dis[v[p]] = dis[x] + ct[p];
q.push(make_pair(dis[v[p]], v[p]));
}
}
}
}
}
bool inTime(int mw)
{
dijkstra(1, mw);
if (dis[n] > t)
{
return false;
}
return true;
}
int main()
{
int att;
cin >> att;
for (int i = 1; i <= att; i++)
{
int ix, iy, iw, it;
int leftw = 0, rightw = 3000000, mid;
init();
cin >> n >> m >> t;
for (int i = 0; i < m; i++)
{
cin >> ix >> iy >> iw >> it;
if (leftw > iw)
{
leftw = iw;
}
if (rightw < iw)
{
rightw = iw;
}
add(ix, iy, iw, it);
add(iy, ix, iw, it);
}
mid = (leftw + rightw) / 2;
while (mid != leftw && mid != rightw)
{
if (inTime(mid))
{
leftw = mid;
}
else
{
rightw = mid;
}
mid = (leftw + rightw) / 2;
}
if (inTime(rightw))
{
cout << rightw << endl;
}
else
{
cout << leftw << endl;
}
}
return 0;
}到了這里，關(guān)于Vj程序設(shè)計(jì)作業(yè)H7的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
