A: selling vegetables
Problem description
There are n vegetable shops in a street, arranged in the order of 1 to N. these shops all sell one kind of vegetable.
On the first day, each store set its own price. Shopkeepers hope that their vegetable prices are consistent with those of other stores. The next day, each store will adjust its prices according to the prices of itself and adjacent stores. Specifically, each store will set the next day's vegetable price as the average of the first day's vegetable price of itself and adjacent stores (rounded by the tailing method).
Note that the store numbered 1 has only one adjacent store 2, the store numbered n has only one adjacent store n-1, and the other stores numbered i have two adjacent stores i-1 and i+1.
Given the price of vegetables in each store on the first day, please calculate the price of vegetables in each store on the second day.
Input format
The first line of input contains an integer n indicating the number of stores.
The second line contains n integers, which in turn represent the price of vegetables in each store on the first day.
Output format
Output a line containing n positive integers, which in turn represent the vegetable price of each store the next day.
sample input
8
4 1 3 1 6 5 17 9
sample output
2 2 1 3 4 9 10 13
Data scale and agreement
For all evaluation cases, 2 ≤ n ≤ 1000, the price of vegetables in each store on the first day is a positive integer of no more than 10000.
#include <iostream>
using namespace std;
int a[1001];
int b[1001];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin >> a[i];
};
for(int i=1;i<=n;i++) {
if (i == 1) {
b[1] = (a[1]+a[2])/2;
} else if (i<n && i>1) {
b[i] = (a[i - 1] +a[i]+ a[i + 1]) / 3;
} else if (i == n) {
b[n] =(a[n]+ a[n - 1])/2;
}
};
for(int i=1;i<=n;i++){
cout<<b[i]<<" ";
}
return 0;
}
B: buy vegetables
Problem description
Xiao H and Xiao W come to a street. They buy vegetables separately. The process of buying vegetables can be described as going to the store to buy some vegetables, and then going to a nearby square to load the vegetables. Both of them have to buy n kinds of vegetables, so they also have to load n times. Specifically, for small H, there are n disjoint time periods [a_1,b_1][a
1
,b
1
],[a_2,b_2][a
2
,b
2
]...[a_n,b_n][a
n
,b
n
]During loading, there are n disjoint time periods [c_1,d_1][c for Xiao W
1
,d
1
],[c_2,d_2][c
2
,d
2
]...[c_n,d_n][c
n
,d
n
]Loading. Among them, a time period [s, t] represents the time from time s to time t, and the duration is t-s.
As they are good friends, they all chat when loading in the square. They want to know how long they can talk.
Input format
The first line of input contains a positive integer n, indicating the number of time periods.
Next n lines, two numbers a per line_ ia
i
，b_ib
i
, describe each loading time period of small H.
Next n lines, two numbers C per line_ ic
i
，d_id
i
, describe each loading time period of XIAO W.
Output format
Output a line, a positive integer, indicating how long they can talk.
sample input
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
sample output
3
Data scale and agreement
For all evaluation cases, 1 ≤ n ≤ 2000, a_ i < b_ i < a_ {i+1}，c_ i < d_ i < c_ {i+1}a
i <b i<a i+1，
C I < d I < C I + 1, for all i(1 ≤ I ≤ n), 1 ≤ a_i, b_i, c_i, d_ia i ,b i,c i ,d i≤ 1000000.
#include<iostream>
using namespace std;
int a[10000010];
int b[10000010];
int c[10000010];
int d[10000010];
int main()
{
int n;
cin>>n;
int nn=n;
int i=0;
while(nn--)
{
cin>>a[i]>>b[i];
i++;
}
nn=n;
i=0;
while(nn--)
{
cin>>c[i]>>d[i];
i++;
}
i=0;int l=0;
int ans=0;
while(i<n&&l<n)
{
if(b[i]<=c[l])
{
i++;
continue;
}
if(d[l]<=a[i])
{
l++;
continue;
}
if(b[i]>c[l])
if(d[l]>b[i])
{
if(c[l]>a[i])
{ ans+=b[i]-c[l];
i++;
continue;
}
else
{
ans+=b[i]-a[i];
i++;
continue;
}
}
else
{
if(a[i]<c[l])
ans+=d[l]-c[l];
else
ans+=d[l]-a[i];
l++;
continue;
}
if(d[l]>a[i])
if(b[i]>d[l])
{ if(a[i]>c[l])
ans+=d[l]-a[i];
else
ans+=d[l]-c[l];
l++;
continue;
}
else
{
if(a[i]>c[l])
ans+=b[i]-a[i];
else
ans+=b[i]-c[i];
i++;
continue;
}
}
cout<<ans<<endl;
}
C: through wormhole
Problem description
Small H has nn secret bases (No. 11 to nn). There are mm two-way paths and ww one-way space-time tunnels between nn secret bases. It takes a certain amount of time t to pass through the path_ iT
i
, and through the space-time tunnel, you can turn back time_ jT
j
Now, little H wants to know whether he can start from a secret base and return to the past through the path and space-time tunnel (i.e. return to the secret base and the time is earlier than the departure time).
Input format
Line 11, an integer FF, indicates the number of test cases
Next, for each test case, the input format is as follows
Line 11, three space separated integers n,m,wn,m,w
The numbers s,e,ts,e,t separated by three spaces in lines 22 to m+1m+1 indicate that there is a two-way road between S, ES and E, which requires tt to pass, and multiple paths are allowed between two points
The three spatially separated numbers s, e, TS, e and T in the m+2m+2 to m+w+1m+w+1 lines indicate that there is a one-way space-time tunnel from ss to ee, and time flows back through the space-time tunnel tt
Output format
For each test case, if small H can go back to the past, output YES, otherwise output NO
The output of each test case occupies one line
sample input
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
sample output
NO
YES
Data scale and agreement
1\leq n\leq 500,1\leq m\leq 4\times 10^4,1\leq w\leq 2001≤n≤500,1≤m≤4×10 4 ,1≤w≤200
1\leq T_i,T_j\leq 10^41≤T i,T j ≤10 4
#include <iostream>
#define INF 1e8
void app()
{
int **maps;
int n, m, w;
scanf("%d %d %d", &n, &m, &w);
maps = new int*[n + 1];
for (int i = 1; i <= n; i++)
{
maps[i] = new int[n + 1];
for (int j = 1; j <= n; j++)
{
maps[i][j] = INF;
}
}
for (int i = 0; i < m; i++)
{
int x, y, s;
scanf("%d %d %d", &x, &y, &s);
maps[x][y] = s < maps[x][y] ? s : maps[x][y];
maps[y][x] = s < maps[y][x] ? s : maps[y][x];
}
for (int i = 0; i < w; i++)
{
int x, y, s;
scanf("%d %d %d", &x, &y, &s);
maps[x][y] = -s < maps[x][y] ? -s : maps[x][y];
}
bool ok = false;
for (int k = 1; k <= n && !ok; k++)
{
for (int j = 1; j <= n && !ok; j++)
{
for (int i = 1; i <= n && !ok; i++)
{
maps[i][j] = maps[i][j] > maps[i][k] + maps[k][j] ? maps[i][k] + maps[k][j] : maps[i][j];
if (maps[i][j] + maps[j][i] < 0)
{
ok = true;
}
}
}
}
if (ok)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
int main()
{
int c;
scanf("%d", &c);
while (c)
{
app();
c--;
}
return 0;
}
D: travel expenses
Problem description
There are n stations, of which station 1 is the departure station. There are n-1 people. You need to arrange them to go to n-1 stations other than the departure station, and then return to the departure station. All paths of the transportation system are one-way paths, connecting two different stations. Each path needs to pay a certain fee. Can you find the minimum amount of the total cost
Input format
The first line is an integer T, which represents the number of test cases.
For each test case, the input format is as follows
Two integers n and m in the first line represent the number of stations and the number of one-way paths between stations respectively.
The next m lines, with three numbers s, e and c in each line, indicate that there is a one-way path from s to e, and the cost is c
Output format
For each test case, output the minimum amount of its total cost, and the output of each test case accounts for one line.
sample input
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
sample output
46
210
Data scale and agreement
1<=n,m<=1000000
The price c is a positive integer and its sum is guaranteed to be less than 1000000000
#include <iostream>
#include <queue>
#include <vector>
using std::pair;
using std::make_pair;
using std::priority_queue;
#define MEM 2000000
#define INF 1e9
typedef long llu;
typedef pair<llu, llu> par;
llu dis1[MEM], dis2[MEM], vstd1[MEM], vstd2[MEM], n, m, w;
llu tot1, tot2, point1[MEM], point2[MEM];
llu w1[MEM], w2[MEM], v1[MEM], v2[MEM], next1[MEM], next2[MEM];
void add(llu x, llu y, llu w)
{
tot1++;
next1[tot1] = point1[x];
point1[x] = tot1;
v1[tot1] = y;
w1[tot1] = w;
tot2++;
next2[tot2] = point2[y];
point2[y] = tot2;
v2[tot2] = x;
w2[tot2] = w;
}
void dijkstra(llu s, llu *dis, llu *vstd, llu *v, llu *w, llu *point, llu *next)
{
priority_queue<par, std::vector<par>, std::greater<par> > q;
for (llu i = 1; i <= n; i++) { dis[i] = INF; vstd[i] = 0; }
dis[s] = 0;
q.push(make_pair(0, s));
while (!q.empty())
{
llu x = q.top().second;
q.pop();
if (!vstd[x])
{
vstd[x] = 1;
for (llu i = point[x]; i; i = next[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 init()
{
tot1 = 0;
tot2 = 0;
for (llu i = 0; i < MEM; i++)
{
dis1[i] = 0;
dis2[1] = 0;
vstd1[i] = 0;
vstd2[i] = 0;
point1[i] = 0;
point2[i] = 0;
w1[i] = 0;
w2[i] = 0;
v1[i] = 0;
v2[i] = 0;
next1[i] = 0;
next2[i] = 0;
}
}
void app()
{
llu cost = 0;
init();
scanf("%ld %ld", &n, &m);
for (llu i = 0; i < m; i++)
{
llu x, y, s;
scanf("%ld %ld %ld", &x, &y, &s);
add(x, y, s);
}
dijkstra(1, dis1, vstd1, v1, w1, point1, next1);
dijkstra(1, dis2, vstd2, v2, w2, point2, next2);
for (llu i = 2; i <= n; i++)
{
cost += dis1[i] + dis2[i];
}
printf("%lu\n", cost);
}
int main()
{
int c;
scanf("%d", &c);
while (c)
{
app();
c--;
}
return 0;
}
E: transportation of goods
Problem description
Consider an undirected graph with N vertices and M edges. The vertex numbered 1 corresponds to a mine from which some precious minerals are extracted. The vertex numbered N corresponds to a mineral processing plant. Each edge connects two different vertices and has two parameters: maximum load C and traffic time D. Now the minerals extracted from the mine will be and a route will be selected to transport the extracted minerals to the factory. The path should have maximum load capacity so that as many minerals as possible can be transported at the same time. The bearing capacity of the path is equal to the minimum value of the maximum bearing capacity of the edge passing through the path. However, these minerals are very sensitive. Once extracted from the mine, they will begin to decompose after T time unit, unless they arrive at the factory within this time interval. Therefore, the total travel time of the selected path (the sum of the travel time of the path) should be less than or equal to T.
Input format
The first line of input contains an integer X indicating the number of test cases.
The first line of each test case contains three integers separated by spaces: N, m, T. Each of the next M lines contains four integers, each separated by a space: A, B, C and D, which means that there is an edge between vertices a and B, with a maximum load of C and a travel time of D. A and B are different integers between 1 and N. There is at most one edge between any two vertices.
Output format
For X test cases, please output the maximum bearing weight of the path under the traffic time limit, and each test case corresponds to one line.
In the data assurance graph, there is at least one path with a total transit time of 1 to n less than or equal to T, that is, there must be a solution.
sample input
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
sample output
13
99
Data scale and agreement
1≤𝑛≤10000， 1≤m≤50000，1≤𝑇≤500000
1≤𝐶≤10000000， 1≤𝐷≤50000
#include <iostream>
#include <queue>
#include <vector>
using std::priority_queue;
using std::pair;
using std::make_pair;
#define MEM 100000
#define INF 10000000000
typedef long unsigned llu;
typedef pair<llu, llu> par;
llu dis[MEM], point[MEM], next[MEM], wl[MEM], ct[MEM], v[MEM];
llu mrkd[MEM];
llu n, m;
llu t, w;
llu tot;
void init()
{
tot = MEM - 1;
while (1)
{
dis[tot] = INF;
point[tot] = 0;
next[tot] = 0;
wl[tot] = 0;
ct[tot] = 0;
v[tot] = 0;
mrkd[tot] = 0;
if (tot == 0) break;
tot--;
}
}
void add(llu x, llu y, llu ww, llu tt)
{
tot++; // Obtain a new memory address (apply for memory for the new edge node)
next[tot] = point[x]; // The next of the new edge node points to the old edge node
point[x] = tot; // The pointer of point x is updated to point to the new edge node
v[tot] = y; // The new edge node sets the second connection point
wl[tot] = ww; // Set parameters for new edges
ct[tot] = tt;
}
void dijkstra(llu s, llu wwb)
{
priority_queue<par, std::vector<par>, std::greater<par> > q;
for (llu i = 1; i <= n; i++) { dis[i] = INF; mrkd[i] = 0; }
dis[s] = 0;
q.push(make_pair(dis[s], s));
while (!q.empty())
{
llu x = q.top().second;
q.pop();
if (!mrkd[x])
{
mrkd[x] = 1;
for (llu p = point[x]; p; p = next[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(llu mw)
{
dijkstra(1, mw);
if (dis[n] > t)
{
return false;
}
return true;
}
void app()
{
llu ix, iy, iw, it;
llu leftw = 0, rightw = 3000000, mid;
init();
scanf("%lu %lu %lu", &n, &m, &t);
for (llu i = 0; i < m; i++)
{
scanf("%lu %lu %lu %lu", &ix, &iy, &iw, &it);
leftw = leftw > iw ? iw : leftw;
rightw = rightw < iw ? iw : rightw;
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;
}
printf("%lu\n", inTime(rightw) ? rightw : leftw);
}
int main()
{
int att;
scanf("%d", &att);
while (att)
{
app();
att--;
}
return 0;
}
thinking
The first question is very simple. Just write it directly: the average value of yourself and adjacent stores, the head and tail are only one of yourself and the front and back; There are three in the middle: head and tail + yourself. The input vegetable price array is the answer after a meal operation.
The second question can also be written directly, but it is more complex than the first question. We need to improve the relationship. Don't nest and write the sentences disorderly. Finally, the output of the cumulative results on the line.
The third question is to find the shortest path, and then compare whether you can go back. The time in this question is the weight, but there is more time-space backflow here, so we regard it as negative:
You can do this,
Travel cost: go to all points, and then return with the smallest weight, and then count the times. It's a little difficult for me to achieve.
An example was given in the class, with this idea:
The relaxation operation learned last semester can't remember clearly in some places. Baidu explained: relaxation operation refers to setting an attribute d[v] for each vertex v ∈ V to describe the upper bound of the weight on the shortest path from the source point s to V, which is called the shortest path estimate.
The fifth question is too difficult to do. You can also write a Dijie Tesla function on the Internet. I can't write it myself.