2018.12.22【NOIP提高组】模拟B组

本文主要是介绍2018.12.22【NOIP提高组】模拟B组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

JZOJ 2700 数字

题目

$$设S(n)为各位数字之和，且当n>9时,S(n)=S(S(n))$$
如果一个数$x$合法当且仅当$x=y\times S(y)$
问在$[L\dots R]$中合法的数

---

分析

First of all,S(n)=(n-1) mod 9+1
这个答案可以用前缀和的方式运用$[1\dots R]-[1\dots L-1]$表达
那么S(n)只能是$1\sim 9$的范围内，所以说可以枚举$S(n)$，就可以得到对于$i$,答案为$\lfloor \frac{n-i\times i}{9\times i}\rfloor +1$,那问题是重复呢,根据一系列的打表发现，和$i$重复的只有$9-i$，所以说根据dalao给出来的answer可以知道每$gcd(i,9-i)$个会重复一次，所以说代码如下

---

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long ll;
inline ll iut(){rr ll ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void print(ll ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
signed main(){for (rr int t=iut();t;--t){rr ll l=iut(),r=iut(),sum=0;for (rr int p=1;p<10;++p)if (r>=p*p){rr ll ans=(r-p*p)/(9*p)+1;sum+=ans;if (p<5&&(9-p)*(9-p)<=r)sum-=ans/(p==3?2:9-p);}else break;for (rr int p=1;p<10;++p)if (l>p*p){rr ll ans=(l-1-p*p)/(9*p)+1;sum-=ans;if (p<5&&(9-p)*(9-p)<l)sum+=ans/(p==3?2:9-p);}else break;print(sum); putchar(10);}return 0;
}

---

JZOJ 3511 cza的蛋糕

题目

用最少的$1\times 2$或$2\times 1$的长方形填充$n\times m$的矩阵，且不存在任意位置可填充(不可重叠)

---

分析

由于$m$比较小，所以说可以使用状态压缩，设$dp[i][j][k]$表示第$i$行状态为$j$下一行状态为$k$的最小值，那么$dp[i][j][k]=min(dp[i-1][y][z]+cnt)（从第一行转移）$
时间复杂度应该是$O(n^2{2}^{2\times m})$

---

代码

#include <cstdio>
#include <cstring>
#define rr register
using namespace std;
struct rec{bool flag; int last,curr;}now;
int dp[2][131][131],a[72],n,m,ans=707406378;
inline void min(int &a,int b){if (a>b) a=b;}
inline void dfs(int dep,int noww,int nexx,int cnt){if (dep&&!(now.last&(1<<dep-1))&&!(noww&(1<<dep-1))) return;//如果还能两行之间填if (dep>1&&!(noww&(1<<dep-1))&&!(noww&(1<<dep-2))) return;//如果同一行之间还能填if (dep==m){min(dp[now.flag][noww][nexx],dp[now.flag^1][now.last][now.curr]+cnt);return;} dfs(dep+1,noww,nexx,cnt);if (!(noww&(1<<dep))&&!(nexx&(1<<dep)))dfs(dep+1,noww|(1<<dep),nexx|(1<<dep),cnt+1);//填两行之间的同一列if (!(noww&(1<<dep))&&!(noww&(1<<dep+1))&&dep<m-1)dfs(dep+2,noww|(1<<dep)|(1<<dep+1),nexx,cnt+1);//填同一行
}
signed main(){freopen("cake.in","r",stdin);freopen("cake.out","w",stdout);scanf("%d%d",&n,&m);for (rr int i=1;i<=n;++i){rr char c=getchar();while (c!='.'&&c!='*') c=getchar();a[i]=(c=='*');for (rr int j=1;j<m;++j)a[i]|=((c=getchar())=='*')<<j;}memset(dp[0],127/3,sizeof(dp[0]));dp[0][(1<<m)-1][a[1]]=0;for (rr int i=1;i<=n;++i){memset(dp[i&1],127/3,sizeof(dp[i&1]));for (rr int j=0;j<(1<<m);++j)for (rr int k=0;k<(1<<m);++k)if (dp[i&1^1][j][k]!=707406378)now=(rec){i&1,j,k},dfs(0,k,a[i+1],0);}for (rr int i=0;i<(1<<m);++i) min(ans,dp[n&1][i][0]);return !printf("%d",ans);
}

---

JZOJ 3519 灵能矩阵

题目

在一棵根是1的树上减少一些点权（最多减到0），问最少共减少多少点权能使所有父节点的子节点相等

---

分析

那么最多留下的就是子节点的最小值乘子节点个数，但是这样还是有风险的，因为这样儿子的儿子可能无法得到平均的值，所以这个x必须是所有儿子x的lcm的倍数，这样保证最小而且合法，所以说$ans=sum(原来的节点权值和)-min\times son-min\times son$ mod l c m { s o n ( x ) } lcm\{son(x)\} lcm{son(x)}

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
typedef long long ll; ll ans;
struct node{int y,next;}e[100001];
int n,a[100001],ls[100001];
inline ll iut(){rr ll ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c-48),c=getchar();return ans;
}
inline ll gcd(ll a,ll b){//根据实时研究，递归gcd比非递归gcd要慢rr ll r=a%b;while (r){a=b;b=r;r=a%b;}return b;
}
inline pair<ll,ll> dp(int x){rr ll lcmm=1,minx=1e18,sum=0,t; rr int son=0;if (a[x]) return make_pair(a[x],lcmm);for (rr int i=ls[x];i;i=e[i].next){rr pair<ll,ll>tt=dp(e[i].y);lcmm*=tt.second/gcd(lcmm,tt.second);minx=minx<tt.first?minx:tt.first;sum+=tt.first; ++son;}lcmm*=son; t=minx*son-minx*son%lcmm;ans+=sum-t; return make_pair(t,lcmm);
}
signed main(){freopen("pylon.in","r",stdin);freopen("pylon.out","w",stdout);n=iut();for (rr int i=1;i<=n;++i) a[i]=iut();for (rr int i=1;i<n;++i){rr int x=iut(),y=iut();e[i+1]=(node){y,ls[x]}; ls[x]=i+1;}dp(1);printf("%lld",ans);return 0;
}

---

后续

再接再厉

这篇关于2018.12.22【NOIP提高组】模拟B组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---