A. Halloumi Boxes

题目链接

题意

有一个长度为n的数组，你每次操作能使一段区间反转，最长能反转的区间的长度是k，问进行若干次操作能否使数组变成非降序排列

分析

  • k>=2就可以一直选长度为2的区间反转，相当于交换相邻的两个数，这样就可以像冒泡排序那样排好序。
  • k=1说明不能进行任何操作，所以判断初始数组是否是非降序即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int >vt(n+1);
    for(int i=1;i<=n;i++){
        cin>>vt[i];
    }
    if(k>=2){
        cout<<"YES"<<endl;
        return;
    }
    for(int i=1;i<=n-1;i++){
        if(vt[i]>vt[i+1]){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

B. Rook

题目链接

分析

模拟题，根据题意模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve(){
    string s;
    cin>>s;
    char t=s[0];
    char p=s[1];
    for(int i=1;i<=8;i++){
        string c="";
        c+=t;
        c+=(char)('0'+i);
        if(c!=s){
            cout<<c<<endl;
        }
    }
    for(int i=0;i<8;i++){
        string c="";
        c+=(char)('a'+i);
        c+=p;
        if(c!=s){
            cout<<c<<endl;
        }
    }
}

C. YetnotherrokenKeoard

题目链接

题意

有一个字符串，遇到$b$就删去最后出现的小写字母，遇到$B$则删去最后出现的大写字母

分析

模拟题。我们令$flag[n]$设为最后需要输出的元素(1代表需要输出，0代表不输出)，把出现小写字母和大写字母的下标分别存入不同的数组，如果遇到$b$则在删去存小写字母下标的数组的最后一个元素并在$flag$里的对应元素操作，遇到$B$同理。

代码

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
void solve(){
    string s;
    cin>>s;
    vector<int>da;
    vector<int>xia;
    int n=s.length();
    vector<int>flag(n);
    for(int i=0;i<s.length();i++){
        if(s[i]=='b'){
            if(xia.size()!=0){
                flag[xia.back()]=0;
                xia.pop_back();
            }
        }
        else if(s[i]=='B'){
            if(da.size()!=0){
                flag[da.back()]=0;
                da.pop_back();
            }
        }
        else{
            flag[i]=1;
            if(s[i]>='a' && s[i]<='z'){
                xia.push_back(i);
            }
            else{
                da.push_back(i);
            }
        }
    }
    for(int i=0;i<n;i++){
        if(flag[i]){
            cout<<s[i];
        }
    }
    cout<<endl;
}

D. StORage room

题目链接

题意

有一个长度为$n$的数组$a$和一个$n*n$的表$M$，满足以下条件:
$$M_{i,j}=a_{i} | a_{j} (i!=j)$$
求一个满足条件的数组$a$，如果没有则输出$NO$
(输入满足$M_{i,j}=M_{j,i}$)

分析

我们把$a_{i}$的二进制数中1所在的位置记为集合$A$，把$a_{i}$和$a_{j}$取或运算得到的结果的二进制数中1的所在的位置记为集合$B_{j}$
可以发现，$A \subseteq B_{j} \quad (j=1, 2, \dots, n; \ j \neq i)$，所以我们把$B_{j}$取交集，这样得到的结果肯定满足条件。取交集反映在数字上就是
$$ a_{i} \&= M_{i,j} $$

代码

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
void solve(){
    int n;
    cin>>n;
    vector<vector<int> >vt(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>vt[i][j];
        }
    }
    vector<int>ans(n+1);
    for(int i=1;i<=n;i++){
        int an=(1<<30)-1;
        for(int j=1;j<=n;j++){
            if(i==j){
                continue;
            }
            an=(an&vt[i][j]);
        }
        ans[i]=an;
    }
    int flag=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((ans[i]|ans[j])!=vt[i][j] && i!=j){
                flag=0;
            }
        }
    }
    if(flag){
        cout<<"YES"<<endl;
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" \n"[i==n];
        }
    }
    else{
        cout<<"NO"<<endl;
    }
}

E. Theofanis’ Nightmare

题目链接

题意

把序列$a$分成若干子序列，设每个序列的位置为$i$，求所有子序列的和和子序列的位置的乘积的和的最大值

分析

我们假设一开始一个数是一个子序列，那么初始贡献就是$$ \sum_{i=1}^n a_{i}*i $$
然后我们从头开始遍历，假设当前这个数为$a_i$，如果这个数要和前面的数合并，对答案的贡献就是$-\sum_{j=i}^n a_{j}$，也就是说如果这个数的后缀和是负数，就可以使答案变大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve(){
    ll n;
    cin>>n;
    vector<int>vt(n+1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>vt[i];
        ans+=(ll)(vt[i]*i);
    }
    vector<ll>sum(n+2);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+vt[i];
    }
    for(int i=2;i<=n;i++){
        if(sum[n]-sum[i-1]<0){
            ans-=(sum[n]-sum[i-1]);
        }
    }
    cout<<ans<<endl;
}

F. Maximum And Queries (easy version)

题目链接

题意

有一数组$a$和$q$次询问，每次询问都会给你一个$k$，你可以对数组进行最多$k$次操作，每次操作你都可以对数组中的数+1，问你数组的与和最大是多少

分析

对于easy version每次询问可以暴力一点。如果答案的二进制数的某一位是1，那么数组中的所有数这一位一定是1，所以我们贪心考虑。从最高位开始，计算要让所有数的这一位为1需要多少次操作，如果足够，答案则加上它，如果不够再考虑低一位

代码

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
void solve() {
    int n, q;
    cin >> n >> q;
    vector<ll> vt(n+1);
    for (int i = 1; i <= n; i++){
        cin >> vt[i];
    }
    vector<ll>v=vt;
    while (q--) {
        ll k;
        cin >> k;
        ll ans = 0;
        vt=v;
        for (int b = 60; b >= 0; b--) {
            ll p=(1ll<<b);
            ll sum=0;
            for(int i=1;i<=n;i++){
                if((vt[i]&p)==0){
                    sum=(ll)sum+p-(vt[i]%p);
                }
                if(sum>k){
                    break;
                }
            }
            if(sum<=k){
                k-=sum;
                ans+=p;
                for(int i=1;i<=n;i++){
                    if((vt[i]&p)==0){
                        vt[i]-=vt[i]%p;
                        vt[i]+=p;
                        
                    }
                }
            }
        }
        cout << ans << endl;
    }
}