C
给定颜色数 $k$ ，对于 $n\times n$ 的网格图，每个格子被染成 $1\sim n$ 的颜色，且所有颜色至少有一个格子染上，对于 $1\leq i,j\leq k\ , i \ \not ={j}$ ，任意一个颜色 $i$ 的格子相邻的格子中，颜色为 $j$ 的格子数量均相同，其中相邻指下标差为 $1$ 或 $n-1$
给定 $k$ 构造满足条件的 $n$ 以及网格图具体方案
玄学解析
首先对于 $k\leq 500$ 的情况，显然能用 $n=k$ ，使一种颜色一列(一行)即可
没有任何原因的 注意到 $k$ 是 $n$ 的两倍，尝试对于 $n\times n$ 是否能构造出 $2n$ 种颜色的方案
为方便讨论，先强制使 $n$ 为偶数，下文会讨论其余情况
那么一个自然的想法是考虑对于 $n\times n$ 的方格，将每 $n\times 2$ 看成一组，其中第一行是 $1\sim n$ 的排列，第二行是 $n+1\sim 2n$ 的排列
考虑到颜色数 $2n$ ，且 $n$ 为偶数的特殊性，自然的想到以 $2\times 2$ 为一块
再考虑到题面中对于相邻的定义，构造形式大概率类似于重复块的循环排列我在写什么，即，类似于
我在写什么？
以 $n=6$ 为例，能构造出：
即，
不难发现这是合法的，而通过手推更大的n也能发现这样合法，但latex太难打了
也就是，当 $k\equiv 0 \pmod 4$ 时，令 $n=\frac{k}{2}$ 即可
而对于 $k\equiv a \pmod 4\ ,\ a\in \{1,2,3\}$ ，将那些 $>k$ 的数 $-n$ 即可
以 $k=5$ 为例
然后通过手模发现这样也是对的
但我并不会证正确性，这跟官方题解好像也不一样
1
2
3
4
5
6
7
8
| int main(){
int n,K;
scanf("%d",&K); if(K==1) return puts("1\n1"),0;
printf("%d\n",n=(K+3)/4*2);
for(rei i=0;i<n;++i) for(rei j=0,r;j<n;++j) r=(i+j)%n+(i&1 ? n : 0),printf("%d%c",r-(r>=K ? n : 0)+1,j==n-1 ? 10 : 32);
getchar(),getchar();
return 0;
}
|
D
给定长度为 $n$ 的数列，给 $q$ 个交换操作，可选择是否操作，能得到 $2^Q$ 个(可能相同的)序列，求所有情况的逆序数总和
直接算总和过于繁琐，对于每一项计算其期望贡献，最后乘 $2^Q$ ，即 $E(N(A))=\sum_{1\leq iA_j)$ ，对于每一对 $(i,j) \ iA_j$ 的概率
考虑第 $q$ 次操作 $(A_X,A_Y)$ ，显然若 $\{i,j\}\cap \{X,Y\}=\varnothing$ ，$p(A_i>A_j)$ 的值不变
而对于 $(A’_X,A’_Y)$ ，操作 $q$ 交换两者的概率可以看作 $\frac{1}{2}$ 。。。。。吗？
考虑到 $A_X=A_Y$ ，此时需要除去它们相等的概率，即 $1-p(A_X>A_Y)-p(A_Y>A_X)$ ，转移即为：
对于 $p(A’_X,A’_i) , i\not \in \{X,Y\}$ ，此时 $A’_X$ 有 $\frac{1}{2}$ 的概率为 $A_X$ , $\frac{1}{2}$ 的概率为 $A_Y$ ，有转移：
其余情况类似不再说明
对于操作 $(X,Y)$ ，能使 $p(A’_i>A’_j)$ 变化的 $(i,j)$ 对需要满足 $\{i,j\}\cap \{X,Y\}\not ={\varnothing}$ ，故只有 $O(n)$ 对
总复杂度为 $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
| const int N=3100;
const int mod=1e9+7;
const int inv2=5e8+4;
ll E;
int n,q,a[N],f[N][N];
inline ll qpow(ll a,int n,ll ans=1){ for(;n;n>>=1,a=a*a%mod) if(n&1) ans=ans*a%mod; return ans;}
inline int half(int x){ return (ll) x*inv2%mod;}
int main(){
scanf("%d%d",&n,&q);
for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
for(rei i=1;i<=n;++i) for(rei j=1;j<=n;++j) f[i][j]=a[i]>a[j];
for(rei i=0,u,v;i<q;++i){
scanf("%d%d",&u,&v); f[u][v]=f[v][u]=half(f[u][v]+f[v][u]);
for(rei j=1;j<=n;++j) if(j!=u && j!=v){
f[u][j]=f[v][j]=half(f[u][j]+f[v][j]);
f[j][u]=f[j][v]=half(f[j][u]+f[j][v]);
}
}
for(rei i=1;i<=n;++i) E+=accumulate(f[i]+i,f[i]+1+n,0ll);
printf("%d\n",(int) qpow(2,q,E%mod));
getchar(),getchar();
return 0;
}
|
E
给定两个长度 $n$ 的 $01$ 串 $s,t$ ，进行若干次操作，每次可以使 $s$ 中某一个位置上的值取反，且保证不存在 $3$ 个及以上连续的相同字符，求把 $s$ 变为 $t$ 所需要的最小操作次数
在 $0 \ 1$ 之间画一条红线， $1 \ 0$ 之间画一条蓝线，默认字符串开头结尾处均有无限多的红蓝线
此时，两个字符串相等等价于两个字符串的红蓝线相等，而更改一个位置上的数相当于将一条红/蓝线左/右移
那么直接枚举红蓝线之间的位置关系，暴力 $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
| const int N=2e4+100;
int n,a[N],b[N];
char s[N],t[N];
inline int calc(){
rei t1=0,t2=0;
for(rei i=1;i<=n-1;++i) if (s[i]=='0' && s[i+1]=='1') a[++t1]=i;
for(rei i=1;i<=n;++i) b[++t2]=0;
for(rei i=1;i<=n-1;++i) if (t[i]=='0' && t[i+1]=='1') b[++t2]=i;
for(rei i=1;i<=n;++i) b[++t2]=n;
rei ret=n*n;
for(rei i=1;i<=t2-t1+1;++i){
rei now=0;
for(rei j=1;j<=i-1;++j) now+=b[j];
for(rei j=1;j<=t1;++j) now+=abs(a[j]-b[i+j-1]);
for(rei j=i+t1;j<=t2;++j) now+=n-b[j];
ret=min(ret,now);
}
return ret;
}
int main(){
scanf("%d%s%s",&n,s+1,t+1);
if(n<=2){
rei ans=0;
for(rei i=1;i<=n;++i) ans+=s[i]!=t[i];
printf("%d\n",ans);
return 0;
}
rei tmp=calc();
for(rei i=1;i<=n;++i) s[i]='0'+'1'-s[i],t[i]='0'+'1'-t[i];
printf("%d\n",tmp+calc());
getchar(),getchar();
return 0;
}
|
F
长度 $2\times n$ 的序列 $A$ 中为 $1\sim 2\times n$ ，要将其填入形成一个排列，其中某些位置已经强制有特定的数，有长度为 $n$ 的序列 $B$ ，其中 $B_i=\min\{A_{2i-1},A_{2i}\}$ ，求所有方案中能得到不同的 $B$ 的数量
考虑 $B$ 的取值方法，对于序列 $A$ 两两考虑每一对数：
对于已经确认的数对，可以直接丢掉不管
对于形如 $(-1,-1)$ ，即，两个都没有填的对
显然数对内的顺序对 $B_i$ 的值无影响，仅需要记录其个数 $cnt1$ ，最后给答案累加阶乘 $cnt1!$ 即可
对于 $(x,-1)$ 的
这种形式有两种，一个是题目指定了一个值且尚未被匹配的数对 $(x,-1)$，或一个数填入到了 $(-1,-1)$ 中
由于 $B_i$ 要取 $\min$ ,所以对所有数从大到小处理
设 $f_{i,j,k}$ 表示当前在第 $i$ 个数，其中有 $j$ 种填过一个数的 $(-1,-1)$ ，$k$ 种题中所给的未匹配的数对 $(d,-1)$
对于新加的第 $i$ 个数 $x$：可以和填了一半进行配对，也可以自己产生一个填了一半的数对
分类，考虑其是否是 $(x,-1)$ 数对中的一个：
- 是：
- 产生新的数对: $\rightarrow f_{i,j,k+1}$
- 填到一个填了一半的 $(-1,-1)$ 中: $\rightarrow f_{i,j-1,k}$
- 不是：
- 填到一个空的 $(-1,-1)$ : $\rightarrow f_{i,j+1,k}$
- 填到一个填了一半的 $(-1,-1)$ 中: $\rightarrow f_{i,j-1,k}$
- 匹配掉一个 $(x,-1)$ 对，其中有 $k$ 种方法: $\times k \rightarrow f_{i,j,k-1}$
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
| const int N=310;
const int mod=1e9+7;
int n,m,ans,a[N<<1];
int cnt1,cnt2,f[N<<1][N][N],S[N<<1];
bool vis[N<<1],book[N<<1];
inline void fix(int &x){ x>=mod ? x-=mod : 0;}
int main(){
scanf("%d",&n);
for(rei i=1;i<=(n<<1);++i) scanf("%d",&a[i]);
for(rei i=1;i<=(n<<1);i+=2){
if(a[i]==-1 && a[i+1]==-1) ++cnt1;
else if(a[i]>0 && a[i+1]>0) vis[ a[i] ]=vis[ a[i+1] ]=true;
else ++cnt2,book[ (~a[i]) ? a[i] : a[i+1] ]=true;
}
for(rei i=(n<<1);i;--i) if(!vis[i]) S[++m]=i;
f[0][0][0]=1;
for(rei i=1;i<=m;++i) for(rei j=0;j<=cnt1+cnt2;++j) for(rei k=0;k<=cnt2;++k){
if(!f[i-1][j][k]) continue;
if(!book[ S[i] ]){
fix(f[i][j+1][k]+=f[i-1][j][k]);
if(j) fix(f[i][j-1][k]+=f[i-1][j][k]);
if(k) fix(f[i][j][k-1]+=(ll) k*f[i-1][j][k]%mod);
}
else{
fix(f[i][j][k+1]+=f[i-1][j][k]);
if(j) fix(f[i][j-1][k]+=f[i-1][j][k]);
}
}
ans=f[m][0][0]; for(rei i=1;i<=cnt1;++i) ans=(ll) ans*i%mod;
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|