心得

赛中ac：5，目前ac：9，题目总数：13

中档可做题还是很多的，可惜遇到了难绷的queueforces，

最后15min才判出来，oi赛制5wa4遗憾离场，赛后把几个题都给调过了，写下题解

题目

J. Breakfast（签到）

签到，不过不是很懂python直接输出39.20为啥wa了

#include
#include
#include
#include

A. Paper Watering（枚举）

先特判1，

对于非1的情况，首先原数是可以一直平方不重的，

如果x开根号遇到了下取整，说明sqrt(x)*sqrt(x)也不会和x重，后续平方也都不会重

暴力模拟这个过程，直至出现1为止

#include
#include
#include
#include
#include

D. nIM gAME（博弈）

发现后手可以控制倒数第二张牌取什么，从而使先手必败

//#include
#include
#include
#include
#include

E. Checksum（枚举）

枚举最终的d有几个1，从而唯一确定后缀补的1的数量和位置，输出即可

//#include
#include
#include
#include
#include

L. Bracket Generation（计数）

一开始把第二个条件看错了，以为只有内层的选完了外层的才能选，没有这个限制之后就很好做

把左右括号相邻的()括号称为叶子节点（建括号树更直观），其他的称为非叶节点

非叶节点能选当且仅当其包含的最大叶子结点x及序列里位于x左侧的叶子结点都选完之后，才能选

将序列倒着考虑，就是非叶节点的一个插空问题

#include
#include
#include
#include
#include

F. Factor（数论）

先把p、k分别质因数分解，求出对应质因数和出现的幂次

对于p的质因子f，如果f也是k的质因子，显然出现多少次都无所谓，都能除尽，删掉这些f

对于p的独有质因子（也就是没有出现在k中的质因子）p1、p2、…，

记每个的最高幂次是k1、k2、…，将这些最高幂次乘起来得到y，

枚举y的因子z，也就是这些独有质因子出现了多少，

分母必须恰好能和z兑掉，且剩下的部分由k出现过的质因子构成，

在[1,x/z]内仅由k出现过的质因子构成的数，这个可以先预处理出所有，再二分

因为仅由质因子组成，所以数量没有太多

#include
#include
#include
#include
#include
f,f2;
vectorg,all;
mapmp;
void dfs(ll v,int y){
    all.pb(v);
    int sz=SZ(g);
    for(int i=y;i<sz;++i){
        if(1ll*v<=x/g[i])dfs(v*g[i],i);
    }
}
void sol(ll v,int y,int z){
    ans+=upper_bound(all.begin(),all.end(),x/v)-all.begin();
    int sz=SZ(f2);
    if(y==sz)return;
    //printf("v:%lld y:%d z:%d fi:%lld se:%d
",v,y,z,f2[y].fi,f2[y].se);
    if(1ll*v<=x/f2[y].fi && z+1<=f2[y].se)sol(v*f2[y].fi,y,z+1);
    for(int i=y+1;i<sz;++i){
        if(1ll*v<=x/f2[i].fi)sol(v*f2[i].fi,i,1);
    }
}
int main(){
	for(int i = 2; i < maxp; ++i) {
		if(!d[i])
		    pr[tot++] = d[i] = i;
		for(int j = 0, z; (z = i * pr[j]) p){
            break;
        }
        if(p%pr[i]==0){
            f.pb(P(pr[i],0));
            while(p%pr[i]==0)p/=pr[i],f.back().se++;
        }
    }
    if(p>1)f.pb(P(p,1));
    //for(auto &x:f)printf("(p:%lld,c:%lld)
",x.fi,x.se);
    rep(i,0,tot-1){
        if(1ll*pr[i]*pr[i]>k){
            break;
        }
        if(k%pr[i]==0){
            g.pb(pr[i]);
            mp[pr[i]]=true;
            while(k%pr[i]==0)k/=pr[i];
        }
    }
    if(k>1){
        g.pb(k);
        mp[k]=true;
    }
    //for(auto &x:g)printf("(g:%lld)
",x);
    for(auto &v:f){
        if(mp.count(v.fi))continue;
        f2.pb(v);
    }
    //for(auto &v:f2)printf("(%lld,%lld) ",v.fi,v.se);puts("");
    dfs(1,0);
    sort(all.begin(),all.end());
    //for(auto &v:all)printf("(v:%lld)
",v);
    sol(1,0,0);
    ptlle(ans);
    return 0;
}

I. Password（dp）

dp[i]表示[1,i]是合法答案的方案数

转移枚举最后一段的长度x，最后这一段和前面的x-k共同拼成了一个长度为k的排列

但是枚举长度为2的时候，会和长度为1的方案有重复，具体来说

不妨k=5，前5个肯定只能是一个排列，k!种方案，不妨是1 2 3 4 5，对于第6个往后，

对于x=1，1 2 3 4 5 [1]，

x=2，1 2 3 4 5 [2 1]和  1 2 3 4 5 [1 2]中只能保留第一个，因为第二个和x=1重复了

x=3，同理，只能保留1 2 3 4 5 [3 1 2]、1 2 3 4 5 [3 2 1]和1 2 3 4 5 [2 3 1]

这个系数是需要递推减掉的，手玩发现：

记长度为x的系数是xs[x]，对于长度x来说，若y<x，则需要在总数里减掉xs[y]*fac[x-y]，

    rep(i,1,k){
        xs[i]=fac[i];
        per(j,i-1,1){
            xs[i]=(xs[i]+mod-1ll*xs[j]*fac[i-j]%mod)%mod;
        }
        //printf(“i:%d xs:%d
“,i,xs[i]);
    }

O(k^2)预处理出系数之后，再O(nk)dp即可

#include
#include
#include
#include
#include

M. House（计算几何）

感觉计算几何的题平时不怎么写所以不太会写，

但实际上出题人应该平时也不怎么写，出的题还是挺基础的

先求出矩形，O(n^2logn)枚举点对，将点对放入（线段中点，线段长度）的map内，

矩形的对角线互相平分，所以共用中点且长度相等的两条对角线能构成一个矩形

两两枚举矩形，对于矩形四条边，任意两条邻边x、y检查一下，

统计房子在x外侧的第五个点的个数，这个需要叉积判断不在矩形内部

此时需要统计向量i->j左侧/右侧有多少点，O(n^3)预处理一下即可

#include
#include
#include
#include
#include
ans[M];
int pos[N][N],neg[N][N];
void ck(int a,int b,int c){
    //printf("a:%d b:%d c:%d res1:%lld
",a,b,c,res);
    if(cross(e[c]-e[b],e[a]-e[b])<0)res+=pos[b][a];
    else res+=neg[b][a];
    //printf("a:%d b:%d c:%d res2:%lld
",a,b,c,res);
}

int main(){
    sci(n);
    rep(i,1,n){
        scanf("%lld%lld",&e[i].x,&e[i].y);
    }
    rep(i,1,n){
        rep(j,1,n){
            if(i==j)continue;
            Point c=e[i]-e[j];
            ll z=dot(c,c);
            //printf("i:%d j:%d x:%lld y:%lld z:%lld
",i,j,e[i].x+e[j].x,e[i].y+e[j].y,z);
            if(i0){
                        //printf("i:%d j:%d neg:%d
",i,j,neg[i][j]);
                        pos[i][j]++;//i->j的逆时针方向 样例房子形状
                    }else if(w<0){
                        neg[i][j]++;
                        //printf("i:%d j:%d neg:%d
",i,j,pos[i][j]);
                    }
                }
            }
        }
    }
    for(auto &x:mp){
        ans[++c]=x.se;
    }
    // rep(i,1,n){
    //     rep(j,1,n){
    //         if(i==j)continue;
    //         printf("i:%d j:%d neg:%d pos:%d
",i,j,neg[i][j],pos[i][j]);
    //     }
    // }
    rep(i,1,c){
        int sz=SZ(ans[i]);
        rep(j,0,sz-1){
            rep(k,j+1,sz-1){
                int a=ans[i][j].fi,d=ans[i][j].se,b=ans[i][k].fi,c=ans[i][k].se;
                //printf("a:%d b:%d c:%d d:%d res:%lld
",a,b,c,d,res);
                ck(b,a,c);ck(a,c,d);ck(c,d,b);ck(d,b,a);
                //printf("a:%d b:%d c:%d d:%d res2:%lld
",a,b,c,d,res);
            }
        }
    }
    ptlle(res);
    return 0;
}
/*
5
4 2
0 2
2 5
4 0
0 0
*/

G. Diamond（分块）

想到分块之后就很好做了，虽然空间稍微用short卡了一下

先把n弥补成块的倍数，方便后面判断，后面的都用0补足即可，

对于第i个块，预处理出块内任意两种数(x,y)的逆序对个数，

计在这个块内x、y出现的第一个位置big[i][x][y]

所以，也需要记录每种数x在第i个块内出现的第一个位置pos[x][i]是多少，

这个位置可以对块长取模，就是一个最大为块长M（300多）的数，short足矣

然后就是在线查询，

对于长度不超过3*M的块，懒得分类讨论有一个块还是两个了，直接暴力，常数略大一点而已

超过3*M的，一定中间有完整块，然后最多两个半块，

对于每个完整块，先加上完整块的答案；对于半块，暴力统计答案

再从前往后、从后往前遍历块，分别统计块间能产生的答案，求和即可

#include
#include
#include
#include
#include