前言
数论专题模拟赛
来到北京第一场模拟赛
T1
赛时想了2h
分为1号点和2号点，但是发现同一种情况可以有不同的分法
所以我们固定以下，规定第一次出现的数为1号点，形式化的一号点个数不小于二号点
就可以dp来做，发现满足卡特兰数
做完了
赛场上由于求的是单独一个数的逆元而不是逆元的前缀和，调了好久
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int T,n;
int a[2*N],f[2*N],q[2*N];
int c(int x,int y){return a[x]*q[x-y]%mod*q[y]%mod;
}
signed main(){freopen("notitle.in","r",stdin);freopen("notitle.out","w",stdout);scanf("%lld",&T);a[1]=1,f[1]=1,q[0]=1;for(int i=2;i<=4e5;i++) a[i]=a[i-1]*i%mod,f[i]=(-(mod/i)*f[mod%i]%mod+mod)%mod;for(int i=1;i<=4e5;i++) q[i]=q[i-1]*f[i]%mod;while(T--){scanf("%lld",&n);printf("%lld\n",(c(2*n,n)-c(2*n,n-1)+mod)%mod);}
}
T2
之前做过，就是没想出来，难受
最初初始的转化，我记得我上次都想到了，这次没想到，或许是考试时注意力不算太集中？
考虑必定过两个线段的端点
然后后面就很显然了，枚举一个端点，然后其它按照斜率跑一遍扫描线
然后在调题的时候注意斜率是 x/y 这样能保证把斜率排序后是连续的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const double eps=1e-5;
struct oil{int l,r,y,w;
}a[N];
struct dot{double x;int w;
}b[N];
int n,cnt,ans;
bool cmp(dot a,dot b){if(fabs(a.x-b.x)<eps) return a.w>b.w;return a.x>b.x;
}
double query(int x,int y,int nx,int ny){// cout<<x<<" "<<y<<" "<<nx<<" "<<ny<<" "<<((double)y-ny)/(nx-x)<<endl;return (double)(nx-x)/(y-ny);
}
int solve(int x,int y,int id){cnt=0;for(int i=1;i<=n;i++){if(i==id||a[i].y==y) continue;double q1=query(x,y,a[i].l,a[i].y),q2=query(x,y,a[i].r,a[i].y);if(q1<q2) swap(q1,q2);b[++cnt]={q1,a[i].w};b[++cnt]={q2,-a[i].w};}sort(b+1,b+1+cnt,cmp);int res=0,num=0;for(int i=1;i<=cnt;i++){res+=b[i].w;num=max(res,num);// printf("%d %lf ",b[i].w,b[i].x);}// printf("\n");return num+a[id].w;
}
int main(){freopen("oil.in","r",stdin);freopen("oil.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].y);if(a[i].l>a[i].r) swap(a[i].l,a[i].r);a[i].w=a[i].r-a[i].l;}// printf("%d\n",solve(a[4].r,a[4].y,4));// return 0;for(int i=1;i<=n;i++){ans=max(ans,solve(a[i].l,a[i].y,i));ans=max(ans,solve(a[i].r,a[i].y,i));}printf("%d\n",ans);
}
T3
海盗分金问题变式
赛场上根本没想去往下推，下次不能被自己吓唬，实际上这个问题就是先从手模入手的
推这种问题需要遵循以下法则（非常重要）
- 设总共有m个钻石，有n个人，(n,m)结果只与(n-1,m) 有关，关系如第二条
- 考虑任意一个人x我们如果当前的i分配数不大于i-1对i的分配数，x就会投反对票
s=1时
我们需要获得至少一半的支持，推的时候发现想要获得1颗钻石的人总奇偶交替出现
s=0时
%%%htc大巨讲的太清楚了
这是手模图片，形如此
然后发现对于一个点的能否存活，只需比较他前面第一个可行点之前的所有不可行点的个数+m+1<=n+1/2就能存活
所以发现规律对于一个n能拆分成 \(n=2^k+2*m\) 就能活
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int T,n,s;
int main(){freopen("distribute.in","r",stdin);freopen("distribute.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d",&n,&s);if(s==1) printf("%d\n",(n+1)/2);else printf("%d\n",(n&1)?n/2:(n-(1<<(int)log2(n)))/2);}
}
T4
题都没读明白（悲