4.13省选模拟
这是博客园的第一百篇随笔\(!\)
不说别的,感觉代码能力真的提升很大,认真敲代码真的很畅快,好嘛\(!\)
一个原来的信竞生送来了一个省选祝福吧,感觉一句话说的很好
能走到现在,你们早已是赢家,抛去世界的一切,这一次,是为自己而战
\(T1\)
考场上一眼看出来正解,半平面交不会写,就造了一个假的半平面交。。(复杂度不对)
考场暴力代码(有一些细节也没处理好,考场上写了\(240+\))
#include
#define int long long
#define MAXN 200005
#define INF 1e30
using namespace std;
int sta[MAXN],son[MAXN],top1[MAXN],zx[MAXN][20],f[MAXN],top;
int head[MAXN],nxt[MAXN],to[MAXN],tot;
int n,m,cnt,siz[MAXN],dep[MAXN];
struct node
{
int a,s,id;
}poz[MAXN];
struct LINE
{
int k,st,ed,id,js,qs;
}Line[MAXN];
void add(int u,int v)
{
tot++;
to[tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
bool cmp(node x,node y)
{
if(x.a!=y.a) return x.amaxn)
{
maxn=siz[y];
son[now]=y;
}
}
}
void dfs_top(int now,int topn)
{
top1[now]=topn;
if(!son[now]) return ;
dfs_top(son[now],topn);
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(top1[y]) continue;
dfs_top(y,y);
}
}
int LCA(int x,int y)
{
while(top1[x]!=top1[y])
{
if(dep[top1[x]]dep[y]) swap(x,y);
return x;
}
int LEN(int x,int y)
{
return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
int Find(int now,int dp)
{
for(int i=18;i>=0;i--)
{
if((dp>>i)&1) now=zx[now][i];
}
return now;
}
//注意编号顺序
signed main()
{
freopen("ant.in","r",stdin);
freopen("ckant.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&poz[i].s);
poz[i].id=i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&poz[i].a);
}
// for(int i=1;i<=n;i++)
// {
// poz[i].s+=poz[i].a;
// }
sort(poz+1,poz+1+n,cmp);
int top=0;
for(int i=1;i<=n;i++)
{
while(top&&poz[sta[top]].s<=poz[i].s) top--;
sta[++top]=i;
}
// for(int i=1;i<=top;i++)
// {
// cout<<"id: "<poz[sta[i]].id)
{
x++;
}
}
if(x=poz[sta[xz]].s+x*poz[sta[xz]].a)
{
jd=x;
xz=i;
}
// cout<<"jd: "<MidLen&&TimLen>1;
if(Line[mid].ed>=T-1)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
// cout<<"mid: "<MidLen&&TimLen 考后重写了一遍半平面交,改了改就过了
#include
#define int long long
#define MAXN 200005
#define INF 1e30
using namespace std;
int sta[MAXN],son[MAXN],top1[MAXN],zx[MAXN][20],f[MAXN],top;
int head[MAXN],nxt[MAXN],to[MAXN],tot;
int n,m,siz[MAXN],dep[MAXN];
struct node
{
int k,b,id;
}poz[MAXN],T[MAXN];
struct line
{
int st,ed,id,js,qs;
}Line[MAXN];
bool cmp(node a,node b)
{
if(a.k!=b.k) return a.kb.b;
return a.id>b.id;
}
int Get(node l1,node l2)
{
int x=ceil((l2.b-l1.b)*1.0/(l1.k-l2.k)*1.0);
if(l1.k*x+l1.b==l2.k*x+l2.b)
{
if(l1.id>l2.id) x++;
}
return x;
}
void add(int u,int v)
{
tot++;
to[tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
void dfs_pre(int now,int fa)
{
zx[now][0]=fa;
for(int i=1;i<=18;i++)
{
zx[now][i]=zx[zx[now][i-1]][i-1];
}
int maxn=-1;
dep[now]=dep[fa]+1;
siz[now]=1;
f[now]=fa;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
dfs_pre(y,now);
siz[now]+=siz[y];
if(siz[y]>maxn)
{
maxn=siz[y];
son[now]=y;
}
}
}
void dfs_top(int now,int topn)
{
top1[now]=topn;
if(!son[now]) return ;
dfs_top(son[now],topn);
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(top1[y]) continue;
dfs_top(y,y);
}
}
int LCA(int x,int y)
{
while(top1[x]!=top1[y])
{
if(dep[top1[x]]dep[y]) swap(x,y);
return x;
}
int LEN(int x,int y)
{
return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
int Find(int now,int dp)
{
for(int i=18;i>=0;i--)
{
if((dp>>i)&1) now=zx[now][i];
}
return now;
}
signed main()
{
freopen("ant.in","r",stdin);
freopen("ant.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&poz[i].b);
poz[i].id=i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&poz[i].k);
}
sort(poz+1,poz+1+n,cmp);
T[top=1]=poz[1];
for(int i=2;i<=n;i++)
{
if(poz[i].k==poz[i-1].k) continue;
while(top>1&&(Get(T[top-1],poz[i])T[top].k*Get(T[top-1],poz[i])+T[top].b&&Get(T[top-1],poz[i])==Get(T[top-1],T[top])))) top--;
T[++top]=poz[i];
}
Line[0].ed=-1;
for(int i=1;i<=top;i++)
{
Line[i].id=T[i].id;
Line[i].st=Line[i-1].ed+1;
if(i!=top) Line[i].ed=Get(T[i],T[i+1])-1;
}
Line[top].ed=INF;
// for(int i=1;i<=top;i++)
// {
// cout<MidLen&&TimLen>1;
if(Line[mid].ed>=T-1)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
// cout<<"mid: "<MidLen&&TimLen \(T2\)
大力插头\(dp\)即可
源自题解.......
#include
#define mod 1000000007
using namespace std;
const int x5[10]={1,5,25,125,625,3125,15625,78125};
int v,past,now;
int f[2][480000],n,m,k,s[100][10],x,y,all;
int b[480000][9];
void out()
{
for (int k=0;k \(T3\)
计数题
如果把各种知识放在一起考虑,那么很麻烦,我们可以考虑一个一个知识去算,然后最后进行一下容斥操作
\(f(k)\)表示前\(k\)道题会做,后\(n-k\)道题不一定的方案数
\(g(k)\)表示前\(k\)道题会做,后\(n-k\)道题不会做的方案数
比较显然,\(f(k)\)包含\(g(k),\)我们需要把\(g(k)\)容斥出来
还是较为套路的二项式反演
\(f(k)=\sum C(j,k) g(j)\)
\(g(k)=\sum (-1)^{j-k} f(j)\)
我们考虑求\(f(x)\)可以把各种知识分开考虑,最后乘起来
我一直再想,这个会不会出现,前面符合要求,后面不符合要求的情况
其实我们每一步都是保证前\(n-k\)个,可以符合条件的方案,我一开始以为最后还要交换顺序之类的
就想的过于麻烦了,然后最后大概就是枚举\(Q\)每一个知识点的实力,最后相乘就好了
至于为什么二项式反演,我们强制让后面都严格大于不可以吗\(?\)
考虑最后他要会做这道题,那么就是说,我们总的中位数要满足条件
但是又说,我们这个即使前\(k\)个这个知识点会做,后面知识点的也不一定满足,这就是我们二项式容斥的必要我们最后\(f(k)\)表示的是全部知识点的情况
考虑每一种知识的时候,我们可以枚举\(Q\)的水平,假设为\(x,\)我们有一个\(a\)的范围使得既满足前\(n-k\)可做,后面的可能不可做,但是这道题会做...(有点混乱)
我们让\((n+1)/2<=a+k<=n\)
最后保留\(x,\)求出多项式系数,然后把多项式乘起来就好了
#include
#define mod 1000000007
#define int long long
#define maxn 102
using namespace std;
int C[105][105];
int sigma[105][105];
int n,m,k,u[105],p[105][105];
int ji;
int sqr(int x) {return (x*x)%mod;}
int qming(int a,int b)
{
if (!b) return 1;
if (b&1) return (sqr(qming(a,b>>1))*a)%mod;
return sqr(qming(a,b>>1));
}
void initC()
{
C[0][0]=1;
C[1][0]=C[1][1]=1;
for (int i=2;i<=maxn;i++)
{
C[i][0]=C[i][i]=1;
for (int j=1;j