Preface
NOIP前突然不知道做什么,感觉思维有点江僵化,就在vjudge上随便组了6道ABC D+CF Div2 C/D做,发现比赛质量还不错,知识点涉及广,难度有梯度,码量稍小,思维较多. 同时发现vjudge的比赛功能很不错
A. ABC112-D-Partition
难度感觉比NOIP T1简单了些了
首先naiive的想法是枚举这个公约数\(D\),但是发现有\(D*N<=M\)这个约束,算了算发现\(M/N <=1e4\)
于是开心从大到小枚举就好了
太水了
int n,m;int main(){ read(n),read(m); for(ri i=m/n;i>=1;i--){ if(m%i==0){printf("%d\n",i);break;} } return 0;} B. ABC110-D-Factorization
应该有NOIP T1难度
我先考虑如果这个M是一个质数,那么就有N种可能,稍稍推广一下,如果\(M = P^c\),那么就相当于你有\(N\)个不同的盒子,然后盒子内可以不装东西,求放\(c\)个物品的方案数
这个就是隔板法的经典模型
如果您不知道是什么就看这篇洛谷日报吧:
于是对于\(M= \prod pi^{ci}\),由于每个\(pi\)是独立的,直接乘法原理相乘就好了
一开始用线性推逆元,不知道怎么回事一直最后一个点WA,最后改成阶乘版本就过了...
int n,m;int c[maxn],tot=0;ll fac[maxn],inv_fac[maxn];ll C(int n,int m){ return fac[m]*inv_fac[n]%P*inv_fac[m-n]%P;}ll ksm(ll a){ ll ans=1; ll c=P-2; while(c){ if(c&1)ans=ans*a%P; a=a*a%P; c=c>>1; } return ans%P;}int main(){ int x,y,M; read(n),read(m); M=m; for(ri i=2;i*i<=M;i++){ if(M%i==0){ c[++tot]=1; M/=i; while(M%i==0){M/=i;c[tot]++;} } } if(M>1)c[++tot]=1; fac[0]=fac[1]=1; for(ri i=2;i<=size;i++) fac[i]=fac[i-1]*i%P; inv_fac[size]=ksm(fac[size]); for(ri i=size-1;i>=0;i--) inv_fac[i]=inv_fac[i+1]*1ll*(i+1)%P; ll ans=1; for(ri i=1;i<=tot;i++){ ans=ans*C(n-1,n+c[i]-1)%P; } printf("%lld\n",ans); return 0;} C. ABC106-D-AtcoderExpress2
个人认为应该有NOIPT2难度了(天天爱跑步算了)
第一眼一看裸题啊!求一段区间内有多少个被完全包含的区间.冷静分析之后发现并不会做
从数据结构想到容斥还是毫无思路
然后下午睡了一觉之后一下子就想出个一看就不是正解的方法:我会二维数点!
我们对于询问/给出的区间都用\((l,r)\)表示,那么你看这个这个东西,它是不是像炉石补偿一个平面直角坐标系上的一个点
同时发现询问区间\((l,r)\),实际上就是询问有多少个点\((l_i,r_i)\)满足\(l_i>=l,r_i<=r\)
画一个图发现它其实就是求一个矩形内有多少个点,我们按照二维数点套路搞一波就好了
关于二维数点:
这里注意排序时的cmp就好了,代码同样短的可怕
int sum[maxn<<3];int n,m,q;inline void add(int x,int d){for(;x<=n;x+=x&(-x))sum[x]+=d;return ;}inline int query(int x){int ans=0;for(;x;x-=x&(-x))ans+=sum[x];return ans;}struct Pt{ int x,y,id; bool operator <(const Pt &rhs)const{ return (x==rhs.x)?(y==rhs.y?id rhs.x;//注意cmp }}pt[maxn<<2];int tot=0,qry[maxn];int main(){ int x,y; read(n),read(m),read(q); for(ri i=1;i<=m;i++){ read(x),read(y); pt[++tot]=(Pt){x,y,0}; } for(ri i=1;i<=q;i++){ read(x),read(y); pt[++tot]=(Pt){x,y,i}; } std::sort(pt+1,pt+1+tot); for(ri i=1;i<=tot;i++){ //printf("%d %d %d %d\n",i,pt[i].id,pt[i].x,pt[i].y); if(!pt[i].id)add(pt[i].y,1); else qry[pt[i].id]=query(pt[i].y); } for(ri i=1;i<=q;i++)printf("%d\n",qry[i]); return 0;} D.CF-EducationalRound52-C-MakeItEqual
这题应该比T1稍难一点
首先naiive的想法就是按照高度排序一遍后,不断向下拓展,但是发现操作繁琐,而且我的做法是一个错误的想法
然后这时候我看到值域居然只有2e5?!然后我们还是按照一样的思路一路向下拓展,如果不行的话切一刀就好了
代码同样很短
注意判0的情况,太坑了
int h[maxn],n,ans=0;int sz[maxn],mx=0,mi=inf,mi_id;ll k,sum=0;int main(){ read(n),read(k); for(ri i=1;i<=n;i++){ read(h[i]); mx=max(mx,h[i]); mi=min(mi,h[i]); sz[h[i]]++; } int num=0; if(mx==mi){puts("0");return 0;} for(ri i=mx;i>=mi;i--){ sum+=num; if(sum>k){ ans++; sum=num; } num+=sz[i]; } ans++;//最后无论如何都要切一刀 printf("%d\n",ans); return 0;} E. CF-Round#485 div.2 D - Fair
这题昨天没想出来,今天看题解发现还挺简单的 雾)
关键还是思维太僵化了
我们可以用BFS求出每个点到某种颜色的最短路,时间复杂度\(O(nk)\)
然后对于每个点都$nth $_ \(element\),求出前s小的颜色距离加起来就好了
const int maxn=100005;const int inf=0x7fffffff;int n,m,k,s;int col[maxn];vector fc[105];struct Edge{ int ne,to;}edge[maxn<<1];int h[maxn],num_edge=1;inline void add_edge(int f,int to){ edge[++num_edge].ne=h[f]; edge[num_edge].to=to; h[f]=num_edge;}int dis[maxn][105];inline void bfs(int c){ queue q; int u,v; for(ri i=0;i F.
咕