题解——2018.1.23

俾斯麦 · 2019-01-23 19:22:50 · 个人记录

LRD大佬的Day2比毒瘤的Day1舒服多了。

拿到题一看，T3居然是tarjan模板（~~比缩点还裸~~），切掉。T1是道毒瘤，打了半天的玄学算法骗了20分，但我身后的SXK大佬rand就有20分。（~~最高分也就20~~）T2是道要优化减边的Kruskal，然而考场上打死都没想出来，只好强行减空间+rand随机数输出，60分。加在一起180，但T3数组开小了，被卡了70分，结果只有110，看来我还是太弱了。

T2:

下一代互联网,基于IPv6 架构,很有可能改变互联网世界.然而这个题和IPv6 并没有什么关系.起成这个名字,是因为liu_runda 在铺网线的时候希望下一代互联网早点出现.

现在给出一个a*b 的金属网格.你有两种网线:长度为1 的,和长度为根号2 的.长度为1 的网线只能让你连接一个交叉点和它上下左右方向的交叉点,长度为根号2 的网线只能让你连接一个交叉点和它斜对角方向的交叉点.

在这个金属网格上,有n 个坐标放置了路由器.现在希望用网线把这n 个路由器连接起来.具体来说,你可以从一个路由器出发,连接若干条首尾相接的长度为1 或根号2 的网线到达另一个路由器,那么这两个路由器就被连通了.中间不能分叉,必须一直到达另一个路由器.从一个路由器可以引出多根网线.我们希望最终任意两个路由器直接或者间接连通.

我们希望铺设网络消耗的网线尽量少.liu_runda 首先发现,要连接两个横纵坐标都不同的路由器,先尽量使用长度为根号2 的网线,可以减少使用网线的根数和总长度,所以他规定任意一对直接连接的路由器,在连接这一对路由器使用网线长度最小的前提下,都必须尽可能使用长度为根号2 的网线.

接下来liu_runda 发现,长度为根号2 的网线比长度为1 的网线贵得多…但是liu_runda并不想收回他的规定.现在,他只能在已经有的辣鸡规定下,合理地选择哪几对路由器进行连接,尽量减少长度根号2 的网线的使用数目.(即使这样的方案下网线的总长度不一定最短)请问他最少需要使用多少根长度为根号2 的网线?

看起来很裸的Kruskal？只需按照2号线的数量排序？

让我们来看一下数据范围

所有数据, n <= 1e5 , 0 < a , b <= 1e9 , 0 < y[ i ] <= a , 0 < x[ i ] <= b . 不会出现横纵坐标相同的两个路由器.

嗯？prim GG , Kruskal GG ->~<-

但实际上，看看下图

我们将 C 点定义为中间点。

上图中的 B-D 边完全可以有 B-C 和 C-D 边构成，而且对于任意跨越中间点的边都可以由中间点构成。

综上，只有相邻两点之间的边才会有价值。

我们便成功的将边数从 N^2 降至 2N 。然后一个清晰的Kreskal。

#include<cstdio>
#include<algorithm>
using namespace std;
const  int  maxn = 100005;
int  father[maxn] , tot = 0 ;
int find(int x){
    return (x==father[x])?father[x]:(father[x]=find(father[x]));
}
struct point{
    int  x ;
    int  y ;
    int  num ;
}P[maxn];
bool cmpx(const point &A,const point &B){ //定义cmp 横边
    return A.x<B.x;                       //注意const point &~
}
bool cmpy(const point &A,const point &B){ //定义cmp 纵边
    return A.y<B.y;
}
struct edge{
    int u,v,w;
    edge(int a=0,int b=0,int c=0){
        u=a;v=b;w=c;
    }
    bool operator <(const edge &B)const{
        return w<B.w;
    }
}E[maxn*2];
int main(){
    freopen("net.in","r",stdin);
    freopen("net.out","w",stdout);
    int n;
    scanf("%*d%*d%d",&n);   //这里有 2 个没用的元素需要读入，大佬用 %*d 解决
    for( int  i = 1 ; i <= n ; ++i ){
        scanf("%d%d", &P[i].x , &P[i].y ) ; //读入
        P[ i ].num = i ; //初始化
    }
    sort( P + 1 , P + n + 1 , cmpx ) ;  // 依照横边sort ->  短的边必定排前面
    for( int  i = 1 ; i < n ; ++i ){
        E[++tot] = edge( P[ i ].num , P[ i+1 ].num , P[ i+1 ].x - P[ i ].x ) ;
    }                             // 重新建边 ， 只保留相邻2点之间最短边
    sort( P + 1 , P + n + 1 , cmpy ) ; 
    for( int  i = 1 ; i < n ; ++i ){
        E[++tot] = edge( P[ i ].num , P[ i+1 ].num , P[ i+1 ].y - P[ i ].y ) ; 
    }                             // 重新建边 ， 只保留相邻2点之间最短边
    sort( E + 1 , E + tot + 1 ) ;
    for( int  i = 1 ;i <= n ; ++i )father[ i ] = i ;//并查集初始化
    int  ans = 0 ; 
    for( int  i = 1 ; i <= tot ; ++i ){
        if( find( E[ i ].u) != find( E[i].v ) ) father[ find(E[i].u) ] = find(E[i].v) , ans += E[i].w ;        
    }          //压行的 克鲁斯卡尔
    printf("%d\n",ans); //完事
    return 0;
}

T2完结

T1：

给出一个RC 的棋盘.共有R 行C 列,RC 个格子.现要在每个格子都填一个非负整数.使得任意一个22 的正方形区域都满足这样的性质:左上角的数字+右下角的数字=左下角的数字+右上角的数字.有些格子已经确定,你不能更改其中的数字.其他格子的数字由你决定.下面是一个符合要求的33 的棋盘:

1  2  3
2  3  4
4  5  6

不难验证每个2*2 的区域都是符合要求的.liu_runda 准备下一盘大棋,为此,他想要知道一个可行的填充棋盘的方案.但是这个方案可能很大.所以你只需对给定的棋盘判定是否存在至少一种可行的填充棋盘的方案.

【输入格式】

第一行输入一个 T ，表示数据组数。接下来 T 组数据。

每组数据的第 1 行 3 个整数 R ,C , n , R 和 C 表示棋盘的大小. n 表示已经被填好数字的格子的数目

接下来 n 行每行 3 个整数 ri , ci , ai , 表示第ri 行 ci 列的格子被填上了数字 ai 。

【输出格式】

T 行.第 i 行是第 i 组数据的答案.有合法方案时输出一行 Yes , 没有时输出一行 No 。

对于这道题，左上 + 右下 = 左下 + 右上。

移动一下~~~ 左上 - 右上 = 左下 - 右下。

再来一下~~~ 左上 - 左下 = 右上 - 右下。

这说明什么？推广一下对于任意 2 列（如图 ABCD）

* A * * B 
* * * * * 
* * * * * 
* * * * * 
* C * * D

B - A = D - C ---------恒成立

好了，可以得到以下玄学算法（~~LRD的标程~~）

#include<cstdio>
#include<cassert>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
typedef long long ll;
int ufs[maxn];ll w1[maxn];
int R,C;
struct node{
  int x,y,val;
  void read(){
    scanf("%d%d%d",&x,&y,&val);
    assert(1<=x&&x<=R&&1<=y&&y<=C);
  }
}P[maxn];
bool cmpx(const node &A,const node &B){
  return A.x<B.x;
}
bool cmpy(const node &A,const node &B){
  return A.y<B.y;
}
int find(int x){
  if(x==ufs[x])return x;
  int rt=find(ufs[x]);
  w1[x]+=w1[ufs[x]];
  return ufs[x]=rt;
}
bool link(int a,int b,ll w){
  if(find(a)!=find(b)){
    int ra=find(a),rb=find(b);
    ufs[ra]=ufs[rb];
    w1[ra]=w+w1[b]-w1[a];
    return true;
  }else{
    return w1[a]==w+w1[b];
  }
}
ll Min1[maxn],Min2[maxn];
int main(){
  freopen("chess.in","r",stdin);
  freopen("chess.out","w",stdout);
  int tests;scanf("%d",&tests);
  while(tests--){
    bool flag=true;
    scanf("%d%d",&R,&C);
    for(int i=1;i<=R;++i){
      ufs[i]=i;w1[i]=0;
    }
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i)P[i].read();
    for(int i=1;i<=n;++i)if(P[i].val<0)flag=false;

    sort(P+1,P+n+1,cmpy);
    for(int i=1;i<n;++i)
      if(P[i].y==P[i+1].y)
        if(!link(P[i].x,P[i+1].x,P[i+1].val-P[i].val))flag=false;

    memset(Min1,0x3f,sizeof(Min1));
    memset(Min2,0x3f,sizeof(Min2));
    for(int i=1;i<=n;++i){
      int rt=find(P[i].x);
      Min1[rt]=min(Min1[rt],P[i].val+w1[P[i].x]);
    }
    for(int i=1;i<=R;++i){
      int rt=find(i);
      Min2[rt]=min(Min2[rt],-w1[i]);
    }
    for(int i=1;i<=R;++i)
      if(ufs[i]==i&&Min1[i]+Min2[i]<0)flag=false;    
    printf("%s\n",flag?"Yes":"No");
  }
  return 0;
}

各位，抱歉暂时没时间了，T1题解仍连载中......