試題 A: 階乘求和
本題總分：5 分
【問(wèn)題描述】
令 S = 1! + 2! + 3! + ... + 202320232023!，求 S 的末尾 9 位數(shù)字。
提示：答案首位不為 0。
【答案提交】
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一
個(gè)整數(shù)，在提交答案時(shí)只填寫(xiě)這個(gè)整數(shù)，填寫(xiě)多余的內(nèi)容將無(wú)法得分。

找規(guī)律，可以先手動(dòng)模擬幾次，會(huì)發(fā)現(xiàn)?隨著n越大，零也越多，當(dāng)n為40的時(shí)候剛好有9個(gè)0

所以到40項(xiàng)以后的末尾9個(gè)階乘的和一定是不變的，可以用手算，也可以寫(xiě)程序

答案是，901327897

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110000;

int f[N];

signed main()
{
    ios::sync_with_stdio(false);
    f[1]=1;
    for(int i=2;i<=50;i++)
        f[i]=f[i-1]*i;
    for(int i=2;i<=50;i++)
        f[i]=f[i-1]+f[i];
    cout<<f[40]%1000000000;
    return 0;
}

試題 B: 幸運(yùn)數(shù)字
本題總分：5 分
【問(wèn)題描述】
哈沙德數(shù)是指在某個(gè)固定的進(jìn)位制當(dāng)中，可以被各位數(shù)字之和整除的正整
數(shù)。例如 126 是十進(jìn)制下的一個(gè)哈沙德數(shù)，因?yàn)?(126)10 mod (1+2+6) = 0；126
也是八進(jìn)制下的哈沙德數(shù)，因?yàn)?(126)10 = (176)8，(126)10 mod (1 + 7 + 6) = 0；
同時(shí) 126 也是 16 進(jìn)制下的哈沙德數(shù)，因?yàn)?(126)10 = (7e)16，(126)10 mod (7 +
e) = 0。小藍(lán)認(rèn)為，如果一個(gè)整數(shù)在二進(jìn)制、八進(jìn)制、十進(jìn)制、十六進(jìn)制下均為
哈沙德數(shù)，那么這個(gè)數(shù)字就是幸運(yùn)數(shù)字，第 1 至第 10 個(gè)幸運(yùn)數(shù)字的十進(jìn)制表示
為：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . ?，F(xiàn)在他想知道第 2023 個(gè)幸運(yùn)數(shù)
字是多少？你只需要告訴小藍(lán)這個(gè)整數(shù)的十進(jìn)制表示即可。
【答案提交】
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一
個(gè)整數(shù)，在提交答案時(shí)只填寫(xiě)這個(gè)整數(shù)，填寫(xiě)多余的內(nèi)容將無(wú)法得分。

Java中有十進(jìn)制轉(zhuǎn)化為二進(jìn)制，十六進(jìn)制，八進(jìn)制的方法，暴力枚舉一下即可。（因?yàn)椴粫?huì)Java所以懶得寫(xiě)了）

試題 C: 數(shù)組分割
時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：10 分
【問(wèn)題描述】
小藍(lán)有一個(gè)長(zhǎng)度為 N 的數(shù)組 A = [A0, A1, . . . , AN?1]。現(xiàn)在小藍(lán)想要從 A 對(duì)
應(yīng)的數(shù)組下標(biāo)所構(gòu)成的集合 I = {0, 1, 2, . . . , N ? 1} 中找出一個(gè)子集 R1，那么 R1
在 I 中的補(bǔ)集為 R2。記 S 1 =
∑
r∈R1
Ar，S 2 =
∑
r∈R2
Ar，我們要求 S 1 和 S 2 均為
偶數(shù)，請(qǐng)問(wèn)在這種情況下共有多少種不同的 R1。當(dāng) R1 或 R2 為空集時(shí)我們將
S 1 或 S 2 視為 0。
【輸入格式】
第一行一個(gè)整數(shù) T，表示有 T 組數(shù)據(jù)。
接下來(lái)輸入 T 組數(shù)據(jù)，每組數(shù)據(jù)包含兩行：第一行一個(gè)整數(shù) N，表示數(shù)組
A 的長(zhǎng)度；第二行輸入 N 個(gè)整數(shù)從左至右依次為 A0, A1, . . . , AN?1，相鄰元素之
間用空格分隔。
【輸出格式】
對(duì)于每組數(shù)據(jù)，輸出一行，包含一個(gè)整數(shù)表示答案，答案可能會(huì)很大，你
需要將答案對(duì) 1000000007 進(jìn)行取模后輸出。
【樣例輸入】
2
2
6 6
2
1 6
【樣例輸出】
4
試題C: 數(shù)組分割 4
第十四屆藍(lán)橋杯大賽軟件賽省賽 Java 大學(xué) B 組
0
【樣例說(shuō)明】
對(duì)于第一組數(shù)據(jù)，答案為 4。（注意：大括號(hào)內(nèi)的數(shù)字表示元素在數(shù)組中的
下標(biāo)。）
R1 = {0}, R2 = {1}；此時(shí) S 1 = A0 = 6 為偶數(shù), S 2 = A1 = 6 為偶數(shù)。
R1 = {1}, R2 = {0}；此時(shí) S 1 = A1 = 6 為偶數(shù), S 2 = A0 = 6 為偶數(shù)。
R1 = {0, 1}, R2 = {}；此時(shí) S 1 = A0 + A1 = 12 為偶數(shù), S 2 = 0 為偶數(shù)。
R1 = {}, R2 = {0, 1}；此時(shí) S 1 = 0 為偶數(shù), S 2 = A0 + A1 = 12 為偶數(shù)。
對(duì)于第二組數(shù)據(jù)，無(wú)論怎么選擇，都不滿(mǎn)足條件，所以答案為 0。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ N ≤ 10。
對(duì)于 40% 的評(píng)測(cè)用例，1 ≤ N ≤ 102。
對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ T ≤ 10, 1 ≤ N ≤ 103
, 0 ≤ Ai ≤ 109。

做法：線性dp

先看思路，當(dāng)數(shù)組總和為奇數(shù)的時(shí)候一定不存在R1和R2，因?yàn)镽2是R1的補(bǔ)集，當(dāng)總和為奇數(shù)的時(shí)候，R1和R2的奇偶性一定不同，因?yàn)槠鏀?shù)加偶數(shù)才是奇數(shù)。

這樣我們就可以定義狀態(tài)

令表示的是當(dāng)前是第個(gè)元素，并且奇偶性是

其中表示的是當(dāng)前第i個(gè)元素為偶數(shù)，當(dāng)前第i個(gè)元素是奇數(shù)

答案就是

狀態(tài)轉(zhuǎn)移方程：

如果是偶數(shù)那么就有

因?yàn)榕紨?shù)加偶數(shù)還是偶數(shù)

奇數(shù)加奇數(shù)還是偶數(shù)

如果是奇數(shù)那么就有

?因?yàn)槠鏀?shù)加偶數(shù)還是奇數(shù)下面同理

即可求解出答案，以下是代碼

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=21000,mod=1000000007;

int n,a[N],s[N];
int f[N][3];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(f,0,sizeof f);
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=a[i];
    if(sum%2)
    {
        cout<<0<<endl;
        return;
    }

    int ans=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]%2==0)
        {
            f[i][0]=1;
            for(int j=1;j<i;j++)
            {
                f[i][0]=(f[i][0]+f[j][0])%mod;
                f[i][1]=(f[i][1]+f[j][1])%mod;
            }
        }
        else
        {
            f[i][1]=1;
            for(int j=1;j<i;j++)
            {
                f[i][1]=(f[i][1]+f[j][0])%mod;
                f[i][0]=(f[i][0]+f[j][1])%mod;
            }
        }
        ans=(f[i][0]+ans)%mod;
    }
    cout<<ans<<endl;
}


signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

?

試題 D: 矩形總面積
時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：10 分
【問(wèn)題描述】
平面上有個(gè)兩個(gè)矩形 R1 和 R2，它們各邊都與坐標(biāo)軸平行。設(shè) (x1, y1) 和
(x2, y2) 依次是 R1 的左下角和右上角坐標(biāo)，(x3, y3) 和 (x4, y4) 依次是 R2 的左下
角和右上角坐標(biāo)，請(qǐng)你計(jì)算 R1 和 R2 的總面積是多少？
注意：如果 R1 和 R2 有重疊區(qū)域，重疊區(qū)域的面積只計(jì)算一次。
【輸入格式】
輸入只有一行，包含 8 個(gè)整數(shù)，依次是：x1，y1，x2，y2，x3，y3，x4 和 y4。
【輸出格式】
一個(gè)整數(shù)，代表答案。
【樣例輸入】
2 1 7 4 5 3 8 6
【樣例輸出】
22
【樣例說(shuō)明】
樣例中的兩個(gè)矩形如圖所示：
試題 D: 矩形總面積 6
第十四屆藍(lán)橋杯大賽軟件賽省賽 Java 大學(xué) B 組
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 20% 的數(shù)據(jù)，R1 和 R2 沒(méi)有重疊區(qū)域。
對(duì)于 20% 的數(shù)據(jù)，其中一個(gè)矩形完全在另一個(gè)矩形內(nèi)部。
對(duì)于 50% 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0, 103
]。
對(duì)于 100% 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0, 105
]。

思路一：掃描線模板

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100010;

struct segment
{
    int x, y1,y2;
    int d;
    bool operator < (const segment&t)const
    {
        return x < t.x;
    }
}seg[N * 2];
struct node
{
    int l,r;
    int cnt;
    int len;
}tr[N * 8];
vector<int>ys;
int n;

int find(int y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u)
{

    if(tr[u].cnt)tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if(tr[u].l != tr[u].r)
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else tr[u].len = 0;
}

void modify(int u,int l,int r,int d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += d;
        pushup(u);
    }
    else
    {
        int mid = tr[u].r + tr[u].l >> 1;
        if (l <= mid)modify(u << 1,l,r,d);
        if (r > mid)modify(u << 1 | 1,l,r,d);
        pushup(u);
    }
}

void build(int u,int l,int r)
{
    tr[u] = {l,r,0,0};

    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
    }
}

signed main()
{
    int T = 1;
    n=2;
    while (n)
    {
        ys.clear();
        int j = 0;
        for (int i = 0 ; i < n ; i ++)
        {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            seg[j ++] = {x1,y1,y2,1};
            seg[j ++] = {x2,y1,y2,-1};
            ys.push_back(y1),ys.push_back(y2);
        }
        sort(seg,seg + j);

        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());
        build(1,0,ys.size() - 2);

        int res = 0;

        for (int i = 0 ; i < j ; i ++)
        {
            if (i)res += tr[1].len * (seg[i].x - seg[i - 1].x);
            modify(1,find(seg[i].y1), find(seg[i].y2) - 1,seg[i].d);
        }

       cout<<res<<endl;
        break;
    }
    return 0;
}

思路二：用數(shù)學(xué)

如果兩個(gè)矩形相交的話就將一個(gè)兩個(gè)矩形補(bǔ)全成一個(gè)大矩形，然后減去兩個(gè)多出來(lái)的小矩形即可。

代碼就懶得寫(xiě)了

試題 E: 蝸牛
時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：15 分
【問(wèn)題描述】
這天，一只蝸牛來(lái)到了二維坐標(biāo)系的原點(diǎn)。
在 x 軸上長(zhǎng)有 n 根竹竿。它們平行于 y 軸，底部縱坐標(biāo)為 0，橫坐標(biāo)分別
為 x1, x2, ..., xn。竹竿的高度均為無(wú)限高，寬度可忽略。蝸牛想要從原點(diǎn)走到第
n 個(gè)竹竿的底部也就是坐標(biāo) (xn, 0)。它只能在 x 軸上或者竹竿上爬行，在 x 軸
上爬行速度為 1 單位每秒；由于受到引力影響，蝸牛在竹竿上向上和向下爬行
的速度分別為 0.7 單位每秒和 1.3 單位每秒。
為了快速到達(dá)目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之間建立了傳
送門(mén)（0 < i < n），如果蝸牛位于第 i 根竹竿的高度為 ai 的位置 (xi
, ai)，就可以
瞬間到達(dá)第 i + 1 根竹竿的高度為 bi+1 的位置 (xi+1, bi+1)，請(qǐng)計(jì)算蝸牛最少需要
多少秒才能到達(dá)目的地。
【輸入格式】
輸入共 1 + n 行，第一行為一個(gè)正整數(shù) n；
第二行為 n 個(gè)正整數(shù) x1, x2, . . . , xn；
后面 n ? 1 行，每行兩個(gè)正整數(shù) ai
, bi+1。
【輸出格式】
輸出共一行，一個(gè)浮點(diǎn)數(shù)表示答案（四舍五入保留兩位小數(shù)）。
【樣例輸入】
3
1 10 11
1 1
2 1
試題E: 蝸牛 8
第十四屆藍(lán)橋杯大賽軟件賽省賽 Java 大學(xué) B 組
【樣例輸出】
4.20
【樣例說(shuō)明】
蝸牛路線：
(0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0)，花費(fèi)時(shí)間為 1 + 0
1
.7 +
0 + 1
1
.3 + 1 ≈ 4.20
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 20% 的數(shù)據(jù)，保證 n ≤ 15；
對(duì)于 100% 的數(shù)據(jù)，保證 n ≤ 105，ai
, bi ≤ 104，xi ≤ 109。

思路：線性dp

定義狀態(tài)表示的是當(dāng)前所在的桿子是第個(gè)桿子表示的是，是否使用傳送門(mén)

表示用傳送門(mén)，表示不用傳送門(mén)

狀態(tài)轉(zhuǎn)移方程就可以寫(xiě)成

當(dāng)使用傳送門(mén)的時(shí)候可以寫(xiě)成?

?其中的意思表示的是

如果此時(shí)傳送過(guò)來(lái)的位置高于在出傳送點(diǎn)的位置的時(shí)候就要滑下去此時(shí)速度是

反之就要爬上去速度是

答案就是

?代碼

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=110000;

int n;
double x[N],a[N],b[N];
double f[N][3];//f[i][1]傳送門(mén)，f[i][0]

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i];

    for (int i = 1; i < n; i++)
        cin >> a[i] >> b[i];

    f[1][0] = x[1];
    f[1][1] = x[1] + a[1] / 0.7;

    for (int i = 2; i <= n; i++)
    {
        f[i][0]=min(f[i-1][0]+x[i]-x[i-1],f[i-1][1]+b[i-1]/1.3);
        f[i][1]=min(f[i][0]+a[i]/0.7,f[i-1][1]+((b[i-1]>a[i])?(b[i-1]-a[i])/1.3:(a[i]-b[i-1])/0.7));
    }
    printf("%.2lf",f[n][0]);

    return 0;
}

試題 G: 買(mǎi)二贈(zèng)一
時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：20 分
【問(wèn)題描述】
某商場(chǎng)有 N 件商品，其中第 i 件的價(jià)格是 Ai?，F(xiàn)在該商場(chǎng)正在進(jìn)行 “買(mǎi)二
贈(zèng)一” 的優(yōu)惠活動(dòng)，具體規(guī)則是：
每購(gòu)買(mǎi) 2 件商品，假設(shè)其中較便宜的價(jià)格是 P（如果兩件商品價(jià)格一樣，
則 P 等于其中一件商品的價(jià)格），就可以從剩余商品中任選一件價(jià)格不超過(guò) P
2
的商品，免費(fèi)獲得這一件商品?？梢酝ㄟ^(guò)反復(fù)購(gòu)買(mǎi) 2 件商品來(lái)獲得多件免費(fèi)商
品，但是每件商品只能被購(gòu)買(mǎi)或免費(fèi)獲得一次。
小明想知道如果要拿下所有商品（包含購(gòu)買(mǎi)和免費(fèi)獲得），至少要花費(fèi)多少
錢(qián)？
【輸入格式】
第一行包含一個(gè)整數(shù) N。
第二行包含 N 個(gè)整數(shù)，代表 A1, A2, A3, . . . ，AN。
【輸出格式】
輸出一個(gè)整數(shù)，代表答案。
【樣例輸入】
7
1 4 2 8 5 7 1
【樣例輸出】
25
試題 G: 買(mǎi)二贈(zèng)一 13
第十四屆藍(lán)橋杯大賽軟件賽省賽 Java 大學(xué) B 組
【樣例說(shuō)明】
小明可以先購(gòu)買(mǎi)價(jià)格 4 和 8 的商品，免費(fèi)獲得一件價(jià)格為 1 的商品；再后
買(mǎi)價(jià)格為 5 和 7 的商品，免費(fèi)獲得價(jià)格為 2 的商品；最后單獨(dú)購(gòu)買(mǎi)剩下的一件
價(jià)格為 1 的商品?？傆?jì)花費(fèi) 4 + 8 + 5 + 7 + 1 = 25。不存在花費(fèi)更低的方案。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 20。
對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 5 × 105，1 ≤ Ai ≤ 109。

思路：簡(jiǎn)單的貪心，每次取最大的兩個(gè)然后免費(fèi)其中兩個(gè)中最小的/2就行

代碼：

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=510000;

int n;
int a[N];

int check()
{
    priority_queue<int>st;
    int res=0;
    int t=0;
    for(int i=n;i;i--)
    {
        if(!st.empty()&&st.top()>=a[i])
        {
            st.pop();
            continue;
        }
        res+=a[i];
        t++;
        if(t>=2){
            t=0;
            st.push(a[i]/2);
        }
    }
    return res;
}


signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int l=-1,r=5e12+1;
    sort(a+1,a+1+n);

    cout<<check()<<endl;
    return 0;
}

試題 J: 魔法陣
時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：25 分
【問(wèn)題描述】
魔法師小藍(lán)為了營(yíng)救自己的朋友小 Q，來(lái)到了敵人布置的魔法陣。魔法陣
可以看作是一幅具有 N 個(gè)結(jié)點(diǎn) M 條邊的無(wú)向圖，結(jié)點(diǎn)編號(hào)為 0, 1, 2, . . . , N ? 1，
圖中沒(méi)有重邊和自環(huán)。敵人在每條邊上都布置了陷阱，每條邊都有一個(gè)傷害屬
性 w，每當(dāng)小藍(lán)經(jīng)過(guò)一條邊時(shí)就會(huì)受到這條邊對(duì)應(yīng)的 w 的傷害。小藍(lán)從結(jié)點(diǎn) 0
出發(fā)，沿著邊行走，想要到達(dá)結(jié)點(diǎn) N ? 1 營(yíng)救小 Q。
小藍(lán)有一種特殊的魔法可以使用，假設(shè)一條路徑按照順序依次經(jīng)過(guò)了以下
L 條邊：e1, e2, . . . , eL（可以出現(xiàn)重復(fù)的邊），那么期間小藍(lán)受到的總傷害就是
P =
∑L
i=1 w(ei)，w(ei) 表示邊 ei 的傷害屬性。如果 L ≥ K，那么小藍(lán)就可以從
這 L 條邊當(dāng)中選出連續(xù)出現(xiàn)的 K 條邊 ec
, ec+1, . . . , ec+K?1 并免去在這 K 條邊行
走期間所受到的傷害，即使用魔法之后路徑總傷害變?yōu)?P
′ = P ?
∑c+K?1
i=c w(ei)。
注意必須恰好選出連續(xù)出現(xiàn)的 K 條邊，所以當(dāng) L < K 時(shí)無(wú)法使用魔法。
小藍(lán)最多只可以使用一次上述的魔法，請(qǐng)問(wèn)從結(jié)點(diǎn) 0 出發(fā)到結(jié)點(diǎn) N ? 1 受
到的最小傷害是多少？題目保證至少存在一條從結(jié)點(diǎn) 0 到 N ? 1 的路徑。
【輸入格式】
第一行輸入三個(gè)整數(shù)，N, K, M，用空格分隔。
接下來(lái) M 行，每行包含三個(gè)整數(shù) u, v,w，表示結(jié)點(diǎn) u 與結(jié)點(diǎn) v 之間存在一
條傷害屬性為 w 的無(wú)向邊。
【輸出格式】
輸出一行，包含一個(gè)整數(shù)，表示小藍(lán)從結(jié)點(diǎn) 0 到結(jié)點(diǎn) N ? 1 受到的最小傷
害。
【樣例輸入 1】
4 2 3
試題J: 魔法陣 20
第十四屆藍(lán)橋杯大賽軟件賽省賽 Java 大學(xué) B 組
0 1 2
1 2 1
2 3 4
【樣例輸出 1】
2
【樣例輸入 2】
2 5 1
0 1 1
【樣例輸出 2】
0
【樣例說(shuō)明】
樣例 1，存在路徑：0 → 1 → 2 → 3，K = 2，如果在 0 → 1 → 2 上使用魔
法，那么答案就是 0 + 0 + 4 = 4；如果在 1 → 2 → 3 上使用魔法，那么答案就
是 2 + 0 + 0 = 2。再也找不到比 2 還小的答案了，所以答案就是 2。
樣例 2，存在路徑：0 → 1 → 0 → 1 → 0 → 1，K = 5，這條路徑總計(jì)恰好
走了 5 條邊，所以正好可以用魔法消除所有傷害，答案是 0。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ N ≤ 20。
對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ N ≤ 100。
對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 1000, 1 ≤ M ≤
N×(N?1)
2 ，1 ≤ K ≤ 10,
0 ≤ u, v ≤ N ? 1，1 ≤ w ≤ 1000

思路：最短路+線性dp

壓軸題難度并不大很經(jīng)典的題目，以往最短路中表示第個(gè)點(diǎn)中最短的距離

這里就需要稍微轉(zhuǎn)化一下表示的是第個(gè)點(diǎn)中免費(fèi)了條邊的費(fèi)用的最短距離。

所以有三種更新方法

假設(shè)此時(shí)第個(gè)點(diǎn)的鄰接點(diǎn)是

第一種更新方法就是當(dāng)?shù)臅r(shí)候就是正常最短路

也即是

第二種更新方式

免費(fèi)了條邊的最小費(fèi)用

也就是

第三種免費(fèi)完k條邊后的最小費(fèi)用

結(jié)果即使

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=2100000,M=2100;

int h[N],ne[N],e[N],w[N],idx;
int f[M][M];
bool st[N];
int n,m,k;

void add(int a,int b,int c)
{
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void spfa()
{
    memset(f,0x3f,sizeof f);
    queue<int>q;
    q.push(0);
    f[0][0]=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            bool flag=false;
            if(f[j][0]>f[t][0]+w[i])
            {
                f[j][0]=f[t][0]+w[i];
                flag=true;
            }

            for(int l=1;l<=k;l++)
            {
                if(f[j][l]>f[t][l-1])
                {
                    f[j][l]=f[t][l-1];
                    flag=true;
                }
            }

            if(f[j][k]>f[t][k]+w[i])
            {
                f[j][k]=f[t][k]+w[i];
                flag=true;
            }
            if(flag)q.push(j);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    memset(h,-1,sizeof h);
    cin>>n>>k>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    spfa();
    cout<<min(f[n-1][0],f[n-1][k]);
    return 0;
}

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-433859.html

到了這里，關(guān)于第十四屆藍(lán)橋杯大賽軟件賽省賽 Java 大學(xué) B 組題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！