这场的前三题都挺水的，第4题骗分也有80，挺良心的。。

  • A 小L的作文

    算送分题，直接一个for循环计数一下就可以了。

  • B 小L的多项式

    根据题意，f(x)可以O(n)计算得到，求f(x1)...f(xm)的话，再for循环一遍就可以了。复杂度O(n*m)。
    由于n,m<=1000，所以可以直接计算。

  • C 小L的编辑器

    对于本题，我是这么考虑的。
    先输入第一个字母建立一个根节点，然后如果往左就在左子树上建一个新节点，如果往右就在右子树上新建点，然后转移到当前点继续相同的操作。
    那么会发现最后的结果是这棵树的中序遍历输出。

代码：

#include<bits/stdc++.h>
using namespace std;
string s,t;
int tot=0,vis[100];
struct node{
    char now;
    int l,r;
}p[1000040];
void dfs(int x){

    if(x==s.size())return;
    if(t[x]=='L'){
        p[tot].l=tot+1;
        tot++;
        p[tot].now=s[x+1];
    }
    else {
        p[tot].r=tot+1;
        tot++;
        p[tot].now=s[x+1];
    }
    dfs(x+1);
}
void dfs2(int x){
    if(x==0)return ;
    dfs2(p[x].l);
    cout<<p[x].now;
    dfs2(p[x].r);
}
int main()
{
    cin>>s>>t;
    tot=1;
    p[tot].now=s[0];
    dfs(0);
    tot--;
    p[tot].l=p[tot].r=0;
    dfs2(1);
    return 0;
}

  • D 小L的数列

    根据题目的条件要求，显然可以先把a数组进行一遍排序。
    很容易想到用dp[i]表示前i个数能排列出来的最大的好序列长度。
    类似LIS的做法，我们强制第i个必选。
    那么有dp[i]=max(dp[i],dp[j]+1) j<i&&gcd(a[i],a[j])>1
    这样做的复杂度是O(n^2)，居然有80分！

想不到优化了，赛后看了题解。
参考了一个思路是，枚举每个数的因子，然后用dp[i]表示因子i为结尾的时候所能构成的最大长度。
即对于一个数a[i]，我们枚举他的因子j（sqrt(a[i])复杂度），找到最大的dp[j]赋值给maxi。接着再枚举一遍a[i]的因子j，将所有的dp[j]=maxi+1。注意特判a[i]本身为质数的情况！

上面的做法其实本质和原暴力dp是相似的，在暴力dp的时候我们是往前找数，并且找的数要和a[i]有相同的因子。那么用dp[i]表示i为因子的话就不用再找数了，只要找一个最大长度的因子就可以了。然后为了维护dp[i]，我们需要把a[i]里所有的因子都变成这个新的最大长度。
太妙了！

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[100040],dp[100004];
int main()
{
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        int maxi=1;
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0,sizeof(dp));
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            int tmp=0;
            int t=a[i];
        for(int j=2;j<=sqrt(a[i]);j++){
            if(a[i]%j==0){
                tmp=max(tmp,dp[j]);
                while(t%j==0)t/=j;
            }
        }    
            if(t>1)tmp=max(tmp,dp[t]);   //特判a[i]为质数的情况
        for(int j=2;j<=sqrt(a[i]);j++){
            if(a[i]%j==0)dp[j]=tmp+1;
        }
            if(t>1)dp[t]=tmp+1;

    }

    for(int i=1;i<=a[n];i++)maxi=max(maxi,dp[i]);
    cout<<maxi<<endl;
    }

    return 0;
}