AtCoder Grand Contest 038 刷题记录
A 01 Matrix
大意：请你构造一个$n*m$的01矩阵，再给你$a$和$b$，使得每行的$\min \{ cnt_0,cnt_1 \} = a$，每列的这个东西等于$b$
题解：直接将这个矩阵横竖切两刀，切点是$a$和$b$，左上和右下填同一个数就行了
1 #include<bits/stdc++.h>
2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
4 #define mem(i,j) memset(i,j,sizeof(i))
5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
6 using namespace std;
7 typedef long long ll;
8 const int N=1010;
9 int n,m,a,b,ans[N][N];
10 inline int read()
11 {
12 int x=0,f=1;
13 char c=getchar();
14 while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
15 while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
16 return f*x;
17 }
18 inline void write(int x)
19 {
20 if (x<0) putchar('-'),x=-x;
21 if (x>9) write(x/10);
22 putchar(x%10+'0');
23 return;
24 }
25 int main()
26 {
27 n=read(),m=read(),a=read(),b=read();
28 FOR(i,1,n)
29 {
30 FOR(j,1,m)
31 {
32 if (i<=b&&j<=a) ans[i][j]=1;
33 else if (i>b&&j>a) ans[i][j]=1;
34 else ans[i][j]=0;
35 }
36 }
37 FOR(i,1,n)
38 {
39 FOR(j,1,m) printf("%d",ans[i][j]);
40 putchar('\n');
41 }
42 return 0;
43 }
View Code
B Sorting a Segment
大意：给你一个排列，以及一个$k$，你可以做一次操作，操作是，选择一个长度为$k$的连续区间，对其排序，问能得到多少种排列
题解：
- 最多的答案上限是$n-k+1$，我们考虑将重复的减去，两个重复贡献的区间只有一下两种情况
- 一，两个区间不相交，并且都是升序的
- 二，两个区间相交，此时左区间滑动到右区间的所有区间都做着同一个重复贡献，于是我们只需判断位置相差$1$的两个区间即可
1 #include<bits/stdc++.h>
2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
3 using namespace std;
4 const int N=2e5+5;
5 int n,k,a[N],ans,st_mn[21][N],st_mx[21][N],b[N],f[N],vis[N];
6 inline void build_st()
7 {
8 FOR(i,1,n) st_mn[0][i]=st_mx[0][i]=a[i];
9 FOR(j,1,20)
10 for (register int i=1;i+(1<<j)-1<=n;i++)
11 {
12 st_mn[j][i]=min(st_mn[j-1][i],st_mn[j-1][i+(1<<(j-1))]);
13 st_mx[j][i]=max(st_mx[j-1][i],st_mx[j-1][i+(1<<(j-1))]);
14 }
15 return;
16 }
17 inline int query_min(int l,int r)
18 {
19 int ret,step=log2(r-l+1);
20 ret=min(st_mn[step][l],st_mn[step][r-(1<<step)+1]);
21 return ret;
22 }
23 inline int query_max(int l,int r)
24 {
25 int ret,step=log2(r-l+1);
26 ret=max(st_mx[step][l],st_mx[step][r-(1<<step)+1]);
27 return ret;
28 }
29 inline void pan()
30 {
31 int tag=0;
32 FOR(i,1,n) f[i]=1;
33 FOR(i,2,n)
34 if (a[i]>a[i-1]) f[i]=max(f[i],f[i-1]+1);
35 FOR(i,1,n) if (f[i]>=k&&!vis[i]) ans--,tag=1;
36 if (tag) ans++;
37 return;
38 }
39 int main()
40 {
41 scanf("%d%d",&n,&k);
42 FOR(i,1,n) scanf("%d",&a[i]);
43 build_st();
44 ans=n-k+1;
45 FOR(i,k+1,n)
46 {
47 int mx=query_max(i-k+1,i-1),mn=query_min(i-k+1,i-1);
48 if (mx<a[i]&&mn>a[i-k]) ans--,vis[i]=1;
49 }
50 pan();
51 printf("%d\n",ans);
52 return 0;
53 }
View Code
C LCMs
大意：给你一个长度为$2e5$，值域为$1e6$的序列$A$，请你求出每对元素的最小公倍数之和
题解：是个简单的反演题，但是一开始中间有个整除条件推错了，使我很傻逼
$$
\begin{eqnarray}
\sum_{i=1}^n \sum_{j=1}^n lcm(A_i,A_j) & = & \sum_{i=1}^n \sum_{j=1}^n \frac{A_ixA_j}{gcd(A_i,A_j)}
\end{eqnarray}
$$