A. Best Subsegment
题意 找 连续区间的平均值 满足最大情况下的最长长度
思路：就是看有几个连续的最大值
#include<bits/stdc++.h>
using namespace std;
const int maxn= 1e5+;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
int maxnum=;
for(int i=;i<n;i++)scanf("%d",&a[i]),maxnum=max(maxnum,a[i]);
int ans=;
int temp=;
for(int i=;i<n;i++){
if(maxnum==a[i]&&i+<n&&a[i]==a[i+])temp++;
else ans=max(temp,ans),temp=;
}
printf("%d",ans);
return ;
}
B. Emotes
题意： n个数字 （正） 每个可以用任意次 一共m次 一个数字不能用超过连续k次 问m次 用的数字的和的最大值是多少
思路：直接找最大和次大 最大k次+次大1次 循环 最后处理一下余数即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
int a[maxn];
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
long long ans=;
int first=a[n-],second=a[n-];
ans=1ll*m/(k+)*(1ll*first*k+second);
m%=(k+);
ans+=1ll*m*first;
printf("%I64d\n",ans); return ;
}
C. Magic Ship
题意：给出n个风向 风是循环运作的 并且给出起点和终点（二维）问可否到达终点
思路：将x y分解 对风求前缀和 二分找步数 看是否满足题意 这里记得二分范围要大 1e18 不然就会gg（虽然过了 但是我总感觉有点怪怪的好像能出数据hack 可能是有完备性证明的，只是我太菜不会证吧。。）
#include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))
#define F first
#define S second
#define pii pair<int ,int >
#define mkp make_pair
#define pb push_back
using namespace std;
const long long inf=1e18;
typedef long long ll;
const int maxn=1e5+;
map<char,pii>mp;
ll sumx[maxn],sumy[maxn];
char s[maxn];
void init(){
mp['U']={,};mp['D']={,-};mp['L']={-,};mp['R']={,};
}
int n;
ll X1,Y1,X2,Y2;
bool check(ll mid){
ll q=mid/n,r=mid%n;
ll nx=X1+sumx[n]*q+sumx[r];
ll ny=Y1+sumy[n]*q+sumy[r];
return (abs(nx-X2)+abs(ny-Y2))<=mid;
}
int main(){
init();
scanf("%lld%lld%lld%lld",&X1,&Y1,&X2,&Y2);
scanf("%d",&n);
scanf("%s",s+);
FOR(i,,n){
sumy[i]=sumy[i-]+mp[s[i]].S;
sumx[i]=sumx[i-]+mp[s[i]].F;
}
ll l=,r=inf;
ll ans=inf;
while(l<=r){
ll mid=l+r>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
if(ans!=inf)cout<<ans<<endl;
else cout<<-<<endl; return ;
}
D. Magic Gems
题意 一个特殊基因可以分成m个普通基因 问刚好n个基因有多少种组成方式 1<=n<=1e18 2<=m<=100
思路:看这数据范围 这题目就一股浓浓的矩阵快速幂的味道 直接列出转移式 构造矩阵 dp[n]=dp[n-1]+dp[n-m];
(1....10) 大概就这意思吧 然后直接套矩阵就行了 （写的时候傻逼用int读long long） m*m的矩阵
(1.......0)
(01......0)
(001......0)
.....
#include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))
#define F first
#define S second
#define pii pair<int ,int >
#define mkp make_pair
#define pb push_back
using namespace std;
const long long inf=1e18;
typedef long long ll;
const int mod=1e9+;
long long n,m;
struct mat{
ll m[][];
mat(){
MS(m,);
}
};
mat Mul(mat a,mat b,int n){
mat res;
int i,j,k;
for( i=;i<=n;i++){
for( j=;j<=n;j++){
res.m[i][j]=;
for(k=;k<=n;k++){
res.m[i][j]=(res.m[i][j]+(a.m[i][k]*b.m[k][j])%mod+mod)%mod;
}
}
}
return res;
}
mat fpow(mat a,ll b,int n){
mat ans;
for(int i=;i<=n;i++)ans.m[i][i]=;
while(b){
if(b&)ans=Mul(ans,a,n);
a=Mul(a,a,n);
b>>=;
}
return ans;
}
const int maxn=1e5+;
int dp[];
int main(){
scanf("%lld%lld",&n,&m);
if(n<=m){
if(n==m)cout<<<<endl;
else
cout<<<<endl;
return ;
}
dp[]=;
for(int i=;i<m;i++)dp[i]=;
dp[m]=dp[]+dp[m-];
mat d;
d.m[][]=;d.m[][m]=;
for(int i=;i<=m+;i++)d.m[i][i-]=;
mat e;
for(int i=;i<=m+;i++){
e.m[m+-i][]=dp[i-];
}
/* for(int i=1;i<=m+1;i++){
cout<<e.m[i][1]<<endl;
}
for(int i=1;i<=m+1;i++){
for(int j=1;j<=m+1;j++){
cout<<d.m[i][j]<<" ";
}
cout<<endl;
}
*/ d=fpow(d,n-m,m+);
d=Mul(d,e,m+);
cout<<(d.m[][])%mod<<endl; return ;
}