OZY退役邀请赛

发表于 分类于 评论数： 阅读次数：

OZY退役邀请赛

比赛链接

C 学前班数学题

题意：
T组询问，每组询问给定两个正整数X，Z
你要找到最小的Y满足LCM(X,Y)=Z。保证有解
$T≤10^6，X,Z\le10^{18}$

唯一要解决的问题就是$gcd (\frac{z}{x},\frac{x}{d})=1$ 最大化d

我只想到log方的，就是x不断/gcd

正解是log的，就是x也同时乘gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void main()
{
    int T=qread();
    while(T--)
    {
        ll x=qread(),z=qread();
        ll a=z/x,b=x;
        while(1)
        {
            ll d=gcd(a,b);b/=d;a*=d;
            if(gcd(a,b)==1)break;
        }
        write2((z/x)*(x/b));
    }
}

51nod2030 Zbox的刷题II

首先题意是带标号的n道题

zsy的做法：正确性比较显然
$$
考虑对每个子集统计贡献，设大小为i的子集贡献系数为bi（显然只跟集合大小有关） \\
\sum_{i=1}^n C_n^ib_i(P^{0i}+P^{1i}…)=\sum_{i=1}^n \frac{C_n^i b_i}{1-P^i} \\
a_0=0,a_n=\sum_{i=0}^n C_n^ib_i,b_n=\sum_{i=0}^n(-1)^{n-i}C_n^ia_i，NTT求b，O(nlogn)
$$

出题人做法：

先说怎么做，就是把ai看做连续点值求这个多项式的下降幂

loj2417 bzoj4576 「USACO 2016 US Open, Platinum」262144

我的做法：
从小到大考虑，孤立的点会变成分界点，但分割这东西我不会怎么写成函数，只能硬着头皮写了1h+，过的时候真的成就感满满（因为担心做法假）
大概就是维护一段区间，然后每次扫同一个值的所有东西，然后向上合并，然后如果这一段长度是奇数，在中间建立分割点，然后因为题目只需要求最大值是什么，所以相互独立进行两组实验，告诉左边【我舍弃了最右边那个】，告诉右边【我舍弃了最左边那个】（xgc的优秀idea）
时间复杂度为 $O(n值域)$ 这个复杂度和正解一样，但不满，所以loj登顶了，code；然后发现也有人和我一样的做法的
正解：code 非常好写……

LOJ3014 「JOI 2019 Final」独特的城市

设直径端点为S和T，按照与谁近划分两点的地盘，则节点x的独特城市一定在x到管理x的端点另一个的路径上

那么我们分别以S和T为根建树，然后最后用所属端点来决定输出哪个答案

如果用dfs遍历节点并用栈保存到根路径上所有当前合法的点，容易发现到其孩子的话最多增加一个节点x本身

那么我们现在得到一个暴力做法：依次遍历每个孩子，然后将栈内到x距离<=【其他孩子能贡献最长到x的链】的节点删除并加入x，回溯的时候还原；等所有节点都处理完了，再求出x的答案（用x的最长链更新后）

发现这样复杂度无法保证，但先别急着换做法；注意到如果那个更新的阈值递减就不用还原了，也就是说我们先用次长链更新，然后访问长孩子，再用最长链更新访问其他孩子，这样就没有还原了，于是就能保证复杂度，即每个点加入度数次，复杂度为线性；code

小学生网格题

题目
题意：
n*m四联通的网格，一个格子被控制满足下面两个条件之一:
1：这个格子被标记
2：这个格子相邻的格子都被标记
给出每个格子控制的收益和标记的代价，求最大收益-代价
1≤n,m≤100

规模、值域很小，费用流好像不是很可行，考虑最小割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
    #define double long double
    typedef long long ll;
    #define pr pair<int,int>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    void chmax(int &x,const ll y) {x=(x>y?x:y);}
    void chmin(int &x,const ll y) {x=(x<y?x:y);}
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    const int INF=0x3f3f3f3f;
    const int MOD=950009857;
    inline ll qpower(ll x,ll e)
    {
        ll ans=1;
        while(e)
        {
            if(e&1) ans=ans*x%MOD;
            x=x*x%MOD;e>>=1;
        }
        return ans;
    }
    inline ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e3+10;
    int hou[N*N];
    struct Edge{int y,g,c;}e[N*N];
    int ln=0;int oth(int k){return k&1?k+1:k-1;}
    void ins(int x,int y,int c)
    {
        // printf("(%d->%d,%d)\n",x,y,c);
        e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;
        e[++ln]=(Edge){x,hou[y],0};hou[y]=ln;
    }
    int st,ed;
    int h[N*N];queue<int> q;
    bool bfs()
    {
        memset(h,0,sizeof h);q.push(st);h[st]=1;
        while(q.size())
        {
            int x=q.front();q.pop();
            for(int k=hou[x];k>0;k=e[k].g)
            {
                int y=e[k].y;
                if(!h[y] and e[k].c) h[y]=h[x]+1,q.push(y);
            }
        }
        return h[ed]>0;
    }
    int dfs(int x,int flow)
    {
        if(x==ed or !flow) return flow;
        int tt=0;
        // printf("dfs(%d,%d)\n",x,flow);
        for(int k=hou[x];k>0;k=e[k].g)
        {
            int y=e[k].y;
            if(h[y]==h[x]+1 and e[k].c)
            {
                int out=dfs(y,min(flow-tt,e[k].c));
                e[k].c-=out;e[oth(k)].c+=out;tt+=out;
            }
            if(tt==flow) break;
        }
        if(!tt) h[x]=0;
        return tt;
    }
    const int dx[4]={0,0,-1,1};
    const int dy[4]={-1,1,0,0};
    int cost[N][N],beneft[N][N];char str[N];
    int to(char c){return ('0'<=c and c<='9'?c-'0':('a'<=c and c<='z'?10+c-'a':36+c-'A'));}
    void main()
    {
        int n=qread(),m=qread();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for(int j=1;j<=m;j++) cost[i][j]=to(str[j]);
        }int ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for(int j=1;j<=m;j++) beneft[i][j]=to(str[j]),ans+=beneft[i][j];
        }
        st=0,ed=N*N-1;int T=m+10,TT=T*(n+2)+10;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        {
            int id=T*i+j;
            for(int pp=0;pp<4;pp++)
            {
                int tx=i+dx[pp],ty=j+dy[pp];if(tx<1 or tx>n or ty<1 or ty>m) continue;
                if((i+j)&1) ins(TT*2+id,TT*3+T*tx+ty,INF);
                else ins(T*tx+ty,TT+id,INF);
            }
            if((i+j)&1) ins(st,id,cost[i][j]),ins(id,TT+id,INF),ins(TT+id,TT*2+id,beneft[i][j]);
            else ins(TT+id,TT*2+id,beneft[i][j]),ins(TT*2+id,TT*3+id,INF),ins(TT*3+id,ed,cost[i][j]);
        }
        while(bfs())
        ans-=dfs(st,INF);
        write(ans);
    }
};
int main()
{
    freopen("a.in","r",stdin);
    srand(time(0));
    mine::main();
}

中学生网格题

题目
题意：
n*m的网格，每个格子可以填1~k
定义两行是相似的，当将各行中的数升序排序后，完全一致
问使得各行两两不相似的方案数
对1e9+7取模

做法一：理论运算次数5亿，常数拉满且带模，不过我卡过去了（943ms），分享一下

考虑一行的合法情况，如果枚举m的分拆数（2e5），那么会产生 $tmp=\frac{tot!}{\prod (cnt_i!)}*C_k^{tot}$ 个本质不同的行（注意不是P，因为分拆方案可能某数字多次出现），但他们的可选择方案数都是$pp=\frac{m!}{\prod (a_i!)}$ （a是m的分拆，cnt是某个数字i在a中出现次数，tot为拆分成多少个不同的数），正确性自己思考一下，就是多重集排列；于是每次做一个n方的dp，考虑在这种拆分下选多少个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define double long double//不加会wa一个点
double ff[N];
ll f[N],fac[N],facinv[N],inv[N],gg[N];int n,m,k;
void dfs(int now,int mi,ll pp,ll tot,ll tmp,double real)
{
    if(tot>k) return;
    if(now==0)//tmp种本质不同的行，这些行的方案每个都是pp种
    {
        tmp=tmp*facinv[k-tot]%MOD;real=real/ff[k-tot];
        gg[0]=1;for(int i=1;i<=n;i++) gg[i]=gg[i-1]*(tmp+MOD-i+1)%MOD*inv[i]%MOD*pp%MOD;
        for(int i=n;i>=1;i--) for(int j=i-1;j>=0;j--)
        {
            if(i-j>real) break;
            f[i]=(f[i]+f[j]*gg[i-j])%MOD;
        }
        return;
    }
    for(int i=mi;i<=now;i++) for(int cnt=1,pp2=pp*facinv[i]%MOD;cnt*i<=now and tot+cnt<=k;cnt++,pp2=pp2*facinv[i]%MOD)
        dfs(now-i*cnt,i+1,pp2,tot+cnt,tmp*facinv[cnt]%MOD,real/ff[cnt]);
}
void main()
{
    fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
    facinv[N-1]=invm(fac[N-1]);for(int i=N-2;i>=0;i--) facinv[i]=facinv[i+1]*(i+1)%MOD;
    inv[1]=1;for(int i=2;i<N;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    ff[0]=1;for(int i=1;i<N;i++) ff[i]=ff[i-1]*i;
    n=qread(),m=qread(),k=qread();
    f[0]=1;dfs(m,1,fac[m],0,fac[k],ff[k]);write(f[n]*fac[n]%MOD);
}

做法二：$O(n^4)$，注意到枚举具体分拆限制了复杂度，考虑用dp而不是dfs

首先做一个简单dp搞出$g(n)$表示n行相似的方案数，转移考虑枚举每种数字出现次数就好了，$O(n^4) $

然后考虑容斥dp，将行分拆成若干组，每组内相似，组间互不相似；你发现我们只需要计算组大小形如$1,1,1…lst(lst \ge1)$这样的分拆就可以了

设$f(a,lst)$表示前面有a个1，考虑前面哪个和最后那个相似，$f(a,lst)=f(a-1,1)*g(lst)-a*f(a-1,lst+1)$

$ans=f(n-1,1)，O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll fac[N],facinv[N],fi[N][N];
ll g[N],tmp[N],f[N][N];
void main()
{
    fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
    facinv[N-1]=invm(fac[N-1]);for(int i=N-2;i>=0;i--) facinv[i]=facinv[i+1]*(i+1)%MOD;
    for(int i=0;i<N;i++) {fi[i][1]=facinv[i];for(int j=2;j<N;j++)fi[i][j]=fi[i][j-1]*fi[i][1]%MOD;}
    int n=qread(),m=qread(),k=qread();
    for(int i=1;i<=n;i++)
    {
        memset(tmp,0,sizeof tmp);tmp[0]=1;
        for(int num=1;num<=k;num++)
            for(int x=m;x>=1;x--) for(int y=0;y<x;y++)
                tmp[x]=mm(tmp[x]+tmp[y]*fi[x-y][i]%MOD);
        g[i]=tmp[m]*qpower(fac[m],i)%MOD;
    }
    for(int lst=1;lst<=n;lst++) f[0][lst]=g[lst];
    for(int i=1;i<n;i++) for(int lst=1;lst<=n;lst++) f[i][lst]=(f[i-1][1]*g[lst]+MOD-i*f[i-1][lst+1]%MOD)%MOD;
    write(f[n-1][1]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/1f5d.html
转载请注明出处，谢谢！