那么，作為一名初入信息競賽的選手，我也試著開始用博客記錄自己的學習歷程，那么這篇文章先簡單介紹一下我自己吧。

本人開始學習信息學大概以來，主要都是用的C++，所以對其他語言并不是十分熟悉。2016我還只是一名NOIP普及組的選手，水掉一個一等獎后美滋滋繼續往下學。最近剛剛搞完今年HDNIOIP提高組前，聽同學說最后一道題是省選第二題的難度后我懵逼了（由于最近剛比完如果想要題解可以搜索“xjr01”， hdNOIP2017 題解 -> " http://www.cnblogs.com/xiao-ju-ruo-xjr/ "），其實第一篇文章也不知道寫什么,那就胡亂寫一下普及組的題解吧（無聊）。

那么首先來看第一題

無腦暴力，哈希前綴和什么的隨便寫，就不解釋了。

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define M 2020 using namespace std; int n,m,k,a[M],ans,x,y,tmp; int need(int x){if(x%k==0) return x/k;return x/k+1; } int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);a[x]++;a[y]--;}for(int i=1;i<=n+1;i++){tmp+=a[i];ans=max(ans,need(tmp));}ans=min(ans,need(m));printf("%d",ans);return 0; }

第二題，一個簡單的動態規劃

設 f [ i ][ j ][ 0 ]表示時刻 i 時耗費了 j 的體力來到a樹，f [ i ][ j ][ 1 ]表示時刻 i 時耗費了 j 的體力來到b樹。

轉移：

f [ i ][ j ][ 1 ]可以從 f [ i-1 ][ ?j-2 ][ 0 ]和 f [ i-1 ][ j ][ 1 ]轉移

f [ i ][ j ][ 0 ]可以從 f [ i-1 ][ ?j-1 ][ 1 ]和 f [ i-1 ][ j ][ 0 ]轉移

（至于為什么你們自己想）

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define M 300 using namespace std; int n,m,f[M][M][2],x,a[M],b[M],ans; int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&b[i]);}f[1][0][0]=a[1];f[1][0][1]=b[1];for(int i=2;i<=n;i++){for(int j=0;j<=m;j++){f[i][j][0]=f[i-1][j][0];f[i][j][1]=f[i-1][j][1];if(j>1) f[i][j][1]=max(f[i-1][j-2][0],f[i][j][1]);if(j>0) f[i][j][0]=max(f[i-1][j-1][1],f[i][j][0]);f[i][j][0]+=a[i];f[i][j][1]+=b[i];}}for(int i=0;i<=m;i++){ans=max(ans,max(f[n][i][0],f[n][i][1]));}printf("%d",ans);return 0; }

然后是第三題

第三題大概是比較復雜的一道題了，關鍵就在于如何處理全排列的序號。
這道題一共分為兩部分

第一部分，將給定的全排列轉化成全排列的序號。

首先對于一個k，他的全排列一共有k!（k的階乘）種排列。

設置一個變量 cnt=0，s[n]存儲這個排列；

對于第 i 位，若有 k 個 j 滿足： i < j <= n 且 s[ j ] > s[ i ]，則我們需要將 cnt 加上 ( n - i )！* k。

為什么呢？對于某一個長為 N 的排列 , 一共分為 N 個部分，第 i 個部分是以 第 i 小的數為開頭的排列，且這N個部分都有（N-1）!個排列。

也就是說，我們對于每一位，從這一位到結尾都看做一個未離散化的排列（依靠每一個數的大小關系把他們看做一個不是很嚴謹的排列） ，然后求這個排列在這些數“全排列”中的哪個部分，也就求得了需要從0向后跳個部分才能達到當前的部分。

這樣我們就求得了給出序列的序號（編號）

我們將m加上cnt，得到k，就得到了最后應該輸出的排列的編號。

第二部分，輸出給定編號的全排列。

讀到這里，你應該已經明白了，對于第 i 位，我們只要用 k 除以（n-i）的階乘，就知道這個序列應該是位于第m個部分，然后輸出在剩余的未輸出過的數中第m小的數即可

所以說，我們只需要一個階乘的預處理，然后瞎搞就好了。

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define M using namespace std; LL n,m,s[22],p[22]; bool f[22]; LL cnt(LL x){LL co=0;for(LL i=x+1;i<=n;i++){if(p[i]<p[x]) co++;}return co; } LL check(LL x){LL co=0;for(LL i=1;i<=n;i++){if(f[i]) continue;co++;if(co==x){f[i]=true;return i;}}return -1;//這句話毫無意義 } int main(){s[0]=1;scanf("%lld%lld",&n,&m);memset(f,true,sizeof(f));for(LL i=1;i<=n;i++) s[i]=s[i-1]*i;for(LL i=1;i<=n;i++) scanf("%lld",&p[i]),f[i]=false;for(LL i=1;i<=n;i++){m+=cnt(i)*s[n-i];}for(LL i=1;i<=n;i++){if(i>1) printf(" ");printf("%lld",check(m/s[n-i]+1));m%=s[n-i];}return 0; }

第四道題，是一個特殊的二叉樹，數字由于n<=10,我就只寫了一個比較好些的但是比較慢的程序。

這個程序大概是這樣，由于在先序遍歷中，子節點一定在父節點后才出現，每一個節點的右子節點（如果有的話）總在它父節點的左子節點后出現，所以我只是暴力建樹，枚舉每個點的父節點，建完樹之后用中序遍歷檢驗建的這棵樹是否正確即可，如果即可，再直接遞歸的計算。

然而，萬萬沒想到，我最后還是栽了一個點應為這道題有^的操作（這里的^是指次方，而不是異或）,我這里就暫時不寫高精度了。

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<stack> #define LL long long #define M 20 using namespace std; LL n,m,p[M],f[M],l[M],r[M],c[M],cnt; string a,b;bool isd(char x){if(x>='0'&&x<='9') return true;return false; } int take(char x){if(isd(x)) return x-'0';if(x=='+') return -1;if(x=='-') return -2;if(x=='*') return -3;return -4; } bool search(LL x){if(p[x]>=0){cnt++;if(p[x]==c[cnt]) return true;return false;}if(l[x]==0||r[x]==0) return false;if(!search(l[x])) return false;cnt++;if(p[x]!=c[cnt]) return false;if(!search(r[x])) return false;return true; } LL pow(LL x,LL y){if(y==0) return 1;return x*pow(x,y-1); } LL calc(LL x){if(p[x]>=0) return p[x];if(p[x]==-1) return calc(l[x])+calc(r[x]);if(p[x]==-2) return calc(l[x])-calc(r[x]);if(p[x]==-3) return calc(l[x])*calc(r[x]);return pow(calc(l[x]),calc(r[x])); } void dfs(LL x){if(x==n+1){cnt=0;if(search(1)){printf("%lld",calc(1));exit(0);}return;}for(LL i=x-1;i>0;i--){if(p[i]>=0) continue;if(l[i]==0){l[i]=x,f[x]=i;dfs(x+1);l[i]=0,f[x]=0;}else if(r[i]==0){r[i]=x,f[x]=i;dfs(x+1);r[i]=0,f[x]=0;}} } int main(){scanf("%lld",&n);cin>>a;cin>>b;f[1]=1;f[2]=1;for(LL i=1;i<=n;i++){p[i]=take(a[i-1]);c[i]=take(b[i-1]);}dfs(2);return 0; }

至于提高組的題解，歡迎大家訪問http://www.cnblogs.com/xiao-ju-ruo-xjr/?

轉載于:https://www.cnblogs.com/OYJason/p/7608106.html

總結

以上是生活随笔為你收集整理的HDnoip2017题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。