水题
目录
小P的2048game
暴力模拟，额写了2遍。。。
噗噗大神自己写过这个游戏。。。
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN=10;
int n,m,d,k,v,step,score;
int bd[MAXN][MAXN];
bool flag;
queue<int>q;
inline int read();
inline void add(){
int cnt=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(!bd[i][j]) ++cnt;
}
}
cnt=1+k%cnt;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(!bd[i][j]){
--cnt;
if(!cnt){
bd[i][j]=v;
return;
}
}
}
}
}
inline bool up(){
for(int i=1,x;i<=n;++i){
bd[0][i]=0;
for(int j=1;j<=n;++j){
if(bd[j][i])
q.push(bd[j][i]);
}
while(q.size()){
x=q.front();
q.pop();
if(q.size()){
if(x==q.front()){
q.pop();
x<<=1;
score+=x;
flag=true;
}
}
if(bd[++bd[0][i]][i]!=x)
flag=true;
bd[bd[0][i]][i]=x;
}
for(int j=bd[0][i]+1;j<=n;++j)
bd[j][i]=0;
}
if(flag){
add();
return true;
}
return false;
}
inline bool down(){
for(int i=1,x;i<=n;++i){
bd[0][i]=n+1;
for(int j=n;j;--j){
if(bd[j][i])
q.push(bd[j][i]);
}
while(q.size()){
x=q.front();
q.pop();
if(q.size()){
if(x==q.front()){
q.pop();
x<<=1;
score+=x;
flag=true;
}
}
if(bd[--bd[0][i]][i]!=x)
flag=true;
bd[bd[0][i]][i]=x;
}
for(int j=bd[0][i]-1;j;--j)
bd[j][i]=0;
}
if(flag){
add();
return true;
}
return false;
}
inline bool left(){
for(int i=1,x;i<=n;++i){
bd[i][0]=0;
for(int j=1;j<=n;++j){
if(bd[i][j])
q.push(bd[i][j]);
}
while(q.size()){
x=q.front();
q.pop();
if(q.size()){
if(x==q.front()){
q.pop();
x<<=1;
score+=x;
flag=true;
}
}
if(bd[i][++bd[i][0]]!=x)
flag=true;
bd[i][bd[i][0]]=x;
}
for(int j=bd[i][0]+1;j<=n;++j)
bd[i][j]=0;
}
if(flag){
add();
return true;
}
return false;
}
inline bool right(){
for(int i=1,x;i<=n;++i){
bd[i][0]=n+1;
for(int j=n;j;--j){
if(bd[i][j])
q.push(bd[i][j]);
}
while(q.size()){
x=q.front();
q.pop();
if(q.size()){
if(x==q.front()){
q.pop();
x<<=1;
score+=x;
flag=true;
}
}
if(bd[i][--bd[i][0]]!=x)
flag=true;
bd[i][bd[i][0]]=x;
}
for(int j=bd[i][0]-1;j;--j)
bd[i][j]=0;
}
if(flag){
add();
return true;
}
return false;
}
inline bool work(){
flag=false;
switch(d){
case 0: return up();
case 1: return down();
case 2: return left();
default:return right();
}
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read(),m=read();
bd[read()][read()]=read();
bd[read()][read()]=read();
for(int i=1;i<=m;++i){
d=read(),k=read(),v=read();
if(!work()) break;
++step;
}
printf("%d\n%d",step,score);
fclose(stdin);
fclose(stdout);
return 0;
}
inline int read(){
char c; int x;
while(c=getchar(),c<'0' || '9'<c);
x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x;
}小P的单调数列seq
数学归纳法就可以证明，只有一个单调上升子序列或一个单调上升子序列+一个单调下降子序列最优，于是dp。。。
#include <cstdio>
#include <algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
const int MAXN=100005;
int a[MAXN],no[MAXN],n,hs[MAXN];
double arr[MAXN],up[MAXN],down[MAXN];
inline int read();
bool cmp(const int &x,const int &y){
return a[x]<a[y];
}
inline void add(const double &x,int l){
for(;l<=n;l+=lowbit(l))
arr[l]=max(arr[l],x);
}
inline double qry(int r){
double s=0;
for(;r;r-=lowbit(r))
s=max(s,arr[r]);
return s;
}
int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)
a[i]=read(),hs[i]=i;
sort(hs+1,hs+n+1,cmp);
for(int i=1;i<=n;++i){
if(a[hs[i]]!=a[hs[i-1]])
++no[0];
no[hs[i]]=no[0];
}
up[1]=a[1];
add(up[1],no[1]);
for(int i=2;i<=n;++i){
up[i]=qry(no[i]-1)+a[i];
add(up[i],no[i]);
}
for(int i=1;i<=n;++i)
arr[i]=0;
down[n]=a[n];
add(down[n],no[n]);
for(int i=n-1;i;--i){
down[i]=qry(no[i]-1)+a[i];
add(down[i],no[i]);
}
double ans=0;
for(int i=1;i<=n;++i){
ans=max(ans,up[i]);
ans=max(ans,(up[i]+down[i]-a[i])/2.0);
}
printf("%.3lf",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
inline int read(){
char c; int x;
while(c=getchar(),c<'0' || '9'<c);
x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x;
}小P的生成树mst
话说当时愣是没推出来（%PB大神）；
普通MST其实也是按边对最终的树的边权贡献关系排的，并且是相对关系（大小吗。。。）。于是这题我们yy出最终向量的倾角θ，则边在最终向量的投影——即贡献为a*cosθ+b*sinθ，枚举求任意两对边贡献相等时的倾角，根据三角函数单调性可知：在这些θ分成的不同角的区域，边的相对关系不变，MST相同，于是求每个区域中θ（两边边界平均值即可）下的MST取最优解。。。
注意去重，而且atan∈[-π/2，3*π/2]，排序后，最大的θ和最小的θ要手动加入，或者序列里人工加上-π/2，3*π/2
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read();
const int MAXN=55,MAXM=205;
const double PI=acos(-1);
int fa[MAXN],part,n,m;
double theta[MAXM*MAXM<<1];
struct line{
int u,v,a,b;
double mod;
}ed[MAXM];
bool cmp(const line &a,const line &b){
return a.mod>b.mod;
}
inline void clean(){
for(int i=1;i<=n;++i)
fa[i]=i;
}
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
inline void uni(const int &x,const int &y){
fa[find(x)]=find(y);
}
inline void prepare(){
double k;
for(int i=1;i<m;++i){
for(int j=i+1;j<=m;++j){
if(ed[i].b==ed[j].b)
k=PI/2;
else{
k=double(ed[i].a-ed[j].a)/(ed[j].b-ed[i].b);
k=atan(k);
}
theta[++part]=k;
theta[++part]=k+PI;
}
}
theta[++part]=-PI/2;
theta[++part]=3*PI/2;
sort(theta+1,theta+part+1);
part=unique(theta+1,theta+part+1)-theta-1;
}
inline double kruskal(){
double ans=0,ang,x,y,sum;
for(int i=1,suma,sumb;i<part;++i){
ang=(theta[i]+theta[i+1])/2;
x=cos(ang),y=sin(ang);
clean();
for(int j=1;j<=m;++j)
ed[j].mod=ed[j].a*x+ed[j].b*y;
sort(ed+1,ed+m+1,cmp);
suma=0,sumb=0;
for(int j=1,k=0,u,v;j<=m;++j){
u=ed[j].u,v=ed[j].v;
if(find(u)!=find(v)){
uni(u,v);
suma+=ed[j].a;
sumb+=ed[j].b;
if(++k==n-1) break;
}
}
sum=suma*suma+sumb*sumb;
ans=max(ans,sum);
}
return sqrt(ans);
}
int main(){
freopen("mst.in","r",stdin);
freopen("mst.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;++i)
ed[i]=(line){read(),read(),read(),read()};
prepare();
printf("%.6lf",kruskal());
fclose(stdin);
fclose(stdout);
return 0;
}
inline int read(){
char c; int x=0,y=1;
while(c=getchar(),(c<'0' || '9'<c) && c!='-');
if(c=='-') y=-1;
else x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x*y;
}