class Solution {
public:
    int cnts[11],cntt[11];
    int id[11][100010],num[100010],vis[100010];
    int n,idx=0;
    stack<char>stk;

    bool isTransformable(string s, string t) {
        n=s.size();
        for(int i=0;i<n;i++) {
            cnts[s[i]-'0']++,cntt[t[i]-'0']++;
        }
        for(int i=0;i<=9;i++) {
            if(cnts[i]!=cntt[i]) return false;
        }
        memset(cnts,0,sizeof cnts);
        memset(cntt,0,sizeof cntt);
        for(int i=0;i<n;i++) {
            id[s[i]-'0'][++cnts[s[i]-'0']]=num[i]=++idx;
        }
        for(int i=0;i<n;i++) {
            int k=id[t[i]-'0'][++cntt[t[i]-'0']];
            for(int j=t[i]-'0'+1;j<=9;j++) {
                if(id[j][cntt[j]]>k) return false; 
            }
        }

        return true;
    }
};

class Solution {
public:
    long long w[210][210],dp[210][210],n,m;

    long long dfs(int x,int y) {
        if(dp[x][y]>=0) return dp[x][y];
        long long res=w[x][y];
        for(int i=1;i<x;i++) {
            res=max(res,dfs(i,y)+dfs(x-i,y));
        }
        for(int i=1;i<y;i++) {
            res=max(res,dfs(x,i)+dfs(x,y-i));
        }
        return dp[x][y]=res;
    }

    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        this->m=m,this->n=n;
        memset(w,0,sizeof w);
        memset(dp,-1,sizeof dp);
        for(int i=0;i<prices.size();i++) {
            w[prices[i][0]][prices[i][1]]=prices[i][2];
        }
        return dfs(m,n);
    }
};

昨天Div4的H题，本来AC的，FST过后发现第40个测试点居然TM超时了

问题出在solve()中第二行的位置，定义了一个unordered_map，用来存每个数字出现过的下标

比赛中是用C+ +20提交的，如果把这里换成map就能AC，或者把提交语言换成C++14也能AC，并且执行时间都很短（31ms）

真是奇了大怪，哪位大佬能解释下么QAQ

#include<bits/stdc++.h>
using namespace std;

int n,a[200010],T;

void solve() {
    cin>>n;
    unordered_map<int,vector<int>>loc;//这里
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        loc[a[i]].push_back(i);
    }
    int resa=0,resl=0,resr=0,mx=0;
    for(auto &i:loc) {
        vector<int>v=i.second;
        int nn=v.size();
        vector<int>b(nn+3,0),pmin(nn+3,1e9+10),rmin(nn+3,0);
        for(int k=0;k<nn;k++) {
            b[k]=v[k]-2*k;
        }
        for(int k=nn-1;k>=0;k--) {
            if(b[k]<=pmin[k+1]) {
                pmin[k]=b[k];
                rmin[k]=k;
            }
            else {
                pmin[k]=pmin[k+1];
                rmin[k]=rmin[k+1];
            }
        }
        for(int k=0;k<nn;k++) {
            int tmp=b[k]-pmin[k]+1;
            if(tmp>mx) {
                mx=tmp;
                resa=i.first;
                resl=v[k];
                resr=v[rmin[k]];
            }
        }
    }
    cout<<resa<<" "<<resl<<" "<<resr<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

class Solution {
public:
    int numberOfCombinations(string num) {
        if(num[0]=='0') return 0;
        int n=num.size(),mod=1e9+7;
        vector<vector<int>>dp(n+2,vector<int>(n+2,0));
        vector<vector<int>>premax(n+2,vector<int>(n+2,0));
        vector<vector<int>>sum(n+1,vector<int>(n+1,0));
        for(int i=n;i>=1;i--) {
            for(int k=n;k>=1;k--) {
                if(num[i-1]==num[k-1]) premax[i][k]=premax[i+1][k+1]+1;
            }
        }
        for(int i=1;i<=n;i++) {
            dp[i][0]=sum[i][0]=1;
        }
        for(int i=2;i<=n;i++) {
            for(int k=1;k<i;k++) {
                if(num[k]=='0') {
                    sum[i][k]=sum[i][k-1];
                    continue;
                }
                if(2*k-i<0) dp[i][k]=sum[k][k-1];
                else dp[i][k]=(sum[k][k-1]-sum[k][2*k-i]+mod)%mod;

                if(2*k-i>=0) {
                    int len=premax[k+1][2*k-i+1];
                    if(k+len>=i||num[k+len]>=num[2*k-i+len]) {
                        dp[i][k]=(dp[i][k]+dp[k][2*k-i])%mod;
                    }
                }
                sum[i][k]=(sum[i][k-1]+dp[i][k])%mod;
            }
        }
        return sum[n][n-1];
    }
};

#include<bits/stdc++.h>
using namespace std;

struct node{
    int ft,dep;
    friend bool operator<(node a,node b) {
        if(a.ft!=b.ft) return a.ft<b.ft;
        else return a.dep>b.dep;
    }
};

int ins[100010],add[100010],depth[100010],mn[100010],seq[100010],n,m,mxd=0,root;
vector<int>g[100010];
set<node>nodes;
long long tot=0;

void dfs1(int now) {
    mn[now]=ins[now];
    for(int i=0;i<g[now].size();i++) {
        int t=g[now][i];
        dfs1(t);
        mn[now]=min(mn[now],mn[t]);
    }
}

void dfs2(int now,int dep) {
    depth[now]=dep;
    if(mn[now]!=0x3f3f3f3f) {
        auto it=nodes.lower_bound({n-mn[now]});
        if(it==nodes.end()) add[now]=2*depth[now];
        else add[now]=2*(depth[now]-it->dep);
        nodes.insert({n-mn[now],dep});
    }
    for(int i=0;i<g[now].size();i++) {
        int t=g[now][i];
        dfs2(t,dep+1);
    }
    if(mn[now]!=0x3f3f3f3f) nodes.erase(nodes.find({n-mn[now],dep}));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,a;i<=n;i++) {
        cin>>a;
        if(a==-1) root=i;
        else g[a].push_back(i);
    }
    memset(ins,0x3f,sizeof ins);
    memset(mn,0x3f,sizeof mn);
    for(int i=1,a;i<=m;i++) {
        cin>>a;
        seq[i]=a;
        if(ins[a]==0x3f3f3f3f) ins[a]=i;
    }
    dfs1(root);
    dfs2(root,0);
    for(int i=1;i<=n;i++) {
        if(mn[i]<ins[i]) add[i]=0;
    }
    for(int i=1;i<=m;i++) {
        if(ins[seq[i]]!=i) {
            cout<<tot-mxd<<'\n';
            continue;
        }
        int a=seq[i];
        tot+=add[a];
        mxd=max(mxd,depth[a]);
        cout<<tot-mxd<<'\n';
    }
    return 0;
}

class BookMyShow {
public:
    struct node{
        int l,r;
        long long mx,sum,lazy;
    }tr[1000010];

    int n,m;

    void build(int u,int l,int r) {
        tr[u]={l,r,0,0,-1};
        if(l==r) return;
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }

    void pushup(int u) {
        tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
        tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    }

    void pushdown(int x) {
        node &u=tr[x],&l=tr[x<<1],&r=tr[x<<1|1];
        if(u.lazy!=-1) {
            l.lazy=r.lazy=u.lazy;
            l.mx=r.mx=l.sum=r.sum=0;
            u.lazy=-1;
        }
    }

    void modify1(int u,int x,int v) {
        if(tr[u].l==x&&tr[u].r==x) {
            tr[u].mx=tr[u].sum=v;
            return;
        }
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify1(u<<1,x,v);
        else modify1(u<<1|1,x,v);
        pushup(u);
    }

    void modify2(int u,int l,int r) {
        if(tr[u].l>=l&&tr[u].r<=r) {
            tr[u].mx=tr[u].sum=tr[u].lazy=0;
            return;
        }
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify2(u<<1,l,r);
        if(r>mid) modify2(u<<1|1,l,r);
        pushup(u);
    }

    int query1(int u,int v) {
        pushdown(u);
        if(tr[u].l==tr[u].r&&tr[u].mx>=v) return tr[u].l;
        if(tr[u<<1].mx>=v) return query1(u<<1,v);
        else if(tr[u<<1|1].mx>=v) return query1(u<<1|1,v);
        else return -1;
    }

    pair<int,int>query2(int u,int x) {
        if(tr[u].l==x&&tr[u].r==x) return {tr[u].mx,tr[u].sum};
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) return query2(u<<1,x);
        else return query2(u<<1|1,x);
    }

    int query3(int u,int x) {
        pushdown(u);
        int res=1e8;
        if(tr[u].sum>=x) res=tr[u].r;
        if(tr[u<<1].sum>=x) res=min(res,query3(u<<1,x));
        else if(tr[u].sum>=x) res=min(res,query3(u<<1|1,x-tr[u<<1].sum));
        return res;
    }

    long long query4(int u,int l,int r) {
        if(tr[u].l>=l&&tr[u].r<=r) {
            return tr[u].sum;
        }
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        long long res=0;
        if(l<=mid) res+=query4(u<<1,l,r);
        if(r>mid) res+=query4(u<<1|1,l,r);
        return res;
    }

    BookMyShow(int n, int m) {
        this->n=n,this->m=m;
        build(1,1,n);
        for(int i=1;i<=n;i++) modify1(1,i,m);
    }

    vector<int> gather(int k, int maxRow) {
        int a=query1(1,k);
        if(a==-1||a-1>maxRow) return {};
        pair<int,int>p=query2(1,a);
        int b=p.first,c=p.second;
        modify1(1,a,b-k);
        return {a-1,m-b};
    }

    bool scatter(int k, int maxRow) {
        int a=query3(1,k);
        if(a==1e8||a-1>maxRow) return false;
        long long pre=0,rt=0;
        if(a!=1) pre=query4(1,1,a-1),rt=k-pre;
        else pre=0,rt=k;
        long long rest=query2(1,a).first;
        modify1(1,a,rest-rt);
        //cout<<rest-rt;
        if(a>1) modify2(1,1,a-1);
        return true;
    }
};

class Solution {
public:
    pair<int,int>p[100010];
    int pc,mb,mw,xc[100010],mx[100010],dp[100010],n;
    long long sum[100010],rsum[100010];

    struct node{
        int l,r;
        int mn;
    }tr[400010];

    void pushup(int u) {
        tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
    }

    void build(int u,int l,int r) {
        tr[u]={l,r,1000000000};
        if(l==r) return;
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }

    void modify(int u,int x,int v) {
        if(tr[u].l==x&&tr[u].r==x) {
            tr[u].mn=min(tr[u].mn,v);
            return;
        }
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }

    int query(int u,int l,int r) {
        if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mn;
        int mid=tr[u].l+tr[u].r>>1,res=1e9;
        if(l<=mid) res=min(res,query(u<<1,l,r));
        if(r>mid) res=min(res,query(u<<1|1,l,r));
        return res;
    }

    int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
        for(int i=0;i<boxes.size();i++) {
            p[i+1]={boxes[i][0],boxes[i][1]};
        }
        n=boxes.size(),pc=portsCount,mb=maxBoxes,mw=maxWeight;
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+p[i].second;
        for(int i=1;i<=n;i++) rsum[i]=sum[n-i+1];
        for(int i=n;i>=1;i--) {
            if(p[i].first==p[i+1].first) xc[i]=xc[i+1];
            else xc[i]=xc[i+1]+1;
        }
        for(int i=1;i<=n;i++) {
            int tmp=lower_bound(rsum+1,rsum+n+1,sum[i-1]+mw,greater<long long>())-rsum;
            tmp=n-tmp+1;
            mx[i]=min(tmp,n);
        }
        build(1,1,n+1);
        modify(1,n+1,-1);
        for(int i=n;i>=1;i--) {
            int up=min({i+mb-1,mx[i],n})+1;
            dp[i]=query(1,i+1,up)+xc[i]+2;
            modify(1,i,dp[i]-xc[i-1]);
        }
        return dp[1];
    }
};

class Solution {
public:
    int cf[200010]={0},cnt[200010];
    unordered_map<int,int>id;
    vector<int>nums;
    int idx=0;

    vector<int> fullBloomFlowers(vector<vector<int>>& fs, vector<int>& ps) {
        for(int i=0;i<fs.size();i++) {
            nums.push_back(fs[i][0]);
            nums.push_back(fs[i][1]);
        }
        for(int i=0;i<ps.size();i++) {
            nums.push_back(ps[i]);
        }
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++) {
            if(id[nums[i]]==0) id[nums[i]]=++idx;
        }
        for(int i=0;i<fs.size();i++) {
            int a=id[fs[i][0]],b=id[fs[i][1]];
            cf[a]++,cf[b+1]--;
        }
        for(int i=1;i<=idx;i++) {
            cnt[i]=cnt[i-1]+cf[i];
        }
        vector<int>res;
        for(int i=0;i<ps.size();i++) {
            res.push_back(cnt[id[ps[i]]]);
        }
        return res;
    }
};

第二次参加PAT就打了顶级，属于是有点膨胀结果被锤爆了QAQ，第一题模拟题甚至0分，也就后两题稍微做了下。不得不说这PAT数据挺水的，我T3后面发现这么明显的一个逻辑错误，竟然只扣了两分；

T1 The Rescue

一个巨恶心的模拟题，同时也是甲级的T4，顶级也只有4个人做出了这题（顶级本来就只有4个满分，其他有好几个有满分机会的大佬也是栽在了这题上），不说了，一分没有，都是泪QAQ

T2 Prize Game

题意是，给定一个长度为n的数组（可能有负数），以及一个整数x，我们可以有一次机会将数组的某个区间乘上x（也可以不乘），问乘完之后，最大子数组和是多少；
数据范围n<=10^6

经典且普通的dp，难以想象这题居然比T1分值高，跟T3同分值

#include<bits/stdc++.h>
using namespace std;

long long a[1000010],dp[1000010][4],x,n;

int main() {
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        dp[i][0]=max({(long long)0,a[i],dp[i-1][0]+a[i]});
        dp[i][1]=max({(long long)0,a[i]*x,dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x});
        dp[i][2]=max({(long long)0,dp[i-1][1]+a[i],dp[i-1][2]+a[i]});
        dp[i][3]=max({(long long)0,dp[i-1][1],dp[i-1][2],dp[i-1][3],dp[i-1][0]});
    }
    cout<<max({(long long)0,dp[n][0],dp[n][1],dp[n][2],dp[n][3]});
    return 0;
}

T3 Memories of Youth

题目的意思是，有m位年轻人，在很久以前，他们每个人都分到了一个code（一个长度为2的string），现在他们想要回忆以前这段时光，于是想知道每个人拿到的code是哪一个，但由于时间太过久远，他们都忘记了。所幸他们还有n张照片，每张照片记录了上面出现了哪些人，以及出现了哪些code（但是哪个人对应哪个code是未知的），现在请你根据这些照片判断，每个人对应的code是哪个，如果不能确定则输出 ‘？’，如果可以确定则输出对应的code；
数据范围m<=54，n<=100

输入格式：
第一行输入m和n；随后对于每张照片，第一行输入一个数字x，表示照片中出现了几个人，第二行输入x个code，第三行输入x个人的编号，均以空格隔开；
输出格式：
按人的编号从小到大输出每个人对应的code，如果不能确定，则输出‘？’；

这道题一开始就给我一种二分图匹配的感觉，但是想了半天，也没法解决不能确定的情况，于是在浪费了半个多小时之后，想到了一种拓扑排序的方法，但拓扑排序属实是把问题搞复杂了，所以这里写的方法是刚刚想到的；

具体想法是，如果说第i个人能够有望与第k个code匹配，那么凡是第i个人出现过的照片，必然包含第k个code；凡是包含了第k个code的照片，必然出现了第i个人；如果同时满足了这两个条件，那么第k个code就能够作为第i个人的备选；如果一个人有两个及以上的code作为备选，那么这个人一定是不能确定的；因为上面的规则是双向的，code和人是等价的，如果按照上面的规则，一个人能对应两个及以上code，反过来说，这其中的每一个code，它也能对应两个及以上的人；

实现比较丑陋QAQ（还是改良后的QAQ）建议直接无视

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt1[200],cnt2[200],idc=0;
unordered_map<string,int>id;
string name[200];
vector<int>have1[200],have2[200];
int d[200],pp[200],p[200],same[200][200];


int main() {
    cin>>m>>n;
    memset(same,1,sizeof same);
    for(int i=1;i<=n;i++) {
        int a;
        cin>>a;
        for(int k=0;k<a;k++) {
            string s;
            cin>>s;
            if(id[s]==0) id[s]=++idc,name[idc]=s;
            have1[i].push_back(id[s]);
        }
        for(int k=0;k<a;k++) {
            int s;
            cin>>s;
            have2[i].push_back(s);
        }
    }
    for(int i=1;i<=n;i++) {
        bool h1[200]={0},h2[200]={0};
        for(int k=0;k<have1[i].size();k++) {
            cnt1[have1[i][k]]++;
            h1[have1[i][k]]=1;
        }
        for(int j=0;j<have2[i].size();j++) {
            cnt2[have2[i][j]]++;
            h2[have2[i][j]]=1;
        }
        for(int k=1;k<=m;k++) {
            if(h1[k]==1) continue;
            for(int j=1;j<=idc;j++) {
                if(h2[j]==0) continue;
                same[k][j]=0;
            }
        }
    }
    for(int i=1;i<=idc;i++) {
        for(int k=1;k<=m;k++) {
            if(cnt1[i]==cnt2[k]&&same[i][k]!=0) {
                if(pp[k]==0) pp[k]=i,p[i]=k;
                else pp[k]=-1,pp[p[i]]=-1;
            }
        }
    }
    for(int i=1;i<=m;i++) {
        if(pp[i]==-1||pp[i]==0) cout<<"?"<<endl;
        else cout<<name[pp[i]]<<endl;
    }
    return 0;
}

题外话：
我今年考研报的是广西某211，今年的专业课的算法压轴题，就是T2的简化版，在不改变数组的前提下，求最大子数组和，同时这也是leetcode上的原题，难度标为easy，分值20分；
结果我的专业课分数有些惨不忍睹，属于群里垫底了QAQ，不会正是因为我的代码比较丑陋所以老师没看明白吧QAQ

class Solution {
public:
    int seq[35],ill[35],con[35],mod=1e9+7;
    int cnt[35],isprime[35],idx=0;
    long long dp[35][1<<10];

    void initial(){
        for(int i=2;i<=30;i++) {
            int tmp=i,ct=0;
            for(int k=2;k<=i/k;k++) {
                if(tmp%k==0) {
                    ct=0;
                    while(tmp%k==0) {
                        tmp/=k;
                        ct++;
                    }
                    if(ct>=2) ill[i]=1;
                }
            }
        }
        for(int i=2;i<=30;i++) isprime[i]=1;
        for(int i=2;i<=30;i++) {
            if(isprime[i]==0) continue;
            for(int k=i+i;k<=30;k+=i) isprime[k]=0;
        }
    }

    long long dfs(int now,int state) {
        if(now==1&&state==0) return 1;
        if(now==1&&state!=0) return 0;
        if(dp[now][state]>=0) return dp[now][state];
        long long res=dfs(now-1,state)%mod;
        if(cnt[now]!=0&&ill[now]==0&&(state&con[now])==con[now]) res=(res+dfs(now-1,state^con[now])*cnt[now])%mod;
        return dp[now][state]=res;
    }

    long long qmi(int v) {
        long long res=1,ds=2;
        while(v) {
            if(v&1) res=res*ds%mod;
            ds=ds*ds%mod;
            v>>=1;
        }
        return res;
    }

    int numberOfGoodSubsets(vector<int>& nums) {
        initial();

        for(int i=2;i<=30;i++){
            if(isprime[i]==0) continue;
            seq[i]=idx++;
        }
        for(int i=2;i<=30;i++) {
            if(ill[i]==1) continue;
            for(int k=2;k<=30;k++) {
                if(isprime[k]==0) continue;
                if(i%k==0) con[i]|=(1<<seq[k]);
            }
        }
        for(int i=0;i<nums.size();i++) cnt[nums[i]]++;
        memset(dp,-1,sizeof dp);
        long long res=0;
        for(int i=1;i<(1<<10);i++){
            res=(res+dfs(30,i))%mod;
        }
        return res*qmi(cnt[1])%mod;
    }
};