7.14 模拟赛

7.14 模拟赛

四题都是 1s 512MB

T1. A

Description

给定一个自然数 $N$，找出一个 $M$，使得 $M > 0$ 且 $M$ 是 $N$ 的倍数，并且 $M$ 的 10 进制表示只包含 $0$ 或 $1$。求最小的 $M$。
如果无解，则输出 $-1$。

$N\le 10^6$

Solution

首先一定不存在 $-1$ 的情况。考虑 $1,11,111…$ 模 $N$ 一定存在相同的两个。相减就是答案。

然后 bfs。这里不想写了。就贺了一发翔哥的。

Code

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
#include<cstdio>
using namespace std;
const int N = 2e6 + 9;
int n,t;
bool vis[N];
int bfs[N],la[N];
void dfs(int i,int nxt)
{
    if(i<0){
        putchar('1');
        return;
    }
    dfs(la[i],i);
    if(bfs[i]*10%n==bfs[nxt])putchar('0');
    else putchar('1');
}
int main()
{
    scanf("%d",&n);
    if(n==0){
        printf("-1\n");
    }
    t=1;
    vis[1]=true;bfs[1]=1;la[1]=-1;
    for(int i=1;i<=t;i++){
        if(bfs[i]==0){
            dfs(la[i],i);
            putchar('\n');
            return 0;
        }
        if(!vis[bfs[i]*10%n]){
            la[++t]=i;
            bfs[t]=bfs[i]*10%n;
            vis[bfs[i]*10%n]=true;
        }
        if(!vis[(bfs[i]*10+1)%n]){
            la[++t]=i;
            bfs[t]=(bfs[i]*10+1)%n;
            vis[(bfs[i]*10+1)%n]=true;
        }
    }
    printf("-1");
    return 0;
}

T2. B

Description

两个串的相似值为，如果两个串在第 $i$ 位是一样的，那么他们的相似值要加上 $w_i$。
现在给你个长度为 $n$ 的串，然后有 $q$ 个询问，每一次给定一个长度为的$n$ 串，和一个值 $k$。求在这个串中，有多少个串和他的相似值不超过 $k$。

$n\le 15,m,q\le 5\times 10^5,w_i,k\le 30$

Solution

观察到 $k$ 很小，答案只有 $2^nk$ 种情况。

令 $f[i][j]$ 为这个数为 $i$ ，有 $f[i][j]$ 个串和其相似值恰好等于 $k$。

考虑位从小到大枚举 $k$，$f[i][j]\Leftarrow f[i\bigoplus 2^k][j-w_i]$

注意枚举顺序和 $w_i=0$ 的情况。

Code

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m,q,w[25];
int a[maxn]; 
int b[(1<<15)+5];
int nums[40005][35],g[40005][35];
#define lowbit(x) ((x)&(-x))
signed main(void){
	int i,j,x,k,sum;char ch;
	read(n);read(m);read(q);
	for (i=0;i<n;i++) read(w[i]);
	for (i=1;i<=m;i++) {
		ch=getchar();while (ch!='0'&&ch!='1') ch=getchar();
		for (j=0;j<n;j++) {
			if (ch=='1') a[i]|=(1<<j);
			ch=getchar();
		}
		b[a[i]]++; 
	}
	int N=(1<<n);
	for (i=0;i<N;i++) nums[i][0]=b[(N-1)^i];
	for (k=0;k<n;k++) {
		memcpy(g,nums,sizeof(g));//w=0
		for (j=30;j>=0;j--) {
			for (i=0;i<N;i++){
				if (j>=w[k]) nums[i][j]+=g[i^(1<<k)][j-w[k]];
			}
		}
	}
	while (q--) {
		x=0;
		ch=getchar();while (ch!='0'&&ch!='1') ch=getchar();
		for (j=0;j<n;j++) {
			if (ch=='1') x|=(1<<j);
			ch=getchar();
		}
		read(k);sum=0;
		for (i=0;i<=k;i++) sum+=nums[x][i];
		printf("%d\n",sum);
	}
	return 0;
}

T3. C

Decription

image-20230714201906721

$t\le 10^6$

Solution

枚举矩阵较短的一边 $n$，这里是 $t$ 的因数，枚举的复杂度是 $O(t^{1/3})$ 。

然后根据最大值的个数（最大值一定在角落），确定 $0$ 的位置，然后直接暴力判断。

总复杂度 $O(n^{4/3})$ ，实际上远远达不到。有点细节。

Code

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int t[maxn],K,Max;
inline int calc(int n,int m,int tmpx,int tmpy,int i) {
	int sum=0,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7,tmp8;
	if (tmpx>i) tmp1=tmp2=tmpy,sum--;
	else tmp1=tmpy-(i-tmpx+1),tmp2=tmpy+(i-tmpx+1);
	if (tmpx+i<=n) tmp3=tmp4=tmpy,sum--;
	else tmp3=tmpy-(i-n+tmpx),tmp4=tmpy+(i-n+tmpx);
	
	if (tmpy>i) tmp5=tmp6=tmpy-i,sum--;
	else tmp5=tmp6=1;
	if (tmpy+i<=m) tmp7=tmp8=tmpy+i,sum--;
	else tmp7=tmp8=m;
//	gdb(sum,tmp1,tmp5,tmp2,tmp7,tmp3,tmp6,tmp4,tmp8);
	if (tmp1>=tmp5) sum+=tmp1-tmp5+1;
	if (tmp2<=tmp7) sum+=tmp7-tmp2+1;
	if (tmp3>=tmp6) sum+=tmp3-tmp6+1;
	if (tmp4<=tmp8) sum+=tmp8-tmp4+1; 
	return sum;
}
inline void solve(int n,int m) {
	if (Max>n+m-2) return ;
	int i,j,tmpx=0,tmpy=0,flag=0;
	if (t[Max]==4) {
		if (n%2==1&&m%2==1) {
			tmpx=n/2+1,tmpy=m/2+1;
			for (i=1;i<Max;i++) if (calc(n,m,tmpx,tmpy,i)!=t[i]) return ;
			printf("%d %d\n%d %d",n,m,tmpx,tmpy);exit(0);
		}
	}
	else if (t[Max]==3||t[Max]>4) return;
	else if (t[Max]==2) {
		if (n%2==0&&m%2==0) return ;
		if (m%2==1) {
			tmpy=(m+1)/2;tmpx=n-(Max-tmpy+1);flag=0;
			for (i=1;i<Max;i++) if (calc(n,m,tmpx,tmpy,i)!=t[i]) {flag=1;break;}
			if (!flag) {printf("%d %d\n%d %d",n,m,tmpx,tmpy);exit(0) ;}
		}
		if (n%2==1) {
			tmpx=(n+1)/2,tmpy=m-(Max-tmpx+1);flag=0;
			for (i=1;i<Max;i++) if (calc(n,m,tmpx,tmpy,i)!=t[i]) {flag=1;break;}
			if (!flag) {printf("%d %d\n%d %d",n,m,tmpx,tmpy);exit(0) ;}
		}
	}
	else if (t[Max]==1) {
		for (j=n-Max;j<=(n+1)/2;j++) {
			tmpx=j,tmpy=m+n-Max-j;flag=0;
			for (i=1;i<=Max;i++) if (calc(n,m,tmpx,tmpy,i)!=t[i]) {flag=1;break;}
			if (!flag) {printf("%d %d\n%d %d",n,m,tmpx,tmpy);exit(0) ;}
		}
	}
}
signed main(void){
	int i,j,x;
	read(K);
	for (i=1;i<=K;i++) {
		read(x);
		if (x>K-1) return puts("-1"),0;
		t[x]++;Max=max(Max,x);
	}
	for (i=1;i*i<=K;i++) if (K%i==0) {
		solve(i,K/i);
	}
	puts("-1");
	return 0;
}

T4. D

Description

给定 $n$ 个数，判断 $a_i$ 是否存在 $j$ 满足 $a_i&a_j=0$。

$n,a_i\le 10^6$

Solution

SOSdp 板子。

Code

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,a[maxn];
const int base=20;
int f[maxn],Max; 
signed main(void){
	int i,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),f[a[i]]=1,Max=max(Max,a[i]);
	for (j=0;j<=base;j++)
		for (i=0;i<=(1<<base);i++) if ((i>>j)&1) {
			f[i]|=f[i^(1<<j)];
		}
	int N=1<<base;
	for (i=1;i<=n;i++) printf("%d ",f[N-1^a[i]]);
	return 0;
}