Ryan_<

T1 赛车【计算几何?+单调栈/队列】

抽象模型：

v-t图：赛车==直线Xi,t=Vi*t+Ki；追上==直线焦点；曾经领先==“水平可见”

单调队列维护

学习了Regina8023的写法:用队列保存当前为答案的元素的下标
单调队列:队列中下标对应直线单调递增,其实维护了一个下凸线

交点在x轴左侧:斜率较小的直线无法成为答案,从前往后扫,向后移动头指针
因为:具有单调性!该种情况不可能在中间出现

bool cmp1(car a,car b)
{return a.v<b.v || (a.v==b.v&&a.K>b.K);}




    sort(a+1,a+n+1,cmp1);
    a[0].v=-1;
    r=0;
    F(i,1,n){
        if(a[i].v==a[i-1].v&&a[i].K<a[i-1].K) continue;
        while(r>1 && poix(a[i],a[q[r]])<poix(a[q[r]],a[q[r-1]])) r--;
        q[++r]=i;
    }
    l=1;
    while(l<r && poix(a[q[l]],a[q[l+1]])<-eps) l++;

被bzoj卡了,cena测ac

输出方式

bool cmp2(int x,int y){return a[x].id<a[y].id;}
    
    printf("%d\n",r-l+1);
    sort(q+l,q+r+1,cmp2);
    printf("%d",a[q[l]].id);
    F(i,l+1,r) printf(" %d",a[q[i]].id);

注意sort左闭右开

模拟time：追上==解方程得t表达式：

double poix(car a,car b)//交点横坐标即为相遇tim! 保证x.K<y.K
{return (double)(a.K-b.K)/(b.v-a.v);}

单调栈维护

T2 卡牌游戏【概率递推】

状态:ans[i][j]表示当前剩余i个人的回合,第j个人最后可以获胜的概率

j是相对当前回合坐庄的人的编号

ans[1][1]=0

从小往大三重循环枚举i,j,k(所抽取的卡牌)

i,j由i-1,next转移过来，next由当前j决定,i-1所有状态的答案在之前已经得出,故可递推计算

类似记忆化搜索的思想?

    ans[1][1]=1;
    F(i,1,n){
        F(j,1,i){//now bianhao
            F(k,1,m){
                int w=((int)c[k]%i)?(int)c[k]%i:i;//被淘汰的元素
                int next=(j>w)?(j-w):(i-w+j);
                ans[i][j]+=ans[i-1][next]/(double)m;
            }
        }
    }

输出%方式：两个%%

   F(i,1,n-1) printf("%.2lf%% ",ans[n][i]*100);
    printf("%.2lf%%",ans[n][n]*100);

另：暴力分：搜索模拟一次游戏，枚举若干次（>1000）游戏得到结果，近似算出答案——精确度要求不高时可做

T3 删除物品【树状数组/线段树+模拟】

关键点:

整体移动物品,在两堆中顺序相反==>拼接

存在物品:1/删除物品:0==>单点修改,区间查询

• 单个元素==>整体处理
• 数据结构的用处：模拟过程！<==抽象模型

注意巧妙的排序方式

 bool cmp(int x,int y){return a[x]>a[y];}  

  
    n1=getint();n2=getint();
    n=n1+n2;
    D(i,n1,1) a[i]=getint();
    F(i,n1+1,n) a[i]=getint();
    top1=n1;top2=n1+1;
    B.clear();
    F(i,1,n) id[i]=i,B.add(i,1);//当前元素存在,0表示不存在
    sort(id+1,id+n+1,cmp);
    F(i,1,n){//相当于a[i]从大到小排序
        int now=id[i];
        if(now>=top2){//当前最大在第二堆
            ans+=B.query(top2,now-1);//弹出之前的元素,记录个数!
            B.add(now,-1);//删除该元素,即将该元素的值赋为0
        }
        else{//当前最大在第一堆
            ans+=B.query(now+1,top1);
            B.add(now,-1);
        }
        top1=now-1;top2=now+1;//元素在now出删除
    }

T4 地形生成【dp前缀和优化+组合计数】

蛮具有思维难度的题：

第一问：可以发现对一座山有影响的只可能是比它高的山，所以我们可以将山按高度从大到小排序，依次插入每座山。对于高度相同的山一起处理，按关键值从小到大排序，然后将每座山能插入的位置数乘到答案中，即min(i,a[i].key+1)+num-1，num为它在高度相同的山中的排名。

第二问：为了不重复计算，我们每次将高度相同的山拿出来，然后让插入之后的顺序也不改变。这样就可以DP计算，f[i][j]=f[i-1][0]+f[i-1][1]+……+f[i-1][j]，其实f数组还可以降到一维。注意每次计算时要将f数组清零。

inline bool cmp(data x,data y)
{
	return x.h==y.h?x.k<y.k:x.h>y.h;
}
	F(i,1,n) a[i].h=read(),a[i].k=read()-1;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i=j)
	{
		memset(f,0,sizeof(f));
		f[0]=1;
		for(j=i;j<=n&&a[i].h==a[j].h;j++)
		{
			ans1=ans1*(min(i,a[j].k+1)+j-i)%mod;
			for(int k=1;k<i&&k<=a[j].k;k++) f[k]=(f[k]+f[k-1])%mod;
		}
		int sum=0;
		for(int k=0;k<i&&k<=a[j-1].k;k++) sum=(sum+f[k])%mod;
		ans2=(ans2*sum)%mod;
	}