嗯。。。还是没有改变那个现状

依旧只是打满了暴力，虽说T2打的的确比暴力好很多，但是因为出题人没有设分所以和暴力等同。

离上面的分差还是大的很，下面还是追的很紧

而且进几场的排名也是连续下滑。。。

虽说比前一段时间上下弹跳好一些吧。。。但是这肯定是不够的啊

还需要努力。还能进步。

T1大模拟，细节打飞调样例调了好久，花了一个多小时。。。

T2理论复杂度勉强但是实际自带巨大常数根本卡不过，我还以为我想到了正解

“我天，二分答案套线段树优化动态规划，神仙题啊，我竟然做出来了，这次稳了”

然后随便来一组随机数据，7s。。。我以为是常数的锅，卡了一阵到3s

其实复杂度就是多了一个log。

二分答案的上界是1e14，eps是1e-4，这样的话log掉也有60。。。

更可怕的是，这样二分答案的值需要有1e-18的精度，double无法接受，死循环了。。。

long double就T死。。。

其实到这里就应该意识到这不是正解了。。。但是没时间了

T3连忙打了一个部分分。

还有4分钟的时候，想摸鱼了。

但是吸取之前的exp，不要摸鱼不要摸鱼不要摸鱼，于是开始打状压

码出来了！多了15分！

一定不要浪费任何一分钟。

一定不要怀疑自己的码力。

计算复杂度时要考虑常数。

T1：小P的2048

模拟，还是不讲了吧。。。

不要颓啊啊啊

#include
int n,m,f[][],p,d,v,rm,s,r[][];
void put(){for(int i=;i<=n;++i,puts(""))for(int j=;j<=n;++j)printf("%d ",f[i][j]);puts("");} void up(){ for(int j=;j<=n;++j)for(int i=;i<=n;++i)if(f[i][j]){ int pos=i;while(pos>&&!f[pos-][j])pos--;
if(pos!=i)f[pos][j]=f[i][j],f[i][j]=;
}
for(int j=;j<=n;++j)for(int i=;i<=n;++i)if(f[i][j])if(f[i-][j]==f[i][j]) f[i-][j]<<=,f[i][j]=,s+=f[i-][j]; for(int j=;j<=n;++j)for(int i=;i<=n;++i)if(f[i][j]){ int pos=i;while(pos>&&!f[pos-][j])pos--;
if(pos!=i)f[pos][j]=f[i][j],f[i][j]=;
}
}
void down(){
for(int j=;j<=n;++j)for(int i=n-;i;--i)if(f[i][j]){ int pos=i;while(pos&&!f[i][pos-])pos--;
if(pos!=j)f[i][pos]=f[i][j],f[i][j]=;
}
for(int i=;i<=n;++i)for(int j=;j<=n;++j)if(f[i][j])if(f[i][j-]==f[i][j]) f[i][j-]<<=,f[i][j]=,s+=f[i][j-]; for(int i=;i<=n;++i)for(int j=;j<=n;++j)if(f[i][j]){ int pos=j;while(pos>&&!f[i][pos-])pos--;
if(pos!=j)f[i][pos]=f[i][j],f[i][j]=;
}
}
void right(){
for(int i=;i<=n;++i)for(int j=n-;j;--j)if(f[i][j]){
int pos=j;while(pos<n&&!f[i][pos+])pos++;
if(pos!=j)f[i][pos]=f[i][j],f[i][j]=;
}
for(int i=;i<=n;++i)for(int j=n-;j;--j)if(f[i][j])if(f[i][j+]==f[i][j])
f[i][j+]<<=,f[i][j]=,s+=f[i][j+];
for(int i=;i<=n;++i)for(int j=n-;j;--j)if(f[i][j]){
int pos=j;while(pos<n&&!f[i][pos+])pos++;
if(pos!=j)f[i][pos]=f[i][j],f[i][j]=;
}
}
int main(){//freopen("game_sample2.in","r",stdin);
scanf("%d%d",&n,&m);rm=m;
for(int x,y,V,i=;i<=;++i)scanf("%d%d%d",&x,&y,&V),f[x][y]=V;
for(int T=;T<=m;++T){
scanf("%d%d%d",&d,&p,&v);
for(int i=;i<=n;++i)for(int j=;j<=n;++j)r[i][j]=f[i][j];
if(d==)up();else if(d==)down();else if(d==)left();else right();
for(int i=;i<=n;++i)for(int j=;j<=n;++j)if(r[i][j]!=f[i][j])goto Y;
rm=T-;goto gg;
Y: int cnt=;for(int i=;i<=n;++i)for(int j=;j<=n;++j)if(!f[i][j])cnt++;
p=p%cnt+;//printf("%d\n",cnt);
for(int i=;i<=n;++i)for(int j=;j<=n;++j)if(!f[i][j]){p--;if(!p){f[i][j]=v;goto ex;}}
ex:;
}
gg: printf("%d\n%d\n",rm,s);
}

T2：小P的单调数列

记一下考场上的思路，其实不错。

如果你不知道那个结论的话，你要考虑怎么处理平均数。

二分答案，设为x，需要check。

即我们需要判断sum>kx是否成立，k表示段数。

那么其实就是每多一段你的sum值就减少了x。

设dp[i][0/1]表示考虑完目前序列的最后一个值为i，目前处于上升/下降段。

转移比较显然，就是线段树优化dp的板子。

复杂度$O(n\ log\ n log(10^9n/eps))$，理论复杂度可过，实际60分（同$O(n^2)$）

//二分答案判平均值：所有区间结束后都减去二分值，最后大于0即可
//dp[i][0/1]是第i位必选，目前是向上还是向下
//离散化+线段树优化dp？
#include
#include
#include
using namespace std;
double max(double a,double b){return a>b?a:b;}
unordered_mapM;
int n,a[],re[],cnt;
struct Segment_tree{
int cl[],cr[];double w[];
void build(int p,int l,int r,double sw){
w[p]=sw;cl[p]=l;cr[p]=r;
if(l==r)return;
build(p<<,l,l+r>>,sw);build(p<<|,(l+r>>)+,r,sw);
}
void set(int p,int pos,double v){
if(cl[p]==cr[p]){w[p]=max(v,w[p]);return;}
if(pos<=cr[p<<])set(p<<,pos,v); else set(p<<|,pos,v); w[p]=max(w[p<<],w[p<<|]); } double ask(int p,int l,int r){ if(l>r)return -1e18;
if(l<=cl[p]&&cr[p]<=r)return w[p]; return max(l<=cr[p<<]?ask(p<<,l,r):-1e18,r>=cl[p<<|]?ask(p<<|,l,r):-1e18); } }up,down; bool chk(double x){ up.build(,,cnt,);down.build(,,cnt,-1e18); for(int i=;i<=n;++i){ double ux=up.ask(,,a[i]-),ut=up.ask(,,a[i]),dx=down.ask(,a[i]+,cnt),dt=down.ask(,a[i],cnt); up.set(,a[i],max(ux,dt-x)+re[a[i]]);down.set(,a[i],max(dx,ut-x)+re[a[i]]); } return max(up.ask(,,n),down.ask(,,n))>x;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]),re[i]=a[i]; sort(re+,re++n); for(int i=;i<=n;++i)if(re[i]!=re[i-])M[re[i]]=++cnt,re[cnt]=re[i]; for(int i=;i<=n;++i)a[i]=M[a[i]]; double l=,r=1e14; while(r-l>1e-)if(chk((l+r)/))l=(l+r)/;else r=(l+r)/;
printf("%.3lf\n",l);
}

可恶的出题人一分不多给

正解需要一个结论：最优解是一个上升段或一个升段+一个降段

证明不是很难，分析平均数的加和性的结果即可。

那么就是简单dp，枚举最高点，两边跑最长上升子序列，树状数组维护，$O(n\ log \ n)$。

#include
#include
#include
using namespace std;
#define int long long
unordered_mapM;
int max(int a,int b){return a>b?a:b;}
int n,a[],re[],cnt,dp[],t[],DP[],fdp[],bdp[],ans;
void set(int p,int w){for(;p<=;p+=p&-p)t[p]=max(t[p],w);}
int ask(int p,int a=){for(;p;p^=p&-p)a=max(a,t[p]);return a;}
main(){//freopen("2.in","r",stdin);
scanf("%lld",&n);
for(int i=;i<=n;++i)scanf("%lld",&a[i]),re[i]=a[i];
sort(re+,re++n);
for(int i=;i<=n;++i)if(re[i]!=re[i-])M[re[i]]=++cnt,re[cnt]=re[i];
for(int i=;i<=n;++i)a[i]=M[a[i]];
for(int i=;i<=n;++i)dp[a[i]]=ask(a[i]-)+re[a[i]],set(a[i],dp[a[i]]),fdp[i]=dp[a[i]],ans=max(ans,dp[a[i]]<<);
for(int i=;i<=cnt;++i)t[i]=;
for(int i=n;i;--i)DP[a[i]]=ask(a[i]-)+re[a[i]],set(a[i],DP[a[i]]),bdp[i]=DP[a[i]];
for(int i=;i<=n;++i)ans=max(ans,fdp[i]+bdp[i]-re[a[i]]);//,printf("%lld %lld %lld %lld\n",i,fdp[i],bdp[i],fdp[i]+bdp[i]-re[a[i]]);
printf("%.3lf\n",ans/2.0);
}

T3：小P的生成树

考虑最大生成树的过程，关于树的边集，其实你在意的不是具体长度，而是相对关系。

显然，在某一角度下的模长和等于向量先求和后求模长。

这样有一个想法就是枚举这个角度。可以AC。

#include
#include
#include
#include
using namespace std;
struct es{
int x,y,a,b;double mod;
friend bool operator<(es a,es b){return a.mod>b.mod;}
}E[];
int n,f[],m;double ans;
int find(int k){return k==f[k]?k:f[k]=find(f[k]);}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].a,&E[i].b);
for(double alpha=;alpha<3.1415926*;alpha+=0.11){
double sine=sin(alpha),cosine=cos(alpha);long long totx=,toty=;
for(int i=;i<=m;++i)E[i].mod=E[i].a*cosine+E[i].b*sine;
sort(E+,E++m);
for(int i=;i<=n;++i)f[i]=i;
for(int i=;i<=m;++i)if(find(E[i].x)!=find(E[i].y))
totx+=E[i].a,toty+=E[i].b,f[f[E[i].x]]=f[E[i].y];
ans=max(sqrt(totx*totx+toty*toty),ans);
}printf("%.6lf\n",ans);
}

81ms

正解更加严谨。

既然只有相对大小关系有影响，那么你考虑任意两条边，它们的大小关系改变时有一个确切的角度。

m2枚举出所有这样的角度，将坐标系划分为m2部分，在每一部分里最大生成树都一样。

在这m2部分里各任意取最点更新最佳答案即可。

#include
#include
#include
#include
using namespace std;
struct es{
int x,y,a,b;double mod;
friend bool operator<(es a,es b){return a.mod>b.mod;}
}E[];
int n,f[],m;double ans;
int find(int k){return k==f[k]?k:f[k]=find(f[k]);}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].a,&E[i].b);
for(int i=;i<=m;++i)for(int j=i+;j<=m;++j){
double alpha=atan(1.0*(E[i].y-E[j].y)/(E[i].x-E[j].x))+0.00001;bg:
double sine=sin(alpha),cosine=cos(alpha);long long totx=,toty=;
for(int i=;i<=m;++i)E[i].mod=E[i].a*cosine+E[i].b*sine;
sort(E+,E++m);
for(int i=;i<=n;++i)f[i]=i;
for(int i=,al=;i<=m,al<n-;++i)if(find(E[i].x)!=find(E[i].y))
totx+=E[i].a,toty+=E[i].b,f[f[E[i].x]]=f[E[i].y],al++;
ans=max(sqrt(totx*totx+toty*toty),ans);
if(alpha<3.1415926){alpha+=3.1415926;goto bg;}
}printf("%.6lf\n",ans);
}

4300ms