中山day11

T1

由于n\le 2000,考虑O(n^2)做法用cnt_{i,j}表示与第i和第j条竖线相交的横线条数，然后暴力枚举一条横线和两条竖线，维护cnt数组并统计答案，然后过了。
code

#include<bits/stdc++.h>
#define int long long
#define y1 y11
using namespace std;
struct node{
    int x1,y1,x2,y2;
};
int n,cnt[2010][2010],ans;
vector<node>a,b;
vector<int>c;
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        node t;
        cin>>t.x1>>t.y1>>t.x2>>t.y2;
        if(t.x1>t.x2)swap(t.x1,t.x2);
        if(t.y1>t.y2)swap(t.y1,t.y2);
        if(t.x1==t.x2)b.push_back(t);
        else a.push_back(t);
    }
    for(int i=0;i<a.size();i++){
        c.clear();
        for(int j=0;j<b.size();j++){
            if(a[i].x1<=b[j].x1&&b[j].x2<=a[i].x2&&b[j].y1<=a[i].y1&&a[i].y2<=b[j].y2){
                c.push_back(j);
            }
        }
        for(int j=0;j<c.size();j++){
            for(int k=j+1;k<c.size();k++){
                ans+=cnt[c[j]][c[k]];
                cnt[c[j]][c[k]]++;
            }
        }
    }
    cout<<ans;
    return 0;
}

欸，这复杂度不是O(n^3)的吗？
注意到代码中有一处三重循环，而且最坏情况下是可以跑满的，但由于这题的一些特殊性质，使代码常数很小，三重循环至多只会进入约5\times 10^8次，常数小的话本地只跑了约500ms(不知道什么奇奇怪怪的原因，测评机上最慢的一个点才123ms，甚至最优解)

T2

DAG上做DP，老经典了。
如果能想到DP，状态应该不难想，用f_{i,j,k}表示以第i个节点结束，长度为j，路径边权和为k的路径边权平方和最大值。这样设计可以保证最后能算出方差并将其最大化。转移式很简单，就不写了。

T3

又是一个DP。
令l为字符串长度，答案字符串为s，原字符串为t，从一开始计数。
定义f[i][j]为用了t的第j到l个字符对s的第i到l个字匹配（t中的字符不一定用到，但s中的字符一定要被匹配）。
转移有3种：
f_{i,j}\gets f_{i,j+1}+1
拿出t的第j个字符，但暂时不匹配（留给后面用的）
条件：什么情况都能用
f_{i,j}\gets f_{i+1,j}
将s的第i个字符与之前从t拿出的某个字符匹配
条件：令s的第i个字符为c，则须保证t的第j到l个字符中c的数量大于s的第i到l个字符中c的数量
f_{i,j}\gets f_{i+1,j+1}
直接将s的第i个字符与t的第j个字符与字符匹配
条件：s的第i个字符与t的第j个字符相同
答案显然为f_{1,1}

T4

不会