头像

Foraino0267

雅礼中学




离线:23分钟前


最近来访(267)
用户头像
AcWing2AK
用户头像
Mr.watanuo
用户头像
Mrs.watanuo
用户头像
封禁用户
用户头像
Resurgence1001
用户头像
宇宙有边
用户头像
不上985不改网名
用户头像
ACWing的用户
用户头像
顽童
用户头像
凌蕸
用户头像
灰人
用户头像
KKKah
用户头像
马路边吃鱼
用户头像
WangJY
用户头像
Sun-Shine
用户头像
陌丨落
用户头像
spy2011
用户头像
不拿NOI金牌不改名
用户头像
QZX
用户头像
Tenko_


凸包闵可夫斯基和的板子题。

啥是闵可夫斯基和

简单来说就是 $A+B=\{ x+y|x\in A, y\in B \}$。

咋求闵可夫斯基和

发现闵可夫斯基和的凸包就是原图所有边极角排序后顺次连接(比如下图两个蓝色的闵可夫斯基和的凸包就是红色部分)。

vEG9tf.png

本题题解

如果 $A=B+C$,那么 $A-B=C$ 即 $A+(-B)=C$,所以 $B$ 取反求一次闵可夫斯基和然后每次判断 $C$ 在不在凸包中就行了。

代码很短。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll r=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
    return r*f;
}
const int N=1e5+50;
const double pi=acos(-1);
const double eps=1e-8;
struct Point {
    ll x,y;
    Point operator + (const Point &) const;
    Point operator - (const Point &) const;
    Point operator * (const ll &) const;
    bool operator == (const Point &) const;
    void operator += (const Point &) ;
    void operator -= (const Point &) ;
};
Point Point::operator +(const Point &a) const{
    Point b={x+a.x,y+a.y};
    return b;
}
Point Point::operator -(const Point &a) const{
    Point b={x-a.x,y-a.y};
    return b;
}
Point Point::operator *(const ll &a) const{
    Point b={x*a,y*a};
    return b;
}
bool Point::operator ==(const Point &a) const{
    return fabs(x-a.x)<eps&&fabs(y-a.y)<eps;
}
void Point::operator +=(const Point &a) {
    x+=a.x,y+=a.y;
}
void Point::operator -=(const Point &a) {
    x-=a.x,y-=a.y;
}
ll dot(Point a,Point b) {
    return a.x*b.x+a.y*b.y;
}
ll cross(Point a,Point b) {
    return a.x*b.y-b.x*a.y;
}
double get_length(Point a) {
    return sqrt(dot(a,a));
}
double get_angle(Point a,Point b) {
    return acos(dot(a,b)/get_length(a)/get_length(b));
}
double get_polar_angle(Point a){
    Point b={1,0};
    double cos_a=1.*dot(a,b)/get_length(a);
    double sin_a=1.*cross(b,a)/get_length(a);
    if(sin_a>=0) return acos(cos_a);
    else return 2.*pi-acos(cos_a);
}
bool cmp_for_polar_angle(Point a,Point b) {
    return (fabs(get_polar_angle(a)-get_polar_angle(b))<eps)?get_length(a)<get_length(b):get_polar_angle(a)<get_polar_angle(b);
}
bool cmp_for_cross(Point a,Point b) {
    return (cross(a,b)==0)?(get_length(a)<get_length(b)):cross(a,b)>0;
}
bool cmp_for_hull(Point a,Point b) {
    return (a.y==b.y)?(a.x<b.x):(a.y<b.y);
}
bool dot_in_convex(Point p,Point a[],int tot) {
    if(cross(p,a[1])>0||cross(a[tot],p)>0) return 0;
    ll critical_p=lower_bound(a+1,a+tot+1,p,cmp_for_cross)-a-1;
    Point A=p-a[critical_p],B=a[critical_p%tot+1]-a[critical_p];
    return cross(p-a[critical_p],a[critical_p%tot+1]-a[critical_p])<=0;
}
Point st[N];
int tail;
int convex_hull(int tot,Point a[]) {
    sort(a+1,a+tot+1,cmp_for_hull);
    tail=0;
    for(int i=1;i<=tot;++i) {
        while(tail>1&&cross(st[tail]-st[tail-1],a[i]-st[tail-1])<=0) tail--;
        st[++tail]=a[i];
    }
    int tmp=tail;
    for(int i=tot-1;i;--i) {
        while(tail>tmp&&cross(st[tail]-st[tail-1],a[i]-st[tail-1])<=0) tail--;
        st[++tail]=a[i];
    }
    if(tot>1) tail--;
    return tail;
}
Point edge_for_msch[N];
Point ans[N];
int cnt_of_msch;
Point start_p;
int minkowski_sum_of_convex_hull(int tota,Point a[],int totb,Point b[]) {
    cnt_of_msch=0;
    int tmpa=convex_hull(tota,a);
    start_p=st[1];
    for(int i=1;i<=tmpa;++i) edge_for_msch[++cnt_of_msch]=st[i%tmpa+1]-st[i];
    int tmpb=convex_hull(totb,b);
    start_p+=st[1];
    for(int i=1;i<=tmpb;++i) edge_for_msch[++cnt_of_msch]=st[i%tmpb+1]-st[i];
    sort(edge_for_msch+1,edge_for_msch+cnt_of_msch+1,cmp_for_polar_angle);
    ans[1]=start_p;
    for(int i=1;i<cnt_of_msch;++i) ans[i+1]=ans[i]+edge_for_msch[i];
    int tmpans=convex_hull(cnt_of_msch,ans);
    return tmpans;
}
int n,m,q;
Point a[N],b[N],query;
int main() {
    n=(int)read(),m=(int)read(),q=(int)read();
    for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
    for(int i=1;i<=m;++i) b[i].x=read(),b[i].y=read(),b[i].x=-b[i].x,b[i].y=-b[i].y;
    int tot_ans=minkowski_sum_of_convex_hull(n,a,m,b);
    Point tmp=st[1];
    for(int i=1;i<=tot_ans;++i) st[i]-=tmp;
    while(q--) {
        query.x=read(),query.y=read();
        query-=tmp;
        printf("%d\n",dot_in_convex(query,st,tot_ans));
    }
    return 0;
}



式子摘自洛谷用户璀璨星空1的题解(Orz。

这题就是求没有等价点的图的最大边数。

考虑原图没有等价点,则补图也没有等价点,求原图最大边数等价于总边数减求补图最小边数。

$n=1$ 答案显然为 $0$;

$n=2、3$ 答案显然为 $-1$;

$n=4$ 时原图和补图都需要联通,所以边数都至少为 $3$ ,而经过枚举,大小为 $4$ 的树不可能没有对称点,所以答案为 $-1$;

$n=5$ 时原图和补图都需要连通,总边数为 $10$,可能情况有 $4/6$ 或 $5/5$ ,经枚举可以知道不可能不存在对称点,所以答案也为 $-1$;

$n=6$ 时原图和补图都需要连通,总边数为 $15$,$5/10$ 时容易得到五个点的树不可能不存在对称点,而 $6/9$ 时可以构造一个环上链长度为 $1,2,3$ 的基环树,所以答案为 $9$;

$n\ge 7$ 时至少都可以构造一个从中心像三个方向发散长度为 $2,3,n-3$ 的树,所以一定存在答案。

我们贪心考虑一下, $n\ge 7$ 时补图的每个联通块一定都是小于 $n$ 的树构成,不选大小为 $6$ 的基环树的原因是容易证明一定有小于或者等于这种选法的答案。

那么我们求出大小为 $n$ 的无标号无根无对称点树的个数就行了,设这个个数序列为 $U$,考虑能不能通过递推求出 $U$ ,发现由于无根不好求,那就用有根的来求。

设有根无对称点的个数为 $R$ ,考虑讨论重心位置:

1、 $n\bmod 2=1$ 时,重心唯一,减去有子树大于二分之一的情况即 $R_n-\frac{1}{2}\sum_1^{n-1}R_{i}R_{n-i}$;

2、 $n\bmod 2= 0$ 时,除开减去有子树大于二分之一的情况以外,还要除去两棵树互为同构的情况即 $R_n-\frac{1}{2}\sum_1^{n-1}R_{i}R_{n-i}-\frac{1}{2}R_{\frac{n}{2}}$。

快速算出 $R_i$ 即可。

又 $ R_n=\sum_{(\sum_{i=1}^{n-1}(i\times x_i))+1=n}\prod_{i=1}^{n-1}{R_i\choose x_i}$ ,考虑生成函数 $F(x)=x\prod_{i=1}^\infty(1+x^i)^{R_i}$。

两边同时取 $\ln$,得到 $\ln F(x)=\ln x+\sum_{i=1}^\infty (R_i\ln(1+x^i))$;

同时求导,得到 $ \dfrac{F’(x)}{F(x)}=\dfrac1x+\sum_{i=1}^{\infty}(R_i\cdot\dfrac{ix^{i-1}}{1+x^i})$;

所以 $xF’(x)=F(x)+F(x)\sum_{i=1}^{\infty}(R_i\cdot\dfrac{ix^{i}}{1+x^i})$;

对比两边 $x^n$ 的系数,得到:

$ R_n=\dfrac1{n-1}\cdot(\sum_{i=1}^{n-1}(R_{n-i}(\sum_{d|i}(-1)^{\frac id+1}dR_d)))$。

直接算 $R,U$,贪心数数即可。

#include<bits/stdc++.h>
#define LL __int128
const int LEN = 100;
using namespace std;
typedef long long ll;
int T;
LL read() {
    LL val=0,cnt=0;
    char ch=' ';
    while(!('0'<=ch&&ch<='9')) ch=getchar();
    while('0'<=ch&&ch<='9') val=(val<<1)+(val<<3)+(ch-'0'),ch=getchar(),++cnt;
    if(cnt>=100) return 0;
    return val;
}
void write(LL val) {
    if(val==0) {
        printf("0\n");
        return;
    }
    int tmp=val;
    stack<char> st;
    while(!st.empty()) st.pop();
    while(tmp>=1) st.push((tmp%10)+'0'),tmp/=10;
    while(!st.empty()) printf("%c",st.top()),st.pop();
    printf("\n");
}
LL n,r[105],u[105];
const LL mod=1e9+7;
int main() {
    LL a,b;
    r[1]=r[2]=1;
    for(int i=3;i<=100;++i) {
        for(int j=1;j<i;++j) {
            LL anss=0;
            int sqt=sqrt(j);
            for(int l=1;l<=sqt;++l) {
                if(j%l) continue;
                anss+=((j/l)&1?1:-1)*l*r[l];
                if(j/l!=l) anss+=(l&1?1:-1)*(j/l)*r[j/l];
            }
            LL tmp=r[i-j]*anss;
            r[i]+=tmp;
        }
        r[i]/=i-1;
    }
    for(int i=1;i<=100;++i) {
        u[i]=r[i]*2;
        for(int j=1;j<i;++j) u[i]-=r[j]*r[i-j];
        if(!(i&1)) u[i]-=r[i>>1];
        u[i]/=2;
    }
    scanf("%d",&T);
    while(T--) {
        n=read();
        LL tmpn=n;
        if(n==1) puts("0");
        else if(n>=2&&n<=5) puts("-1");
        else if(n==6) puts("9");
        else if(n==0) puts("155132763");
        else {
            LL ans=0;
            for(int i=1;i<=100;++i) {
                LL tmpi=i;
                if(tmpn>=(tmpi*u[i])) tmpn-=(tmpi*u[i]),ans+=u[i];
                else {
                    ans+=(tmpn/i);
                    break;
                }
            }
            write(((ans+n*(n-3)/2)%mod+mod)%mod);
        }
    }
    return 0;
}



Foraino0267
1个月前

很牛的一道题啊,思路部分摘自 command_block 的博客。

首先 k-th Min-Max 容斥,这玩意儿同样是在期望条件下成立的,代公式得到 $ans=\sum_{T\subset S} (-1)^{|T|-k}{{|T|-1}\choose{k-1}}E(min(T))$,$E(min(T))$ 的结果非常显然,就是$\frac{m}{\sum_{i\in T}p_i}$。

但是直接 $2^n$ 枚举子集肯定会寄,然后发现值域居然给了个范围,考虑根据值 DP ,考虑设 $f_{i,j,k}$ 为前 $i$ 个里选了 $j$ 个,$\sum p_i$ 为 $k$,第一维可以滚掉,但是 $n^2m$ 时间复杂度仍然会寄。

然后观察到还有什么奇怪的范围可能作为状态数出现,发现 $k$(因为是第 $k$ 大,所以这里的 $k$ 就是原题的 $n-k$)很小,考虑能不能搞个跟 $k$ 相关的 DP 优化掉一个 $n$(即不记录选择的个数),我们考虑剩下的那一个关于集合大小的系数,加入一个数后会得到 $(-1)^{|T|-k+1}{{|T|}\choose{k-1}}$,关键是后面那坨组合数不好搞,强行把它拆开成 $(-1)^{|T|-k+1}{{|T|}\choose{k-1}}=(-1)^{|T|-k-1}{{|T|}\choose{k-2}}-(-1)^{|T|-k}{{|T|-1}\choose{k-1}}$,这样记录一个 $k$ 就行了,容易得到 DP 式子 $f_{i,j,k}+=f_{i-1,j,k}$,$f_{i,j+p_i,k}+=f_{i-1,j,k-1}-f_{i-1,j,k}$,第一维还是可以滚掉。

代码很短,难在思维。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int M=100005,K=15,N=1005;
int qpow(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ans;
}
int f[2][M][K];
int n,m,k;
int p[N];
int ans;
int main() {
    scanf("%d%d%d",&n,&k,&m);
    k=n-k+1;
    for(int i=1;i<=n;++i) scanf("%d",&p[i]);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j)
            for(int l=0;l<=k;++l) f[i&1][j][l]=f[i&1^1][j][l];
        if(!p[i]) continue;
        for(int j=0;j<=m-p[i];++j)
            for(int l=1;l<=k;++l) f[i&1][j+p[i]][l]=(1ll*f[i&1][j+p[i]][l]+f[i&1^1][j][l-1]-f[i&1^1][j][l]+mod)%mod;
    }
    for(int i=1;i<=m;++i) ans=(ans+1ll*f[n&1][i][k]*qpow(i,mod-2)%mod*m%mod+mod)%mod;
    printf("%d\n",ans);
    return 0;
}


新鲜事 原文

Foraino0267
1个月前
天依生日快乐!



Foraino0267
1个月前

$Min-Max$ 容斥定理在期望条件下也是成立的。
直接套用 $Min-Max$ 容斥。
子集和就直接用 $or$ 的 $DWT$ 就好了。
代码巨短。

#include<bits/stdc++.h>
using namespace std;
const int N=21;
const double eps=1e-9;
int n;
double a[1<<N],ans;
int count1(int x) {
    int ans=0;
    while(x) ans+=x&1,x>>=1;
    return ans;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<1<<n;i++) scanf("%lf",&a[i]);
    for(int mid=1;mid<1<<n;mid<<=1)
        for(int i=0;i<1<<n;i+=mid<<1)
            for(int j=0;j<mid;++j) a[i+j+mid]+=a[i+j];
    for(int i=0;i<(1<<n)-1;++i) {
        if(1-a[i]<eps) {
            puts("INF");
            return 0;
        }
        a[i]=1./(1-a[i]);
    }
    for(int i=1;i<1<<n;++i) ans+=((count1(i)&1)?1.:-1.)*a[i^((1<<n)-1)];
    printf("%.12lf",ans);
    return 0;
}



Foraino0267
1个月前

数据范围看错了,事实上数据范围允许一个很简单的容斥。
推广辗转相除版高斯消元,废除取模!!!!1

#include<bits/stdc++.h>
using namespace std;
const int N=20,M=250;
const int mod=1e9+7;
int n;
int e[N][N],d[N][N];
bool vis[N];
int lastans;
vector<pair<int,int> > v[N];
int delt(int a[N][N],int sz) {
    int ans=1;
    for(int i=1;i<=sz;++i) {
        for(int j=i+1;j<=sz;++j) {
            while(a[i][i]) {
                int div=a[j][i]/a[i][i];
                for(int l=i;l<n;++l) a[j][l]=(a[j][l]-1ll*a[i][l]*div%mod+mod)%mod;
                swap(a[i],a[j]);
                ans=-ans;
            }
            swap(a[i],a[j]);
            ans=-ans;
        }
    }
    for(int i=1;i<=sz;++i) ans=(1ll*ans*a[i][i])%mod;
    return (ans+mod)%mod;
}
void dfs(int t,int num) {
    if(t>=n) {
        memset(e,0,sizeof(e));
        memset(d,0,sizeof(d));
        for(int i=1;i<n;++i) {
            if(vis[i]) {
                int tmpm=v[i].size();
                for(int j=0;j<v[i].size();++j) {
                    int tmpu=v[i][j].first,tmpv=v[i][j].second;
                    d[tmpu][tmpu]++;
                    d[tmpv][tmpv]++;
                    e[tmpu][tmpv]++;
                    e[tmpv][tmpu]++;
                }
            }
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) e[i][j]=(d[i][j]-e[i][j]+mod)%mod;
        lastans=(1ll*lastans+delt(e,n-1)*(1-((((n-1)&1)^(num&1))<<1))%mod+mod)%mod;
        return;
    }
    dfs(t+1,num);
    vis[t]=1;
    dfs(t+1,num+1);
    vis[t]=0;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int m;
        scanf("%d",&m);
        for(int j=1;j<=m;++j) {
            int tmpu,tmpv;
            scanf("%d%d",&tmpu,&tmpv);
            v[i].push_back(make_pair(tmpu,tmpv));
        }
    }
    dfs(1,0);
    printf("%d\n",lastans);
    return 0;
}


新鲜事 原文

Foraino0267
1个月前
NOI推迟了,好! 同步赛取消了,€€£你【】什么时候【】啊??!



Foraino0267
1个月前

题目即
$$
\sum_{T}\prod_{e\in T}p_e\prod_{e\notin T}(1-p_e)=\sum_{T}\prod_{e\in T}p_e\frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)}=\prod_{e}(1-p_e)\sum_{T}\prod_{e\in T}\frac{p_e}{1-p_e}
$$
最右边那个可以直接用矩阵树定理求。

$p_e$ 是 $0$ 或者 $1$ 的时候加上一个偏移量调节一下就好了。

因为输出是小数,所以行列式不用辗转相除,很方便。

#include<bits/stdc++.h>
using namespace std;
const int N=55;
const double eps=1e-8;
int n;
double e[N][N],d[N][N];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) {
            scanf("%lf",&e[i][j]);
            if(e[i][j]<eps) e[i][j]=eps;
            else if(e[i][j]>1.-eps) e[i][j]=1.-eps;
        }
    double ans=1;
    for(int i=1;i<=n;++i) 
        for(int j=i+1;j<=n;++j) ans=ans*(1.-e[i][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) e[i][j]=e[i][j]/(1.-e[i][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) d[i][i]+=e[i][j];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) e[i][j]=d[i][j]-e[i][j];
    for(int i=1;i<n;++i) {
        for(int j=i+1;j<n;++j) {
            double div=e[j][i]/e[i][i];
            for(int l=i;l<n;++l) e[j][l]=e[j][l]-e[i][l]*div;
        }
    }
    for(int i=1;i<n;++i) ans*=e[i][i];
    printf("%.12lf",ans);
}



Foraino0267
1个月前
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
const int N=10,M=100;
int n,m;
int a[N][N];
int cnt;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ma1[M][M],ma2[M][M];
int ans=1;
int f=1;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j) {
            char ch=getchar();
            while(ch!='.'&&ch!='*') ch=getchar();
            if(ch=='.') a[i][j]=++cnt;
        }
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(!a[i][j]) continue;
            for(int l=0;l<4;++l) {
                int x=i+dx[l],y=j+dy[l];
                if(!x||!y||x>n||y>m) continue;
                if(!a[x][y]) continue;
                ma1[a[i][j]][a[x][y]]++;
                ma2[a[i][j]][a[i][j]]++;
            }
        }
    }
    for(int i=1;i<=cnt;++i)
        for(int j=1;j<=cnt;++j) ma2[i][j]=(ma2[i][j]-ma1[i][j]+mod)%mod;
    cnt--;
    for(int i=1;i<=cnt;++i) {
        for(int j=i+1;j<=cnt;++j) {
            while(ma2[i][i]) {
                int div=ma2[j][i]/ma2[i][i];
                for(int l=i;l<=cnt;++l) ma2[j][l]=(ma2[j][l]-1ll*div*ma2[i][l]%mod+mod)%mod;
                swap(ma2[i],ma2[j]);
                f=-f;
            }
            swap(ma2[i],ma2[j]);
            f=-f;
        }
    }
    ans=f;
    for(int i=1;i<=cnt;++i) ans=(1ll*ans*ma2[i][i]%mod+mod)%mod;
    printf("%d\n",ans);
    return 0;
}



Foraino0267
2个月前

发现都是权值线段树+动态开点的题解,交个短得多的 CDQ 分治(那个::l::r是不小心变量重名了引用的全局变量)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
int n;
ll l,r;
int a[N];
ll s[N],w[N];
ll ans;
void merge_sort(int l,int r) {
    if(l==r) return;
    int mid=l+r>>1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    int head=l,tail=l-1;
    for(int i=mid+1;i<=r;++i) {
        while(s[i]-s[tail+1]>=::l&&tail+1<=mid) tail++;
        while(s[i]-s[head]>::r&&head<=mid) head++;
        ans+=tail-head+1;
    }
    int i=l,j=mid+1,cnt=0;
    while(i<=mid&&j<=r) {
        if(s[i]<s[j]) w[++cnt]=s[i++];
        else w[++cnt]=s[j++];
    }
    while(i<=mid) w[++cnt]=s[i++];
    while(j<=r) w[++cnt]=s[j++];
    for(int i=l;i<=r;++i) s[i]=w[i-l+1];
}
int main() {
    scanf("%d%lld%lld",&n,&l,&r);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    merge_sort(0,n);
    printf("%lld\n",ans);
    return 0;
}