比赛链接：Dashboard - Codeforces Global Round 25 - Codeforces

A

题意：有 $n$ 栈灯从 $1-n$ 排成一排，初始时全是熄灭状态，每次只能选择两盏不相邻的熄灭的灯将其点亮，问能否达到一种给定的状态。

将最终状态中点亮的灯分成前后两半，每次分别在两半中选一盏灯。注意特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        char s[55];
        cin>>s;
        int num=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='1')num++;
        }
        if(num%2==1)
        {
            cout<<"NO\n";
            continue;
        }
        int p=0;
        bool flag=1;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='1')
            {
                p++;
            }
            if(p==num/2 )
            {
                if(num==2&&s[i+1]=='1')
                flag=0;
                break;
            }
        }
        if(flag)cout<<"YES\n";
        else cout<<"NO\n";
    }
}

B

题意：有 $n$ 头牛比赛，每头牛有个能力值，从头到尾两两比赛，赢家和下一个比较，输的淘汰。现在排在第 $k$ 位的牛可以选择和任一个位置的牛交换，求这头牛能赢的比赛的最大数目。

首先考虑直接把第 $k$ 头牛放在第一个位置的答案是多少，再考虑将其和 $k$ 之前最大的牛交换的答案是多少，比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int a[n+5];
        for(int i=1;i<=n;i++)cin>>a[i];
        bool flag=0;
        int ans=-1;
        for(int i=1;i<k;i++)
        {
            if(a[i]>a[k])
            {
                ans=i-2;
                
                swap(a[i],a[k]);
                k=i;
            
                flag=1;
                break;
            }
        }
        if(!flag)
        {
            swap(a[k],a[1]);
            k=1;
        }

        int num;
        if(k==1)num=0;
        else num=1;
        for(int i=k+1;i<=n;i++)
        {
            if(a[i]<a[k])num++;
            else break;
        }
        cout<<max(ans,num)<<endl;
    }
}

C

有一家公司卖票一共 $n$ 天，每一天的单价是 $a_i$ ，现在需要采购 $k$ 张票，每天买的票的最大数量不能超过 $m$ ，而且若在某一天买了 $x$ 张票，那么以后每一天的单价都会增加 $x$ 。求最小代价。

假设买一天买 $b_i$ 张，那么一共的消费就是
$$
\sum(a_i+\sum b_j)b_i=\sum a_ib_i+\sum_{1\leq j<i\leq n}b_ib_j
$$
可得最后的结构与 $a$ 的顺序无关，那么如下贪心：将 $a_i$ 从小到大排序，依次每一个 $b_i$ 都分配 $m$ ，最后一个分配 $k%m$ 。易得到前项这样是最大的，那么对于第二项，有：
$$
\sum_{1\leq j<i\leq n}b_ib_j=\frac{1}{2}(\sum b_i)^2-\frac{1}{2}(\sum b_i^2)
$$
此时 $\frac{1}{2}(\sum b_i)^2$ 是定值，而要使 $\frac{1}{2}(\sum b_i^2)$ 最大，就要使每个 $b_i$ 尽可能一样，与贪心策略符合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    int a[n+5];
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int ans=0;
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        if(tot+m<=k)
        {
            tot+=m;
            ans+=m*a[i];
        }
        else
        {
            ans+=(k-tot)*a[i];
            break;
        }
    }
    ans+=m*m*(k/m)*(k/m-1)/2+(k-k/m*m)*(k/m)*m;
    cout<<ans<<endl;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

math

D

题意：有一个人买东西，有 $n$ 元钱，而且他来到一个摊子就会尽最大可能买下能买的东西。现需要你摆出不超过60个摊子，每个摊子物品无限，但价格相同，使得这个人在依次光顾每个摊子后恰好买 $k$ 件东西。

若 $k=n$ ，那么只需要一个卖价为1的摊子即可。

其他情况，考虑只摆两个摊子（很多这种构造题都是构造极少的数据即可通过），第一个摊子只买一个，第二个摊子设卖价为1，因此需满足：
$$
n/(n-k+1)=1,\ n-k+1>k-1
$$
即若满足
$$
2k<n+1
$$
则一定可以构造。

若不满足这个条件，即需要买的物品超过了钱的一半，那么每个摊子的价格不能超过2，经简单验证显然不成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    long long n,k;
    cin>>n>>k;
    if(k==n)
    {
        cout<<"YES\n1\n1\n";
        return ;
    }
    if(k>n)
    {
        cout<<"NO\n";
        return ;
    }
    if(2*k>=n+2)
    {
        cout<<"NO\n";
        return  ;
    }
    cout<<"YES\n2\n"<<n-k+1<<" "<<1<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

math

E

题意：给出一个串 $s$ ，找出一种划分，使得将其划分成多个子串后每个子串都不是回文串。

若 $s$ 本来就不是回文，那么直接输出即可。

其他情况，考虑最多划分成两个串：枚举分界点，若依次分割两个段都不是回文那么满足条件。用manacher判断是否是回文。

若以任意一个位置划分都不满足条件，可以证明那么这个串一定不存在合法划分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

vector<int> manacher(string s)
{
    string t;
    for(auto c:s)
    {
        t+=string("#")+c;
    }
    t+=string("#");
    int n=t.length();
    vector<int>p(n+2);
    t="$"+t+"%";
    
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=max((int)0,min(r-i,p[l+r-i]));
        
        while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++;
        if(i+p[i]>r)
        {
            r=i+p[i];
            l=i-p[i];
        }
    }
    return vector<int>(begin(p)+2,end(p)-2);
}

void solve()
{
    string s;
    cin>>s;
    int n=s.length();
    vector<int>f=manacher(s);
    if(f[n-1]!=n)
    {
        cout<<"YES\n1\n"<<s<<'\n';
        return ;
    }
    bool flag=0;
    for(int i=0;i<n-1;i++)
    {
        if(f[i]<i && f[i*2+1+n-1-i]<n-1-i)
        {
            cout<<"YES\n2\n";
            for(int j=0;j<=i;j++)cout<<s[j];cout<<" ";
            for(int j=i+1;j<n;j++)cout<<s[j];cout<<endl;
            return ;
        }
    }
    cout<<"NO\n";
    return ;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

strings