E
看完题想到二分答案直接一步步贪心，没多想直接和队友说了下，感觉贪心会有点问题，放了一会后冷静分析了一下，发现返回造成的浪费是不可避免的，就很对了！
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
ll m;
ll a[N],b[N];
bool chk(ll ans){
for(int i=1;i<=n;i++) b[i]=(ans-1)/a[i]+1;
b[n+1]=0;
ll res=m;
for(int i=1;i<=n;i++){
if(b[i]<=0){
if(i<n) res--;
if(res<0) return 0;
continue;
}
res-=b[i]*2-1;
b[i+1]-=b[i]-1;
if(res<0) return 0;
}
return 1;
}
void work(){
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll l=0,r=1e18;
while(l<r){
ll mid=(l+r+1)>>1;
if(chk(mid)) l=mid;
else r=mid-1;
}
printf("%lld\n",l);
}
int main() {
int T; cin>>T; while(T--) work();
return 0;
}
G
考虑容斥没覆盖到的2，可以得到一个\(O(n^4)\)的dp，然后自闭一会觉得不可优化；但发现跑不满，用均值不等式和平方前缀和粗略地分析一下常数，发现上界会除掉48，然后就随便过了！
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=105,P=1e9+7;
void inc(int& x,int y){
x+=y;
if(x>=P) x-=P;
}
int prd(int x,int y){
x=1ll*x*y%P;
return x;
}
int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=prd(a,a)) if(x&1) s=prd(s,a);
return s;
}
int n,m,a[N];
int tot,pos[N];
int su[N],c[N][N],f[N][2][N*N];
void work(){
cin>>n>>m;
tot=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==2) pos[++tot]=i;
}
pos[0]=0; pos[tot+1]=n+1;
for(int i=1;i<=n;i++) su[i]=i*(i+1)/2;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
int last=i-1,sum=0;
for(int j=i;j<=n;j++){
if(a[j]==1){
sum+=su[j-last-1];
last=j;
}
c[i][j]=sum+su[j-last];
//cout<<"last="<<last<<endl;
//cout<<i<<" "<<j<<" "<<c[i][j]<<endl;
}
}
//memset(f,0,sizeof(f));
for(int i=1;i<=tot+1;i++) for(int p=0;p<2;p++) for(int x=0;x<=c[1][n];x++) f[i][p][x]=0;
f[0][0][0]=1;
for(int i=1;i<=tot+1;i++){
for(int j=0;j<i;j++){
for(int p=0;p<2;p++){
int t=c[pos[j]+1][pos[i]-1];
//cout<<i<<" "<<j<<" "<<t<<endl;
for(int x=t;x<=c[1][pos[i]-1];x++)
inc(f[i][p][x],f[j][!p][x-t]);
// printf("i=%d ")
}
}
}
int ans=0;
for(int x=1;x<=c[1][n];x++) {
int sum=f[tot + 1][1][x];
// cout<<"x="<<x<<" sum="<<sum<<endl;
inc(sum,P-f[tot+1][0][x]);
inc(ans,prd(sum,fpw(x,m)));
}
cout<<ans<<endl;
}
int main() {
int T; cin>>T; while(T--) work();
return 0;
}
I
过完G看了下感觉没什么思路，最后队友在写一个比较麻烦的做法，可惜来不及了。
最大最小很难同时考虑，先考虑最大：在最小值确定时，如何求出最大值的最小值？直接扫一遍dp即可。
考虑最小值固定为某个值\(v\)的条件（因为是求最值的问题，所以可以看做最小值不小于该值，大于的部分以更劣的方式计算，并且在之后会枚举计算到）：发现其实就是所有小于\(v\)的长度为1或2的段无效，放到dp上就是一些转移无效。
于是考虑从小到大枚举v，就是一个每次禁止掉一些新的转移的过程；而上述的dp是没有方向性的（即方便区间合并），那么是个很经典的问题，直接用线段树维护dp即可（即用区间分治代替线性dp）。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll F=1e10;
int n,a[N],b[N];
void Min(ll& x,ll y){
if(y<x) x=y;
}
struct SGT{
ll mnmx[N<<2][2][2];
#define mid ((l+r)>>1)
#define lc (u<<1)
#define rc ((u<<1)|1)
void mrg(int u){
for(int p=0;p<2;p++) for(int q=0;q<2;q++){
mnmx[u][p][q]=F;
for(int k=0;k<2;k++) Min(mnmx[u][p][q],max(mnmx[lc][p][k],mnmx[rc][k][q]));
}
}
void bld(int u,int l,int r){
if(l==r){
mnmx[u][0][0]=a[l];
if(l<n) mnmx[u][0][1]=b[l];
else mnmx[u][0][1]=F;
if(l>1) mnmx[u][1][0]=-F;
else mnmx[u][1][0]=F;
mnmx[u][1][1]=F;
return;
}
bld(lc,l,mid);
bld(rc,mid+1,r);
mrg(u);
}
void upd(int u,int l,int r,int d,int x,int y){
if(l==r){
mnmx[u][x][y]=F;
return;
}
if(d<=mid) upd(lc,l,mid,d,x,y);
else upd(rc,mid+1,r,d,x,y);
mrg(u);
}
}T;
struct node{
int v,d,x,y;
};
bool cmp(node u,node v){
return u.v<v.v;
}
void work(){
scanf("%d",&n);
vector<node>h;
h.clear();
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
h.push_back((node){a[i],i,0,0});
if(i>1) {
b[i - 1] = a[i - 1] + a[i];
h.push_back((node) {b[i - 1], i - 1, 0, 1});
}
}
std::sort(h.begin(), h.end(),cmp);
T.bld(1,1,n);
ll ans=F;
for(auto u:h){
ans=min(ans,T.mnmx[1][0][0]-u.v);
//cout<<T.mnmx[1][0][0]<<" "<<u.v<<endl;
T.upd(1,1,n,u.d,u.x,u.y);
}
printf("%lld\n",ans);
}
int main() {
int T; cin>>T; while(T--) work();
return 0;
}
J
看到是签到题，直接认为是取前m+1个-1，再列出一些细节判一下就行，然后喜提一发罚时；然后队友提出会在m个之后取最小的，把第m+1个改成后缀最小值才对。（有点急没考虑清楚，造成拖累了几分钟的进度和签到+1，算是比较小的失误吧）
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N];
ll s[N],mn[N];
void work(){
int cnt=0,t=0;
scanf("%d%d",&n,&m);
for(int x,i=1;i<=n;i++){
scanf("%d",&x);
if(!x){
cnt++;
continue;
}
a[++t]=x;
s[t]=s[t-1]+a[t];
}
mn[t]=a[t];
for(int i=t-1;i>=1;i--) mn[i]=min(mn[i+1],1ll*a[i]);
if(m==n) puts("Richman");
else if(cnt>m) puts("Impossible");
else {
m-=cnt;
printf("%lld\n",s[m]+mn[m+1]-1);
}
}
int main() {
int T; cin>>T; while(T--) work();
return 0;
}