佳木斯集训Day2

D2好点了，最起码不像之前那么水

T1按照常规操作是个找规律，类似于括号匹配的题，但是又不是，推进栈里，然后看最长的左括号有多少个，然后直接cout就可以了

#include <bits/stdc++.h>

using namespace std;

int n,point,ans=-;

char a[];

stack <char>s;

int main()

{

    cin>>n;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

        s.push(a[i]);

        if(s.top()=='(')

        point++;

        else

        s.pop(),point--;

        ans=max(ans,point);

    }

    if(ans%==)

    cout<<ans/+<<endl;

    else

    cout<<ans/<<endl;

}

哎，居然可以折叠代码，我才发现

T2本来以为是个搜索，结果正解就是个搜索，dfs+一个简单的找规律，咳咳，看完题解就会了

不知道为什么，这道题我爆0了

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int t,head[],x,y,n,in[],ans[];

int point=;

ll sum;

struct Tree{

    int v,nxt;

}g[];

void add(int u,int v)

{

    g[++point].v=v;

    g[point].nxt=head[u];

    head[u]=point;

}

void dfs(int x,int nw)

{

    ans[x]=;

    for(int i=head[x];i;i=g[i].nxt)

    {

        if(g[i].v==nw)continue;

        dfs(g[i].v,x);

        ans[x]+=ans[g[i].v];

    }

    sum+=ans[x];

}

void solve(int x,int square,ll nw)

{

    sum=max(sum,nw);

    for(int i=head[x];i;i=g[i].nxt)

    {

        if(g[i].v==square)

        continue;

        solve(g[i].v,x,nw+n-2LL*ans[g[i].v]);

    }

}

int main()

{

    memset(head,,sizeof(head));

    cin>>n;

    for(int i=;i<=n-;i++)

    {

        cin>>x>>y;

        add(x,y);

        add(y,x);

        in[x]++;

        in[y]++;

    }

    dfs(,);

    solve(,,sum);

    cout<<sum<<endl;

    return ;

}

T3 是个神奇的二分答案，加上了一个神奇的剪枝就能AC，然而蒟蒻的我并没有想到剪枝，所以我RE60

 #include <bits/stdc++.h>

 #define ll long long

 using namespace std;

 ll n,m,ans=;

 ll c;

 ll pos[];

 ll start,finish,admit,dis,maxn;

 bool Black(ll k)

 {

     ll v=k;

     ll point=;

     for(ll i=start;i<finish;i++)

     {

         if(k<(pos[i+]-pos[i])*c)

         return ;

         if(v<(pos[i+]-pos[i])*c)

         {

             v=k;

             point++;

         }

         v=v-(pos[i+]-pos[i])*c;

         if(point>admit||v<)

         return ;

     }

     return ;

 }

 void divide(ll l,ll r)

 {

     if(l==r)

     {

         ans=max(ans,l);

         //cout<<ans<<endl;

         return ;

     }

     ll mid=(l+r)/;

     if(Black(mid)==)

     divide(l,mid);

     else

     divide(mid+,r);

 }

 int main()

 {

     cin>>n>>m;

     for(ll i=;i<=n;i++)

     cin>>pos[i];

     for(ll i=;i<=m;i++)

     {

         cin>>start>>finish>>c>>admit;

         if(ans&&Black(ans))

         continue;

         divide(,1e18);

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

佳木斯集训Day2

最新文章

热门文章