模拟赛1总结

题目

T1-Analysis

请先思考后再展开

这是一道当时感觉很神,后来感觉很签到的好题
关键在于,判断是否是n的倍数
把加0看做乘以10,加1看做乘以10再加1
这里运用到了一个技巧————用余数表示
再通过记忆化,能够把原本【2的次幂】的复杂度,降低到n
具体的实现可以用bfs
路径的记录,可以以余数为索引,记录从哪个余数继承过来
当然无脑string也行,毕竟就是一个等差数列的复杂度

T1-Code-Std

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAXN=1100000;
int MOD;
int from[MAXN];
int ans[MAXN],tot;
void add(int x)
{
int nx=from[x];
ans[++tot]=!( (nx*10%MOD)==x );
}
queue<int> q;
void bfs()
{
q.push(1);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=0;i<=1;i++)
{
int nx=(x*10+i)%MOD;
if(from[nx]<0)
{
from[nx]=x;
q.push(nx);
}
}
}
if(from[0]<0) puts("-1");
else
{
tot=0;add(0);
int now=from[0];
while(now>1) add(now),now=from[now];
ans[++tot]=1;//debug 漏了
}
}
void main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
memset(from,-1,sizeof from);
scanf("%d",&MOD);
bfs();
for(int i=tot;i>=1;i--) putchar('0'+ans[i]);
}
};
int main()
{
mine::main();
}

T2-Analysis

请先思考后再展开

考虑用dp来预处理
神仙转化问题:【把原本的串取反,允许修改k的配额,能得到多少个目标串】
设$f(S,i,k)$为,当前状态为S,处理到第i位,剩下可分配额为k,后面能够得到多少个目标串
计数类dp,显然是倒推的
$f(S,i,k)=f(S,i+1,k)+【k>=w_i】f(S^bin[i],i+1,k-w_i)$

T2-Code-Std

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=16,MAXM=510000;
int n;
int w[MAXN];
int ct[1<<MAXN];
int f[1<<MAXN][MAXN][40];
int bin[MAXN];
char s[MAXN];
int read()
{
scanf("%s",s);
int now=0;
for(int j=0;j<=n-1;j++) if(s[n-j-1]=='1') now+=bin[j];
return now;
}
void main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
bin[0]=1;for(int i=1;i<MAXN;i++) bin[i]=bin[i-1]<<1;
int m,q;scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++) ct[bin[n]-1-read()]++;//取反
for(int i=n+1;i>=1;i--)
for(int s=0;s<=bin[n]-1;s++)
for(int k=0;k<=30;k++)
{
if(i==n+1) f[s][i][k]=ct[s];
else
{
f[s][i][k]=f[s][i+1][k];
if(k>=w[i]) f[s][i][k]+=f[s^bin[n-i]][i+1][k-w[i]];
}
}
while(q--)
{
int now=read(),k;scanf("%d",&k);
printf("%d\n",f[now][1][k]);
}
}
};
int main()
{
mine::main();
}

T3-Analysis

请先思考后再展开

原题:cf_R495_div_d
然后我的代码其实如果加上快读就卡过去了,大概0.5s的速度……
毕竟我的快速check函数,还是下了一番功夫的,从【面积】下降到【最大编号】

先说说我的想法:
1.
设计一个check函数
表示在n乘m的矩阵中,数字i出现了几次(假设(1,1)=1)
然后这个东西很多人是暴力【面积】做的
其实可以通过找规律,分类讨论一下,降到【最大编号】

2.
确认一个最大的完美正方形,
每次调用check函数计算数字的需求量,然后判合法性

3.
经过上一步,已经保证这个正方形会贴边了,
这样我们就能直接把它在那条边上移动(注意交换n和m)
最后还是分4个块,然后调用check判合法性

讲讲正解和我不同的部分:
1.
通过一层层向外枚举,得到第一个不能完美菱形的数字,这个数字就是0的x坐标
可以这样考虑:x在外面,则高度为x-1~0,也就是x个
然后做法的话,其实可以直接每层数字,数量+4,而我硬生生调用一个函数来计算……
当然因为这个在外面,所以速度可以很随便,只是不那么优美

2.
在枚举出矩阵的形状后,
可以直接把最大那个数字mx放在(n,m)的位置,
因为即使它在其他的角落,矩阵也能翻转过来
这样的好处在于,最大曼哈顿距离确定为$mx=n-x+m-y$
移项后得到$y=n+m-x-mx$,也就是说能够直接得出y
这样就省去了枚举y的时间了

现在复杂度就是$O(\sqrt n \times check复杂度)$
而check复杂度就是
$\sum_{i=1 to \sqrt n} i+n/i$
根据等差数列和调和级数
$n/2+nlog_2 \sqrt n$

当然你要是暴力,问题不大,
因为实际上外面的循环不会到满的根号,毕竟约数个数不会太大
根据我打的表,一千万内最多的也只有448个

T3-Code-Old

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
int mymax(int x,int y) {return x>y?x:y;}
const int MAXN=1000001;
int c[MAXN];
int need[MAXN];
inline int check(int n,int m,int i)
{
if(n>m) swap(n,m);
if(i<=n) return i;
if(i<=m) return n;
if(i<=m+n-1) return (n+m-1)-i+1;
return 0;
}
int k=2;
bool okay()
{
for(int i=1;i<=k+k;i++)
if(check(k/2+1,k/2,i)*4>c[i])
return 0;
return 1;
}
int ansx,ansy;
bool trying(int n,int m)
{
int need;
int midx=k/2+1;
for(int tx=1;tx<=m-k+1;tx++)
{
int midy=tx+k/2+1-1;
//printf("%d %d %d %d\n",n,m,midx,midy);
int mxx=mymax(n-midx,midx-1)+mymax(m-midy,midy-1)+5;
bool bk=0;
for(int i=1;i<=mxx;i++)
{
need=check(midx,midy,i+1)+check(n-midx,midy,i)+check(midx,m-midy,i)+check(n-midx,m-midy,i-1);
if(need!=c[i]) {bk=1;break;}
if(need==0) break;
}
if(bk==0)
{
ansx=midx,ansy=midy;
return 1;
}
}
return 0;
}
int read()
{
int x=0;
char c=getchar();
while(c<'0' or c>'9') c=getchar();
while('0'<=c and c<='9') x=x*10+c-'0',c=getchar();
return x;
}
void main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
int mx;scanf("%d",&mx);
for(int i=1;i<=mx;i++)
{
int x;scanf("%d",&x);
c[x]++;
}
while(k*k<=mx)
{
if(!okay()) break;
k++;
}
k--;
for(int n=1;n*n<=mx;n++)
{
if(mx%n!=0) continue;
int m=mx/n;
if(trying(n,m)) {printf("%d %d\n%d %d",n,m,ansx,ansy);return;}
if(trying(m,n)) {printf("%d %d\n%d %d",m,n,ansx,ansy);return;}
}
puts("-1");
}
};
int main()
{
mine::main();
}

T3-Code-Std

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
int mymax(int x,int y) {return x>y?x:y;}
const int MAXN=1000001;
int c[MAXN];
int check(int n,int m,int i)
{
if(n>m) swap(n,m);
if(i<=n) return i;
if(i<=m) return n;
if(i<=m+n-1) return (n+m-1)-i+1;
return 0;
}
int mxnum=0;
int ansx,ansy;
bool trying(int n,int m)
{
ansy=n+m-mxnum-ansx;
int mxx=mymax(n-ansx,ansx-1)+mymax(m-ansy,ansy-1)+5;
bool bk=1;
for(int i=1;i<=mxx;i++)
{
int need;
need=check(ansx,ansy,i+1)+check(n-ansx,ansy,i)+
check(ansx,m-ansy,i)+check(n-ansx,m-ansy,i-1);
if(need!=c[i]) {bk=0;break;}
if(need==0) break;
}
if(bk) printf("%d %d\n%d %d",n,m,ansx,ansy);
return bk;
}
int read()
{
int x=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while('0'<=c and c<='9') x=x*10+c-'0',c=getchar();
return x;
}
void main()
{
int mx;scanf("%d",&mx);
for(int i=1;i<=mx;i++)
{
int t=read();
mxnum=mymax(mxnum,t);
c[t]++;
}
if(c[0]!=1) {puts("-1");return;}//debug 0很烦人
ansx=1;
int need=4;
while(c[ansx]>=need) need+=4,ansx++;
for(int n=1;n*n<=mx;n++)
{
if(mx%n!=0) continue;
int m=mx/n;
if(trying(n,m) or trying(m,n)) return;
}
puts("-1");
}
};
int main()
{
mine::main();
}

T4-Analysis

请先思考后再展开

又是一道很好的脑力题
$a_i & a_j =0$
其实就是没有同时对应存在的1

依然是巧妙地转化题目:
用个数组记录合法性
【取反后a】存在合法解a
并且因为【有合法解性】是可以传递的
所以倒着递推(像背包?),枚举每个数字,
每个【有合法解性】的数字,把某个1去掉后,都能从a得到合法解

T4-Code-Std

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=1100000;
int bin[30];
int a[MAXN];
bool b[MAXN];
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
int mx=bin[20]-1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]^mx]=1;
for(int s=mx;s>=1;s--)
{
if(!b[s]) continue;
for(int i=0;i<=19;i++) if(s&bin[i]) b[s^bin[i]]=1;
}
for(int i=1;i<=n;i++) printf("%d ",b[a[i]]);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/4f83.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%