A.小P的2048
作为一个看B哥玩了一个寒假的人这种题闭眼切好吧
模拟即可。程序模块化后直接复制粘贴。
说什么模拟不能复制粘贴的都没水平
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
typedef long long ll;
int n,m;
ll a[11][11];
int num=0;
ll b[11][11];
ll ans=0;
ll Lmove(int x)
{
ll res=0,last=0;int now=0;
for(int i=1;i<=n;i++)
{
if(!a[x][i])continue;
if(last!=a[x][i])
{
last=a[x][i];
a[x][i]=0;
now++;
a[x][now]=last;
}
else
{
last=0;
res+=a[x][i]*2;
ll val=a[x][i]*2;
a[x][i]=0;
a[x][now]=val;
}
}
return res;
}
ll Rmove(int x)
{
ll res=0,last=0;int now=n+1;
for(int i=n;i;i--)
{
if(!a[x][i])continue;
if(last!=a[x][i])
{
last=a[x][i];
a[x][i]=0;
now--;
a[x][now]=last;
}
else
{
last=0;
res+=a[x][i]*2;
ll val=a[x][i]*2;
a[x][i]=0;
a[x][now]=val;
}
}
return res;
}
ll Umove(int x)
{
ll res=0,last=0;int now=0;
for(int i=1;i<=n;i++)
{
if(!a[i][x])continue;
if(last!=a[i][x])
{
last=a[i][x];
a[i][x]=0;
now++;
a[now][x]=last;
}
else
{
last=0;
res+=a[i][x]*2;
ll val=a[i][x]*2;
a[i][x]=0;
a[now][x]=val;
}
}
return res;
}
ll Dmove(int x)
{
ll res=0,last=0;int now=n+1;
for(int i=n;i;i--)
{
if(!a[i][x])continue;
if(last!=a[i][x])
{
last=a[i][x];
a[i][x]=0;
now--;
a[now][x]=last;
}
else
{
last=0;
res+=a[i][x]*2;
ll val=a[i][x]*2;
a[i][x]=0;
a[now][x]=val;
}
}
return res;
}
ll LM()
{
ll res=0;
for(int i=1;i<=n;i++)
res+=Lmove(i);
return res;
}
ll RM()
{
ll res=0;
for(int i=1;i<=n;i++)
res+=Rmove(i);
return res;
}
ll UM()
{
ll res=0;
for(int i=1;i<=n;i++)
res+=Umove(i);
return res;
}
ll DM()
{
ll res=0;
for(int i=1;i<=n;i++)
res+=Dmove(i);
return res;
}
void cpy()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[i][j];
}
bool dif()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]!=b[i][j])return 1;
return 0;
}
int ask()
{
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!a[i][j])res++;
return res;
}
bool find(int pos,int val)
{
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j])continue;
cnt++;
if(cnt==pos)
{
a[i][j]=val;return 1;
}
}
return 0;
}
void print()
{
printf("%d
%lld
",num,ans);
exit(0);
}
int main()
{
n=read();m=read();
int x_1=read(),y_1=read(),v_1=read(),x_2=read(),y_2=read(),v_2=read();
a[x_1][y_1]=v_1;a[x_2][y_2]=v_2;
for(int i=1;i<=m;i++)
{
int dv=read(),K=read(),v=read();
cpy();
switch(dv)
{
case 0:ans+=UM();break;
case 1:ans+=DM();break;
case 2:ans+=LM();break;
case 3:ans+=RM();break;
}
if(dif())num++;
else print();
int r=ask();
int p=(K%r)+1;
find(p,v);
}
print();
return 0;
}
B.小P的单调数列
结论：必然存在一个最优子序列，它的单调区间数不超过2。
那么，其实最优子序列只有可能是单增或单增+单减。
正反都跑一遍dp，树状数组优化即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=1e5+5;
typedef long long ll;
int a[N],n,b[N],type;
ll f[N],g[N],c[N];
double ans=0.0;
unordered_map<int,int> link;
int lb(int x){return x&-x;}
void update(int x,ll val)
{
for( ;x<=type;x+=lb(x))
c[x]=max(c[x],val);
}
ll ask(int x)
{
ll res=0;
for( ;x;x-=lb(x))
res=max(res,c[x]);
return res;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
if(link.find(b[i])==link.end())link[b[i]]=++type;
/**for(int i=1;i<=n;i++)
cout<<link[a[i]]<<' ';puts(" ");*/
f[1]=a[1];
update(link[a[1]],f[1]);
for(int i=2;i<=n;i++)
{
if(link[a[i]]==1)f[i]=a[i];
else f[i]=ask(link[a[i]]-1)+a[i];
update(link[a[i]],f[i]);
}
memset(c,0,sizeof(c));
g[n]=a[n];
update(link[a[n]],g[n]);
for(int i=n-1;i;i--)
{
if(link[a[i]]==1)g[i]=a[i];
else g[i]=ask(link[a[i]]-1)+a[i];
update(link[a[i]],g[i]);
}
for(int i=1;i<=n;i++)
{
ans=max(ans,0.5*(g[i]+f[i]-a[i]));
ans=max(ans,1.0*f[i]);
}
printf("%.3lf
",ans);
return 0;
}
C.小P的生成树
首先，复数可以直接看成向量。
如果我们已经得到生成树各边的和向量的方向，想使它的模长最大，那么就应该让各边在这个方向上的投影之和最大。
针对这个条件，我们可以把每条边在该方向上的投影作为新的权值，跑最大生成树即可。
如何得到这个方向向量？
直接枚举角度，得到它的方向向量$(cos heta ,sin heta)$。然后重新赋边权跑Kruskal即可。取最优答案。
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=55,M=205;
int n,m,fa[N];
double ans=0.0,al;
struct edge
{
int x,y;
double a,b,w;
friend bool operator < (const edge &x,const edge &y)
{
return x.w>y.w;
}
}e[M];
double modl(double a,double b)
{
return sqrt(a*a+b*b);
}
int findf(int x)
{
if(fa[x]==x)return x;
return fa[x]=findf(fa[x]);
}
void Kruskal()
{
int t=0;
double resa=0.0,resb=0.0;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
e[i].w=e[i].a*cos(al)+e[i].b*sin(al);
sort(e+1,e+m+1);
for(int i=1;i<=m;i++)
{
int x=e[i].x,y=e[i].y,fx=findf(x),fy=findf(y);
if(fx!=fy)
{
fa[fx]=fy;
resa+=e[i].a;resb+=e[i].b;
t++;
}
if(t==n-1)break;
}
ans=max(ans,modl(resa,resb));
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
e[i].x=read(),e[i].y=read(),e[i].a=read(),e[i].b=read();
for(al=0.000;al<=6.300;al+=0.001)
Kruskal();
printf("%.6lf
",ans);
return 0;
}