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