第一次打cf的月赛……

A

题意：给你一个数列，问你能不能保证里面只有两种数且个数相等。2<=n<=100，1<=ai<=100。

水……没看完题就交了结果YES的时候还要输出这两种数是什么，然后就+1了……

#include <iostream>

#define maxn 105

using namespace std;

int n,a,t[maxn],c[maxn],d[maxn];

int main()

{

    cin>>n;

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

    {

        cin>>a;

        t[a]++;

    }

    int cnt=;

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

    {

        if(t[i])

        {

            c[++cnt]=t[i];

            d[cnt]=i;

        }

    }

    if(cnt!=)

        cout<<"NO";

    else if(c[]!=c[])

        cout<<"NO";

    else

        cout<<"YES"<<endl<<d[]<<' '<<d[];

    return ;

 }

B

题意：给你一个只含字母的字符串，求仅由小写字母构成的最长子串。

从左到右扫一遍同时记录长度len，遇到大写字母就更新答案并把len归零就好了。一遍过。

#include <iostream>

#include <string>

#include <cctype>

#include <cstring>

using namespace std;

int n;

string s;

bool used[];

int main()

{

    cin>>n>>s;

    int len=,cnt=,ans=;

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

    {

        if(isupper(s[i]))

        {

            memset(used,false,);

            len=;

            cnt=;

        }

        else

        {

            len++;

            if(!used[s[i]])

            {

                used[s[i]]=true;

                cnt++;

                ans=max(ans,cnt);

            }

        }

    }

    cout<<ans;

    return ;

}

C

题意：一条直线道路，起点为0，终点为a，有一辆车在起点和终点来回开k次（来算一次，回算一次）。车的油箱有b汽油，每走1路程就耗1汽油。在路上f的位置有一个加油站，可以帮你把油箱加满。问要完成这k次来回最少需要加多少次油。

如果车现在停在加油站，并且油还够开到终点（或者起点）再回头开到加油站，那么显然不用加油。

干脆把加油站当作检查点，每次检查下还剩多少油，判断需不需要加油。k次以后输出结果。如果加了油也回不来加油站，那么输出-1。要注意特判第一回还有最后一回。

四遍才过……

#include <iostream>

using namespace std;

int a,b,f,k;

int main()

{

    cin>>a>>b>>f>>k;

    int ans=,pet=b-f;

    if(pet<)

    {

        cout<<-;

        return ;

    }

    bool ahead=true;

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

    {

        if(ahead)

        {

            if(pet-*(a-f)>=)

                pet-=*(a-f);

            else

                pet=b-*(a-f),ans++;

        }

        else

        {

            if(pet-*f>=)

                pet-=*f;

            else

                pet=b-*f,ans++;

        }

        ahead^=;

        if(pet<)

        {

            cout<<-;

            return ;

        }

    }

    if(ahead)

    {

        if(pet-(a-f)<)

        {

            if(b-(a-f)>=)

                ans++;

            else

            {

                cout<<-;

                return ;

            }

        }

    }

    else

    {

        if(pet-f<)

        {

            if(b-f>=)

                ans++;

            else

            {

                cout<<-;

                return ;

            }

        }

    }

    cout<<ans;

    return ;

}

D

题意：给你一个n项数列，里面的数字均在1~n范围内，问最少替换多少个数字才能变成一个1~n的排序，输出字典序最小的方案。

细节貌似有点多，还没做出来……

E

题意：有n个物品，每个物品价值为pi，拿起来要ti的时间，但是这个物品在时间大于等于di时就不能拿了。问怎样使拿到的物品价值之和最大。

容易看出这是道傻逼背包题，得f(i,j)=max{f(i-1,j), f(i-1,j-t[i])+p[i]} (j<d[i]且j>=t[i])，答案就是max{f(n,x) | 0<=x<=2000}。

当时还不懂怎么输出方案，比赛完了才想到每次转移记录一下，然后从答案开始逆过来找哪个物品被拿了。

然后交了上去，WA了。跑去看下别人的AC代码，发现别人都对物品按照di升序排序再选了。我也试了一发，交上去马上就A了。

之后才想明白，f(i,j)是按照1,2,...,i的顺序选择物品得到的价值最大值，如果不排序就会导致有些在后面但是d很小的物品选不到。

#include <iostream>

#include <stack>

#include <algorithm>

using namespace std;

int n;

struct item { int t, d, p, id; } a[];

bool cmp(const item& x, const item& y) { return x.d < y.d; }

int dp[][];

bool took[][];

int main()

{

    ios::sync_with_stdio(false);

    int ans = ;

    cin >> n;

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

    {

        a[i].id = i;

        cin >> a[i].t >> a[i].d >> a[i].p;

    }

    sort(a + , a +  + n, cmp);

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

    {

        ans = ;

        for (int j = ; j <= ; j++)

        {

            if (j < a[i].d && j >= a[i].t && dp[i - ][j - a[i].t] + a[i].p >= dp[i - ][j])

            {

                dp[i][j] = dp[i - ][j - a[i].t] + a[i].p;

                took[i][j] = true;

            }

            else

                dp[i][j] = dp[i - ][j];

            if (dp[i][j] >= dp[i][ans])

                ans = j;

        }

    }

    cout << dp[n][ans] << endl;

    stack<item> s;

    int j = ans;

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

    {

        if (took[i][j])

        {

            s.push(a[i]);

            j -= a[i].t;

        }

    }

    cout << s.size() << endl;

    while (!s.empty())

    {

        cout << s.top().id << ' ';

        s.pop();

    }

    return ;

}

未完待+1s（可能）

巴特西

Codeforces Round #436 (Div. 2)

A

B

C

D

E

最新文章

热门文章