csps模拟测试7273简单的操作小P的2048小P的单调数列小P的生成树

题面：https://www.cnblogs.com/Juve/articles/11678564.html

简单的操作：

考场上sb了，没看出来

如果有奇环一定不能缩成一条链，判掉奇环后就是bfs最短路了

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int MAXN=;

 const int MAXM=1e5+;

 int n,m,col[MAXN],tot=,ans=,bel[MAXN],res[MAXN];

 int to[MAXM<<],nxt[MAXM<<],pre[MAXN],cnt=;

 void add(int u,int v){

     ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

 }

 bool dfs(int x,int c){

     col[x]=c,bel[x]=tot;

     for(int i=pre[x];i;i=nxt[i]){

         int y=to[i];

         if(col[y]==c) return ;

         else if((!col[y])&&(!dfs(y,-c))) return ;

     }

     return ;

 }

 int dis[MAXN];

 void bfs(int st){

     memset(dis,,sizeof(dis));

     queue<int>q;

     dis[st]=;

     q.push(st);

     while(!q.empty()){

         int x=q.front();

         q.pop();

         for(int i=pre[x];i;i=nxt[i]){

             int y=to[i];

             if(dis[y]==){

                 dis[y]=dis[x]+;

                 q.push(y);

             }

         }

     }

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=,u,v;i<=m;++i){

         scanf("%d%d",&u,&v);

         add(u,v),add(v,u);

     }

     for(int i=;i<=n;++i){

         if(!col[i]){

             ++tot;

             if(!dfs(i,)){

                 ans=-;

                 break;

             }

         }

     }

     if(ans==-){

         printf("%d\n",ans);

         return ;

     }

     for(int i=;i<=n;++i){

         bfs(i);

         for(int j=;j<=n;++j){

             res[bel[i]]=max(res[bel[i]],dis[j]-);

         }

     }

     for(int i=;i<=tot;++i){

         ans+=res[i];

     }

     printf("%d\n",ans);

     return ;

 }

2048：

话说我不会2048考场上是不是爆0了？

就是模拟

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,m,mp[][],ans=;

 bool flag=,vis[][];

 int get(){

     int res=;

     for(int i=;i<=n;++i){

         for(int j=;j<=n;++j)

             res+=(mp[i][j]==);

     }

     return res;

 }

 void put(int pos,int val){

     for(int i=;i<=n;++i){

         for(int j=;j<=n;++j){

             if(mp[i][j]!=) continue;

             --pos;

             if(pos==){

                 mp[i][j]=val;

                 return ;

             }

         }

     }

 }

 void mergeup(){

     for(int i=;i<=n;++i){

         for(int j=;j<=n;++j){

             if(mp[i][j]==) continue;

             int p=i-,k=mp[i][j];

             while(p>&&mp[p][j]==) mp[p][j]=k,mp[p+][j]=,--p;

             if(p!=i-) flag=;

             if(vis[p][j]==&&mp[p+][j]==mp[p][j]) mp[p][j]<<=,mp[p+][j]=,flag=vis[p][j]=,ans+=mp[p][j];

         }

     }

 }

 void up(){

     for(int i=;i<=n;++i){

         for(int j=;j<=n;++j){

             if(mp[i][j]==) continue;

             int p=i-,k=mp[i][j];

             while(p>&&mp[p][j]==) mp[p][j]=k,mp[p+][j]=,--p;

             if(p!=i-) flag=;

         }

     }

 }

 void mergedown(){

     for(int i=n-;i>=;--i){

         for(int j=;j<=n;++j){

             if(mp[i][j]==) continue;

             int p=i+,k=mp[i][j];

             while(p<=n&&mp[p][j]==) mp[p][j]=k,mp[p-][j]=,++p;

             if(p!=i+) flag=;

             if(vis[p][j]==&&mp[p-][j]==mp[p][j]) mp[p][j]<<=,mp[p-][j]=,flag=vis[p][j]=,ans+=mp[p][j];

         }

     }

 }

 void down(){

     for(int i=n-;i>=;--i){

         for(int j=;j<=n;++j){

             if(mp[i][j]==) continue;

             int p=i+,k=mp[i][j];

             while(p<=n&&mp[p][j]==) mp[p][j]=k,mp[p-][j]=,++p;

             if(p!=i+) flag=;

         }

     }

 }

 void mergeleft(){

     for(int j=;j<=n;++j){

         for(int i=;i<=n;++i){

             if(mp[i][j]==) continue;

             int p=j-,k=mp[i][j];

             while(p>&&mp[i][p]==) mp[i][p]=k,mp[i][p+]=,--p;

             if(p!=j-) flag=;

             if(vis[i][p]==&&mp[i][p]==mp[i][p+]) mp[i][p]<<=,mp[i][p+]=,flag=vis[i][p]=,ans+=mp[i][p];

         }

     }

 }

 void left(){

     for(int j=;j<=n;++j){

         for(int i=;i<=n;++i){

             if(mp[i][j]==) continue;

             int p=j-,k=mp[i][j];

             while(p>&&mp[i][p]==) mp[i][p]=k,mp[i][p+]=,--p;

             if(p!=j-) flag=;

         }

     }

 }

 void mergeright(){

     for(int j=n-;j>=;--j){

         for(int i=;i<=n;++i){

             if(mp[i][j]==) continue;

             int p=j+,k=mp[i][j];

             while(p<=n&&mp[i][p]==) mp[i][p]=k,mp[i][p-]=,++p;

             if(p!=j+) flag=;

             if(vis[i][p]==&&mp[i][p]==mp[i][p-]) mp[i][p]<<=,mp[i][p-]=,flag=vis[i][p]=,ans+=mp[i][p];

         }

     }

 }

 void right(){

     for(int j=n-;j>=;--j){

         for(int i=;i<=n;++i){

             if(mp[i][j]==) continue;

             int p=j+,k=mp[i][j];

             while(p<=n&&mp[i][p]==) mp[i][p]=k,mp[i][p-]=,++p;

             if(p!=j+) flag=;

         }

     }

 }

 int main(){

     scanf("%d%d",&n,&m);

     int xx1,yy1,vv1,xx2,yy2,vv2;

     scanf("%d%d%d%d%d%d",&xx1,&yy1,&vv1,&xx2,&yy2,&vv2);

     mp[xx1][yy1]=vv1,mp[xx2][yy2]=vv2;

     for(int i=,d,k,v;i<=m;++i){

         scanf("%d%d%d",&d,&k,&v);

         memset(vis,,sizeof(vis));

         flag=;

         if(d==) mergeup(),up();

         if(d==) mergedown(),down();

         if(d==) mergeleft(),left();

         if(d==) mergeright(),right();

         if(!flag){

             printf("%d\n%d\n",i-,ans);

             return ;

         }

         put(k%get()+,v);

     }

     printf("%d\n%d\n",m,ans);

     return ;

 }

数列：

可以证明最优答案要么是单增，要么先增后减

然后就是最长上升子序列了，好像也不太一样，都差不多

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXN=1e5+;

 int n,a[MAXN],b[MAXN],f[MAXN],g[MAXN],mx=;

 int lsh[MAXN];

 double ans=0.0;

 struct BIT{

     int c[MAXN];

     int lowbit(int x){

         return x&(-x);

     }

     int update(int pos,int val){

         for(int i=pos;i<=mx;i+=lowbit(i)){

             c[i]=max(c[i],val);

         }

     }

     int query(int pos){

         int res=;

         for(int i=pos;i>;i-=lowbit(i)){

             res=max(res,c[i]);

         }

         return res;

     }

 }t1,t2;

 double max(double a,double b){

     return a>b?a:b;

 }

 signed main(){

     scanf("%lld",&n);

     for(int i=;i<=n;++i){

         scanf("%lld",&a[i]);

         lsh[i]=a[i];

     }

     sort(lsh+,lsh+n+);

     mx=unique(lsh+,lsh+n+)-lsh-;

     for(int i=;i<=n;++i) b[i]=lower_bound(lsh+,lsh+mx+,a[i])-lsh;

     for(int i=;i<=n;++i){

         f[i]=t1.query(b[i]-)+a[i];

         g[i]=t2.query(b[n-i+]-)+a[n-i+];

         t1.update(b[i],f[i]);

         t2.update(b[n-i+],g[i]);

     }

     for(int i=;i<=n;++i)

         ans=max(ans,max(f[i],(f[i]+g[n-i+]-a[i])/2.0));

     printf("%0.3lf\n",ans);

     return ;

 }

生成树：

连虚数都出来了。。。

把每一个虚数看作向量，枚举角度更新答案

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int MAXN=;

 const int MAXM=;

 int n,m,fa[MAXN];

 double ans=0.0,xx,yy;

 int find(int x){

     return fa[x]=(fa[x]==x?x:find(fa[x]));

 }

 struct node{

     int fr,to;

     double a,b;

     friend bool operator < (node p,node q){

         return p.a*xx+p.b*yy<q.a*xx+q.b*yy;

     }

 }e[MAXM];

 double kruskal(){

     int vala=,valb=,sum=;

     for(int i=;i<=n;++i) fa[i]=i;

     sort(e+,e+m+);

     for(int i=;i<=m;++i){

         int x=find(e[i].fr),y=find(e[i].to);

         if(x!=y){

             fa[x]=y;

             ++sum,vala+=e[i].a,valb+=e[i].b;

             if(sum==n-) break;

         }

     }

     return sqrt(vala*vala+valb*valb);

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=,u,v;i<=m;++i){

         double a,b;

         scanf("%d%d%lf%lf",&u,&v,&a,&b);

         e[i]=(node){u,v,a,b};

     }

     for(double i=0.0;i<=63.00;i+=0.01){

         xx=sin(i),yy=cos(i);

         ans=max(ans,kruskal());

     }

     printf("%0.6lf\n",ans);

     return ;

 }

巴特西

csps模拟测试7273简单的操作小P的2048小P的单调数列小P的生成树

最新文章

热门文章