【题解】牛客OI月赛12-普及组

前言

qwq由于题目出现了一些洼点，导致了一些阅读理解上的差错，先说声对不起qwq
语文学的不好，我以后一定好好学

A 被鸽了的课本

只需要判断 $(x+y) \times ( 1 - a\%)$ 和 $(x + \frac{y}{2})$ 的大小就好了

考点：无

B 被鸽了的美男老师K

我们模拟一下这个过程，对被埋了的人打标记，然后统计一下相同点的人有多少个，把他们的方向转一下，循环 $t$ 次就行了效率 $O(nt)$

考点：模拟

坑点：同一个位置可能有两个人，而此时两个人向后转和对穿而过是没有区别的，但是如果是3个人就有区别了。

C 被鸽了的应急理智顶液

我们考虑按位拆分，然后从最高位往下贪心即可，显然一位最多被修改一次。

然后从最高位往下贪心，当前第 $i$ 位增加 $2^i$ 可以相当于下一位 $i-1$ 增加 $2 \times 2^(i-1)$ 。

所以要优先使得高的取满

具体的说：我们优先使得该位的or = 1，然后再使得xor = 1。

效率 $O(64N)$

考点：贪心

坑点：发现 $\sum_{i=1}^{62} 2^i >2^{63} - 1$ , 因此要开unsigned long long

D 被鸽了的文件清除

考虑 $dp[i][j][0/1]$ 表示到i为止，用了j次手动删除，最后一次用的什么删除

考虑转移

$dp[i][j][0] = max\{dp[i-1][j][0/1] + b[i]\};$

$dp[i][j][1] = max\{dp[i-1][j-1][0] + a[i]\};$

空间有点卡考虑滚动数组优化一下

考点：dp

坑点：要说的话就是要开long long吧

各题代码

A

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

int main()
{
    int a = _, b = _, c = _;
    double a1 = a + b * 0.5;
    double a2 = (a + b) * (100 - c) * 0.01;
    if(a1 >= a2) puts("By myself");
    else puts("Through school");
}

B

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int N = 1e3 + 5;

int n, t, x[N], b[N], vis[N];
int cnt[N << 1];

int main() 
{
    n = _; t = _;
    for( int i = 0; ++i <= n; )
        x[i] = _, b[i] = _, vis[i] = 0;
    for( int i = 1; i <= t; i++ ) 
    {
        for( int j = 1; j <= n; j++ ) 
            x[j] = x[j] + (b[j] == 0 ? -1 : 1); 
        for( int j = 1; j <= n; j++ )
            if(!vis[j]) cnt[x[j]] = 0;
        for( int j = 1; j <= n; j++ )
            if(!vis[j])    
                cnt[x[j]]++; 
        for( int j = 1; j <= n; j++ )
            if(!vis[j] && cnt[x[j]] > 1)
                b[j] ^= 1; //掉转方向
        for( int j = 1; j <= n; j++ )
            if(x[j] <= i)
                vis[j] = 1; 
    }    
    int tmp = 0;
    for( int i = 0; ++i <= n; )
        tmp += vis[i];
    cout << tmp << ln;
}

C

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

int n, k;
int cnt[64], s[64];
unsigned long long ans;

int main()
{
    n = _; k = _;
    for( int i = 0; ++i <= n; )
    {
        ll x = _;
        int flag = 0;
        for( int j = 62; j >= 0; j-- )
        {
            int tmp = ((1ll << j) & x)?1:0;
            flag |= tmp; 
            cnt[j] += tmp; 
            if(flag) s[j]++; 
        }
    }
    for( int i = 62; i >= 0; i-- )
    {
        if(s[i] == 0) continue;
        // cout << i << ln;
        if(cnt[i]) ans += (1llu << i);
        else if(k)  
            --k, cnt[i] = 1, ans += (1llu << i);
        if(cnt[i] & 1) ans += (1llu << i);
        else if(k)
        {
            --k; 
            ans += (1llu << i);    
        }
    }
    cout << ans << ln;
}

D

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int N = 1e5 + 5;
int n, k, a[N], b[N];
ll dp[2][1005][2];

int main()
{
    n = _; k = _;
    for( int i = 0; ++i <= n; )
        a[i] = _, b[i] = _;
    dp[1][0][0] = b[1];
    for( int i = 1; ++i <= n; )
    {
        dp[i & 1][0][0] = dp[(i - 1) & 1][0][0] + b[i];
        for( int j = 1; j <= k; j++ )
        {
            dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1]) + b[i];
            dp[i & 1][j][1] = dp[(i - 1) & 1][j - 1][0] + a[i];
        }
    }
    ll tmp = 0;
    for( int i = 0; i <= k; i++ )
        tmp = max( tmp, dp[n&1][i][0]),
        tmp = max( tmp, dp[n&1][i][1]);
    cout << tmp << ln;
}