Educational Codeforces Round 63 选做

时间:2022-01-21 09:33:23

D. Beautiful Array

题意

给你一个长度为 \(n\) 的序列。你可以选择至多一个子段,将该子段所有数乘上给定常数 \(x\) 。求操作后最大的最大子段和。

题解

考虑最大子段和的子段一共有三类点:1. 左边没有 \(\times x\) 的点 ; 2. 中间 \(\times x\) 的点; 3. 右边没有 \(\times 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(k\le 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\) 取 \(1\sim n\) 可以通过预处理阶乘使插值复杂度降到 \(O(n)\) 。

当然由于本题 \(k\le 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\n",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\n",k);
fflush(stdout);
return 0;
}
printf("! -1\n");
fflush(stdout);
}

Educational Codeforces Round 63 选做的更多相关文章

  1. Educational Codeforces Round 64 选做

    感觉这场比赛题目质量挺高(A 全场最佳),难度也不小.虽然 unr 后就懒得打了. A. Inscribed Figures 题意 给你若干个图形,每个图形为三角形.圆形或正方形,第 \(i\) 个图 ...

  2. Educational Codeforces Round 65 选做

    好久没更博客了,随便水一篇 E. Range Deleting 题意 给你一个长度为 \(n\) 的序列 \(a_1,a_2,\dots a_n\) ,定义 \(f(l,r)\) 为删除 \(l\le ...

  3. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; 题解

    Educational Codeforces Round 63 (Rated for Div. 2)题解 题目链接 A. Reverse a Substring 给出一个字符串,现在可以对这个字符串进 ...

  4. &lbrack;Educational Codeforces Round 63 &rsqb; D&period; Beautiful Array (思维&plus;DP)

    Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array time limit per test 2 seconds ...

  5. Educational Codeforces Round 63部分题解

    Educational Codeforces Round 63 A 题目大意就不写了. 挺简单的,若果字符本来就单调不降,那么就不需要修改 否则找到第一次下降的位置和前面的换就好了. #include ...

  6. Educational Codeforces Round 63 Div&period; 2

    A:找到两个相邻字符使后者小于前者即可. #include<bits/stdc++.h> using namespace std; #define ll long long #define ...

  7. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; D&period; Beautiful Array 分类讨论连续递推dp

    题意:给出一个 数列 和一个x 可以对数列一个连续的部分 每个数乘以x  问该序列可以达到的最大连续序列和是多少 思路: 不是所有区间题目都是线段树!!!!!! 这题其实是一个很简单的dp 使用的是分 ...

  8. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; D&period; Beautiful Array(动态规划&period;递推)

    传送门 题意: 给你一个包含 n 个元素的序列 a[]: 定义序列 a[] 的 beauty 为序列 a[] 的连续区间的加和最大值,如果全为负数,则 beauty = 0: 例如: a[] = {1 ...

  9. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; D&period; Beautiful Array &lpar;简单DP&rpar;

    题目:https://codeforces.com/contest/1155/problem/D 题意:给你n,x,一个n个数的序列,你可以选择一段区间,区间的数都乘以x,然后求出最大字段和 思路: ...

随机推荐

  1. python---difflib

    文件内容差异对比 difflib为python的标准库模块,无需安装.作用时对比文本之间的差异.并且支持输出可读性比较强的HTML文档,与LInux下的diff 命令相似.在版本控制方面非常有用. # ...

  2. JavaScript Array 对象

    JavaScript Array 对象 Array 对象 Array 对象用于在变量中存储多个值: var cars = ["Saab", "Volvo", & ...

  3. Mycat&plus;Mysql 插入数据报错 i&lbrack;Err&rsqb; 1064 - partition table&comma; insert must provide ColumnList

    使用Navicat连接Mycat 8066 成功插入了分库表和全局表 1.全局表 sql如下: '); '); '); 插入成功! 2.分库表 sql如下: ', null, null, null, ...

  4. hi3531的h264压缩中改动波特率

    typedef struct hiVENC_ATTR_H264_CBR_S { HI_U32 u32Gop; HI_U32 u32StatTime; HI_U32 u32ViFrmRate; HI_F ...

  5. 浅谈Android系统的图标设计规范

    http://homepage.yesky.com/89/11620089.shtml 目前移动平台的竞争日益激烈,友好的用户界面可以帮助提高用户体验满意度,图标Icon是用户界面中一个重要的组成部分 ...

  6. 立贴读 《CLR》

    弱弱的说,我要开始读<CLR>这本书了,怕自己不能坚持下来,特立贴监督自己,本来是大牛们涉及的区域,现在好朋友的鼓励下,勇敢的踏入,如有错误,还请各位指正.

  7. Java创建柱状图及饼状图

    Java创建图表其实还是很方便的,但是要引入相关的jar包.如下 jfreechart.jar jcommon,jar gnujaxp.jar 其中最主要的是jfreechart.jar. 下面就让我 ...

  8. &lbrack;pycharm&rsqb;远程调试服务器项目

    Pycharm远程调试服务器项目 准备工作 创建一个临时项目,用pycharm打开项目 mkdir xxx 准备一台远程服务器,尝试连接服务器 ssh worker@ip 同步项目到pycharm 配 ...

  9. bzoj千题计划297:bzoj3629&colon; &lbrack;JLOI2014&rsqb;聪明的燕姿

    http://www.lydsy.com/JudgeOnline/problem.php?id=3629 约数和定理: 若n的标准分解式为 p1^k1 * p2^k2 …… 那么n的约数和= π (Σ ...

  10. 网站优化JS css压缩

    在nginx 中开启gzip压缩后,可以大大减少资js css 体积,原来200KB,压缩后只有66KB server{ gzip on; gzip_types text/plain applicat ...