D
需要构造一个 $N\times N$ 的矩阵 $A$ ，满足：$1\leq a_{i,j}\leq 10^{15}$ ； $a_{i,j}$ 互不相同；存在正整数 $m$ 满足对于任意矩阵中任意两个相邻的数字 $x,y$ 有 $\max(x,y)\mod \min(x,y)=m$
假设 $m=1$ ，考虑一个格子 $v$ ，如果它去模 $a,b,…$ 得到 $1$ ，则有 $\text{lcm}(a,b,…)|v-1$
假设格子 $v$ 单调，，则右边 > 左边，下面 > 上面，$\because a_{i,j} 模 a_{i-1,j},a_{i,j-1}$ 均为 $1$ ，$\therefore$ $\text{lcm}(a_{i,j-1},a_{i-1,j})|a_{i,j}-1$
可以固定第一行及第一列来得到整张表，但这种方法通常会超过 $10^{15}$
考虑题中：网格图中相邻的两个格子，那么建立二分图：黑白染色后相邻两点间连边
取出二分图中的一半 $A$ ，在其中任意填数并保证互不相同，对于另一部分 $B$ 的每个点，权值为与其相邻的点（$A$ 中的点）上的数的 $\text{lcm}$ $+1$
但此时，二分图中有 $\frac{N^2}{2}=1.25\times 10^5$ 个点，最终的 $\text{lcm}$ 可达到 $(\frac{1.25\times 10^5}{2})^4$ ，即 $10^{19}$ ，超出范围
从数论的角度：考虑一个数相邻的四个位置，平均填数下每个数 $N^2$ 级别，若能使对角线上的两个格子的 $\gcd$ 是 $N$ 级别的，那么四个数的 $\text{lcm}$ 就是 $N^4=6.25\times 10^{10}$ ，能接受该级别
考虑令一条对角线上的元素有一个共同的 $\gcd$ 即可使对角线上相邻的两数有一个 $N$ 级别的 $\gcd$
那么进行以下操作：
- 对每一条对角线，标记一个数 $w$
- 对每一个格子 $a_{i,j}$ ，设经过他的两条对角线为 $d_1,d_2$ ，令 $a_{i,j}=w_{d_1}\times w_{d_2}$
为了保证所有数互不相同，取 $w$ 为最小的若干个素数
而二分图另一部分就是相邻 $4$ 个素数的乘积 $+1$
显然对角线条数 $<2\times N$ ，第 $500$ 个素数为 $3571$ ，第 $1000$ 个素数为 $7919$ ，其 $\text{lcm}=3571^2\times 7919^2<10^{15}$ ，则正确性得证
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
| const int N=510;
int n;
int pn,c[7930],p[1054];
ll a[N][N];
inline void sieve(int n){
memset(c,-1,sizeof c);
for(rei i=2;i<=n;++i){
if(!~c[i]) p[pn]=i,c[i]=pn++;
for(rei j=0,v;(v=i*p[j])<=n && j<=c[i];++j) c[v]=j;
}
}
int main(){
int *q;
scanf("%d",&n),sieve(7929);
q=p+(n-1);
for(rei i=0;i<n;++i) for(rei j=0;j<n;++j) if((i^j)&1) a[i][j]=p[ (i+j-1)/2 ]*q[ (j-i+n-1)/2 ];
for(rei i=0;i<n;++i) for(rei j=0;j<n;++j) if(!((i^j)&1)){
ll &s=a[i][j]; s=1;
if (i || j) s*=p[ (i+j-2)/2 ];
if (i!=n-1 || j!=n-1) s*=p[ (i+j)/2 ];
if (i || j!=n-1) s*=q[ (j-i+n)/2 ];
if (i!=n-1 || j) s*=q[ (j-i+n-2)/2 ];
++s;
}
if(n==2) a[1][1]=a[1][1]*2-1;
for(rei i=0;i<n;++i) for(rei j=0;j<n;++j) printf("%lld%c",a[i][j],j==n-1 ? 10 : 32);
getchar(),getchar();
return 0;
}
|
E
给一个由 $a,b$ 组成的字符串，进行 $0$ 或若干次任意一种以下操作：将 $aa$ 转化为 $b$ ，将 $bb$ 转化为 $a$ ，求能得到多少种不同的串
这里有一个 $\text{trick}$ ：将 $a$ 赋值为 $1$ ，$b$ 赋值为 $2$ ，那么所有字符对应的数之和模 $3$ 的结果不变，记该结果为 $K$
那么显然能得到一个结论：串 $s$ 转化为字符 $c$ 的充要条件是 $K(s)=K(c)$ 且 $s$ 不是长度大于 $1$ 的 $ab$ 交错的串
枚举 $t$ 的第一个字符，根据贪心，指定 $s$ 尽可能短的前缀
用 $f_i$ 表示 $s[1,…,i]$ 变成本质不同的串数量，允许 $3\mid K(s)$ 的串可以是空串
如此可以保证合法结果不漏：以 $s=abb$ 为例，$ab$ 变为空串，$b$ 仍是 $b$ ，合起来的结果 $b$ 恰好合法
考虑转移：
$K(s[1,…,i])=0$ 则 $s[1,…,i]$ 是空串
$t$ 的最后一个字符是 $s_i$ ，贪心的，分配一个 $s_i$ ，则有 $f_{i-1}$ 个以 $s_i$ 结尾的串
$t$ 的最后一个字符不是 $s_i$ ，找一个最短的后缀分配：
设该后缀为 $s[j+1,…,i]$ ，那么有 $f_j$ 个以 $s_i$ 的“互补”结尾的串
那么有转移：$f_i=[\ 3\mid K(s[1,…,i]) \ ]+f_{i-1}+f_j$ ，其中 $j=\max\{p\mid K(s[p+1,…,i])+K(s_i)=3\}$
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=1e5+100;
const int mod=1e9+7;
int n,f[N],S[N],B[3]={1};
char s[N];
bool flag=0;
inline void fix(int &x){ x>=mod ? x-=mod : 0;}
int main(){
scanf("%s",s),n=strlen(s);
rei i;
for(i=1;i<n && s[i]!=s[i-1];++i);
if(i==n) return puts("1"),0;
f[0]=1;
for(rei i=1;i<=n;++i){
S[i]=(S[i-1]+s[i-1])%3;
f[i]=f[i-1]+!S[i];
fix(f[i]+=B[ S[i]^S[i-1]^3 ]);
B[ S[i] ]=f[i];
}
if(!S[n]) fix(f[n]+=mod-1);
printf("%d\n",f[n]);
getchar(),getchar();
return 0;
}
|
F
给定两个 $N$ 节点的树 $A,B$ ，对 $A$ 执行若干次操作，每次选择一个叶节点，删除其边并连向任意一个另外的点，每个点只能被选择一次 ，求使 $AB$ 相同的最小操作次数
由 一个点只能操作一次的性质 ：规定一个点作为根，并规定不能操作它，问题则转化为有根树上的问题
此时，一个点被操作当且仅当它在两棵树中父亲不同
有约束条件：
- 若点 $u$ 不需操作，则 $fa_u$ 不能被操作
- $u$ 必须在 $faA_u$ 前被操作，$faB_u$ 后被操作
利用第一个，枚举 $u$ 判断是否满足
第二个用拓扑排序得到合法方案
枚举第一个被操作的点 $u$ 后，以 $u$ 作为根重读上述步骤即可
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
| const int N=57;
int fa[N],ndeg[N],deg[N],vis[N],mp[N][N],n,ans;
vector<int> A[N],B[N];
void dfs(int u,int fath){
fa[u]=fath; if(vis[fath] && mp[u][fath]) vis[u]=1;
for(int v:B[u]) if(v!=fath) dfs(v,u);
}
inline void clear(){
memset(mp,0,sizeof mp);
for(rei i=1;i<=n;++i) A[i].clear(),B[i].clear();
}
int main(){
rei T; scanf("%d",&T);
while(T--){
scanf("%d",&n); ans=n+1;
clear();
for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),mp[u][v]=mp[v][u]=1,A[u].push_back(v),A[v].push_back(u);
for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),B[u].push_back(v),B[v].push_back(u);
for(rei i=1;i<=n;++i) ndeg[i]=A[i].size();
for(rei i=1;i<=n;++i){
rei cost=0,u;
memset(vis,0,4*n+4);
vis[i]=1; dfs(i,0); memcpy(deg+1,ndeg+1,4*n);
while(true){
for(u=1;u<=n;++u) if(!vis[u] && deg[u]==1 && vis[ fa[u] ]) break;
if(u>n) break; vis[u]=1,++cost;
for(int v:A[u]) --deg[v];
}
for(u=1;u<=n;++u) if(!vis[u]) break;
if(u>n) ans=min(ans,cost);
if(A[i].size()>1 || u>n || ans<=n) continue;
memset(vis,0,4*n+1);
vis[0]=1,memcpy(deg+1,ndeg+1,4*n);
while(true){
for(u=1;u<=n;++u) if(!vis[u] && deg[u]<=1 && vis[ fa[u] ]) break;
if(u>n) break; vis[u]=1;
for(int v:A[u]) --deg[v];
}
for(u=1;u<=n;++u) if(!vis[u]) break;
if(u>n) ans=n;
}
printf("%d\n",ans>n ? -1 : ans);
}
getchar(),getchar();
return 0;
}
|