賣菜

題目鏈接

滿分思路

就是模擬一下這個調整第二天菜價的過程，其中對于兩種只有一個鄰居的情況下做出調整，三個for循環分別處理
輸入，調整，輸出

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int yes[N],today[N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>yes[i];}for(int i=1;i<=n;i++){if(i==1){today[i]=(yes[i]+yes[i+1])/2;}else if(i==n){today[n]=(yes[n-1]+yes[n])/2;}else{today[i]=(yes[i-1]+yes[i]+yes[i+1])/3;}}for(int i=1;i<=n;i++){cout<<today[i]<<" ";}
}

買菜

題目鏈接

滿分思路

這題說白了就是兩個人都去買菜去了，然后回來把菜裝車的時候倆人會聊會天，這樣一來一回，問的是 兩個人在這個買菜的過程中能聊多久，其實題目已經給出提示了，對于時間段用區間來表示，那么我們是不是只需要找到兩個人時間重合的部分就好，對于這個重合部分怎么表示呢
畫個圖其實就很明了了，這里截一下Y總課上的圖示
即：兩個區間右端點取一個兩者最小值（min）減去左端點取一個最大值

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=2010;
int n;
PII p[N],q[N];
int get(PII a,PII b)
{if(a.y<b.x ||b.y<a.x){return 0;}else{return min(a.y,b.y)-max(a.x,b.x);//對于線段的重合部分取（右端點最小-左端點最大）}
}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>p[i].x>>p[i].y;}for(int i=0;i<n;i++){cin>>q[i].x>>q[i].y;}int res=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){res+=get(p[i],q[j]);}}cout<<res<<endl;return 0;
}

再賣菜

第三題是個大模擬 非常麻煩 先跳過了 滿分比較艱難
這三題名字？？ 我還以為我題目看錯了 這出題人？？？

題目鏈接

滿分題解（差分約束）

其實這題你仔細看一下，是不是就是第一道題的逆過程，但是往往逆過程是比較難的，這題就是，
知道今天的菜價，問你的是昨天菜價多少，這個其實就需要我們自己找約束條件了，雖然調整的規則一樣
但往往你并不能通過這家或幾家今天的菜價就能知道這家昨天的菜價，而且這對于所有店都是這樣，這其實就是難點所在 等我學完 差分約束 回來補上個人心得

solution 1(枚舉 correct but 超時)

#include <iostream>
#include <vector>using namespace std;// 檢查當前枚舉的第一天菜價序列是否符合第二天菜價的要求
bool check(const vector<int>& day1Prices, const vector<int>& day2Prices) {int n = day1Prices.size();// 檢查第一個商店if ((day1Prices[0] + day1Prices[1]) / 2 != day2Prices[0]) {return false;}// 檢查中間的商店for (int i = 1; i < n - 1; ++i) {if ((day1Prices[i - 1] + day1Prices[i] + day1Prices[i + 1]) / 3 != day2Prices[i]) {return false;}}// 檢查最后一個商店if ((day1Prices[n - 2] + day1Prices[n - 1]) / 2 != day2Prices[n - 1]) {return false;}return true;
}// 枚舉并找到符合要求的第一天菜價
vector<int> findDay1Prices(const vector<int>& day2Prices) {int n = day2Prices.size();vector<int> day1Prices(n);// 枚舉第一個商店的菜價，從 1 開始for (int firstPrice = 1; ; ++firstPrice) {day1Prices[0] = firstPrice;bool valid = true;// 推導后續商店的菜價for (int i = 1; i < n; ++i) {if (i == 1) {// 第二個商店的菜價根據第一個商店和自身推導day1Prices[i] = 3 * day2Prices[i - 1] - day1Prices[i - 1];if (day1Prices[i] <= 0) {valid = false;break;}} else if (i == n - 1) {// 最后一個商店的菜價根據前一個商店和自身推導day1Prices[i] = 2 * day2Prices[i] - day1Prices[i - 1];if (day1Prices[i] <= 0) {valid = false;break;}} else {// 中間商店的菜價根據相鄰商店推導day1Prices[i] = 3 * day2Prices[i] - day1Prices[i - 1] - day1Prices[i - 2];if (day1Prices[i] <= 0) {valid = false;break;}}}if (valid && check(day1Prices, day2Prices)) {return day1Prices;}}return {};
}int main() {int n;cin >> n;vector<int> day2Prices(n);for (int i = 0; i < n; ++i) {cin >> day2Prices[i];}vector<int> day1Prices = findDay1Prices(day2Prices);for (int i = 0; i < n; ++i) {if (i > 0) {cout << " ";}cout << day1Prices[i];}cout << endl;return 0;
}

solution 2(正解)

作者：Tilbur
代碼解析

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310,M=1e5+10;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];
int b[N];
int n;void add(int a, int b, int c)  // 添加一條邊a->b，邊權為c
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}void spfa()  // 求1號點到n號點的最短路距離
{int hh = 0, tt = 0;memset(dist, -0x3f, sizeof dist);dist[0] = 0;q[tt ++ ] = 0;while (hh != tt){int t = q[hh ++ ];if (hh == N) hh = 0;st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] <dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j])     // 如果隊列中已存在j，則不需要將j重復插入{q[tt ++ ] = j;if (tt == N) tt = 0;st[j] = true;}}}}
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d",&b[i]);memset(h, -1, sizeof h);for(int i=2;i<n;i++){add(i-2,i+1,3*b[i]);add(i+1,i-2,-3*b[i]-2);}add(0,2,2*b[1]),add(2,0,-2*b[1]-1);add(n-2,n,2*b[n]),add(n,n-2,-2*b[n]-1);for(int i=1;i<=n;i++) add(i-1,i,1);spfa();for(int i=1;i<=n;i++) cout<<dist[i]-dist[i-1]<<' ';return 0;
}