天天看點
傳回

NOIP模拟題彙總（加厚版）\(NOIP\)模拟題彙總（加厚版）

\(NOIP\)模拟題彙總（加厚版）

T1 string

描述

有一個僅由 '0' 和 '1' 組成的字元串 \(A\)，可以對其執行下列兩個操作：

  • 删除 \(A\)中的第一個字元；
  • 若 \(A\)中 '1' 出現的次數為奇數，則在 \(A\) 的末尾插入 '1'，否則在 \(A\) 的末尾插入 '0'．

現在給出一個同樣僅由 '0' 和 '1' 組成的字元串 \(B\)，請你判斷 \(A\) 能否在任意多次操作後轉化為 \(B\)。

輸入

輸入檔案第一行一個正整數 \(T\)，表示有 \(T\) 組資料需要進行判斷。

接下來依次輸入 \(T\) 組資料，每組資料有兩行，其中第一行包含一個字元串 \(A\)，第二行包含一個字元串 \(B\)。

輸出

輸出共 \(T\) 行，對應 \(T\) 組詢問。若第 \(i\) 組資料中 \(A\)串可以轉化為 \(B\) 串則輸出 "YES"；否則輸出 "NO"。

輸入樣例 1 

2
01011
0110
0011
1110

輸出樣例 1 

YES
NO

提示

對于 \(20％\) 的資料，\(n\)≤\(10\), \(T\)=\(3\)

對于 \(50％\) 的資料，\(n\)≤\(1000\), \(T\)≤\(20\)。

對于 \(100％\) 的資料，\(n\)≤\(10^6\), \(T\)≤\(50\)。

題解

一道水題，但我考試的時候沒想出來 。

自己手推幾組樣例，就會發現一個規律：ans隻與01串中\(1\)的個數有關

因為你可以講前面的數删掉加到後面形成組合；

是以如果\(A\)中\(1\)的個數大于等于\(B\)中\(1\)的個數則輸出\(YES\)，否則輸出\(NO\)；

但是要注意若\(A\)中\(1\)的個數為奇數要拿\((\)\(A\)中\(1\)的個數+1\()\)與\(B\)中\(1\)的個數比較即可；

code： 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#define ll long long
#define R register
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
char a[N],b[N];
int lena,lenb,A,B,t;
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    read(t);
    while(t--){
        A=0;B=0;
        scanf("%s%s",(a+1),(b+1));
        lena=strlen(a+1);
        lenb=strlen(b+1);
        for(R int i=1;i<=lena;i++)
            if(a[i]=='1')A++;
        for(R int i=1;i<=lenb;i++)
            if(b[i]=='1')B++;
        if(A&1)A++;
        if(A>=B)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

T2 glide

描述

大森林中茂盛地生長着 \(N\) 棵樹，從 \(1\) 到 \(N\) 編号，第 \(i\) 棵樹的高度是 \(H_i\)，住在這片森林裡的飛鼠 Makik 可以在樹與樹之間滑翔。

有 \(M\) 組樹能供 \(Makik\)在其間滑翔，在每組樹間滑翔的時間是固定的。滑翔時，\(Makik\) 每秒會下落 \(1\) 米，即當 \(Makik\) 目前位置距離地面 \(h\) 米時，它經過 \(t\) 秒的滑翔後會落到距離地面 \(h-t\)米的高度上。但若\(h-t\) 小于 \(0\) 或比要到達的樹高還要大，則 \(Makik\) 不能進行這次滑行。

除滑翔外，\(Makik\) 還可以沿着一棵樹爬上爬下，每向上或向下移動 \(1\) 米均需花費 \(1\) 秒的時間。現在，\(Makik\) 想要從第 \(1\) 棵樹上高度為 \(X\) 米的位置移動到第 \(N\) 棵樹的頂端（高度為 \(H_N\) 的位置），請你幫它算一算最少要花費多少秒的時間。

輸入

輸入檔案第一行包含三個整數 \(N\),\(M\),\(X\)，分别表示樹的數量、能供 \(Makik\) 在其間滑翔的樹的組數和 \(Makik\) 的初始高度。

下面 \(N\) 行，其中第 \(i\) 行包含一個整數，表示第 \(i\) 棵樹的高度 \(H_i\)。

接下來 \(M\) 行，其中 \(j\) 行包含三個整數 \(A_j\),\(B_j\),\(T_j\)(\(A_j\)\(\neq\) \(B_j\))，表示 \(Makik\) 可以在第 \(A_j\) 棵樹和第 \(B_j\) 棵樹間互相滑行，每次滑行的時間是 \(T_j\) 秒。資料保證每一組樹都不會被多次給出。

輸出

輸出一行一個整數，表示 \(Makik\) 到達第 \(N\) 棵樹所至少要花費的秒數。如果不能到達，輸出 \(-1\)。

題解

我這道題在最短路上搞了一些操作，感覺想貪心，感覺不對，但是AC了;

輸入樣例 1 

>5 5 0
>50
>100
>25
>30
>10
>1 2 10
>2 5 50
>2 4 20
>4 3 1
>5 4 20
>```

輸出樣例 1 

110

提示

樣例說明：

先沿第 \(1\) 棵樹向上爬 \(50\) 米，再依次滑翔到第 \(2\) 棵、第 \(4\) 棵、第 \(5\) 棵樹上，最後沿第 \(5\) 棵樹向上爬 \(10\) 米。

資料規模與約定

對于 \(30\%\) 的資料，\(N\leq 1000\), \(M\leq 3000\), \(H_i\leq 100\), \(T_j\leq 100\)。

對于另外 \(30\%\) 的資料，\(X=0\)。

對于 \(100 \%\) 的資料，\(2\leq N\leq 100000\), \(1\leq M\leq 300000\), \(1\leq H_i\leq 10^9\), \(1\leq T_j\leq 10^9\), \(0\leq X\leq H_1\)。

題解

std講的思路：

一直跑\(SPFA\)(或\(Dij\)堆優化)，最後\(ans\)=（地底下的距離乘以2+地上的距離）；

std’s code: 
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define M 600005
#define _inf -4557430888798830400ll

int n, m, h[N];
long long X, d[N];

priority_queue<pair<long long, int> > q;

int head[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void spfa(int s)
{
    memset(d, 0xc0, sizeof d);
    d[s] = X;
    q.push(make_pair(X, s));
    while (!q.empty())
    {
        int x = q.top().second; long long y = q.top().first; q.pop();
        if (y != d[x]) continue;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val <= h[x])
            if (d[edge[i].to] < min(y - edge[i].val, 1ll * h[edge[i].to]))
                d[edge[i].to] = min(y - edge[i].val, 1ll * h[edge[i].to]),
                q.push(make_pair(d[edge[i].to], edge[i].to));
    }
}

int main()
{
    cin >> n >> m >> X;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &h[i]);
    for (int x, y, z, i = 1; i <= m; ++i)
        scanf("%d%d%d", &x, &y, &z),
        add(x, y, z), add(y, x, z);
    spfa(1);
    if (d[n] == _inf) cout << -1 << endl;
    else cout << (X - d[n]) * 2 - X + h[n] << endl;
    return 0;
}

我的思路：

老師的思路中細節比較少但可能不太好想，但我的寫法比較好了解 \((*/ω＼*)\)。

我的思路就是在\(SPFA\)中模拟一個\(H\)數組，\(H_i\)表示跑最短路時，在\(i\)點時的高度(就是你以最短路去走到\(i\)點時的高度)。

我認為就是在最短路時模拟......(細節比較多)

my code： 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#define ll long long
#define R register
#define N 300005 
#define INF 0x7fffffffffLL
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
int n,m,x,head[N],tot,flag,h[N],H[N],vis[N],u,v,w;
ll dist[N];
inline int abss(R int x){return x<0?-x:x;}
struct node{
    int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
    edge[++tot].nex=head[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    head[u]=tot;
}
inline void spfa(R int s){
    queue<int>q;
    for(R int i=1;i<=n;i++)dist[i]=INF;
    q.push(s);vis[s]=1;dist[s]=0;H[s]=x;
    while(!q.empty()){
        R int x=q.front();q.pop();vis[x]=0;
        for(R int i=head[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
//-------------下面是模拟判斷 細節比較多-------------------------------------------------------
             R int now=0;//now是模拟你需要爬多少步  正數為向上爬  負數為想下爬
            if(H[x]-edge[i].dis<0)now=(edge[i].dis-H[x]);//以目前高度跳到要更新的點會跳到地下
            else if(H[x]-edge[i].dis>h[xx])now=(-1)*(H[x]-edge[i].dis-h[xx]);//跳到天上
            if(H[x]+now>h[x]||H[x]+now<0)continue;//判斷目前能不能爬（不能爬到地下或天上）
            if(dist[xx]>dist[x]+edge[i].dis+abss(now)){
                dist[xx]=dist[x]+edge[i].dis+abss(now);
                H[xx]=H[x]+now-edge[i].dis;// 實時更新H數組
                if(!vis[xx]){
                    vis[xx]=1;
                    q.push(xx);
                }
            }
        }
    }
}
int main(){
    freopen("glide.in","r",stdin);
    freopen("glide.out","w",stdout);
    read(n);read(m);read(x);
    for(R int i=1;i<=n;i++)read(h[i]);
    for(R int i=1;i<=m;i++){
        read(u);read(v);read(w);
        add(u,v,w);add(v,u,w);
    }
    spfa(1);
    if(dist[n]==INF)printf("-1\n"); 
    else printf("%lld\n",dist[n]+h[n]-H[n]);//因為題中說要爬到第n棵樹的樹頂
    return 0;
}

T3 vestige

描述

作為魔導士的你進入了一片遺迹。遺迹内共有 \(n\) 個密室，編号從 \(1\) 到 \(n\)。密室間由 \(m\) 條雙向通道相連通，通道的長度不盡相同。由于遺迹已塵封多年，通道裡都充滿着污穢。你需要先淨化掉所有通道裡的污穢，才能邁出探索的腳步。

首先，你可以使用神聖驅魔術，淨化以 \(1\) 号密室為中心一定區域内所有的道路。當你標明一個非負整數距離 \(X\) 後，消耗 \(C\times X\) 個魔力點（\(C\) 為常數），此時若一條通道兩端的密室與 \(1\) 号密室的距離均不大于 \(X\)，這條通道就會被淨化。之後，你需要分别淨化其餘通道，淨化一條通道所需魔力點數即為這條通道的長度。

請确定淨化的方式，使消耗的魔力點數盡可能少。

輸入

輸入檔案第一行包含三個正整數 \(n\), \(m\), \(C\)，分别表示密室數量、通道數量和與使用神聖淨化術相關的常數。

接下來 \(m\) 行，其中第 \(i\) 行包含 \(3\) 個整數 \(u_i\), \(v_i\), \(d_i\)，依次表示第 \(i\) 條通道兩端密室的編号和這條通道的長度。

輸出

輸出一行一個整數，表示消耗魔力點數的最小值。

輸入樣例 1 : 

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

輸出樣例 1 : 

14

提示

對于 \(32\%\) 的測試資料，\(n\)≤\(100\), \(m\)≤\(200\), \(C\)≤\(100\), \(di\)≤\(10\)。

對于 \(64\%\) 的測試資料，\(n\)≤\(100\), \(m\)≤\(4000\)。

對于 \(100\%\) 的測試資料，滿足以下條件：\(2≤n≤100000, 1≤m≤200000, 1≤C≤100000，u_i≠v_i，1≤d_i≤100000\)，在兩個密室間直接連接配接的通道不超過一條。

題解

我的歪解

我首先想的是分治，我想二分肯定不行，因為它是沒有單調性的。

我想了一下感覺它的大部分資料應該是有凸性的（例如\(y=x^2\)的函數圖像)，是以可以三分。

下面是我的三分代碼（得了84分，可以說騙了不少，當時手賤\(SPFA\)寫錯了，竟有68分）

三分模闆沒過的我居然瞎歪歪了一個三分

歪解code： 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#define ll long long
#define R register
#define N 400005
#define INF 0x7fffffffffffLL
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
ll n,m,c,tot,h[N],vis[N],pd[N];
ll dist[N],sum,now_ans,now;
struct bian{
    int u,v;
    ll w;
}b[N];
struct node{
    int nex,to;
    ll dis;
}edge[N<<1];
inline void add(R int u,R int v,R ll w){
    edge[++tot].nex=h[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    h[u]=tot;
}
inline void spfa(R int s){
    for(R int i=1;i<=n;i++)dist[i]=INF;
    queue<int> q;q.push(s);dist[s]=0;vis[s]=1;
    while(!q.empty()){
        R int x=q.front();q.pop();vis[x]=0;
        for(R int i=h[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
            if(dist[xx]>dist[x]+edge[i].dis){
                dist[xx]=dist[x]+edge[i].dis;
                if(!vis[xx]){
                    vis[xx]=1;
                    q.push(xx);
                }
            }
        }   
    }
}
inline ll check(R ll mid){
    ll tot=0;
    for(R int i=1;i<=n;i++)pd[i]=0;
    for(R int i=1;i<=n;i++)
        if(dist[i]<=mid)pd[i]=1;
    for(R int i=1;i<=m;i++)
        if(pd[b[i].u]&&pd[b[i].v])
            tot+=b[i].w;
    return tot-mid*c;//這是你能節省的
}
int main(){ 
    freopen("vestige.in","r",stdin);
    freopen("vestige.out","w",stdout);
    read(n);read(m);read(c);
    for(R int i=1;i<=m;i++){
        read(b[i].u);read(b[i].v);read(b[i].w);
        add(b[i].u,b[i].v,b[i].w);add(b[i].v,b[i].u,b[i].w);sum+=b[i].w;
    }
    spfa(1);
    R ll l=0,r=sum;
    while(l<=r){
        R ll tmp=(r-l)/3;
        R ll mid1=l+tmp;
        R ll mid2=r-tmp;
        if(check(mid1)>check(mid2)) r=mid2-1;
        else l=mid1+1;
    }
    ll tmp=check(l),temp=check(r);
    if(tmp>temp)now=l,now_ans=tmp;
    else now=r,now_ans=temp;
    printf("%lld\n",sum-now_ans);
    return 0;
}

當然了，三分本來就是一個非常好的騙分算法（也會是正解），有些題在加一些暴力，一定會有神奇的效果；

講課老師說加上暴力這道題應該可以\(A\)掉,但懶惰的我并沒有去實踐，有興趣的可以試一試；

正解

這其實是一道經典的最短路的一種題型。

先跑一遍\(SPFA\)，處理出\(dist\)數組；

然後再利用\(dist\)數組處理出每一條邊的\(maxdis\);

将\(maxdis\)數組從小到大排序（結構體排序）；

NOIP模拟題彙總（加厚版）\(NOIP\)模拟題彙總（加厚版）

看完圖應該都懂了吧。

code: 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#define ll long long
#define R register
#define N 800005
#define int long long
#define INF 9999999999999999LL
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
ll n,m,c,tot,h[N],vis[N],pd[N],maxdis[N];
ll dist[N],sum,ans,maxsum;
struct bian{
    int u,v,w; 
}b[N];
struct node{
    int nex,to,dis;
}edge[N<<1];
struct MAX{
    int maxdis,id;
    friend bool operator < (const MAX &a,const MAX &b){
        return a.maxdis<b.maxdis;
    }
}md[N];
inline void add(R int u,R int v,R int w){
    edge[++tot].nex=h[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    h[u]=tot;
}
inline void spfa(R int s){
    for(R int i=1;i<=n;i++)dist[i]=INF;
    queue<int> q;q.push(s);dist[s]=0;vis[s]=1;
    while(!q.empty()){
        R int x=q.front();q.pop();vis[x]=0;
        for(R int i=h[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
            if(dist[xx]>dist[x]+edge[i].dis){
                dist[xx]=dist[x]+edge[i].dis;
                if(!vis[xx]){
                    vis[xx]=1;
                    q.push(xx);
                }
            }
        }   
    }
}
signed main(){ 
    freopen("vestige.in","r",stdin);
    freopen("vestige.out","w",stdout);
    read(n);read(m);read(c);
    for(R int i=1;i<=m;i++){
        read(b[i].u);read(b[i].v);read(b[i].w);
        add(b[i].u,b[i].v,b[i].w);add(b[i].v,b[i].u,b[i].w);sum+=b[i].w;
    }
    spfa(1);
    for(R int i=1;i<=m;i++)
        md[i].maxdis=max(dist[b[i].u],dist[b[i].v]),md[i].id=i;
    sort(md+1,md+1+m);
    ans=sum;
    for(R int i=1;i<=m;i++){
        sum-=b[md[i].id].w;
        ans=min(ans,1LL*md[i].maxdis*c+sum);
    }
    printf("%lld\n",ans);
    return 0;
}

T4 copy

描述

從前有一個$ {1, 2, \dots , n}$ 的排列，你希望用剪切/粘貼操作，将這個排列變成 \(1,2, \dots , n\)。

一次剪切/粘貼操作指的是把序列中某段連續的子區間整體向前或者向後平移一段距離。由于你認為同時按 $Ctrl+X $很累手指，是以想要知道最少的操作次數。

輸入

輸入檔案包含多組資料。

每組資料有兩行，其中第一行包含一個正整數 \(n\)，第二行給出一組 \({1, 2, ..., n}\) 的排列。

以一個 \(0\) 來結束輸入。

輸出

對于每組資料，輸出一行一個整數，表示最小的操作次數。

輸入樣例 1: 

6
2 4 1 5 3 6
5
3 4 5 1 2
0

輸出樣例 1 : 

2
1

提示

對于 \(20 \%\) 的資料，資料組數 \(\leq 6\)。

對于\(100\%\) 資料，\(n \leq 9\)，資料組數 \(\leq 50\)。

題解

\(IDA^*\)的一道很不錯的題

但是還是講一下粗略的講\(IDA^*\),(我覺得可能一些人并不了解)；

一道入門題

以\([SCOI2005]\)騎士精神為例，先講一下\(IDA^*\)的基礎前置知識;

突然加上一道題。。。

T4+ [SCOI2005]騎士精神

描述

　在一個\(5×5\)的棋盤上有\(12\)個白色的騎士和\(12\)個黑色的騎士， 且有一個空位。在任何時候一個騎士都能按照騎

士的走法（它可以走到和它橫坐标相差為\(1\)，縱坐标相差為\(2\)或者橫坐标相差為\(2\)，縱坐标相差為\(1\)的格子）移動到空

位上。 給定一個初始的棋盤，怎樣才能經過移動變成如下目标棋盤： 為了展現出騎士精神，他們必須以最少的步

數完成任務。

NOIP模拟題彙總（加厚版）\(NOIP\)模拟題彙總（加厚版）

輸入

第一行有一個正整數\(T(T<=10)\)，表示一共有\(N\)組資料。接下來有\(T\)個\(5×5\)的矩陣，\(0\)表示白色騎士，\(1\)表示黑色騎 士，\(*\)表示空位。兩組資料之間沒有空行。

輸出

　對于每組資料都輸出一行。如果能在\(15\)步以内（包括\(15\)步）到達目标狀态，則輸出步數，否則輸出-\(1\)。

輸入樣例 1: 

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

輸出樣例1： 

7
-1

題解

題意：給你一個初始棋盤，要求用最少的步數移動馬達到如上圖的目标狀态（要求棋盤中的馬隻能走“日”）。

咱們先抛開\(IDA^*\)，先如何優化爆搜；

這裡的馬和象棋裡的馬走法相同，但題目中要求讓馬走，但是要是馬的話，搜尋分支比較多，是以我們要考慮讓空格走（很顯然吧）。

下面步入正題：

\(IDA^*\)就是帶有疊代加深和估價函數優化的搜尋。

可能某些人對以上兩個名詞很陌生，下面一些前置知識可能會帶你透徹一下。

前置知識1：疊代加深

定義：

每次限定一個\(maxdep\)最大深度，使搜尋樹的深度不超過\(maxdep\)。

for(R int maxdep=1;maxdep<=題目中給的最大步數;maxdep++){
        dfs(0,maxdep);//0為出入函數中目前步數，maxdep為傳入的最大深度。
        if(success)break;//如果搜尋成功則會在dfs函數中将success指派為1。
    }

使用範圍:

1.在有一定的限制條件時使用（例如本題中“如果能在\(15\)步以内（包括\(15\)步）到達目标狀态，則輸出步數，否則輸出\(－1\)。“）。

2.題目中說輸出是以解中的任何一組解。

為什麼能夠降低時間複雜度：

我們可能會在一個沒有解（或解很深的地方無限遞歸然而題目中要求輸出任何的一組解），是以我們限制一個深度，讓它去周遊更多的分支，去更廣泛地求解，(其實和\(BFS\)有異曲同工之妙)。

前置知識2：估價函數

定義：

\(f(n)=g(n)+h(n)\)

其中\(f(n)\)是節點的估價函數，\(g(n)\)是現在的實際步數，\(h(n)\)是對未來步數的最完美估價（“完美”的意思是可能你現實不可能實作，但你還要拿最優的步數去把\(h(n)\)算出來，可能不太好口胡，可以參考下面的執行個體）。

應用：

void dfs(int dep,int maxdep){
        if(evaluate()+dep>maxdep)return;
        //evaluate函數為對未來估價的函數，若未來估價加實際步數>疊代加深的深度則return。
        if(!evaluate){
            success=1;
            printf("%d\n",dep);
            return;
        }
        ......
    }
前置知識3：\(A^*\)和\(IDA^*\)的差別

\(A^*\)是用于對\(BFS\)的優化；

\(IDA^*\)是對結合疊代加深的\(DFS\) 的優化。

本質上隻是在\(BFS\)和\(DFS\)上加上了一個估價函數。

何時使用因題而定：

\(A^*\)（[SCOI2007]k短路）;\(IDA^*\)（[SCOI2005]騎士精神和UVA11212 Editing a Book 就是上面的兩道題）。

前置知識畢！！！

現在就是要想一個比較好的估價函數（若估價函數不好的話，優化效率就并不高，例如若估價函數一直為0，那就是爆搜）。

我們可以想一下，每次空白格子和黑白棋子交換，最優的情況就是每次都把黑白棋子移動到目标格子。

那麼你的估價函數就出來了：

const int goal[7][7]={
        {0,0,0,0,0,0},
        {0,1,1,1,1,1},
        {0,0,1,1,1,1},
        {0,0,0,2,1,1},
        {0,0,0,0,0,1},
        {0,0,0,0,0,0}
    };    
    inline int evaluate(){
        R int cnt=0;
        for(R int i=1;i<=5;i++)
            for(R int j=1;j<=5;j++)
                if(mp[i][j]!=goal[i][j])cnt++;
        return cnt;
    }

下面就是爆搜了：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#define ll long long
#define R register
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
int n,m,t,mp[7][7],stx,sty,success;
char ch;
const int dx[]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[]={0,2,-2,2,-2,1,-1,1,-1};
const int goal[7][7]={
    {0,0,0,0,0,0},
    {0,1,1,1,1,1},
    {0,0,1,1,1,1},
    {0,0,0,2,1,1},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0}
};
inline int evaluate(){
    R int cnt=0;
    for(R int i=1;i<=5;i++)
        for(R int j=1;j<=5;j++)
            if(mp[i][j]!=goal[i][j])cnt++;
    return cnt;
}
inline int safe(R int x,R int y){
    if(x<1||x>5||y<1||y>5)return 0;
    return 1;
}
inline void A_star(R int dep,R int x,R int y,R int maxdep){
    if(dep==maxdep){
        if(!evaluate())success=1;
        return;
    }
    for(R int i=1;i<=8;i++){
        R int xx=x+dx[i];
        R int yy=y+dy[i];
        if(!safe(xx,yy))continue;
        swap(mp[x][y],mp[xx][yy]);
        int eva=evaluate();
        if(eva+dep<=maxdep)
            A_star(dep+1,xx,yy,maxdep);
        swap(mp[x][y],mp[xx][yy]);//回溯
    }
}
int main(){
    read(t);
    while(t--){
        success=0;
        for(R int i=1;i<=5;i++){
            for(R int j=1;j<=5;j++){
                cin>>ch;
                if(ch=='*')mp[i][j]=2,stx=i,sty=j;//記錄起點即為空白格子
                else mp[i][j]=ch-'0';
            }
        }
        if(!evaluate()){printf("0\n");continue;}
        for(R int maxdep=1;maxdep<=15;maxdep++){
            A_star(0,stx,sty,maxdep);
            if(success){printf("%d\n",maxdep);goto ZAGER;}
        }
        printf("-1\n");
        ZAGER:;
    }
    return 0;
}

\(IDA^*\)入門鋪墊完成。。。終于到T4了

大緻題意：給出一個1~n的排列，每次可以交換相鄰兩個區間，問最少移動幾次使其變成1,2,3...n。

本題若是想用\(IDA^*\)便是考察估價函數的設計（本題估價函數确實不好設計）。

若這個區間是連續的那麼

畫一個圖想一下

NOIP模拟題彙總（加厚版）\(NOIP\)模拟題彙總（加厚版）

code(沒有任何其他剪枝，不動任何的思維): 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath> 
#define ll long long
#define R register
#define N 10
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
int n,maxdep,num[N],tmp[N],success;
inline int gujia(){
    R int tot=0;
    for(R int i=1;i<=n-1;i++)
        if(num[i+1]!=num[i]+1) tot++;
    tot+=(num[n]!=n);
    return (tot+2)/3;
}
inline void ctrl_x(R int l,R int mid,R int r){
    R int now=l;
    for(R int i=mid+1;i<=r;i++)
        tmp[now++]=num[i];
    for(R int i=l;i<=mid;i++)
        tmp[now++]=num[i];
    for(R int i=l;i<=r;i++)
        num[i]=tmp[i];
}
inline void dfs(R int dep){
    if(success)return;
    R int zager=gujia();
    if(zager+dep>maxdep)return;
    if(!zager){
        printf("%d\n",dep);
        success=1;return;
    }
    for(R int l=1;l<=n-1;l++){
        for(R int mid=l;mid<=n-1;mid++){
            for(R int r=mid+1;r<=n;r++){
                ctrl_x(l,mid,r);
                dfs(dep+1);
                if(success)return;
                ctrl_x(l,l+r-mid-1,r);
            }
        }
    }
}
inline void IDAstar(){
    success=0;
    for(maxdep=1;maxdep;maxdep++){
        dfs(0);
        if(success)break;
    }
}
int main(){
    freopen("copy.in","r",stdin);
    freopen("copy.out","w",stdout);
    while(233){
        read(n);
        if(!n)break;
        for(R int i=1;i<=n;i++)read(num[i]);
        IDAstar();
    }
    return 0;
}

T5 trainfair

描述

在 \(MS\) 國有 \(N\) 座城市，編号從 \(1\) 到 \(N\) ，其中 \(1\) 号城市是 \(MS\) 國的首都。

\(MS\) 國裡，隻有一家鐵路公司，經營着 \(M\) 條連接配接着各城市的鐵路線路，每條線路都雙向地連接配接着兩座不同的城市。通過這些線路，我們可以在任意兩座城市間通行。

原本，乘坐一條線路隻需要花費 \(1\) 角錢。可是由于經營不善，鐵路公司提出計劃，要在今後的 \(Q\) 年間，每年給某一條線路漲價為 \(2\) 角錢。保證一條線路不會被漲價多次。

另外，這個鐵路公司每年都會在每一座城市進行一次居民滿意度調查。原本每一座城市中的居民都對鐵路公司的服務十分滿意，但線上路漲價後就說不定了。每一年的滿意度調查都會在當年的漲價計劃實施後進行。如果一座城市中的居民在當年坐火車去首都所需的最少花費相比于計劃提出前增加了，他們就會對鐵路公司抱有不滿。首都的居民永遠不會對鐵路公司抱有不滿。

在計劃施行前，你需要幫助鐵路公司統計出未來的每一年中，各将有多少城市的居民對鐵路公司抱有不滿。

輸入

輸入檔案第一行包含三個正整數 \(N\), \(M\), \(Q\)，分别表示 \(MS\) 國的城市數量、鐵路路線數量和漲價計劃将要實施的時間長度。

接下來 \(M\) 行，其中第 \(i\) 行包含 \(2\) 個整數 \(U_i, V_i\)，表示第 \(i\) 條路線連接配接着編号為 \(U_i\) 和 \(V_i\) 的兩座城市。

接下來 \(Q\) 行，其中第 \(j\) 行包含一個整數 \(R_j\)，表示計劃施行後第 \(j\) 年将會讓第 \(R_j\) 條線路漲價。

輸出

輸出 \(Q\) 行，其中第 \(j\) 行表示第 \(j\) 年居民對鐵路公司抱有不滿的城市的數量。

輸入樣例 1 : 

5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3

輸出樣例 1 

0
2
2
4
4

提示

對于 \(24\%\) 的測試資料，\(N \leq 100, M \leq 4950, Q \leq 30\)。

對于 \(48\%\) 的測試資料，\(Q \leq 30\)。

對于另 \(32\%\) 的測試資料，正确的輸出中不同的數字不超過\(50\) 種。

對于 \(100\%\) 的測試資料，滿足以下條件：

\(2 \leq N \leq 10^5, 1 \leq Q \leq M \leq 2 \times 10^5\),

\(1 \leq U_i, V_i \leq N, U_i ≠ V_i，1 \leq R_j \leq M\)，且兩個城市間直接連接配接的路線不超過一條。

題解

大緻題意：\(N\)個點\(M\)條邊，初始邊權均為1，每次修改一條邊的權值，問每次修改後有幾個點的到1的最短路與初始最短路的長度不同。

我的暴力思路（60分）

首先\(48\%\)資料的可以發現\(Q\)很小，使用暴力修改（其實是\(O(1)\)）暴力\(Q\)遍\(SPFA\),每次暴力統計\(ans\)。

為什麼能過\(60\%\)的資料呢（好像是資料水）。

我們可以想一下，假如我們修改過一條邊，那麼下次再次修改的時候就已經沒有貢獻了，是以可以用\(used\)數組标記，如果标記過直接輸出上次的\(ans\)。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<vector>
#define ll long long
#define R register
#define INF 0x3f3f3f3f
#define N 200005
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
int n,m,q,u,v,tot,x,ans;
int h[N],used[N],id[N],dist[N],vis[N],last[N];
struct node{
    int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
    edge[++tot].nex=h[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    h[u]=tot;
}
inline void spfa(R int s){
    queue<int> q;
    for(R int i=1;i<=n;i++)dist[i]=INF,vis[i]=0;
    q.push(s);vis[s]=1;dist[s]=0;
    while(!q.empty()){
        R int x=q.front();q.pop();vis[x]=0;
        for(R int i=h[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
            if(dist[xx]>dist[x]+edge[i].dis){
                dist[xx]=dist[x]+edge[i].dis;
                if(!vis[xx]){
                    vis[xx]=1;q.push(xx);
                }
            }
        }
    }
}
int main(){
    freopen("trainfair.in","r",stdin);
    freopen("trainfair.out","w",stdout);
    read(n);read(m);read(q);
    for(R int i=1;i<=m;i++){
        read(u);read(v);
        add(u,v,1);add(v,u,1);
        id[i]=tot;//記錄邊的序号
    }
    spfa(1);
    for(R int i=1;i<=n;i++)last[i]=dist[i];//初始最短路的值
    for(R int i=1;i<=q;i++){
        read(x);
        edge[id[x]].dis+=2;
        edge[id[x]-1].dis+=2;//修改
        if(used[x])printf("%d\n",ans);//标記
        else{
            spfa(1);ans=0;//暴力SPFA
            for(R int j=1;j<=n;j++)
                if(dist[j]!=last[j])ans++;//暴力統計ans
            printf("%d\n",ans);
            used[x]=1;
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

正解

正解和上面的暴力思路可以說是沒有多少相似的地方。。。

大緻思路：
  1. 在原圖上跑一邊\(SPFA\)（或\(Dij\)堆優化），目的是處理出最短路數組\(dist\)。
  2. 重建立一個關于最短路的拓撲圖，即如果滿足最短路\(dist[xx]==dist[x]+edge[i].dis\)的性質則建邊，由于我們在原圖從\(1\)開始跑，而我們要的拓撲圖是要從每個點連到\(1\)，是以要反向建邊，并且統計每個點的出度。 
    inline void bfs(R int x){
 for(R int x=1;x<=n;++x){
     for(R int i=h[x];i;i=edge[i].nex){
         R int xx=edge[i].to;
         if(dist[xx]==dist[x]+edge[i].dis)
             ADD(xx,x,edge[i].dis,edge[i].id);chu[xx]++;nxt[i/2]=xx;
     }
 } 
}
  3. 下面就是核心的 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<vector>
#define ll long long
#define R register
#define INF 0x3f3f3f3f
#define N 200005
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
int n,m,q,u,v,tot=1,opt,ans,t=1;
int h[N],used[N],dist[N],vis[N],head[N],chu[N],nxt[N];
struct node{
    int nex,to,dis,id;
}edge[N<<1],e[N<<1];
inline void ADD(R int u,R int v,R int w,R int id){
    e[++t].nex=head[u];
    e[t].to=v;
    e[t].dis=w;
    e[t].id=id; 
    head[u]=t;
}
inline void add(R int u,R int v,R int w,R int id){
    edge[++tot].nex=h[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    edge[tot].id=id; 
    h[u]=tot;
}
inline void spfa(R int s){
    queue<int> q;
    for(R int i=1;i<=n;i++)dist[i]=INF;
    q.push(s);vis[s]=1;dist[s]=0;
    while(!q.empty()){
        R int x=q.front();q.pop();vis[x]=0;
        for(R int i=h[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
            if(dist[xx]>dist[x]+edge[i].dis){
                dist[xx]=dist[x]+edge[i].dis;
                if(!vis[xx]){
                    vis[xx]=1;q.push(xx);
                }
            }
        }
    }
}
inline void bfs(R int x){
    for(R int x=1;x<=n;++x){
        for(R int i=h[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
            if(dist[xx]==dist[x]+edge[i].dis){
                ADD(xx,x,edge[i].dis,edge[i].id);chu[xx]++;nxt[i/2]=xx;
            }
        }
    } 
}
queue<int> Q;
int main(){
    freopen("trainfair.in","r",stdin);
    freopen("trainfair.out","w",stdout);
    read(n);read(m);read(q);
    for(R int i=1;i<=m;i++){
        read(u);read(v);
        add(u,v,1,i);add(v,u,1,i);
    }
    spfa(1);
    bfs(1);tot=1; 
    memset(h,0,sizeof(h));
    for(R int i=1;i<=n;i++){
        for(R int j=head[i];j;j=e[j].nex){
            R int xx=e[j].to;
            add(xx,i,e[j].dis,e[j].id); 
        }
    }   
    while(q--){
        read(opt);R int x=nxt[opt];
        if(used[opt]||x==0){printf("%d\n",ans);continue;}
        used[opt]=1;chu[x]--;
        if(!chu[x]){
            Q.push(x);
            while(!Q.empty()){
                R int u=Q.front();Q.pop();ans++;
                for(R int i=h[u];i;i=edge[i].nex){
                    R int v=edge[i].to;
                    if(used[edge[i].id])continue;
                    used[edge[i].id]=1;
                    chu[v]--;if(!chu[v])Q.push(v);
                }
            }
        }
        printf("%d\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

未完待續......

轉載于:https://www.cnblogs.com/ZAGER/p/9740673.html

資料結構與算法
上一篇: Java中Integer和int的差別
下一篇: NOIp模拟題 之 肮髒的牧師 （桶排序）

繼續閱讀