Steven_MengのBlog

比赛传送门

$Pro1$

A. XORinacci

定义:

$f(0)=a,f(1)=b,f(n)=f(n-1) \oplus f(n-2)$

给你$a,b$,求$f(n)$

$Sol1$

找规律:

$f(0)=a,f(1)=b,f(2)=a \oplus b,f(3)=b \oplus (a \oplus b)=a,f(4)=a \oplus (a \oplus b)=b …. $

于是发现以$3$个数为循环节:

$Code1$

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
#undef int
int main(){
#define int long long
int t=read();
for (register int i=1;i<=t;++i){
int a=read(),b=read(),n=read();
printf("%I64d\n",(n%3==0?a:(n%3==1?b:a^b)));
}
}

$Pro2$

B. Uniqueness

给你一个序列$a_1,a_2,…a_n$,你要选定一段连续的区间$[l,r]$并且删去,使得剩下的数互不相同。

求删去区间长度的最小值。

$Sol2$

由于$n \le 2000$,所以$O(n^2)$的解法应该能轻松过。

考虑枚举左端点$l$,然后从$n$开始推$r$。

假设$[l,r]$是不合法的区间,那么$[l,r-1]$肯定不合法,于是只要枚举到一个不合法的$r$,就统计答案,退出循环。

还有一个$O(n)$的解法,观察到$l$往左推进,右端点的极左位置肯定是向右移动的,于是维护$l,r$两个指针,注意到两个指针最多移动$n$次,于是这个解法是$O(n)$的。

$Code2$

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
//n^2解法
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],b[MAXN],n;
inline void discrete(){
for (register int i=1;i<=n;++i) b[i]=a[i];
sort(b+1,b+1+n);
for (register int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
}
int cnt[MAXN];
int main(){
n=read();
for (register int i=1;i<=n;++i){
a[i]=read();
}
discrete();
int ans=0x7fffffff;

memset(cnt,0,sizeof(cnt));
for (register int i=1;i<=n;++i){
cnt[a[i]]++;
if (cnt[a[i]]>1){
break;
}
ans=min(ans,n-i);
}

memset(cnt,0,sizeof(cnt));
for (register int i=n;i>=1;--i){//两种特判
cnt[a[i]]++;
if (cnt[a[i]]>1){
break;
}
ans=min(ans,i-1);
}

for (register int i=1;i<=n;++i){
memset(cnt,0,sizeof(cnt));
for (register int j=1;j<=i;++j){
cnt[a[j]]++;
if (cnt[a[j]]>1) {//如果前半部分不合法,就退出
printf("%d\n",ans==0x7fffffff?0:ans);
return 0;
}
}
for (register int j=n;j>=i+1;--j){
cnt[a[j]]++;
if (cnt[a[j]]>1) break;//退出
ans=min(ans,j-i-1);
}
}
printf("%d\n",ans);
}

$Pro3$

C. Magic Grid

给你$0$到$n^2-1$的数,将他们填进$n \times n$的矩阵,满足每行和每列的异或和相等。

$n$是$4$的倍数。

$Sol3$

考虑每$4 \times 4$个矩阵填数。

对于$4 \times t,4 \times t+1,4 \times t+2,4 \times t+3$四个数,都可以表示为$…00,…01,…10,…10$的形式,异或一下,全部都可以抵消。

对于$4 \times t,4 \times (t+1),4 \times (t+2),4 \times (t+3)$四个数,也是同样可以抵消。

$Code3$

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int ans[1005][1005];
int main(){
int n=read();
int p=n/4;
int cnt=0;
for (register int i=1;i<=p;++i){
for (register int j=1;j<=p;++j){
for (register int k=0;k<4;++k){
for (register int l=0;l<4;++l){
ans[(i-1)*4+k+1][(j-1)*4+l+1]=cnt++;
}
}
}
}
for (register int i=1;i<=n;++i){
for (register int j=1;j<=n;++j){
printf("%d ",ans[i][j]);
}
printf("\n");
}
}

$Pro4$

D. Restore Permutation

给你一个数组$p_1,p_2,…p_n$,要你求数组$a_1,a_2,…a_n$

其中$\{a\}$是$1$到$n$的排列,数组$p$的生成方式为$p_i=\sum _{j=1}^i a[j] (a[j]\le a[i])$

$Sol4$

考虑逆推,即从$a_n$推到$a_1$

维护一个树状数组,一开始的值为$1,2,…n$。

对于$a_i$,在树状数组上面二分,找到使得前缀和$\le p_i$的最大位置$pos$

把$a_i$设成$pos$,然后将树状数组上面把位置$pos$设成$0$即可。

$Code4$

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace BIT{
int C[MAXN];
#define lowbit(i) (i&(-i))
inline void Add(int x,int val){
for (register int i=x;i<MAXN;i+=lowbit(i)){
C[i]+=val;
}
}
inline int Query(int x){
int ans=0;
for (register int i=x;i>0;i-=lowbit(i)){
ans+=C[i];
}
return ans;
}
};
using namespace BIT;
int a[MAXN],n;
inline int BinSearch(int pos){
int l=0,r=MAXN-1,ans;
while (l<r-1){
int mid=(l+r)>>1;
if (Query(mid)<=a[pos]) l=mid;
else r=mid;
}
return r;
}
int ans[MAXN];
#undef int
int main(){
#define int long long
n=read();
for (register int i=1;i<=n;++i) a[i]=read();
for (register int i=1;i<=n;++i){
Add(i,i);
}
for (register int i=n;i>=1;--i){
int pos=BinSearch(i);
Add(pos,-pos);
ans[i]=pos;
}
for (register int i=1;i<=n;++i){
printf("%I64d ",ans[i]);
}
}

 评论