莫尼塞墊底祭。逗宁。兩個號大兇果然沒有好事情
紹興一中NOI P模擬賽小小小小題解
1.脫離地牢
Description
在一個神秘的國度里，年輕的王子Paris與美麗的公主Helen在一起過著幸福的生活。他們都隨身帶有一塊帶磁性的陰陽魔法石魁兼，身居地獄的魔王Satan早就想著得到這兩塊石頭了何恶，只要把它們?nèi)芑琒atan就能吸收其精華大增自己的魔力哼拔。于是有一天他趁二人不留意引有，把他們帶到了自己的地牢，分別困在了不同的地方倦逐。然后Satan念起了咒語譬正，準備煉獄，界時二人都將葬身于這地牢里檬姥。 危險曾我！Paris與Helen都知道了Satan的意圖，他們要怎樣才能打敗魔王穿铆，脫離地牢呢您单？Paris想起了父王臨終前給他的備忘本，原來他早已料到了Satan的野心荞雏，他告訴Paris只要把兩塊魔法石合在一起虐秦，念出咒語，它們便會放出無限的光榮凤优，殺死魔王悦陋，脫離地牢，而且本子上還附下了地牢的地圖筑辨，Paris從中了解到了Helen的位置所在俺驶。于是他決定首先要找到Helen，但是他發(fā)現(xiàn)這個地牢很奇怪棍辕，它會增強二人魔法石所帶的磁力大小暮现，而且會改變磁力的方向还绘。這就是說，每當Paris向南走一步栖袋，Helen有可能會被石頭吸引向北走一步拍顷。而這個地獄布滿了巖石與熔漿，Paris必須十分小心塘幅，不僅他不能走到巖石或熔漿上昔案，而且由于他行走一步，Helen的位置也會改變电媳，如果Helen碰到巖石上踏揣，那么她將停留在原地，但如果Helen移動到了熔漿上匾乓，那么她將死去捞稿，Paris就找不到她了。 Paris仔細分析了地圖钝尸，他找出了一條最快的行走方案括享，最終與Helen相聚。他們一起念出了咒語“·#￥%^…*&@!”,轟隆一聲珍促，地牢塌陷了铃辖，他們又重見光明…
Input
輸入數(shù)據(jù)第一行為兩個整數(shù)n,m(3<=n,m<=20),表示地牢的大小，n行m列猪叙。接下來n行娇斩，每行m個字符，描述了cf地牢的地圖穴翩，“.”代表通路犬第，“#”代表巖石，“芒帕！”代表熔漿歉嗓，“H”表示Helen,“P”表示Paris。輸入保證地牢是封閉的背蟆，即四周均是巖石或熔漿鉴分。接下來一行有四個字符“N”（北），“S”（南）带膀，“W”（西）志珍，“E”（東）的排列，表示Paris分別向NSWE四個方向走時Helen受磁石磁力影響的移動方向垛叨。
Output
輸出文件只有一行伦糯，如果Paris能找到Helen，輸出一整數(shù)d，為Paris最少需要行走的步數(shù)敛纲；如果Paris在255步之后仍找不到Helen喂击，則輸出“Impossible”。注意相遇是指Paris與Helen最終到達同一個格子载慈，或者二人在相鄰兩格移動后碰到了一起惭等，而后者的步數(shù)算他們移動后的步數(shù)珍手。
Sample Input
5 5
#####
#H..#
#.!.#
#.#P#
#####
WNSE
Sample Output
5
這道題的相遇條件是走到同一個格子或者兩人互換位置办铡。然后就是妥妥的bfs，記得vis數(shù)組去重放在統(tǒng)計答案之后琳要。不然會wa兩個點寡具。
另.蒟蒻還目睹了yyh用dfs水掉了此題。稚补。童叠。然而跑的飛快
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,flag,ans=256,fh[5];
char c[200][200];
int f[21][21][21][21];
int dx[5]={-1,1,0,0};
int dy[5]={0,0,-1,1};
void dfs(int sx,int sy,int tx,int ty,int step)
{
if(f[sx][sy][tx][ty]<=step||step>=256||step>=ans) return;
f[sx][sy][tx][ty]=step;//根據(jù)yyh大佬改進的判重
if((sx==tx&&sy==ty))
{
ans=step;
flag=1;
return;
}
if((sx==tx&&abs(sy-ty)==1)||(abs(sx-tx)==1&&sy==ty)){
for(int i=0;i<4;i++){
if(sx+dx[i]==tx&&sy+dy[i]==ty&&tx+dx[fh[i]]==sx&&ty+dy[fh[i]]==sy){
ans=step+1;
flag=1;
return;
}
}
}
if(ans<=step) return;
// cout<<sx<<" "<<sy<<" "<<tx<<" "<<ty<<endl;
for(int i=0;i<4;i++)
{
int px=sx+dx[i];
int py=sy+dy[i];
int hx=tx+dx[fh[i]];
int hy=ty+dy[fh[i]];
// cout<<px<<" "<<py<<" "<<hx<<" "<<hy<<endl;
if(c[px][py]!='#'&&c[px][py]!='!'&&c[hx][hy]!='!')
{
if(c[hx][hy]=='#') dfs(px,py,tx,ty,step+1);
else dfs(px,py,hx,hy,step+1);
}
}
}
int main()
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
int sx,sy,tx,ty;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",c[i]+1);
for(int j=1;j<=m;j++)
{
if(c[i][j]=='P')sx=i,sy=j,c[i][j]='.';
if(c[i][j]=='H')tx=i,ty=j,c[i][j]='.';
}
}
char ch;
for(int i=0;i<4;i++)
{
cin>>ch;
if(ch=='N') fh[i]=0;
else if(ch=='S') fh[i]=1;
else if(ch=='W') fh[i]=2;
else if(ch=='E') fh[i]=3;
}
memset(f,0x3f3f3f3f,sizeof f);
// for(int i=0;i<4;i++)
// cout<<fh[i]<<" ";puts("");
dfs(sx,sy,tx,ty,0);
if(flag) printf("%d",ans);
else puts("Impossible");
return 0;
}
/*
5 5
#####
#H..#
#.!.#
#.#P#
#####
ENSW
*/
2.Reward
題目描述：
眾所周知，liverpool的主帥貝尼特斯喜歡輪換陣法课幕，是陣法變換的大家厦坛。他的首發(fā)陣容往往讓對方主帥無法捉摸，以至于失去布陣的先機乍惊，其創(chuàng)下的999場首發(fā)陣容不同的紀錄至今無人能望其項背杜秸。其接班人dick充分繼承了他的優(yōu)良傳統(tǒng)，并將其發(fā)揚光大润绎，出現(xiàn)了完全隨機的陣容……
為什么dick可以毫無障礙的把輪換進行到底呢撬碟？其原因在于dick的一個黑箱小程序，他的功用在于給定一個數(shù)n莉撇，可求出約數(shù)總數(shù)為n的最小數(shù)——根據(jù)這個數(shù)字呢蛤，dick再經(jīng)過一系列的數(shù)學(xué)式轉(zhuǎn)換，最終可以獲得11個首發(fā)球員的號碼棍郎。
作為liverpool競爭對手的Manchester Unit其障、Arsenal、Chelsea聯(lián)合起來涂佃，經(jīng)過多年的潛訪調(diào)查考證研究分析證明后終于成功的盜得了dick的輸入數(shù)n的規(guī)律励翼，以及最后轉(zhuǎn)化的數(shù)學(xué)式，眼看成功勝利在望巡李，他們開出巨額賞金懸賞可以解決dick黑箱小程序的人才抚笔，以實現(xiàn)他們打破liverpool不敗神話的愿望。
不管為了巨額獎金還是擊敗liverpool的榮譽侨拦，我想你應(yīng)該會試一試吧殊橙。
輸入數(shù)據(jù)：
輸入僅一個數(shù)n，表示約數(shù)總數(shù)。
輸出數(shù)據(jù)：
輸出僅一個數(shù)膨蛮，表示最小的具有n個約數(shù)的數(shù)叠纹。
輸入樣例：
4
輸出樣例：
6
數(shù)據(jù)規(guī)模：
對于50%的數(shù)據(jù) n<=50
對于100%的數(shù)據(jù) n<=50000
公式：原數(shù)=p1(t1)*p2(t2)p3^(t3)....
約數(shù)個數(shù)=(t1+1)(t2+1)(t3+1)(t4+1)...
45分到手。
然后我們考慮DP
Mst數(shù)組表示用第i個素數(shù)之前有j個因數(shù)敞葛，用后還剩下需要消除的因數(shù)個數(shù)
f數(shù)組表示第i個素數(shù)用后使得剩下j個因數(shù)所需的答案log10之后的數(shù)
關(guān)于為什么要log10：因為約數(shù)定理是乘法誉察，而乘法會比較麻煩，所以轉(zhuǎn)成位數(shù)后用加法實現(xiàn)惹谐，這也是為什么lg和from數(shù)組要用double的原因
#include<bits/stdc++.h>
#define maxn 50010
#define int long long
#define mo 1000000000
using namespace std;
int zhi[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53},n,mst[20][maxn];
double lg[20],f[20][maxn];
struct bignum
{
int a[2300];
bignum(int i=0)
{
memset(a,0,sizeof a);
if(!i) return;
a[0]=1;
a[1]=i;
}
friend bignum operator *(bignum x,bignum y)
{
bignum z;
for(int i=1;i<=x.a[0];i++)
{
int p=0;
for(int j=1;j<=y.a[0];j++)
{
p+=x.a[i]*y.a[j]+z.a[i+j-1];
z.a[i+j-1]=p%mo;
p/=mo;
}
z.a[i+y.a[0]]=p;
}
z.a[0]=x.a[0]+y.a[0];
while(z.a[0]&&!z.a[z.a[0]])
z.a[0]--;
return z;
}
void print()
{
printf("%lld",a[a[0]]);
for(int i=a[0]-1;i>0;i--)
printf("%09lld",a[i]);
puts("");
}
};//高精
bignum power(int x,int y)
{
bignum s=bignum(1),p=bignum(x);
if(y==0) return s;
for(;y;y/=2,p=p*p)
if(y&1) s=s*p;
return s;
}
void work(int i,int j,int k)
{
if(f[i][k]<=f[i-1][j]+(j/k-1)*lg[i]) return;
mst[i][k]=j;
// wrs(mst[i][k]);
f[i][k]=f[i-1][j]+(j/k-1)*lg[i];
}
signed main()
{
freopen("reward.in","r",stdin);
freopen("reward.out","w",stdout);
for(int i=1;i<17;i++)
lg[i]=log10(zhi[i]);
// for(int i=1;i<17;i++)
// printf("%lf ",lg[i]);
scanf("%d",&n);
if(n==1)
{
puts("1");
return 0;
}
for(int i=0;i<=16;i++)
for(int j=1;j<=n;j++)
f[i][j]=1e15;
f[0][n]=1;
for(int i=1;i<17;i++)
for(int j=1;j<=n;j++)
{
if(n%j) continue;
int k=1;
for(;k*k<j;k++)
{
// wrs(i);
// wrs(j);
// wln(k);
if(j%k) continue;
work(i,j,k);
work(i,j,j/k);
}
if(k*k==j) work(i,j,k);
}
/*循環(huán)中i表示第i個素數(shù)持偏，j表示未使用第i個素數(shù)前剩下的因數(shù)個數(shù)，k表示使用第i個素數(shù)后剩下的因數(shù)個數(shù)氨肌，即當前使用的實際是j/k-1個*/
int j=1;
bignum ans=bignum(1);
for(int i=16;i;i--)
{
ans=ans*power(zhi[i],mst[i][j]/j-1);
j=mst[i][j];
}
ans.print();
return 0;
}
3.書本整理
【問題描述】
小明的書架上放了許多書鸿秆，為了使書架變得整潔，小明決定整理書架怎囚，他將所有書按高度大小排列卿叽，這樣排了之后雖然整齊了許多，但小明發(fā)現(xiàn)恳守，書本的寬度不同考婴，導(dǎo)致書架看上去還是有些凌亂。小明把這個凌亂值定義為相鄰兩本書的寬度差的絕對值的和催烘。
例如有4本書：
1×2
5×3
2×4
3×l
那么小明將其排列整齊后的順序是：
1×2
2×4
3×l
5x3
凌亂值就是2+3+2=7沥阱。
于是小明決定拿掉其中的k本書，使凌亂值最小颗圣，你能幫他求出這個最小值嗎喳钟？已知每本書的高度都不一樣。
【問題輸入】
第一行兩個數(shù)字n和k在岂，代表書總共有n本奔则，要求從中去掉k本。(l≤n≤100蔽午，1≤k<n)易茬。下面的n行，每行兩個數(shù)字表示一本書的高度和寬度及老，它們均小于200抽莱。
【問題輸出】
一行一個整數(shù)，表示書架的最小凌亂值骄恶。
【樣例輸入】
4 1
1 2
2 4
3 1
5 3
【樣例輸出】
3
【數(shù)據(jù)范圍】
30%的數(shù)據(jù)食铐，n≤20。
100%的數(shù)據(jù)僧鲁，n≤l00．k<n虐呻。
求n本書去掉k本的最小凌亂值象泵。
f[i][j]表示前i本書去除j本書，第i本必須留下所獲得的最小代價
[偽代碼]
for(int kk=0;kk<=min(k,i-2);kk++)
f[i][j]=min(f[i][j],f[i-kk-1][j-kk]+abs(a[i].w-a[i-kk-1].w));
if(j==i-1) f[i][j]=0;
ans=min(f[n-i][k-i])(0<=i<=k)
或者反過來更好理解：求n本書取出 n-k本最小凌亂值斟叼。
f[i][j]表示前i本書取j本書偶惠，第i本必須留下所獲得的最小代價
for(int i=1;i<=n;i++){
f[i][1]=0;
for(int j=2;j<=min(i,n-k);j++)
for(int l=1;l<i;l++)
f[i][j]=min(f[i][j],f[l][j-1]+abs(b[l].w-b[i].w));
}
for(int i=n-k;i<=n;i++)ans=min(ans,f[i][n-k]);
這是我掛掉的dp
for(int i=0;i<=n;i++) f[i][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n-k;j++)
for(int q=1;q<i;q++)
{
f[i][j]=min(f[i-1][j],f[i-1][j-1]+abs(a[q].w-a[i].w));
}
思路和yg的差不多 然后循環(huán)就不知道怎么寫了。朗涩。還去壓了一維忽孽。。
yg//第i位取j個最后一個為k
for(int i=1;i<=n;i++)
for(int j=1;j<=min(i,n-m);j++)
for(int k=j;k<=i;k++){
if(j==1){f[i][j][k]=0;continue;}
for(int p=1;p<k;p++)f[i][j][k]=min(f[i][j][k],f[i-1][j-1][p]+abs(a[k].w-a[p].w));
}
int ans=0x7fffffff;
for(int i=n-m;i<=n;i++)ans=min(ans,f[n][n-m][i]);
4.木棍
有N根木棍谢床，每根的長度L和重量W已知兄一。這些木棍將被一臺機器一根一根地加工。機器需要一些啟動時間來做準備工作萤悴，啟動時間與木棍被加工的具體情況有關(guān)瘾腰。啟動時間遵循以下規(guī)則：
1．加工第一根木棍的啟動時間為1分鐘。
2．加工完長度為Li覆履，重量為Wi的木棍后，緊跟著加工長度為Li+1费薄，重量為
Wi+1的木棍時硝全，若Li<=Li+1且Wi<=Wi+1，則加工木棍I+1時楞抡，不需要啟動時間伟众。例如：有5根木棍，它們的長度和重量為（9,4）召廷，（2,5）凳厢，（1,2，）竞慢，（5,3）先紫，（4,1），則最小總啟動時間為2分鐘（加工序列為（4,1）筹煮，（5,3）遮精，（9,4），（1,2）败潦，（2,5））本冲。
輸入:
第一行一個整數(shù)n(1<=n<=5000)，表示木棍的數(shù)量劫扒。第二行2n個整數(shù)檬洞，l1,w1,l2,w2,…,ln,wn(1<=li,wi<=10000)，為各根木棍的長度和重量沟饥，這2n個整數(shù)以若干個空格分隔添怔。
輸出:
一行: 一個整數(shù)环戈，即最小總啟動時間。
樣例輸入1
5
4 9 5 2 2 1 3 5 1 4
樣例輸出1
2
樣例輸入2
3
2 2 1 1 2 2
樣例輸出2
1
貪心澎灸。按長度排序院塞，按寬度求lis，標記性昭，繼續(xù)求lis拦止，直到全部標記完畢。做過的題目思路有影響然而寫掛了糜颠？汹族！以后還是要好好總結(jié)
既然寫了那么多遍代碼就不給了
