D. Beautiful Array
题意
给你一个长度为 (n) 的序列。你可以选择至多一个子段，将该子段所有数乘上给定常数 (x) 。求操作后最大的最大子段和。
题解
考虑最大子段和的子段一共有三类点：1. 左边没有 ( imes x) 的点 ； 2. 中间 ( imes x) 的点； 3. 右边没有 ( imes x) 的点。
考虑 dp 。设 (f[i][1/2/3]) 表示前 (i) 个数，第 (i) 个数作为第 1/2/3 类点的最大子段和。转移显然。
code
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=3e5+5;
inline int gi()
{
char c; int x=0,f=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
return x*f;
}
int a[N],n,x;
long long f[N][5],ans=0;
int main()
{
n=gi(),x=gi();
for(int i=1;i<=n;++i) a[i]=gi();
for(int i=1;i<=n;++i)
{
f[i][1]=max(0ll,f[i-1][1])+a[i];
f[i][2]=max(0ll,max(f[i-1][1],f[i-1][2]))+1ll*a[i]*x;
f[i][3]=max(f[i-1][2],f[i-1][3])+a[i];
ans=max(ans,max(f[i][1],max(f[i][2],f[i][3])));
}
printf("%I64d",ans);
}
E. Guess the Root
题意
交互题。有一个 (k(kle 10)) 次多项式 (f(x)) ，你可以进行不超过 (50) 次询问，每次询问给出 (x) ，返回 (f(x)) 。求 (x_0) 使得 (f(x_0) equiv 0 mod (10^6 + 3)) 。
题解
以下设 (m=10^6+3) 。
插值傻逼题。询问 (k+1) 次，然后枚举零点插值判断即可。
直接插值是 (O(m k^2 log m)) 的。众所周知，当 (x) 取 (1sim n) 可以通过预处理阶乘使插值复杂度降到 (O(n)) 。
当然由于本题 (kle 10)，我们甚至可以直接暴力打表分母。复杂度 (O(mk)) 。
code
#include<cstdio>
const int N=25,Mod=1e6+3;
const int n=11;
int y[N],k,inv[Mod+2];
int fm[]={404910,950915,220896,410947,30845,962989,30845,410947,220896,950915,404910};
inline int po(int x, int y)
{
int r=1;
while(y)
{
if(y&1) r=1ll*r*x%Mod;
x=1ll*x*x%Mod, y>>=1;
}
return r;
}
int judge(int k)
{
int ans=0,base=1;
for(int i=1;i<=n;++i) if(k!=i) base=1ll*base*(k-i)%Mod;
if(1<=k&&k<=11) return (1ll*base*fm[k-1]%Mod*y[k]%Mod+Mod)%Mod;
base=(base+Mod)%Mod;
for(int i=1;i<=n;++i)
ans=(ans+1ll*base*inv[(k-i+Mod)%Mod]%Mod*fm[i-1]%Mod*y[i]%Mod)%Mod;
return ans;
}
int main()
{
for(int i=1;i<=n;++i)
{
printf("? %d
",i);
fflush(stdout);
scanf("%d",&y[i]);
}
inv[0]=inv[1]=1;
for(int i=2;i<Mod;++i) inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
for(int k=0;k<Mod;++k)
if(!judge(k))
{
printf("! %d
",k);
fflush(stdout);
return 0;
}
printf("! -1
");
fflush(stdout);
}