牛客小白月賽116 題解
A 簡(jiǎn)單游戲
問(wèn) 最大值的序號(hào)是否為給定數(shù)值，按題意輸出即可。
a=list(map(int,input().split()))
print(["No","Yes"][max(a[:3])==a[a[3]-1]])
B 邪神的戰(zhàn)斗力
可以看出 就是所有邪神的戰(zhàn)斗力之和的
倍，所以我們對(duì)輸入的
求和，再除以
就可以得到所有邪神的戰(zhàn)斗力之和
。那么對(duì)于第
個(gè)邪神，她的戰(zhàn)斗力就是
。
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 的新加法 簡(jiǎn)單變體
發(fā)現(xiàn) 。（此處
指代二進(jìn)制與位運(yùn)算。）
本題中 。可以直接暴力運(yùn)算通過(guò)本題。
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 的消消樂(lè)
對(duì)于形如 AAAAA 的，可以直接消除到只剩一個(gè)
對(duì)于形如 AABBA 的，可以一直通過(guò)選擇 消除到只剩
BA
對(duì)于形如 AAABB 的，由于最后一定會(huì)在開(kāi)頭留一個(gè) A，最后只能通過(guò)選擇 將
B 消除到不超過(guò)三個(gè)
注意題目并未保證大寫(xiě)字母一定是 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 曠課大師
原題解被證明為假題解。正在討論。作為本場(chǎng)負(fù)責(zé)人，對(duì)?？凸ぷ魅藛T以及參賽者深感抱歉。
更新：
確定本場(chǎng) Unrated。再次向牛客工作人員和參賽者表達(dá)我的歉意。
對(duì)于使用第一種能力的情況我們考慮二分答案，二分答案 后用 DP 檢查可行性，
在第
天已經(jīng)出席了
次的情況下，老師的懷疑值在全程不大于
的情況下，當(dāng)前能達(dá)到的最小值。
對(duì)于第二種能力，由于懷疑值不會(huì)減小，我們可以考慮選出 天，并讓這些天的
值和最大。對(duì)這個(gè)問(wèn)題可以使用 DP 解決，設(shè)
表示當(dāng)前取到第
天，已取了
次時(shí)因出席減少的懷疑值的最大值。
#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 的新加法 困難變體
發(fā)現(xiàn) 。（此處
指代二進(jìn)制與位運(yùn)算。）
由于每次運(yùn)算只有在 當(dāng)前位均為 1 的情況下，左移，而
，可以發(fā)現(xiàn)
的情況下，這個(gè)值如果不為 0，最低位
一定已經(jīng)大于等于
了，如果再進(jìn)行下一次運(yùn)算，由于
，答案一定為 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 經(jīng)典 DP
我們發(fā)現(xiàn) 的范圍很小，這意味著每次乘以的
實(shí)際上種類(lèi)不超過(guò)
，所以我們可以先跑一遍
的值域dp，把和為
的所有方案數(shù)求出來(lái)，即求出
代表子段和為
的方案數(shù)。
然后我們考慮求出每一輪中可以使得 變?yōu)?
的方案數(shù)，這可以雙重循環(huán)進(jìn)行轉(zhuǎn)移，但是這樣超時(shí)也爆空間，于是考慮矩陣快速冪優(yōu)化，先跑出一輪中
到
的方案數(shù)
，其中
，求出每次的轉(zhuǎn)移方程矩陣，再矩陣快速冪乘以初始矩陣（
，其他位置均為
）跑一下即可。
#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();
}
新易盛公司福利 104人發(fā)布