牛客小白月赛 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 的消消乐

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 旷课大师

#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 的新加法 困难变体

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

#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();
}