2019-2020 Winter Petrozavodsk Camp, Day 8 Almost Algorithmic Contest 题解

发表于 | 评论数： | 阅读次数：
Solved A B C D E F G H I J K L
9/12 Ø Ø O . O O O O O . . Ø
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

比赛链接

毛营题好难！而且全是数学题，还卡常…

A

题目描述

给定一个 $n_1,n_2,m\le 2e6$ 的二分图，求近似最大匹配，要求大于等于真实值的 $0.95$ 倍。

解题思路

大力卡常数，暴力地卡时限跑 Hopcroft-Karp 进行匹配，很勉强能在 3.5s 通过所有数据。头一次见到时限开和标程等同的题。

这题主要记一个结论：如果最大匹配为 $K$，跑了匹配 $k$ 次 Dinic 或者 HK 的答案至少为 $\frac{k}{k+1}K$。因此跑前 $19$ 次就是对的。证明看不懂，在题解中。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 4000010
#define M 4000010
struct Edge{
    int e,n;
}e[M];
int hd[M],cnt=1;
int n1,n2;
void add(int a,int b){
    e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
    e[++cnt].e=a;e[cnt].n=hd[b];hd[b]=cnt;
}
int dep[M],mat[M];
queue<int>Q;
bool dfs(int p){
    int i;
    for(i=hd[p];i;i=e[i].n){
        int q=e[i].e;
        if(dep[q]!=dep[p]+1)continue;
        dep[q]=0;
        if(mat[q]==-1||dfs(mat[q])){
            mat[q]=p;mat[p]=q;
            return 1;
        }
    }
    return 0;
}
bool bfs(){
    int i;
    memset(dep,0,sizeof(int)*(n1+n2+1));
    queue<int>Q;
    for(i=1;i<=n1;i++)if(mat[i]==-1)Q.push(i);
    bool flag=0;
    while(!Q.empty()){
        int p=Q.front();Q.pop();
        for(i=hd[p];i;i=e[i].n){
            int q=e[i].e;
            if(!dep[q]){
                dep[q]=dep[p]+1;
                if(mat[q]==-1)flag=1;
                else dep[mat[q]]=dep[q]+1,Q.push(mat[q]);
            }
        }
    }
    return flag;
}
double start=0;
int hk(){
    int i,j,ans=0;
    for(j=0;j<19;j++){
        if(!bfs())break;
        for(i=1;i<=n1;i++)
            if(mat[i]==-1&&dfs(i))
                ans++;
        if((clock()-start)*1.0/CLOCKS_PER_SEC+ans/2000000.0>=3.3)break;
    }
    return ans;
}
int read(){
    int res=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0',c=getchar();
    return res;
}
int u[M],v[M];
int main(){
    int i,m;
    vector<int>ans;
    start=clock();
    n1=read();n2=read();m=read();
    for(i=0;i<m;i++){
        u[i]=read();v[i]=read();
        add(u[i],v[i]+n1);
    }
    for(i=1;i<=n1+n2;i++)mat[i]=-1;
    int res=hk();
    printf("%d\n",res);
    for(i=0;i<m;i++){
        int _u=u[i],_v=v[i];
        if(mat[_u]==_v+n1)ans.pb(i+1);
    }
    assert(res==ans.size());
    for(auto q:ans)printf("%d\n",q);
    return 0;
}

B

题目描述

给一个长度为 $n\le 2e5$ 的小写字母串，对于每一个 $k\in[1,n]$，计算 $f(k)$。

其中，$f(k)$ 表示，将串切成 $\lfloor\frac nk\rfloor$ 段，每段长度为 $k$ 的子串，有多少对子串的汉明距离 $\le 1$。

解题思路

常规套路进行分块。

$k\le \lfloor\sqrt n\rfloor$ 时，对于每个 $k$ 可以 $O(n)$ 暴力计算，总复杂度 $O(n\sqrt n)$

$k> \lfloor\sqrt n\rfloor$ 时，每次有 $O(\sqrt n)$ 个子串，两两之间进行 $O(1)$ 判断，总复杂度同样为 $O(n\sqrt n)$

使用字符串哈希。线性暴力计算的做法大概是，相同和距离为 $1$ 两种情况分别处理，后者只需要枚举每一位将其哈希值清零即可，可以用 $vector$ 排序的小常数 $\log$ 或者大常数哈希。两两间 $O(1)$ 判断时，可以预处理出来每一位的差值，用哈希表存一下，但是常数大过不了；也可以求出两串 $lcp$ ，然后对于后半段进行相等的哈希判断。

常数巨大，需要卡常。

AC代码

点击
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 200010
#define P 26
ll qp(ll a,int p,int mod){
    ll ans=1;
    for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
    return ans;
}
namespace string_hash{
    const int mod1=991145149;
    const int mod2=998244353;
    const int bas1=233;
    const int bas2=10007;
    struct pair_hash{
        template<class T1,class T2>
		size_t operator()(const pair<T1,T2>&p)const{
            return hash<T1>{}(p.fi)^hash<T2>{}(p.se);
        }
    };
    int pw1[N],inv1[N],pw2[N],inv2[N],h1[N],h2[N];
    pii gethash(int l,int r){
        int has1=1LL*(h1[r]-(l?h1[l-1]:0)+mod1)*inv1[l]%mod1;
        int has2=1LL*(h2[r]-(l?h2[l-1]:0)+mod2)*inv2[l]%mod2;
        return mp(has1,has2);
    }
    char s[N];
    void inithash(){
        int i;
        pw1[0]=inv1[0]=1;
        pw2[0]=inv2[0]=1;
        for(i=1;i<N;i++){
            pw1[i]=pw1[i-1]*1LL*bas1%mod1;
            pw2[i]=pw2[i-1]*1LL*bas2%mod2;
            inv1[i]=qp(pw1[i],mod1-2,mod1);
            inv2[i]=qp(pw2[i],mod2-2,mod2);
        }
        for(i=0;s[i];i++){
            h1[i]=((i?h1[i-1]:0)+1LL*(s[i]-'a')*pw1[i])%mod1;
            h2[i]=((i?h2[i-1]:0)+1LL*(s[i]-'a')*pw2[i])%mod2;
        }
    }
}
using namespace string_hash;
namespace sa{
    char s[N];
    int n,sa[N],c[N],x[N],y[N];
    void getsa(int m){
        int i,k;
        for(i=0;i<=n&&i<N;i++)x[i]=y[i]=0;
        for(i=0;i<=m;i++)c[i]=0;
        for(i=1;i<=n;i++)c[x[i]=s[i]-'a']++;//also x[i]=s[i]-'a'
        for(i=1;i<=m;i++)c[i]+=c[i-1];
        for(i=n;i;i--)sa[c[x[i]]--]=i;
        for(k=1;k<=n;k<<=1){
            int p=0;
            for(i=n-k+1;i<=n;i++)y[++p]=i;
            for(i=1;i<=n;i++)if(sa[i]>k)y[++p]=sa[i]-k;
            for(i=0;i<=m;i++)c[i]=0;
            for(i=1;i<=n;i++)c[x[y[i]]]++;
            for(i=1;i<=m;i++)c[i]+=c[i-1];
            for(i=n;i;i--)sa[c[x[y[i]]]--]=y[i];
            swap(x,y);
            p=x[sa[1]]=1;
            for(i=2;i<=n;i++)
                x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
            if(p>=n)break;
            m=p;
        }
    }
    int h[N],rnk[N];
    void geth(){
        int i,j,k=0;
        for(i=1;i<=n;i++)rnk[sa[i]]=i;
        for(i=1;i<=n;i++){
            if(k)k--;
            j=sa[rnk[i]-1];
            while(s[i+k]==s[j+k])k++;
            h[rnk[i]]=k;
        }
    }
    int rmq[N][23],lg[N];
    void initlcp(int _n){
        int i,j;
        n=_n;
        for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
        getsa(260);
        geth();
        for(i=1;i<=n;i++)rmq[i][0]=h[i];
        for(i=1;i<=22;i++)
            for(j=1;j+(1<<i-1)<=n;j++)
                rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<i-1)][i-1]);
    }
    int getlcp(int x,int y){
        if(x==y)return n-x+1;
        if(rnk[x]>rnk[y])swap(x,y);
        int l=rnk[x]+1,r=rnk[y];
        int p=lg[r-l+1];
        return min(rmq[l][p],rmq[r-(1<<p)+1][p]);
    }
}
int main(){
    int i,j,k,n;
//	n=200000;
//	for(i=0;i<n;i++)s[i]='a';
 	scanf("%d%s",&n,s);
 	strcpy(sa::s+1,s);
 	sa::initlcp(n);
 	inithash();
    
    int sq=sqrt(n)/2+1;
    for(i=1;i<=sq;i++){
        ll same=0,_same=0; 
        vector<pii>v;
        // same
        for(j=0;j<n/i;j++){
            int l=j*i,r=j*i+i-1;
            auto pr=gethash(l,r);
            v.pb(pr);
        }
        sort(v.begin(),v.end());
        for(j=0;j<v.size();j++){
            int cnt=1;
            while(j+1<v.size()&&v[j+1]==v[j])j++,cnt++;
            same+=cnt*(cnt-1LL)/2;
        }
        // almost same
        v.clear();
        for(j=0;j<n/i;j++){
            int l=j*i,r=j*i+i-1;
            auto pr=gethash(l,r);
            int has1=pr.fi,has2=pr.se;
            for(k=l;k<=r;k++){
                // wildcard 
                int tmphas1=has1-1LL*(s[k]-'a')*pw1[k-l]%mod1;
                tmphas1=(tmphas1+27LL*pw1[k-l]%mod1+mod1)%mod1;
                int tmphas2=has2-1LL*(s[k]-'a')*pw2[k-l]%mod2;
                tmphas2=(tmphas2+27LL*pw2[k-l]%mod2+mod2)%mod2;
                v.pb(mp(tmphas1,tmphas2));
            }
        }
        sort(v.begin(),v.end());
        for(j=0;j<v.size();j++){
            int cnt=1;
            while(j+1<v.size()&&v[j+1]==v[j])j++,cnt++;
            _same+=cnt*(cnt-1LL)/2;
        }
        ll ans=same+_same-i*same;
        printf("%lld ",ans); 
    }
// 	printf("%lf\n",1.0*clock()/CLOCKS_PER_SEC);
    for(;i<=n;i++){
        vector<pii>hs;
        int ans=0;
        for(j=0;j<n/i;j++){
            for(k=0;k<j;k++){
                int l1=j*i,r1=j*i+i-1;
                int l2=k*i,r2=k*i+i-1;
                int lcp=sa::getlcp(l1+1,l2+1);
                if(lcp>=i-1)ans++;
                else if(gethash(l1+lcp+1,r1)==gethash(l2+lcp+1,r2))ans++;
            }
        }
        printf("%d ",ans);
    }
// 	printf("%lf\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}

C

题目描述

给定长度为 $n\le 5e5$ 的排列 $a$。从左到右扫，如果当前元素比上一个元素大，那保留这个元素；否则，可以选择删除上一个元素或者删除本元素，但要求序列保持单调递增。问最后删掉的元素最少是多少。

如：$645123$，就可以 $6$，删掉 $4$，删掉 $5$，删掉 $6$ 加上 $1$，加上 $2$，加上 $3$，最终长度为 $3$。

解题思路

假设固定了 $i$ 没有删，设 $f_i$ 表示固定了 $i$ 的最长长度，看看 $i$ 能对哪些 $j>i$ 做贡献。设 $nxt_i$ 表示最小且满足 $a_j>a_i$ 的 $j$，则 $i$ 可以转移到 $[nxt_i,nxt_{nxt_i})$ 区间，即下标 $[l_i,r_i]$ 值域 $[a_i,\infty)$ 的二维数点。

开始的想法是在值域上开一棵权值线段树，则每一个 $i$ 对于一段下标序列有贡献，可以线段树分治配合动态开点线段树求解，点数是 $O(4n+n\log^ 2n)$，时空复杂度都有两个 $\log $，感觉过不太了。

但发现，直接对 $a_i$ 从小到大枚举 $i$，就可以贡献整个未计算的区间，于是直接线段树维护就好了。复杂度 $O(n\log n)$。

对于 $f_i$ 的初始值，可以设一个无穷小的原点 $0$，这样从 $0$ 开始更新就可以了。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 500010
int nxt[N],a[N],f[N];
int sta[N],top;
int mx[N<<2],L[N<<2],R[N<<2],lazy[N<<2];
void pushup(int p){
    mx[p]=min(mx[p<<1],mx[p<<1|1]);
}
void pushdown(int p){
    int t=lazy[p];
    if(!t)return;
    if(mx[p<<1]<t){
        mx[p<<1]=t;
        lazy[p<<1]=t;
    }
    if(mx[p<<1|1]<t){
        mx[p<<1|1]=t;
        lazy[p<<1|1]=t;
    }
    lazy[p]=0;
}
void build(int p,int l,int r){
    L[p]=l;R[p]=r;
    if(l==r){
        mx[p]=-1e9;
        return;
    }
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
    pushup(p);
}
int query(int p,int l){
    if(L[p]>l||R[p]<l)return 0;
    if(L[p]==R[p])return mx[p];
    pushdown(p);
    return query(p<<1,l)+query(p<<1|1,l);
} 
void modify(int p,int l,int r,int x){
    if(L[p]>r||R[p]<l||mx[p]>x)return;
    if(L[p]>=l&&R[p]<=r){
        mx[p]=x;
        lazy[p]=x;
        return;
    }
    pushdown(p);
    modify(p<<1,l,r,x);
    modify(p<<1|1,l,r,x);
    pushup(p);
}
int p[N];
int main(){
    int i,j,n;
    scanf("%d",&n);n++;
    for(i=2;i<=n;i++)scanf("%d",&a[i]),a[i]++;
    a[n+1]=n+1;
    a[1]=1;
    for(i=1;i<=n+1;i++){
        while(top&&a[sta[top]]<a[i]){
            nxt[sta[top]]=i;
            top--;
        }
        sta[++top]=i;
    }
    build(1,1,n);
    // init f
    memset(f,-1,sizeof(f));
    f[1]=1;
    // enumerate from low a to high a
    for(i=1;i<=n;i++)p[i]=i;
    sort(p+1,p+1+n,[&](const int&x,const int&y){return a[x]<a[y];});
    for(j=1;j<=n;j++){
        i=p[j];
        if(f[i]==-1)f[i]=query(1,i);
        int t1=nxt[i],t2=nxt[t1]-1;
        modify(1,t1,t2,f[i]+1);
    }
    printf("%d",n-*max_element(f+1,f+1+n));
    return 0;
}

按照第一种方式实现了一下，比较有趣。$1e5$ 的点就占用了 $500M$ 内存。

MLE代码

点击
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 800010
int nxt[N],a[N],f[N];
int sta[N],top;
int mn[N<<5],lazy[N<<5],root[N<<5],ls[N<<5],rs[N<<5],tot,n;
void pushdown(int);
int newnode(int fa){
    pushdown(fa);
    ++tot;
    assert(tot<N<<5);
    mn[tot]=mn[fa];
    assert(lazy[fa]==0);
    lazy[tot]=0;
    ls[tot]=ls[fa];
    rs[tot]=rs[fa];
    return tot;
}
void pushup(int p){
    mn[p]=min(mn[ls[p]],mn[rs[p]]);
}
void update(int p,int x){
    if(mn[p]<x){
        mn[p]=max(mn[p],x);
        if(!lazy[p]||lazy[p]<x)
            lazy[p]=x;
    }
}
void tag(int&p,int fa,int x){
    if(!p){
        p=newnode(fa);
        update(p,x);
        return;
    }
    update(p,x);
}
void pushdown(int p){
    int t=lazy[p];
    if(!t)return;
    int lson=ls[p],rson=rs[p];
    ls[p]=rs[p]=0;
    tag(ls[p],lson,t);
    tag(rs[p],rson,t);
    lazy[p]=0;
}
void build(int& p,int l,int r){
    if(!p)p=newnode(0);
    mn[p]=-1e9;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(ls[p],l,mid);
    build(rs[p],mid+1,r);
    pushup(p);
}
void modify(int&rt,int fa,int l,int r,int ql,int qr,int id){
    assert(qr>=l&&ql<=r);
    pushdown(fa);
    if(!rt)rt=newnode(fa);
    if(l>=ql&&r<=qr){
        tag(rt,fa,f[id]+1); // f[id] has been calculated
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(ql<=mid){
        int lson=ls[rt];
        ls[rt]=0;
        modify(ls[rt],lson,l,mid,ql,qr,id);
    }
    if(qr>mid){
        int rson=rs[rt];
        rs[rt]=0;
        modify(rs[rt],rson,mid+1,r,ql,qr,id);
    }
    pushup(rt);
}
struct Q{
    int l,r,id;
};
int query(int& rt,int fa,int l,int r,int ql){
    pushdown(fa);
    if(!rt)rt=newnode(fa);
    if(l==r)return mn[rt];
    int mid=(l+r)>>1;
    pushdown(rt);
    if(ql<=mid)return query(ls[rt],ls[fa],l,mid,ql);
    else return query(rs[rt],rs[fa],mid+1,r,ql);
}
void dfs(int p,int l,int r,vector<Q>&queries){
    vector<Q>vl,vr;
    int mid=(l+r)>>1;
    int tmptot=tot;
    pushdown(root[p/2]);
    root[p]=newnode(root[p/2]);
    for(auto q:queries){
        if(q.l<=l&&q.r>=r)
            modify(root[p],root[p/2],1,n,a[q.id]+1,n,q.id);
        else{
            if(q.l<=mid)vl.pb(q);
            if(q.r>mid)vr.pb(q);
        }
    }
    if(l==r){
        // calculate f[l]
        f[l]=query(root[p],root[p/2],1,n,a[l]);
        return;
    }
    dfs(p<<1,l,mid,vl);
    dfs(p<<1|1,mid+1,r,vr);
}
int main(){
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    a[n+1]=n+1;
    a[0]=0;
    for(i=0;i<=n+1;i++){
        while(top&&a[sta[top]]<a[i]){
            nxt[sta[top]]=i;
            top--;
        }
        sta[++top]=i;
    }
    build(root[0],1,n);
    vector<Q>v;
    for(i=0;i<=n;i++){
        if(nxt[i]>n)continue;
        int t1=nxt[i],t2=nxt[t1]-1;
        // j\in [t1,t2), a[j]>=a[i]
        v.pb(Q{t1,t2,i});
    }
    for(i=1;i<=n;i++)f[i]=-1e9;
    f[0]=1;
    dfs(1,1,n,v);
//	for(i=1;i<=n;i++)printf("%d ",f[i]);
    printf("%d",n-*max_element(f+1,f+1+n)+1);
    return 0;
}

D

题目描述

解题思路

AC代码

点击
1
2


E

题目描述

有一个 $n\le 8000$ 排列 $p$，你不知道这个 $p$。一共有 $2n$ 次操作，每次加入一个元素或者删掉一个元素，你要维护这个集合。每次可以询问不超过 $30$ 个该集合中元素的大小关系，保证每个元素仅会被插入和删除各一次。每一次操作后，输出集合中的最小元素。

解题思路

维护一棵线段树，每次仅会有 $O(\log n)$ 个元素，进行询问即可。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 32010
int L[N],R[N],mn[N];
void build(int p,int l,int r){
    L[p]=l;R[p]=r;
    mn[p]=0;
    if(l==r){
        mn[p]=0;
        return;
    }
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
}
set<int>v;
void getnodes(int p,int l,int op){
    if(L[p]>l||R[p]<l)return;
    if(L[p]==R[p]){
        if(op)mn[p]=L[p],v.insert(L[p]);
        else mn[p]=0;
        return;
    }
    if(l<=R[p<<1]){
        getnodes(p<<1,l,op);
        if(mn[p<<1|1])v.insert(mn[p<<1|1]);
    }
    else{
        getnodes(p<<1|1,l,op);
        if(mn[p<<1])v.insert(mn[p<<1]);
    }
}
char s[10];
int a[40],pos[N];
void pushup(int p){
    int x1=mn[p<<1],x2=mn[p<<1|1];
    if(!x1)mn[p]=mn[p<<1|1];
    else if(!x2)mn[p]=mn[p<<1];
    else{
        if(pos[x1]<pos[x2])mn[p]=x1;
        else mn[p]=x2;
    }
}
void process(int p,int l,int op){
    if(L[p]>l||R[p]<l)return;
    if(L[p]==R[p])return;
    process(p<<1,l,op);
    process(p<<1|1,l,op);
    pushup(p);
}
int main(){
    int x,i,j,n,op;
    scanf("%d",&n);
    build(1,1,n);
    for(i=0;i<2*n;i++){
        scanf("%s%d",s,&x);
        if(s[0]=='a')op=1;
        else op=0;
        v.clear();
        getnodes(1,x,op);
        
        printf("%d",v.size());
        for(auto p:v)printf(" %d",p);
        puts("");fflush(stdout);
        
        for(j=0;j<v.size();j++){
            scanf("%d",&a[j]);
            pos[a[j]]=j;
        }
        
        process(1,x,op);
        if(!mn[1])printf("-1\n");
        else printf("%d\n",mn[1]);
        fflush(stdout);
    }
    return 0;
}

F

题目描述

有一个 $n\le 1e5,m\le 3e5$ 的平面图，问是否所有面（包括最外面）都为三角形。

解题思路

根据欧拉定理，有 $F+V-E=2$。当所有面都为三角形时，每条边在两个三角形中，有 $3F= 2E$，即 $E=3V-6$。这是一个充要条件，直接判断即可。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    if(m==3*n-6)printf("YES");
    else printf("NO"); 
    return 0;
}

G

题目描述

一个 $n\in[40,1e5]$ 的元排列，通过 $n-k+1$ 次操作，每次操作将 $[i,i+k-1]$ 中元素随机重排，获得排列 $a$。给定 $a$，问 $k$ 是多少。保证 $20k\le n$。

解题思路

经典问题，考虑 $i$ 的去向： $[i-k+1,i+k-1]$。全部元素都没有到 $i-k+1$ 的概率很低，为 $(1-\frac 1{2k})^n=((1-\frac 1{2k})^{2k})^{\frac n{2k}}=(\frac 1e)^{\frac n{2k}}\le (\frac 1e)^{10}$。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
int main(){
    int i,n,ans=0,p;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&p);
        ans=max(ans,p-i+1);
    }
    printf("%d",ans);
    return 0;
}

H

题目描述

给一个 $n\times m(2\le n,m\le 50)$ 的矩阵，将矩阵上下、左右分别粘起来变成一个圆环结构。

每一个位置有元素 $a_{i,j}\in[0,500]$。可以进行任意次操作，每次将某整行或某整列元素都加某个值。最后获得的矩阵中，定义分数为相邻两个元素相同的对数。最大化这个分数。

解题思路

行列操作互不影响，拆开考虑，以下仅讨论对于整行的增加对于同列不同行的相邻元素贡献。

设 $f_i$ 表示第 $i$ 行相较于 $i+1$ 行整体增加的数量，$cnt_{i,k}$ 表示 $a_{i+1,j}-a_{i,j}=k$ 的 $j$ 个数，则 $(i,i+1)$ 两行对答案的贡献为 $cnt_{i,f_i}$。因此，就是要求 $\sum_{i}f_i=0$ 条件下， $\sum_{i}cnt_{i,f_i}$ 的最大值。

每一行中 $cnt$ 有 $O(n)$ 处不为零；总的值域大小不会超过 $O(1000n)$。因此可以得到一个 $O(1000n^2m)$ 的背包。但这其中要求每次 $f_i$ 都在 $[-500,500]$ 范围内；需要处理某个 $f_i$ 不在该范围内的情况。

对于某个 $f_i$ 超出范围的情况，$cnt_{i,f_i}$ 肯定为 $0$ ，于是可以贪心求解，找出每一行 $cnt$ 的最大值，贪心地取前 $n-1$ 个，用最后一个进行中和。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 52
#define M 502
int h[N][N],ht[N][N],f[N][M<<1],g[N][M*N*2];
set<int>s[N];
int id(int x){return x+M;}
int _id(int x){return x-M;}
int id2(int x){return x+M*N;}
int _id2(int x){return x-M*N;}
int solve(int h[][N],int n,int m){
    int i,j;
    // knapsack
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++){
        s[i].clear();
        for(j=1;j<=m;j++){
            int delta=h[i][j]-h[i%n+1][j];
            s[i].insert(id(delta));
            f[i][id(delta)]++;
        }
    }
    memset(g,-1,sizeof(g));
    memset(g[1],0,sizeof(g[1]));
    for(j=0;j<M*2;j++)g[1][id2(_id(j))]=f[1][j];
    for(i=2;i<=n;i++){
        memcpy(g[i],g[i-1],sizeof(g[i])); // from 0
        for(auto x:s[i]){
            int delta=_id(x);
            for(j=max(0,delta);j<M*N*2&&j-delta<M*N*2;j++){
                if(g[i-1][j-delta]<0)continue;
                g[i][j]=max(g[i][j],g[i-1][j-delta]+f[i][x]);
            }
        }
    }
    // greedy
    int greedy=0;
    multiset<int>S;
    for(i=1;i<=n;i++){
        int x=*max_element(f[i],f[i]+M*2);
        S.insert(x);
    }
    for(auto x:S)greedy+=x;
    greedy-=*S.begin();
    
    return max(g[n][id2(0)],greedy);
}
int main(){
    int i,j,k,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            scanf("%d",&h[i][j]);
            ht[j][i]=h[i][j];
        }
    int ans=solve(h,n,m)+solve(ht,m,n);
    printf("%d\n",ans);
    return 0;
}

I

题目描述

给定 $d,k\le 10^{100}$，求 $\gcd_{x=1}^{\infty}((x+d)^k-x^k)$ 。

解题思路

$(x+d)^k-x^k=\sum_{i=1}^{k}d^i\binom{k}{i}x^{k-i}$

逐个 $d$ 的质因数 $p$ 进行考虑。显然，答案中的质数都为 $d$ 的质因数。于是设 $p^q|d,p^a|k,p^{b_i}|\binom{k}{i} $。由卢卡斯定理，$b_i=a-f_i$，其中 $p^{f_i}|i$。如果 $p^y$ 为和式中恰好一项的因数且最小，那么 $p$ 对答案贡献为 $p^y$。（为简化表示，所有整除符号都代表了最高次幂）

于是考虑，这个最小项为第一项的情况，即最小项出自 $dkx^{k-i}$。第 $i$ 项中 $p$ 的指数为 $iq+a-f_i$。要有 $iq+a-f_i>q+a(i>1)$，需要 $(i-1)q<f_i$。由于 $f_i\le i$，故 $q>1$ 时显然。

考虑 $q=1$ 的情况，感性理解，$p$ 如果很大，那么 $q=1$ 的时候也满足。打表发现仅当 $p=2$ 时出现不满足，当 $k=1(a=0)$ 的时候贡献为 $2^1$，$k=2(a=1)$ 的时候贡献为 $2^3$，$a\ge 2$ 时贡献为 $2^{a+2}$。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
d,k=map(int,input().split())
td=d
tk=k
c1=0
c2=0
while td%2==0:
    td//=2
    c1+=1
while tk%2==0:
    tk//=2
    c2+=1
 
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)
 
 
ans=td*gcd(td**320,tk)
if c1>=2:
    ans=ans*2**(c1+c2)
elif c1==1:
    ans=ans*2**(min(k,c2+2))
print(ans)

J

题目描述

解题思路

AC代码

点击
1
2


K

题目描述

解题思路

AC代码

点击
1
2


L

题目描述

给一个 $n\le 1e6$ 的非负序列 $a_i\in[0,1e18]$，其中有些位置的元素待填。要求对于每个位置 $i\in[1,n-1]$，$a_ia_{i+1}\min(a_i,a_{i+1})\le C$。问有多少种填元素的方法。如果无数种方案，输出 $-1$。

解题思路

如果已填元素中有不符合要求的，方案为零。如果一个待填元素周围都是待填元素或者 $0$，那么有无数种方法。剩下的情况仅有两种：

  1. $a?b$
  2. $a??b$

对于第一种情况，可以根据左右分别求出两个区间，取 $\min$ 即可。

对于第二种情况，求出左右两个未知元素 $x,y$ 的合法区间（设分别为 $x\in[0,A],y\in[0,B]$），而且要两个未知元素 $x,y$ 满足题中条件。题中条件画出来是两段以 $x=y$ 对称的曲线，且与 $x=y$ 的交点为 $\sqrt[3]{C}$，要求的就是这个曲线和两个边界 $A,B$ 构成图像中整点个数。因此对于每个 $x\le \sqrt[3]C$ 预处理一下整点个数，询问时二分即可。

AC代码

点击
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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<cassert>
#include<ctime>
#include<bitset>
typedef long long ll;
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 1000010
const int mod=998244353;
ll a[N],b[N];
ll s[N],f[N];
ll c,tr;
ll border(ll x){
    if(!x)return 4e18;
    if(x>tr){
        return (ll)(sqrt(c)/sqrt(x));
    }else{
        return c/(x*x);
    }
}
int main(){
    int i,n;
    scanf("%d%lld",&n,&c);
    while((tr+1)*(tr+1)*(tr+1)<=c)tr++;
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=a[i];
        if(a[i]==-1)b[i]=0;
    }
    // no solution
    for(i=1;i<n;i++)
        if(a[i]!=-1&&a[i+1]!=-1){
            ll x=min(a[i],a[i+1]),y=max(a[i],a[i+1]);
            if(1.0*x*x*y>1e18||x*x*y>c)return printf("0"),0;
        }
    // 0 -1 0, inf
    for(i=1;i<=n;i++)
        if(a[i]==-1&&!b[i-1]&&!b[i+1])
            return printf("-1"),0;
    // prepare sum
    for(i=1;i<=tr;i++){
        ll y=c/(1LL*i*i);
        s[i]=(s[i-1]+(y-tr))%mod;
        f[tr-i+1]=y;
    }
    // calculate
    ll ans=1;
    for(i=1;i<=n;i++){
        if(a[i]==-1&&a[i-1]!=-1){
            if(a[i+1]==-1){
                ll A=border(a[i-1]);
                ll B=border(a[i+2]);
                ll tmp=0;
                if(A>tr&&B>tr){
                    int id=tr+1-(lower_bound(f+1,f+1+tr,A)-f);
                    tmp=(s[tr]-s[id]+mod+id*(A%mod-tr+mod)%mod)%mod;
                    id=tr+1-(lower_bound(f+1,f+1+tr,B)-f);
                    tmp=(tmp+s[tr]-s[id]+mod+id*(B%mod-tr+mod)%mod)%mod; // [1,id]*[tr+1,B]
                    tmp=(tmp+tr*tr%mod)%mod; // [1,tr]*[1,tr]
                    tmp=(tmp+A+B+1)%mod; // 0
                }else if(A<=tr&&B<=tr){
                    tmp=(A+1)*(B+1)%mod;
                }else{
                    if(A>B)swap(A,B);
                    int id=tr+1-(lower_bound(f+1,f+1+tr,B)-f);
                    if(id>A){
                        tmp=(A%mod+1)*(B%mod+1)%mod;
                    }else{
                        tmp=(s[A]-s[id]+mod)%mod;
                        tmp=(tmp+(id+1)*(B%mod+1)%mod)%mod;
                        tmp=(tmp+(A-id)*(tr+1)%mod)%mod;
                    }
                }
                ans=ans*tmp%mod;
            }else{
                ll A=border(a[i-1]);
                ll B=border(a[i+1]);
                ans=ans*(min(A,B)%mod+1)%mod;
            }
        }
//		printf("%lld\n",ans);
    }
    printf("%lld",ans);
    return 0;
}