转载请注明出处：

　　上一次失误掉进Div2，这次也很可惜，B题读错了题又差一点。。。

【A.Lights Out】

　　

　　题目大意：按开关会导致周围相邻开关状态一起变化，给出操作问结果。

　　简单模拟

1 #include 
      
        2 using namespace std; 3  4 const int dx[5]={
    0,1,0,-1,0}; 5 const int dy[5]={
    1,0,-1,0,0}; 6 int res[5][5],x; 7  8 int main(){ 9     for(int i=1;i<=3;i++)10         for(int j=1;j<=3;j++){11             cin>>x;12             for(int k=0;k<5;k++)13                 res[i+dx[k]][j+dy[k]]+=x;14         }15     for(int i=1;i<=3;i++){16         for(int j=1;j<=3;j++)17             cout<<(res[i][j]+1)%2;18         cout<
      

 

【B.Convex Shape】

　　

　　题目大意：判断所给图形是不是所谓"Convex Shape"(即任意两个格子互达且只需转向一次)

　　枚举两个格子，沿着路径走就可以了= =竟然读错题了啊囧

1 #include 
      
        2 using namespace std; 3  4 int n,m,x[3000],y[3000],cnt; 5 char s[50][50]; 6  7 bool check(int x,int a1,int b1,int y,int a2,int b2){ 8     for(int i=min(a1,b1);i<=max(a1,b1);i++) 9         if(s[x][i]!='B') return 0;10     for(int i=min(a2,b2);i<=max(a2,b2);i++)11         if(s[i][y]!='B') return 0;12     return 1;13 }14 15 int main(){16     cin>>n>>m;17     for(int i=0;i
       
        >s[i];19         for(int j=0;j
       
      

 

【C.k-Multiple Free Set】(A in Div1)

　　

　　

　　题目大意：从所给数集中找出最大子集，使得子集中不存在x,y，使得y=x*k。求最大子集的大小。

　　我思路大体是这样的。。。

　　首先我把题目抽象成一个图的问题，对于集合中x,x*k，将他们连边，最后图中会形成若干条链，不同的链一定互不干扰，问题转换成在每条链中选取尽量多的点。

　　到这里就可以做了（博主就是这样做的结果时间内存都巨大），但是可以继续想

　　选取尽量多的点的一种方法就是：链头上的点先选，然后隔一个点选一个。这样就有了一种贪心的方法，先将集合中数字排序，然后如果该数可选，就选，不可选就不选。

　　代码1：贪心方法

1 #include 
      
        2 #include 
       
         3 #include 
        
       
      

　　代码2：图方法

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
        
       
      

 

【D.Zero Tree】(B in Div1)

　　

　　

　　题目大意，给定一棵带权树，每次可以选取包括节点1的一棵子树，使其所有点权±1，问最少操作次数使得所有节点点权为0.

　　显然应该先把叶子节点变成0，然后依次向上做。dfs即可

1 #include 
      
        2 #define mn 100010 3 #define mm 200010 4 using namespace std; 5 typedef long long ll; 6 template
       
        inline void gmax(T &a,T b){
    if(a
        
         pre)26         if(j->pnt!=fa){27             dfs(j->pnt,x);28             gmax(t_add,add[j->pnt]);29             gmax(t_sub,sub[j->pnt]);30         }31     w[x]+=t_add-t_sub;32     if(w[x]<0) t_add-=w[x];33     else t_sub+=w[x];34     add[x]=t_add,sub[x]=t_sub;35 }36 37 int main(){38     cin>>n;39     for(int i=1;i
         
          >a>>b;41         addedge(a,b);42     }43     for(int i=1;i<=n;i++)44         cin>>w[i];45     dfs(1,0);46     cout<
          
           <
          
         
        
       
      

 

【E.】The Last Hole!(C in Div 1)

　　

　　

　　题如其名，最后一题是个坑。。。等会写

 

【D.Lovely Matrix】(Div 1)

　　

　　题目大意：n×m格子，格子有权值，有空格，问是否可以交换某些列的次序，使得每一行上的数字不减。

　　显然是拓扑排序。问题在于数据范围有点大，如果出现权值相同的格子，建图时逐个连边复杂度非常高。我们可以考虑附加点P[x]，使权值为x的点都连向P[x]，然后由P[x]连向比x大的点。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define mm 200010 5 #define mn 400010 6 using namespace std; 7  8 queue
         
           q; 9 int n,m,ans[mn],deg[mn],cnt,idx;10 struct REC{
    int v,p;}a[mn];11 12 struct EDGE{13     int pnt;14     EDGE *pre;15     EDGE(){}16     EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}17 }Edge[mm],*SP=Edge,*edge[mn];18 19 inline void addedge(int a,int b){20     edge[a]=new(++SP)EDGE(b,edge[a]);21     deg[b]++;22 }23 24 inline bool cmp(REC a,REC b){
    return a.v
          
           >n>>m;28     for(int i=0;i
           
            >a[j].v;31 a[j].p=j;32 }33 sort(a,a+m,cmp);34 for(int j=0;j
            
             pre)48 if(!--deg[j->pnt]) q.push(j->pnt);49 }50 if(idx
            
           
          
         
        
       
      

【E. Mirror Room】(Div 1)

　　

　　题目大意：光线在镜子格里反射，问能经过多少格子。

　　看了liouzhou101大神的代码明白了，其实就是用了一堆map和set然后模拟。。。。

　　好不容易仿照着写出来了，但是今天CF评测机抽风，在第24个点tle，连liouzhou101的代码现在都过不了。。。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include