T1:模板题

此题相对简单，就是读入的时候，用一个桶排，把读入数字的所有因数加1，然后，从大到小扫一遍，看一下以i为倍数的数是否有k个，然后输出即可。

见代码：

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

int n,v,k=,maxx=-0x3f3f3f,a[],t[],b[];

void g(int x)

{

    for(int i=;i*i<=x;i++)

    {

        if(x%i==)

        {

            t[i]++;

            t[x/i]++;

            if(i*i==x)

            t[i]--;

        }

    }

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&v);

        g(v);

        if(v>maxx)

        maxx=v;

    }

    for(int i=maxx;i>=;i--)

    {

        while(t[i]>=k)

        {

            b[k]=i;

            k++;

        }

    }

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

    printf("%d\n",b[i]);

    return ;

}

好题哉！！！

T2:伸展

因为是n²,但是本人只会暴力模拟，所以过。

T3：线索

思路：当遇上左括号，用一个大根堆储蓄起来。然后当遇上左括号时，将其压入一个小跟堆，若左堆为空，则弹出右堆堆顶。不然则弹出左堆堆顶。最后若左堆依然不为空，则清空左堆。此贪心正确性显然：当遇上右括号且左边有左括号时，优先拿代价大与其匹配。而若左边没有小括号，则不使用代价最小的右括号。最后若左括号有多，则全部弹出。

见代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

priority_queue<int,vector<int>,less<int> >q1;

priority_queue<int,vector<int>,greater<int> >q2;

ll n,k,k1=,red,ans;

char a[];

int main()

{

    freopen("assassin.in","r",stdin);

    freopen("assassin.out","w",stdout);

    scanf("%lld",&n);

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

    scanf(" %c",&a[i]);

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

    {

        scanf("%lld",&red);

        if(a[i]=='(')

        {

            q1.push(red);

        }

        else

        {

            q2.push(red);

            if(!q1.empty())

            {

                q1.pop();

                k++;

            }

            else

            {

                ans+=q2.top();

                q2.pop();

            }

        }

    }

    while(!q1.empty())

    {

        ans+=q1.top();

        q1.pop();

    }

    printf("%lld",ans);

    return ;

}

好题哉！！！

T4:自由

据大佬们说，此题是动归的斜率优化，当然数据有点小$n^{2}$也可以过。

但是……最基础的$n^{3}$我都不会。所以如清风般略过。

巴特西

中山Day10——普及

T1:模板题

好题哉！！！

T2:伸展

T3：线索

好题哉！！！

T4:自由

好题哉！！！

最新文章

热门文章