A - String Game

这种问最多多少次..不是dp就是二分/三分/贪心.开始以为是检测子串,看了下样例2,结果发现是检测子序列..白写了个哈希.二分答案即可.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+5;
char a[N],b[N],c[N];
int w[N];
int len,sz;
bool vis[N];
/*ull h_b,h[N],base=131,k[N];
ull get(int l,int r)
{
    return h[r]-h[l-1]*k[r-l];
}

void init()
{
    k[0]=1;
    for(int i=1;i<=sz;i++)    h_b=(b[i]-'a'+1)+h_b*base;
    for(int i=1;i<=id;i++)    h[i]=(c[i]-'a'+1)+h[i-1]*base,k[i]=k[i-1]*base;
}
*/
bool check(int x)
{
    int idb=1,id=0;memset(vis,false,sizeof vis);
    for(int i=1;i<=x;i++)    vis[w[i]]=true;
    for(int i=1;i<=len;i++)
        if(!vis[i])    c[++id]=a[i];
    //init();
    for(int i=1;i<=id;i++)
    {
        if(c[i]==b[idb])    idb++;
        if(idb==sz+1)        return true;
    }return false;
}

int main()
{
    scanf("%s",a+1);
    scanf("%s",b+1);
    len=strlen(a+1);sz=strlen(b+1);
    int l=0,r=len-1,ans=0;
    for(int i=1;i<=len;i++)    scanf("%d",&w[i]);
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            ans=max(ans,mid);
            l=mid+1;
        }
        else r=mid-1;
    }printf("%d\n",ans);
    return 0;
}

B - Chef Monocarp

陌生词汇:optimal 最佳的.
dp.令f[i][j]表示:到了第i个数,我选到了第几个数的min代价是多少.因为我们发现顺序的改变不影响答案,然后我们排序后直接转移即可.

#include <bits/stdc++.h>
using namespace std;
const int N=205;
int f[N][N<<1];//到了第i个数,我选到了第几个数的min代价是多少. 
int w[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)    scanf("%d",&w[i]);
        sort(w+1,w+1+n);memset(f,0x3f,sizeof f);
        for(int i=0;i<=2*n;i++)    f[0][i]=0;
        int ans=2e9;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n*2;j++)
            {
                f[i][j]=min(f[i][j],f[i-1][j-1]+abs(j-w[i]));
                f[i][j]=min(f[i][j],f[i][j-1]);
                ans=min(ans,f[n][j]);
            }
        }printf("%d\n",ans);
    }
    return 0;
}
/*
1
4
1 4 4 4
*/

C - Reachability from the Capital

寻找每个联通块的大小,然后优先选大的,依次联通即可.

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5;
struct graph{
    int id;int sz;
}S[N];//统计下联通块的大小. 
vector<int>g[N];
bool vis[N];//判断该点是否可到.以及防止走环. 
bool look[N];//防止走环. 
void dfs(int u,int fa)//讲u这个点为根的图联通. 
{
    if(vis[u])    return;vis[u]=true;
    for(int v:g[u])    dfs(v,u);
}

int DFS(int u,int fa)//判断下每个联通块的大小. 
{
    if(look[u]||vis[u])    return 0;look[u]=true;S[u].sz=1;
    for(int v:g[u])    S[u].sz+=DFS(v,u);
    return S[u].sz;
}

bool cmp(graph A,graph B)    {    return A.sz>B.sz;    }
int main()
{
    int n,m,s;scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }int ans=0;dfs(s,s);
    for(int i=1;i<=n;i++)
    {
        memset(look,false,sizeof look);
        DFS(i,i);S[i].id=i;
    }sort(S+1,S+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(!vis[S[i].id])    dfs(S[i].id,S[i].id),ans++;
    }printf("%d\n",ans);
    return 0;
}

D - Tree Painting

肯定的选法就是每个点都会被选,然后我们只需要看哪个点选作根价值最大.换根dp一下即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
ll f[N];//某个点作为根的答案.
ll sz[N];//求子树大小.
vector<int>v[N]; 
void dfs(int u,int fa,int root)
{
    sz[u]=1;
    for(int x:v[u])
        if(x!=fa)    dfs(x,u,root),sz[u]+=sz[x];
    f[root]+=sz[u];
}

void DP(int u,int fa)
{
    for(int x:v[u])//换成x为根. 
    {
        if(x==fa)    continue;
        f[x]=f[u]+sz[1]-2*sz[x];
        DP(x,u);
    }
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);    
    }dfs(1,1,1);//以1为根节点跑出子树大小.
    DP(1,1);ll ans=0;
    for(int i=1;i<=n;i++)    ans=max(ans,f[i]);
    printf("%lld\n",ans);
    return 0;
}

E - Kate and imperfection

因为gcd一定是所有数的最大约数,所以我们不妨枚举到n的时候,每个点的最大公约数是谁即可.

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int b[N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+i;j<=n;j+=i)
        {
            b[j]=i;
        }
    }sort(b+1,b+1+n);for(int i=2;i<=n;i++)    cout<<b[i]<<' ';puts("");
    return 0;
}