莫尼塞垫底祭。。两个号大凶果然没有好事情
绍兴一中NOI P模拟赛小小小小题解
1.脱离地牢
Description
在一个神秘的国度里，年轻的王子Paris与美丽的公主Helen在一起过着幸福的生活。他们都随身带有一块带磁性的阴阳魔法石，身居地狱的魔王Satan早就想着得到这两块石头了，只要把它们溶化，Satan就能吸收其精华大增自己的魔力。于是有一天他趁二人不留意，把他们带到了自己的地牢，分别困在了不同的地方。然后Satan念起了咒语，准备炼狱，界时二人都将葬身于这地牢里。 危险！Paris与Helen都知道了Satan的意图，他们要怎样才能打败魔王，脱离地牢呢？Paris想起了父王临终前给他的备忘本，原来他早已料到了Satan的野心，他告诉Paris只要把两块魔法石合在一起，念出咒语，它们便会放出无限的光荣，杀死魔王，脱离地牢，而且本子上还附下了地牢的地图，Paris从中了解到了Helen的位置所在。于是他决定首先要找到Helen，但是他发现这个地牢很奇怪，它会增强二人魔法石所带的磁力大小，而且会改变磁力的方向。这就是说，每当Paris向南走一步，Helen有可能会被石头吸引向北走一步。而这个地狱布满了岩石与熔浆，Paris必须十分小心，不仅他不能走到岩石或熔浆上，而且由于他行走一步，Helen的位置也会改变，如果Helen碰到岩石上，那么她将停留在原地，但如果Helen移动到了熔浆上，那么她将死去，Paris就找不到她了。 Paris仔细分析了地图，他找出了一条最快的行走方案，最终与Helen相聚。他们一起念出了咒语“·#￥%^…*&@!”,轰隆一声，地牢塌陷了，他们又重见光明…
Input
输入数据第一行为两个整数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，输出一整数d，为Paris最少需要行走的步数；如果Paris在255步之后仍找不到Helen，则输出“Impossible”。注意相遇是指Paris与Helen最终到达同一个格子，或者二人在相邻两格移动后碰到了一起，而后者的步数算他们移动后的步数。
Sample Input
5 5
#####
#H..#
#.!.#
#.#P#
#####
WNSE
Sample Output
5
这道题的相遇条件是走到同一个格子或者两人互换位置。然后就是妥妥的bfs，记得vis数组去重放在统计答案之后。不然会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;//根据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的主帅贝尼特斯喜欢轮换阵法，是阵法变换的大家。他的首发阵容往往让对方主帅无法捉摸，以至于失去布阵的先机，其创下的999场首发阵容不同的纪录至今无人能望其项背。其接班人dick充分继承了他的优良传统，并将其发扬光大，出现了完全随机的阵容……
为什么dick可以毫无障碍的把轮换进行到底呢？其原因在于dick的一个黑箱小程序，他的功用在于给定一个数n，可求出约数总数为n的最小数——根据这个数字，dick再经过一系列的数学式转换，最终可以获得11个首发球员的号码。
作为liverpool竞争对手的Manchester Unit、Arsenal、Chelsea联合起来，经过多年的潜访调查考证研究分析证明后终于成功的盗得了dick的输入数n的规律，以及最后转化的数学式，眼看成功胜利在望，他们开出巨额赏金悬赏可以解决dick黑箱小程序的人才，以实现他们打破liverpool不败神话的愿望。
不管为了巨额奖金还是击败liverpool的荣誉，我想你应该会试一试吧。
输入数据：
输入仅一个数n，表示约数总数。
输出数据：
输出仅一个数，表示最小的具有n个约数的数。
输入样例：
4
输出样例：
6
数据规模：
对于50%的数据 n<=50
对于100%的数据 n<=50000
公式：原数=p1(t1)*p2(t2)p3^(t3)....
约数个数=(t1+1)(t2+1)(t3+1)(t4+1)...
45分到手。
然后我们考虑DP
Mst数组表示用第i个素数之前有j个因数，用后还剩下需要消除的因数个数
f数组表示第i个素数用后使得剩下j个因数所需的答案log10之后的数
关于为什么要log10：因为约数定理是乘法，而乘法会比较麻烦，所以转成位数后用加法实现，这也是为什么lg和from数组要用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);
}
/*循环中i表示第i个素数，j表示未使用第i个素数前剩下的因数个数，k表示使用第i个素数后剩下的因数个数，即当前使用的实际是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.书本整理
【问题描述】
小明的书架上放了许多书，为了使书架变得整洁，小明决定整理书架，他将所有书按高度大小排列，这样排了之后虽然整齐了许多，但小明发现，书本的宽度不同，导致书架看上去还是有些凌乱。小明把这个凌乱值定义为相邻两本书的宽度差的绝对值的和。
例如有4本书：
1×2
5×3
2×4
3×l
那么小明将其排列整齐后的顺序是：
1×2
2×4
3×l
5x3
凌乱值就是2+3+2=7。
于是小明决定拿掉其中的k本书，使凌乱值最小，你能帮他求出这个最小值吗？已知每本书的高度都不一样。
【问题输入】
第一行两个数字n和k，代表书总共有n本，要求从中去掉k本。(l≤n≤100，1≤k<n)。下面的n行，每行两个数字表示一本书的高度和宽度，它们均小于200。
【问题输出】
一行一个整数，表示书架的最小凌乱值。
【样例输入】
4 1
1 2
2 4
3 1
5 3
【样例输出】
3
【数据范围】
30%的数据，n≤20。
100%的数据，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的差不多 然后循环就不知道怎么写了。。还去压了一维。。
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已知。这些木棍将被一台机器一根一根地加工。机器需要一些启动时间来做准备工作，启动时间与木棍被加工的具体情况有关。启动时间遵循以下规则：
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））。
输入:
第一行一个整数n(1<=n<=5000)，表示木棍的数量。第二行2n个整数，l1,w1,l2,w2,…,ln,wn(1<=li,wi<=10000)，为各根木棍的长度和重量，这2n个整数以若干个空格分隔。
输出:
一行: 一个整数，即最小总启动时间。
样例输入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，标记，继续求lis，直到全部标记完毕。做过的题目思路有影响然而写挂了？！以后还是要好好总结
既然写了那么多遍代码就不给了
网友评论