A Codehorses T-shirts

相同长度之间互相转化即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int N=105;
int n,a[N],b[N],ans;
string s[N],t[N];
map<string,int>mp;
int main()
{
    mp["S"]=1,mp["M"]=2,mp["L"]=3;
    mp["XS"]=4,mp["XL"]=5;
    mp["XXS"]=6,mp["XXL"]=7;
    mp["XXXS"]=8,mp["XXXL"]=9;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i],a[mp[s[i]]]++;
    for(int i=1;i<=n;i++)
        cin>>t[i],b[mp[t[i]]]++;
    for(int i=1;i<=9;i++)
        ans+=abs(a[i]-b[i]);
    printf("%d\n",ans/2);
    return 0;
}

B Light It Up

把0和m点插进去，处理出s[0/1][i]为i&1为0或1区间长度的后缀和，然后枚举要插入的区间，贪心的把点插在p[i]+1（区间关灯）或p[i+1]-1（区间开灯），然后取后面反的前缀和更新ans即可

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,a[N],s[2][N],ans;
int read()
{
    int r=0,f=1;
    char p=getchar();
    while(p>'9'||p<'0')
    {
        if(p=='-')
            f=-1;
        p=getchar();
    }
    while(p>='0'&&p<='9')
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
int main()
{
    n=read()+2,m=read();
    for(int i=2;i<n;i++)
        a[i]=read();
    a[n]=m;
    for(int i=n-1;i>=1;i--)
        s[i&1][i]=a[i+1]-a[i]+s[i&1][i+1],s[~i&1][i]=s[~i&1][i+1];
    // for(int i=1;i<=n;i++)
        // cerr<<s[0][i]<<" "<<s[1][i]<<endl;
    ans=s[1][1];
    for(int i=1;i<n;i++)
        if(a[i+1]-a[i]>1)
            ans=max(ans,s[1][1]-s[1][i]+s[i&1][i+1]+a[i+1]-a[i]-1);//,cerr<<i<<" "<<s[1][1]-s[1][i]<<" "<<s[i&1][i+1]<<" "<<a[i+1]-a[i]-1<<endl;
    printf("%d\n",ans);
    return 0;
}

C Covered Points Count

hash一下左右端点，差分前缀和处理出hash后的点（代表这之后的一整段区间）的被覆盖次数，然后把区间长度加进相应的长度ans里即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N=500005;
long long n,tot,has,a[N],l[N],r[N],g[N],rl[N],ans[N];
map<long long,long long>mp;
long long read()
{
    long long r=0,f=1;
    char p=getchar();
    while(p>'9'||p<'0')
    {
        if(p=='-')
            f=-1;
        p=getchar();
    }
    while(p>='0'&&p<='9')
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
int main()
{
    n=read();
    for(long long i=1;i<=n;i++)
        l[i]=read(),r[i]=read(),g[++tot]=l[i],g[++tot]=r[i]+1;
    sort(g+1,g+1+tot);
    for(long long i=1;i<=tot;i++)
        if(i==1||g[i]!=g[i-1])
            mp[g[i]]=++has,rl[has]=g[i];
    for(long long i=1;i<=n;i++)
        a[mp[l[i]]]++,a[mp[r[i]+1]]--;
    for(long long i=2;i<=has;i++)
        a[i]+=a[i-1];
    // for(long long i=1;i<=has;i++)
        // cerr<<i<<" "<<rl[i]<<" "<<a[i]<<endl;
    for(long long i=1;i<has;i++)
        ans[a[i]]+=rl[i+1]-rl[i];
    for(long long i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    return 0;
}

D Yet Another Problem On a Subsequence

考的时候没做出来

设f[i]为选i为一个a1的方案数，转移是\( f[i]=\sum_{j=i+a[i]+1}{n+1}C_{i-j-1}{a[i]}*f[j] \) 最后的答案是\( ans=\sum_{i=1}^{n}f[i] \)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005,mod=998244353;
int n,a[N],f[N],ans,c[N][N];
void jia(int &x,int y)
{
    x+=y;
    if(x>=mod)
        x-=mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    c[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    f[n+1]=1;
    for(int i=n;i>=1;i--)
        if(a[i]>0)
        {
            for(int j=i+a[i]+1;j<=n+1;j++)
                jia(f[i],1ll*c[j-i-1][a[i]]*f[j]%mod);
            jia(ans,f[i]);
        }
    printf("%d\n",ans);
    return 0;
}

E We Need More Bosses

比较裸，先缩了边双然后求树的直径即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
int n,m,h[N],cnt,dfn[N],low[N],tot,s[N],top,bl[N],col,con,st,mx;
bool v[N];
pair<int,int>b[N<<1];
struct qwe
{
    int ne,no,to;
}e[N<<1];
int read()
{
    int r=0,f=1;
    char p=getchar();
    while(p>'9'||p<'0')
    {
        if(p=='-')
            f=-1;
        p=getchar();
    }
    while(p>='0'&&p<='9')
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
void add(int u,int v)
{
    cnt++;
    e[cnt].ne=h[u];
    e[cnt].no=u;
    e[cnt].to=v;
    h[u]=cnt;
}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tot;
    s[++top]=u;
    for(int i=h[u];i;i=e[i].ne)
        if(e[i].to!=fa)
        {
            if(!dfn[e[i].to])
            {
                tarjan(e[i].to,u);
                low[u]=min(low[u],low[e[i].to]);
            }
            else
                low[u]=min(low[u],dfn[e[i].to]);
        }
    if(low[u]==dfn[u])
    {
        col++;
        while(s[top]!=u)
            bl[s[top--]]=col;
        bl[s[top--]]=col;
    }
}
void dfs(int u,int fa,int len)
{
    if(len>mx)
        st=u,mx=len;
    for(int i=h[u];i;i=e[i].ne)
        if(e[i].to!=fa)
            dfs(e[i].to,u,len+1);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    tarjan(1,0);
    for(int i=1;i<=cnt;i++)
        if(bl[e[i].no]!=bl[e[i].to])
            b[++con]=make_pair(bl[e[i].no],bl[e[i].to]);
    memset(h,0,sizeof(h));
    cnt=0;
    for(int i=1;i<=con;i++)
        add(b[i].first,b[i].second);
    dfs(1,0,0);
    mx=0;
    dfs(st,0,0);
    printf("%d\n",mx);
    return 0;
}