牛客小白月赛116 题解

A 简单游戏

问 最大值的序号是否为给定数值，按题意输出即可。

a=list(map(int,input().split()))
print(["No","Yes"][max(a[:3])==a[a[3]-1]])

B 邪神的战斗力

可以看出 就是所有邪神的战斗力之和的 倍，所以我们对输入的 求和，再除以 就可以得到所有邪神的战斗力之和 。那么对于第 个邪神，她的战斗力就是 。

from sys import stdin

input=lambda:stdin.readline()
ri=lambda:int(input())
rl=lambda:list(map(int,input().split()))

n=ri()
a=rl()
s=sum(a)//(n-1)
print(*[s-a[i] for i in range(n)])

C Poi 的新加法 简单变体

发现 。（此处 指代二进制与位运算。）

本题中 。可以直接暴力运算通过本题。

from sys import stdin

input=lambda:stdin.readline()
ri=lambda:int(input())
rl=lambda:list(map(int,input().split()))

T=ri()
for _ in range(T):
	n,q=rl()
	a=rl()
	for __ in range(q):
		l,r=rl()
		cur=a[l-1]
		for i in range(l,r):
			cur=(cur&a[i])<<1
		print(cur)

D Poi 的消消乐

对于形如 AAAAA 的，可以直接消除到只剩一个

对于形如 AABBA 的，可以一直通过选择 消除到只剩 BA

对于形如 AAABB 的，由于最后一定会在开头留一个 A，最后只能通过选择 将 B 消除到不超过三个

注意题目并未保证大写字母一定是 AB

from collections import Counter
from sys import stdin

input=lambda:stdin.readline()
ri=lambda:int(input())
rl=lambda:list(map(int,input().split()))

T=ri()
for _ in range(T):
    n=ri()
    s=input()
    cnt=Counter(s)
    if cnt[s[0]]==n:
        print(1)
        continue
    sl=1
    while sl<n and s[sl]==s[0]:
        sl+=1
    if sl==cnt[s[0]]:
        print(1+min(3,n-sl))
    else:
        print(2)

E 旷课大师

原题解被证明为假题解。正在讨论。作为本场负责人，对牛客工作人员以及参赛者深感抱歉。

更新：

确定本场 Unrated。再次向牛客工作人员和参赛者表达我的歉意。

对于使用第一种能力的情况我们考虑二分答案，二分答案 后用 DP 检查可行性， 在第 天已经出席了 次的情况下，老师的怀疑值在全程不大于 的情况下，当前能达到的最小值。

对于第二种能力，由于怀疑值不会减小，我们可以考虑选出 天，并让这些天的 值和最大。对这个问题可以使用 DP 解决，设 表示当前取到第 天，已取了 次时因出席减少的怀疑值的最大值。

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
using ull=unsigned long long;
const ll INF=100000000000000;
ll a[30004]={0};
ll n,k,m;
bool check(ll maxn) {
    vector<vector<ll>> dp(n+5,vector<ll>(k+5,INF));
    dp[0][0]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=k;++j){
            if(dp[i-1][j]+a[i]<=maxn)
                dp[i][j]=min(dp[i][j],dp[i-1][j]+a[i]);
            if(j>0&&dp[i-1][j-1]!=INF)
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]/2);
        }
    }
    return dp[n][k]!=INF;
}
void solve() {
    cin >> n >> k >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    ll ans1, ans2 = 0;
    if (k * m >= n) {
        ans2 = 0;
    } else {
        vector<ll> prefix_sum(n + m + 5, 0);
        for (int i = 1; i <= n; ++i)
            prefix_sum[i] = prefix_sum[i - 1] + a[i];
        vector<vector<ll>> dp(n + 5, vector<ll>(k + 5, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                if (i - m >= 0)
                    dp[i][j] = max(dp[i][j], dp[i - m][j - 1] + (prefix_sum[i] - prefix_sum[i - m]));
            }
        }
        ans2 = prefix_sum[n] - dp[n][k];
    }
    ll l = 0, r = ans2+7;
    while (l < r) {
        ll mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    ans1 = l;

    cout << min(ans1, ans2) << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
//    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

F Poi 的新加法 困难变体

发现 。（此处 指代二进制与位运算。）

由于每次运算只有在 当前位均为 1 的情况下，左移，而 ，可以发现 的情况下，这个值如果不为 0，最低位 一定已经大于等于 了，如果再进行下一次运算，由于，答案一定为 0。

from sys import stdin

ri=lambda:int(stdin.readline())
rl=lambda:list(map(int,stdin.readline().split()))
T=ri()
for _ in range(T):
	n,q=rl()
	a=rl()
	for __ in range(q):
		l,r=rl()
		cur=a[l-1]
		for i in range(l,r):
			cur=(cur&a[i])<<1
			if cur==0:
				break
		print(cur)

G 经典 DP

我们发现 的范围很小，这意味着每次乘以的 实际上种类不超过 ，所以我们可以先跑一遍 的值域dp，把和为 的所有方案数求出来，即求出 代表子段和为 的方案数。

然后我们考虑求出每一轮中可以使得 变为 的方案数，这可以双重循环进行转移，但是这样超时也爆空间，于是考虑矩阵快速幂优化，先跑出一轮中 到 的方案数 ，其中 ，求出每次的转移方程矩阵，再矩阵快速幂乘以初始矩阵（，其他位置均为 ）跑一下即可。

#include<bits/stdc++.h>
#define print cout<<format
#define up(i,x,y) for (auto i=x;i<=y;i++)
#define down(i,x,y) for (auto i=x;i>=y;i--)
#define elif else if

using ll=long long;
using namespace std;

const ll mod=1000000007;

template<typename T=ll>
struct matrix{
	int n;
	vector<vector<T>>a;
	matrix (int _n): n(_n),a(_n,vector<T>(_n,0)) {}
	matrix operator* (matrix<T> &b){
		matrix<T> res{n};
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
				for (int k=0;k<n;k++)
					res[i][j]=(res[i][j]+a[i][k]*b[k][j]%mod)%mod;
		return res;
	}
	matrix operator* (matrix<T> &&b){ return (*this)*b; }
	vector<T>& operator[] (int y){ return a[y]; }
};

template<typename T=ll>
T qpow(T a,ll b){
    T res{a.n};
    for (int i=0;i<a.n;i++) res[i][i]=1;
    while(b){
            if (b&1) res=res*a;
            a=a*a;
            b>>=1;
    }
	return res;
}

void solve(){
	ll n;
	cin>>n;
	vector<ll>a(n+1);
	up(i,1,n) cin>>a[i];
	ll c,m,k,t;
	cin>>c>>m>>k>>t;
	c%=m;
	vector v(m,0ll);
	up(i,1ll,n){
		a[i]%=m;
		vector<ll> s(m,0ll);
		s[a[i]]=1;
		up(j,0,m-1) s[(a[i]+j)%m]=(s[(a[i]+j)%m]+v[j])%mod;
		up(j,0,m-1) v[j]=(v[j]+s[j])%mod;
	}
	matrix p(m);
	up(i,0ll,m-1){
		up(j,0ll,m-1){
			p[j][i*j%m]=(p[j][i*j%m]+v[i])%mod;
		}
	}
	matrix q(m);
	q[c][c]=1;
	auto res=q*qpow(p,t);
	print("{}",res[c][k]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    // cin>>T;
    while(T--) solve();
}