C

贪心/构造
给定一个n*n的乱序的$gcd(a_i,a_j)$表,逆推出一个序列满足这个表

我们将这n*n个数从大到小排序,很明显最大的数对应$gcd(a_n,a_n) = a_n$
然后去掉它之后最大的数又对应$gcd(a_{n-1},a_{n-1}) = a_{n-1}$
然后我们去掉所有的$gcd(a_n,a_i),gcd(a_n-1,a_i) … $ 以此类推
然后重复这个步骤,最后得出答案。

我的写法略残,和题解有出入,游程编码后对连续几个进行分析。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 501;
const double eps = 1e-10;

int a[maxn*maxn],b[maxn*maxn],cnt[maxn*maxn];
map<int,int> decc;

int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}

int main()
{
//freopen("ans.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n*n;++i) scanf("%d",a+i);
sort(a,a+n*n,greater<int>());
int pn = 0,ct = 1;
a[n*n] = -1;
for(int i=1;i<=n*n;++i)
{
if(a[i]!=a[i-1])
{
b[pn] = a[i-1];
cnt[pn++] = ct;
ct = 1;
}
else ++ct;
}
decc.clear();
vector<int> ans;

for(int i=0;i<pn;++i)
{
int cur = 0,de = decc[b[i]];
bool flag = false;
for(int j=i-1;j>=0;--j)
{
if(b[j]%b[i] == 0) cur += ans[j];
}
//printf("%d %d %d\n",b[i],cur,cnt[i]-de);
int j = 1;
while(j*j + 2*cur*j <= cnt[i] - de)
{
if( ((j+2*cur)*j) == (cnt[i] - de))
{
ans.push_back(j);
flag = true;
break;
}
++j;
}
if(!flag) ans.push_back(0);
for(int j=i-1;j>=0;--j)
{
decc[gcd(b[i],b[j])] += ans[i]*ans[j]*2;
}
}
ct = 0;
for(int i=0;i<ans.size();++i)
{
for(int j=0;j<ans[i];++j)
{
printf("%d%c",b[i],++ct == n?'\n':' ');
}
}
// printf("%d\n",ct);
return 0;
}

D

DP/矩阵快速幂
LIS,给定一个n个数的序列,然后复制为T段,求最长非递减序列

YY了一个做法竟然是对的
求一个前n段的d[a[i]] 表示以a[i]结尾的LIS
和后n段的d[a[i]] 表示以a[i]开头的LIS
记录cnt[a[i]]

$ans = max(d[a[i]]+d[a[j]]+(T-2n)max(cnt[a[i]],cnt[a[j]])) \; a[i] \leq a[j]$

我们发现最多n段的LIS就会不会因顺序再变化,n段以后只会重复LIS最后一个元素(或之前的某一个元素)
所有我们只用求前n段和后n段的LIS,然后中间取一样的元素,求一个最大值即可。
复杂度$O(n^4)$ 好吧,因为是CF,就偷懒了,标准做法应该是 $O(n^2log(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
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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 110;
int a[2*maxn*maxn],cnt[maxn*3];
int d[2][2*maxn*maxn],dp[2][maxn*3];

int main()
{
//freopen("test.txt","r",stdin);
int n,T;
scanf("%d %d",&n,&T);
int m = min(n,T);
for(int i=0;i<n;++i) scanf("%d",a+i);
memset(cnt,0,sizeof cnt);
memset(d,0,sizeof d);

if(m*2 >= T) m = T;

for(int i=0;i<n;++i)
{
++cnt[a[i]];
for(int j=1;j<m;++j) a[i+n*j] = a[i];
}

for(int i=0;i<n*m;++i)
{
d[0][i] = 1;
for(int j=0;j<i;++j)
{
if(a[i] >= a[j])
{
d[0][i] = max(d[0][i],d[0][j]+1);
}
}
dp[0][a[i]] = d[0][i];
}

int ans = 0,t = T-m*2;
if(m == T)
{
for(int i=1;i<=300;++i) ans = max(ans,dp[0][i]);
printf("%d\n",ans);
return 0;
}

for(int i=n*m;i>=0;--i)
{
d[1][i] = 1;
for(int j=i+1;j<n*m;++j)
{
if(a[i] <= a[j])
{
d[1][i] = max(d[1][i],d[1][j]+1);
}
}
dp[1][a[i]] = d[1][i];
}

for(int i=1;i<=300;++i)
{
if(!cnt[i]) continue;
for(int j=i;j<=300;++j)
{
if(cnt[j])
{
ans = max(ans,dp[0][i]+dp[1][j]+max(cnt[i],cnt[j])*t);
}
}
}
printf("%d\n",ans);
return 0;
}

第一个做法是矩阵快速幂,值得学习。
构造一个矩阵我们定义C[i][j] 为从序列中第i个元素开始,第j个元素结束的LIS。
注意若 i>j 则表示在j在下一个序列,长度从1开始计

然后矩阵运算的关系式为
$C_{ij} = max_{k=1}^n (A_{ik} + B_{kj})$

表示前后两个序列合并在一起的LIS,这样我们可以用矩阵快速幂加速了。
注意这样的运算是不是乘法,初始矩阵不是单位矩阵,应该都设为0。不可达应设为-INF。

复杂度$O(n^3log(T))$

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<bits/stdc++.h>
using namespace std;

const int maxn = 110;
const int INF = 0x3f3f3f3f;
typedef int Matrix[maxn][maxn];

int a[maxn],n,T;

void Mul(Matrix a,Matrix b,Matrix c)
{
Matrix res;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
res[i][j] = -INF;
for(int k=0;k<n;++k)
{
if(a[i][k] > -INF && b[k][j] > -INF)
res[i][j] = max(res[i][j],a[i][k]+b[k][j]);
}
}
memcpy(c,res,sizeof res);
}

void Pow(Matrix A,int n,Matrix c)
{
Matrix res,a;
memcpy(a,A,sizeof(a));
memset(res,0,sizeof res);

while(n)
{
if(n&1) Mul(res,a,res);
n>>=1;
Mul(a,a,a);
}
memcpy(c,res,sizeof res);
}

int main()
{
//freopen("test.txt","r",stdin);
Matrix d,res;
scanf("%d %d",&n,&T);
for(int i=0;i<n;++i) scanf("%d",a+i);
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
if(a[j] < a[i]) d[i][j] = -INF;
else
{
d[i][j] = 1;
for(int k=0;k<j;++k)
{
if(a[k] <= a[j]) d[i][j] = max(d[i][j],d[i][k]+1);
}
}
// printf("%d %d %d\n",i,j,d[i][j]);
}
}
Pow(d,T,res);
int ans = 0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
ans = max(ans,res[i][j]);

printf("%d\n",ans);
return 0;
}