中山 day1

T1

注意到1 \le m \le 20直接搜索，对于字符串t的每个子序列先判断它是否回文，然后再判断它是否是s的子序列。时间复杂度O((n+m)2^m)。由于n\le10^6,显然超时。
我们发现在判断t的一个子序列是否也是s的子序列上耗时较多，可以先预处理出suf_{i,j}表示第i个字符后字符j第一次出现的位置，这样判断时可以利用suf数组进行跳转，时间复杂度O(m2^m+n)
还有，如果同时从两边搜并加以剪枝，复杂度可达O(2^m+n)，而且常数极小，1ms拿捏。

code

#include
#define int long long
using namespace std;
struct node{
    int ls,rs,lt,rt,f;
}a[1<<20];
string s,t;
int n,m,pre[100010][30],suf[100010][30],lst[30],ans;
void dfs(int x){
    ans=max(ans,a[x].f);
    if(a[x].lt==a[x].rt)return;
    for(int i=a[x].lt+1;i<a[x].rt;i++){
        for(int j=i;j<a[x].rt;j++){
            if(t[i]!=t[j])continue;
            int tm=x|(1<<i)|(1<a[tm].rs)continue;
            if(i==j){
                a[tm].f=a[x].f+1;
                dfs(tm);
            }
            if(i<j&&a[tm].ls>s>>t;
    n=s.size();m=t.size();
    for(int i=0;i<26;i++)lst[i]=-1;
    for(int i=0;i<n;i++){
        lst[s[i]-'a']=i;
        for(int j=0;j<26;j++){
            pre[i][j]=lst[j];
        }
    }
    for(int i=0;i=0;i--){
        lst[s[i]-'a']=i;
        for(int j=0;j<26;j++){
            suf[i][j]=lst[j];
        }
    }
    a[0].ls=-1;
    a[0].rs=n;
    a[0].lt=-1;
    a[0].rt=m;
    dfs(0);
    cout<<ans<<endl;
    return 0;
}

T2

一眼缩点
先tanjan求SCC，接着缩点，然后处理每个联通块，再对每个连通块dp一下（记忆化搜索），最后选结果前k+1大的加起来就好了。
由于之前并没有正式写过缩点，稍微借助了oi.wiki和洛谷

T3

一种神奇的做法是二分，并check一下是否存在长度至少为k的连续子数组平均值大于二分值mid。其二分单调性显然，但关键是怎么check呢？比较棘手的是平均值最后要除以n，再与mid比较，但这里如果我们将原数组每个元素减mid,对应平均值也减mid，此时只需将平均值与0比较，即判断平均值的正负号。而除以n操作不会改变结果的符号，也就是说这个操作可以省去。
现在问题变成判断是否存在一个长度至少为k的连续子序列使其元素和大于0。从小到大扫描数组，并维护前(当前位置-k+1)的前缀和最小值，并与当前位置前缀和比较即可。

code

#include
#define int long long
using namespace std;
int read();
double b[300010];
int n,k,a[300010];
signed main(){
    freopen("average.in","r",stdin);
    freopen("average.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i1e-6){
        double mid=(l+r)/2;
        for(int i=1;iminn){
                flag=1;
                break;
            }
        }
        if(flag)l=mid;
        else r=mid;
    }
    printf("%lf",l);
    return 0;
}
int read(){
    int res=0;
    char c=getchar();
    while(c'9')c=getchar();
    while(c>='0'&&c<='9'){
        res=res*10+c-'0';
        c=getchar();
    }
    return res;
}

T4

打表，相信别人已经打完了