NOIP 2001 提高组 题解
No 1. 一元三次方程求解
看见有人认真推导了求解公式，然后猥琐暴力过的同学们在一边偷笑~~~
数据小 暴力枚举即可
double a,b,c,d;
double x;
int main()
{
ios_base::sync_with_stdio();
cin>>a>>b>>c>>d;
;i<=;i+=)
{
x=i/;
if(abs(a*x*x*x+b*x*x+c*x+d)<0.01)
{
printf("%.2f ",x);
}
}
;
}
No 2. 数的划分
dp/dfs
dp
用f(i,j)表示i这个数分成k份有多少种分法
毫无疑问
f[i][j]=f[i-][j-]+f[i-j][j];
因为 f(i,j) 可以从 f(i-1,j-1)推出 又要保持不下降的分划 所以可以从f(i-j,j)推出
int n,k;
][];
void init()
{
cin>>n>>k;
;i<=n;i++)
{
;j<=i;j++)
{
f[i][j]=inf;
}
}
;i<=n;i++)
{
f[i][]=;
}
}
int main()
{
init();
;i<=n;i++)
{
;j<=i;j++)
{
f[i][j]=f[i-][j-]+f[i-j][j];
}
}
cout<<f[n][k]<<endl;
;
}
dfs
暴力枚举
只要不下降+剪枝就可以了
int n,k;
int ans;
void dfs(int nw,int sum,int num)
{
if(num==k)
{
if(sum==n)
{
ans++;
}
else
{
return;
}
}
if(sum==n)
{
return;
}
for(int i=nw;i<=n-sum;i++)
{
dfs(i,sum+i,num+);
}
return;
}
int main()
{
ios_base::sync_with_stdio();
cin>>n>>k;
;i<=n/;i++)
{
dfs(i,i,);
}
cout<<ans<<endl;
;
}
No 3. 统计单词个数
dp
这几年dp考的好多啊
这题题解我真的不会写 我的写法我自己都看不懂
复制一段
划分这个DP，很基础。
然后，是sum[i][j],第i个字母到第j个字母一共可以形成多少个单词，ccy也用的Dp。
sum[i][j]=sum[i][-1]+（包含可以添加最后一个字母j的单词的总个数）。
ccy，WA在……比如现在可以添加一个新单词，k到j，但是，若果以k为起点，在sum[i][j-1]中已经有过单词，该新单词就不添加。于是乎，ccy光荣地WA掉一个点，因为，
那个点有两个相同的单词，我就扩展了两次。
string s;
int slen;
string words[maxm];
int wordslen[maxm];
int f[maxn][maxm];
int sum[maxn][maxn];
int n,k,m;
void init()
{
string tmp;
cin>>n>>k;
;i<=n;i++)
{
cin>>tmp;
s+=tmp;
}
slen=s.size();
cin>>m;
;i<=m;i++)
{
cin>>words[i];
wordslen[i]=words[i].size();
}
}
int add(int l,int r)
{
;
>=) ans=sum[l][r-];
};
;i<=m;i++)
{
;
if (qd<l) continue;
if (qd==s.find(words[i],qd))
{
if (vis[qd]) continue;
vis[qd]=;
ans++;
;j<=m;j++)
{
int dq=r-wordslen[j];
if (dq==qd)
if (dq==s.find(words[j],dq))
{
ans--;
break;
}
}
}
}
return ans;
}
void gsum()
{
;i<=slen-;i++)
;j++)
{
sum[i][j]=add(i,j);
}
}
void work()
{
;i<=slen-;i++)
f[i][]=sum[][i];
;i<=slen-;i++)
;j<=min(k-,i+);j++)
;u<=i-;u++)
f[i][j]=max(f[i][j],f[u][j-]+sum[u+][i]);
;
)
ans=sum[][slen-];
else
;i<=slen-;i++)
ans=max(ans,f[i][k-]+sum[i+][slen-]);
printf("%d\n",ans);
}
int main()
{
int qn;
qn=;
while(qn--)
{
init();
gsum();
work();
}
;
}
No 4. Car的旅行路线
简单的Dijkstra就可以过了
直接贴代码
struct sb
{
int x,y,c;
} pos[];
];
];
],y[],costt[];
double dis(int x,int y)
{
double k;
k=sqrt(pow(pos[x].x-pos[y].x,)+pow(pos[x].y-pos[y].y,));
if(pos[x].c==pos[y].c)
k*=costt[pos[x].c];
else
k*=costf;
return k;
}
double dij(int st)
{
double min,k;
int i,j,p;
memset(b,,sizeof(b));
memset(d,,sizeof(d));
d[st]=;
; i<=tot; i++)
{
min=1e38;
; j<=tot; j++)
if(!b[j]&&d[j]<min)
{
min=d[j];
p=j;
}
b[p]=;
; j<=tot; j++)
if(!b[j])
d[j]=d[j]>d[p]+dis(p,j)?d[p]+dis(p,j):d[j];
}
k=1e38;
; i<=tot; i++)
{
if(pos[i].c==ed)
; j<=; j++)
k=d[i+j]<k?d[i+j]:k;
if(pos[i].c==ed)
break;
}
return k;
}
main()
{
cin>>tc;
double min=1e38;
int i,j,k;
while(tc)
{
cin>>n>>costf>>st>>ed;
; i<=n; i++)
{
cin>>x[]>>y[]>>x[]>>y[]>>x[]>>y[]>>costt[i];
; j<=; j++)
; k<=; k++)
-k-j]-x[j])+(y[j]-y[k])*(y[-k-j]-y[j])==)
{
x[]=x[k]+x[-k-j]-x[j];
y[]=y[k]+y[-k-j]-y[j];
}
; j<=; j++)
{
pos[++tot].x=x[j];
pos[tot].y=y[j];
pos[tot].c=i;
}
}
; i<=tot; i++)
{
if(pos[i].c==st)
; j<=; j++)
min=dij(i+j)<min?dij(i+j):min;
if(pos[i].c==st)
break;
}
printf("%.1lf",min);
tc--;
}
;
}
The End