XXI Open Cup named after E.V. Pankratiev. Grand Prix of NorthBeach

发表于

最后1h过了两题。不过最后是双开，不然应该过不了这么多。

想得还是太慢了。代码实现能力也差了一点。

A. Arrange and Count!

以后都给我写双哈希！！

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x)
{
	x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASET int ___;for(read(___);___--;)

ll Mod[2]={998244853,1004535809};
ll mod;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}

const int N=2e5+5;
ll base=1e5+19;
map<pair<ll,ll>,int> ma;
ll pw[N],f[N],a[N],g[N][2];

inline ll get(int l,int r)
{
	return Dec(f[r],f[l-1]*pw[r-l+1]%mod);
}
int n;
int main()
{
	for(;~scanf("%d",&n);)
	{
		ma.clear();

		mod=Mod[0];
		pw[0]=1;
		fo(i,1,2*n) pw[i]=pw[i-1]*base%mod;
		fo(i,1,n) read(a[i]);
		fo(i,1,n) a[i+n]=a[i];
		fo(i,1,n+n) f[i]=(f[i-1]*base+a[i])%mod;
		fo(i,1,n) g[i][0]=get(i,i+n-1);
		reverse(a+1,a+n+n+1);
		fo(i,1,n+n) f[i]=(f[i-1]*base+a[i])%mod;
		fo(i,1,n) g[i][1]=get(i,i+n-1);

		reverse(a+1,a+n+n+1);
		mod=Mod[1];
		pw[0]=1;
		fo(i,1,2*n) pw[i]=pw[i-1]*base%mod;
		fo(i,1,n+n) f[i]=(f[i-1]*base+a[i])%mod;
		fo(i,1,n) ma[{get(i,i+n-1),g[i][0]}]++;
		reverse(a+1,a+n+n+1);
		fo(i,1,n+n) f[i]=(f[i-1]*base+a[i])%mod;
		fo(i,1,n) ma[{get(i,i+n-1),g[i][1]}]++;
		printf("%d\n",ma.size());
	}
	return 0;
}

B. Build More 2020’s!

不太会啊。。。

二分答案 $x$，维护 $x$ 个栈表示当前填的情况。

遇到 $0$ 优先填 $2$，遇到 $2$ 优先开一个。

时间复杂度 $O(n\log n)$。

C. Choose Two Subsequences

D. Determinant Strikes Back

线性代数基础题or找规律。

找规律/结论就不说了。

显然一个方阵 $A$ 的特征值为 $0$ 的数量为 $n-rank(A)$。因为特征值相当于沿着某个特征向量的放大倍数。

矩阵 $A_{ij}=a_ib_j$ 的秩显然为 $1$，因此原式一定为 $x^n+x^{n-1}\times K$ 的形式。然后就简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
int main()
{
	int n,x;
	for(;~scanf("%d%d",&n,&x);)
	{
		ll ans=x%mod;
		VI a(n+1),b(n+1);
		fo(i,1,n) read(a[i]);
		fo(i,1,n) read(b[i]);
		fo(i,1,n) ans=Add(ans,1ll*a[i]*b[i]%mod);
		printf("%lld\n",Pow(x,n-1)*ans%mod);
	}
	return 0;
}

E. Efficient Data Structure

$c_i=\max_j{a_j+b_{j+1}+b_{j+2}+\cdots+b_i}=s_i+\max_j{a_j-s_j}$，其中 $s_i=\sum_{j\le i} b_j$。

随便维护。

H. Hamming Distance

性质：$i$ 这个数的所有出现位置为 $2^{i-1}+k\cdot 2^{i},k\geq 0$。

距离和比较简单，枚举一下每个 $a_i$，算出其一左一右的位置就好了。

对于最小值，我们找到最小的 $k$ 使得 $2^k-1\geq n$。

那么 $n$ 个数不会跨越两个以上的 $S_k$ （注意这里需要稍微特判一下 $m$ 比较小的情况），而整个串必然是 $S_k+x_1+S_k+x_2+S_k+\cdots$ 这样的形式。

那么直接将大于 $k$ 的都看成 $k+1$，整个 $S_m$ 看成 $S_{k+1}$ 即可。

剩下的利用等差数列的性质，从 $1$ 到 $k+1$ 枚举每个数字，类似统计距离和的方法，使用个前缀和即可 $O(n\log n)$ 完成。

有一点细节。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x)
{
	x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASET int ___;for(read(___);___--;)

const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
const int N=(1<<19)+1;

ll pw[N];
int a[N];
int f[22][N],g[N];
inline void solve(int n,int m)
{
	fo(i,1,n) read(a[i]);
	int k=1;
	for(;(1<<k)-1<=n;k++);
	k++;
	ll ans2=Dec(pw[m],n)*n%mod;
	fo(i,1,n)
	{
		int x=a[i],k1=0,k2=0;
		if(x<=20)
			k1=(i+(1<<(x-1))-1)/(1<<x),
			k2=((n-i+1)+(1<<(x-1))-1)/(1<<x);
		if(x>20||(x<=20&&pw[m-x]>=k1+k2))
			ans2=Dec(ans2,Dec(pw[m-x],k1+k2));
	}

	if(n==pw[m]-1&&m<=20)
	{
		printf("%lld %lld\n",ans2,ans2);
		return;
	}
	fo(i,1,n) if(a[i]>=k) a[i]=k;
	auto get = [&](int x,int t){return (x*2+1)*(1<<(t-1));};
	fo(i,1,n)
	{
		int x=a[i],k1=0,k2=0;
		k1=(i+(1<<(x-1))-1)/(1<<x),
		k2=((n-i+1)+(1<<(x-1))-1)/(1<<x);
		if(pw[m-x]>=k1+k2)
		{
			f[x][get(k1,x)-i]++;
			int pos=get(pw[k-x]-k2,x)-i;
			if(pos<=pw[k]-1) f[x][pos]--;
		}
	}
	fo(x,1,k)
	{
		fo(j,(1<<x),(1<<k)-1) f[x][j]+=f[x][j-(1<<x)];
		fo(j,0,(1<<k)-1) g[j]+=f[x][j],f[x][j]=0;
	}
	int ans=0;
	fo(j,0,(1<<min(k,m))-n) ans=max(ans,g[j]);
	fo(j,0,(1<<k)-1) g[j]=0;
	ans=n-ans;
	printf("%d %lld\n",ans,ans2);
}

int main()
{
	pw[0]=1;
	fo(i,1,200000) pw[i]=pw[i-1]*2%mod;
	for(int n,m;~scanf("%d%d",&n,&m);) solve(n,m);
	return 0;
}

I. Integers and Ranges

根据套路，删掉重合的线段，然后区间具有单调性。

将 $0\sim 9$ 分为 ${0,9},{3,6},{1,2,4,5,7,8}$ 三类。

一个区间里面只要有 $2$ 个或以上 $3$ 的因子就可以满足条件了。

那么设 $f_{i,j}$ 表示考虑到 $i$ 且第 $1$ 个 $3$ 的因子在 $i$ 这，第 $2$ 个 $3$ 的因子在 $j$ 这，$l\le j$ 的区间全部满足条件的方案数。

转移分两类即可：

  • 放 $3$ 或 $6$：$f_{i,j}=\sum {k} f{j,k}\times 2\times 6^{j-i-1}\times [\forall r\in[j,i-1],l\le k]$

  • 放 $0$ 或 $9$：$f_{i,i}=\sum_{j,k} f_{j,k}\times 2\times 6^{j-i-1}\times [\forall r\in[j,i-1],l\le k]$

后缀和优化一下即可。

时间复杂度 $O(n^2)$。

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
const int N=1005;
const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
ll f[N][N],h[N][N],pw[N];
int a[N];
void solve(int n,int m)
{
	fo(i,0,n) a[i]=0;
	fo(i,1,m)
	{
		int x,y; read(x,y);
		a[y]=max(a[y],x);
	}
	memset(f,0,sizeof(f));
	memset(h,0,sizeof(h));
	h[0][0]=f[0][0]=1;
	fo(i,1,n)
	{
		int k=0;
		fd(j,i-1,0)
		{
			k=max(k,a[j]);
			if(k>j) break;
			f[i][j]=h[j][k]*pw[i-j-1]%mod*2%mod;
			f[i][i]=Add(f[i][i],h[j][k]*pw[i-j-1]%mod*2%mod);
		}
		h[i][i]=f[i][i];
		fd(j,i-1,0) h[i][j]=Add(h[i][j+1],f[i][j]);
	}
	ll ans=0;
	int k=0;
	fo(i,1,n) k=max(k,a[i]);
	fo(i,k,n)
		fo(j,i,n)
			ans=Add(ans,f[j][i]*pw[n-j]%mod);
	printf("%lld\n",ans);
}

int main()
{
	pw[0]=1;
	fo(i,1,1000) pw[i]=pw[i-1]*6%mod;
	for(int n,m;~scanf("%d%d",&n,&m);) solve(n,m);
	return 0;
}