前言

……終于改完了，像之前小L一樣崩潰。今天C組和B組一起做題，所以……

---

正題

---

題目1：教主的花園（jzoj1792）

一平面直角坐標(biāo)系，在x軸的位置建立一堵墻，墻上有n道門(mén)，給出門(mén)的位置，詢(xún)問(wèn)兩個(gè)坐標(biāo)的距離（曼哈頓）。

輸入輸出（建議無(wú)視）

Input

輸入的第1行為一個(gè)正整數(shù)N，為屏障上入口的個(gè)數(shù)。
第2行有N個(gè)整數(shù)，a1, a2, …, aN，之間用空格隔開(kāi)，為這N個(gè)入口的橫坐標(biāo)。
第3行為一個(gè)正整數(shù)M，表示了M個(gè)詢(xún)問(wèn)。
接下來(lái)M行，每行4個(gè)整數(shù)x1, y1, x2, y2，有y1與y2均不等于0，表示了一個(gè)詢(xún)問(wèn)從(x1, y1)到(x2, y2)的最短路。

Output

輸出共包含m行，第i行對(duì)于第i個(gè)詢(xún)問(wèn)輸出從(x1, y1)到(x2, y2)的最短路距離是多少。

Sample Input

2
2 -1
2
0 1 0 -1
1 1 2 2

Sample Output

4
2

解題思路

有三種情況
1. 坐標(biāo)之間不隔墻
2. 坐標(biāo)之間隔墻，并且最近的墻在兩個(gè)坐標(biāo)之間：

3. 坐標(biāo)之間隔墻，并且最近的墻在兩個(gè)坐標(biāo)之間

然后前兩種情況之接輸出曼哈頓距離，第三種情況輸出兩個(gè)距離門(mén)的距離和。
用二分確定最近的門(mén)

代碼

#include<cstdio> #include<algorithm> using namespace std; int n,a[100001],m,x,y,zx,zy,l,r,mid,last; bool ok; int abs(int x) {if (x<0) return 0-x;else return x; } int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);//排序scanf("%d",&m);for (int i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&zx,&zy);//輸如if (y<0 && zy>0 || y>0 && zy<0)//如果中間隔墻{l=1;r=n;last=2147483647;//last記錄離門(mén)最近距離ok=true;while (l<=r){mid=(int)(l+r)/2;if (zx>a[mid] && x<a[mid] || zx<a[mid] && x>a[mid])//如果門(mén)在中心{l=mid;last=0;break;//退出}if (min(abs(a[mid]-x),abs(a[mid]-zx))*2<last)//如果找到更近的距離{last=min(abs(a[mid]-x),abs(a[mid]-zx))*2;//記錄if (a[mid]<x) l=mid;else r=mid;}elseif (a[mid]<x) l=mid+1;else r=mid-1;}printf("%d\n",last+abs(x-zx)+abs(zy-y));//輸出}else printf("%d\n",abs(zx-x)+abs(zy-y));//輸出} }

---

題目2：教主泡嫦娥（jozj1793）

有一個(gè)環(huán)形山地，有n個(gè)落腳點(diǎn)，可以從任意落腳點(diǎn)任意狀態(tài)出發(fā)。每個(gè)落腳點(diǎn)的代價(jià)為

當(dāng)教主從第i個(gè)落腳點(diǎn)，走到第j個(gè)落腳點(diǎn)的時(shí)候（i和j相鄰）
j的海拔高于i的海拔：如果教主處于上升狀態(tài)，教主需要耗費(fèi)兩段高度差的絕對(duì)值的體力；否則耗費(fèi)高度差平方的體力。
j的海拔低于i的海拔：如果教主處于下降狀態(tài)，教主需要耗費(fèi)兩段高度差的絕對(duì)值的體力；否則耗費(fèi)高度差平方的體力。

求走一圈的最小代價(jià)

輸入輸出（建議無(wú)視）

Input

輸入的第一行為兩個(gè)正整數(shù)N與M，即落腳點(diǎn)的個(gè)數(shù)與切換狀態(tài)所消耗的體力。
接下來(lái)一行包含空格隔開(kāi)的N個(gè)正整數(shù)，表示了每個(gè)落腳點(diǎn)的高度，題目保證了相鄰落腳點(diǎn)高度不相同。

Output

輸出僅包含一個(gè)正整數(shù)，即教主走一圈所需消耗的最小體力值。
注意：C++選手建議使用cout輸出long long類(lèi)型整數(shù)。

Sample Input

6 7
4 2 6 2 5 6

Sample Output

27

解題思路

如果枚舉落腳點(diǎn)肯定會(huì)超時(shí)，所以我們就不能這么做。
用f[i][j][k]表示在第i個(gè)落腳點(diǎn)，狀態(tài)為j，在當(dāng)前有沒(méi)有改變狀態(tài)。
然后O(n)的時(shí)間復(fù)雜度輕易過(guò)
動(dòng)態(tài)轉(zhuǎn)移方程：
f[i][j][0]=f[i-1][j][0]+abs(a[i]-a[i-1]) 直接走過(guò)
f[i][j][1]=min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])+m)+abs(a[i]-a[i-1]) 改變狀態(tài)

f[i][j][0]=f[i-1][j][0]+pows(a[i]-a[i-1])
f[i][j][1]=min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])+m)+pows(a[i]-a[i-1])
在這題被逼瘋，默默AC不想說(shuō)話

代碼

#include<cstdio> #include<cstring> #include<iostream> using namespace std; long long f[10001][2][2],ans; int a[10001],n,m; long long abs(long long x) {if (x<0) return 0-x;else return x; } long long pows(long long x) {return x*x;} void dp() {f[0][1][1]=f[0][0][1]=1e16-1;for (int i=1;i<=n;i++)for (int j=0;j<2;j++)if ((a[i]<a[i-1])^j){f[i][j][0]=f[i-1][j][0]+abs(a[i]-a[i-1]);f[i][j][1]=min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])+m)+abs(a[i]-a[i-1]);}else{f[i][j][0]=f[i-1][j][0]+pows(a[i]-a[i-1]);f[i][j][1]=min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])+m)+pows(a[i]-a[i-1]);}//動(dòng)態(tài)轉(zhuǎn)移 } int main() {scanf("%d%d",&n,&m);for (int i=0;i<n;i++){scanf("%d",&a[i]);}a[n]=a[0];memset(f,0ll,sizeof(f));dp();//dp一次ans=min(min(f[n][0][0],f[n][0][1]),min(f[n][1][0],f[n][1][1]));//取最小情況memset(f,0ll,sizeof(f));f[0][0][0]=1e16-1;//從f[0][1][0]推過(guò)去dp();//dp一次ans=min(ans,f[n][1][1]-m);//取值memset(f,0ll,sizeof(f));f[0][1][0]=1e16-1;//從f[0][0][0]推過(guò)去dp();//dp一次ans=min(ans,f[n][0][1]-m);//取值cout<<ans<<endl; }

---

題目3：保鏢排隊(duì)（jzoj1794）

有n個(gè)保鏢，除第一個(gè)保鏢外每個(gè)保鏢都有一個(gè)上司，每個(gè)上司的下屬都有在上司心目中的武力值。排隊(duì)要求：

①互為上司-下屬的兩個(gè)保鏢，上司在前，下屬在后
②對(duì)于一個(gè)保鏢的所有下屬，武功實(shí)力較強(qiáng)的在前，較弱的在后。

求排隊(duì)方案數(shù)

輸入輸出（建議無(wú)視）

Input

輸入的第一行為一個(gè)正整數(shù)T，表示了數(shù)據(jù)組數(shù)。
對(duì)于每組數(shù)據(jù)：
第一行為一個(gè)正整數(shù)N。
接下來(lái)N行，每行描述一個(gè)保鏢。
第i+1行，會(huì)有一個(gè)整數(shù)K，代表第i個(gè)保鏢的下屬個(gè)數(shù)，接下來(lái)K個(gè)數(shù)，代表第i個(gè)保鏢的下屬按照武功實(shí)力從高到低的編號(hào)。

Output

輸出包括C行，每行對(duì)于每組數(shù)據(jù)輸出方案數(shù)mod 10007后的結(jié)果。

Sample Input

2
5
2 2 3
2 4 5
0
0
0
7
2 2 3
2 4 5
2 6 7
0
0
0
0

Sample Output

3
10

解題思路

首先想到的是樹(shù)形dp，由于保鏢一沒(méi)有上司所以一定是根。然后就是插空問(wèn)題了，將3個(gè)保鏢插入到3個(gè)空中，用組合的方法求插空方案數(shù)。用楊輝三角求組合。然后樹(shù)形dp

代碼

#include<cstdio> #include<cstring> using namespace std; struct line{int y,next; }a[10001];//鄰接表 int f[1001],s,ls[1001],n,k,t,w,head,num[1001]; int cost[1002][1002]; void dp(int x) {int q=ls[x];f[x]=1;if (q==0){num[x]=1;return;//沒(méi)有子樹(shù)}while (q!=0){dp(a[q].y);num[x]+=num[a[q].y];//累計(jì)f[x]=((f[x]*f[a[q].y])%10007)*(cost[num[x]-1][num[a[q].y]-1])%10007;//求方案數(shù)q=a[q].next;}num[x]++;//算上自己 } int main() {cost[0][0]=1;for (int i=1;i<=1001;i++)for (int j=1;j<=i;j++){cost[i][0]=1;cost[i][j]=(cost[i-1][j]+cost[i-1][j-1])%10007;}//楊輝三角scanf("%d",&t);for (int ti=1;ti<=t;ti++){w=0;s=0;memset(ls,0,sizeof(ls));memset(f,0,sizeof(f));memset(num,0,sizeof(num));//初始化scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d",&a[++w].y);a[w].next=ls[i];ls[i]=w;}}dp(1);//dpprintf("%d\n",f[1]);} }

---

題目4：教主的別墅（jzoj1795）

有N個(gè)人，有男有女，分成m段連續(xù)的部分，求分割的最小和最大字典序。

輸入輸出（建議無(wú)視）

Input

　　輸入的第1行為兩個(gè)正整數(shù)N與M，用空格分隔。
　　第2行包含一個(gè)長(zhǎng)度為N的串，僅由字符組成，第i 個(gè)字符為0表示在這個(gè)位置上的LHXee為女生，若為1則為男生。

Output

　　輸出文件包含兩行，每行M個(gè)正整數(shù)，正整數(shù)之間用空格隔開(kāi)，行末無(wú)多余空格。這M個(gè)正整數(shù)從左到右描述了你所分的每個(gè)組的人數(shù)。
　　第1行為字典序最小的方案，第2行為字典序最大的方案。

Sample Input

8 3
11001100

Sample Output

1 2 5
5 2 1

解題思路

這道題貪心竟然能過(guò)？？？

深搜TLE，貪心只能過(guò)樣例

聽(tīng)某dalao講用前綴和到第i個(gè)房間的男女差值（絕對(duì)值），然后每個(gè)房間最大差值為：

summsumm
然后正推一次反推一次。

#include<cstdio> #include<iostream> using namespace std; int n,m,sum[5000002],ans,anss,t,last,w,a[100002]; char c; int abs(int x) {if (x<0) return 0-x;else return x; }//絕對(duì)值 int main() {scanf("%d%d\n",&n,&m);for (int i=1;i<=n;i++){cin>>c;if (c=='0') sum[i]-=1;else sum[i]+=1;sum[i]+=sum[i-1];}ans=abs(sum[n])/m;//求最大差值if (abs(sum[n])%m!=0) ans++;//向上取整if (sum[n]==0){int l=0;for (int i=1;i<=n;i++)if (sum[i]==0) l++;if (l>=m) ans=0;else ans=1;//能否做到?jīng)]有差值}t=m;last=0;for (int i=1;i<=n;i++){anss=abs(sum[n]-sum[i])/(t-1);if (abs(sum[n]-sum[i])%(t-1)!=0) anss++;if (abs(sum[i]-sum[last])<=ans && anss<=ans){printf("%d ",i-last);last=i;t--;if (t==1) break;}}//查找printf("%d\n",n-last);ans=abs(sum[n])/m;if (abs(sum[n])%m!=0) ans++;if (sum[n]==0){int l=0;for (int i=1;i<=n;i++)if (sum[i]==0) l++;if (l>=m) ans=0;else ans=1;}t=m;last=n;w=0;for (int i=n-1;i>=1;i--){anss=abs(sum[i])/(t-1);if (abs(sum[i])%(t-1)!=0) anss++;if (abs(sum[last]-sum[i])<=ans && anss<=ans){a[++w]=last-i;last=i;t--;if (t==1) break;}}//倒著查找a[++w]=last;//記錄for (int i=w;i>=1;i--) printf("%d ",a[i]); }

總結(jié)

以上是生活随笔為你收集整理的【jzoj】2018.2.7NOIP普及组——某【BC】组模拟赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。