Codeforces Round 492 (Div.1)-白红宇

Codeforces Round 492 (Div.1)

阅读量：4630 次

发布时间：2019-06-09

本文共 4048 字，大约阅读时间需要 13 分钟。

大概这一场考的还算可以吧..

上来刚A...然后A死难写...

然后B是水题..

C猜了个结论错掉了,也找到了反例

然后后面干脆的直接把数据random_shuffle以后再跑这个贪心...

就过了...

D..

感谢Q巨...

Q巨猜了个结论让我交了一发..

然后过了...

========================================================

A题

给你一个4*n的网格图,第一行第四行是停车场

第二行第三行是过道

现在一共有k辆车(编号1~k)停在过道上,你需要把它们挪到正确的位置上

你一旦将一辆车停入停车区,就不可以移动它,也就是说你必须让正确的车进入正确的位置

求一个20000步以内的方案,n<=50,k<=2n

做法;

你可以考虑,整个2*n的区域直接把它变成一个环,

例如上图

把它变成

1->2->0->4

^ |

| v

5<-0<-0<-3

的一个环,然后在这个环上每次移动一个车,顺便把前面所有的车都往前推一格(或者推进目的地)

时间复杂度O(100*99+100) 99表示最多移动99下才能到目的地(这个环上)

我们就一直让它转直到所有车都到目的地

(如果位置是满的,而且一开始没有车可以到目的地,输出-1)

实现的时候不是这么写的..而是把每个没到终点的都往终点推...

B题

2n个数,1~n各出现2次

每次可以交换两个连续的数

问几次能让每个数出现的两次是连续的

n<=100

直接...暴力把跟第一个相同的拖到第二个....然后依次做下去...

C题

n个向量,长度<=1e6

每个向量可以选择+1或者-1倍,要求

最后向量的和加起来长度<=1.5*1e6

我的做法:

直接每次让当前向量和下一个合并,取小的那一个

如果最后发现错了,就把数据random_shuffle一下,再做一次,直到做出来为止

过了,虽然不知道为啥

std做法:

每次三个里面,肯定有两个(可能经过乘以-1后)会有一对成为一个120°以外的角

那么两个<=1e6的向量加起来还在1e6以内

那么最后就可以得到两个,加起来一定在1.5*1e6(实际上在sqrt(2)*1e6)以内

D题:

A和B在玩一个游戏

它们在填一个n位的二进制数,每次随机一个人过来选一位填成0或者1

最后得分是c[二进制数数值]

A要让它尽量大,B要让它尽量小

问期望得到的值是多少,然后接下来r次修改

每次修改c数组里面一个数的值,然后再询问

n<=18

r<=2¹⁸

做法:

直接所有的c的和然后除以2^n

Q老师的结论...

EF不会做

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        using namespace std;#define move moasudoasjsapint a[4][55];struct move{ int id; int x; int y; move (int iid=0,int xx=0,int yy=0) { id=iid; x=xx+1; y=yy+1; } void output() { printf("%d %d %d\n",id,x,y); }};vector
                        
                          ans;bool vis[105];int n;int newx,newy;void find_next(int sx,int sy){ newx=sx; newy=sy; if (sx==1) { if (sy==0) { newx++; } else { newy--; } } else { if (sy==n-1) { newx--; } else { newy++; } }}void find_way(int sx,int sy,int tx,int ty,int id){ if ((sx==tx)&&(sy==ty)) return; find_next(sx,sy); int ttx=newx; int tty=newy; if (a[newx][newy]!=0) { if (a[ttx^1][tty]==a[ttx][tty]) { ans.push_back(move(a[ttx][tty],ttx^1,tty)); vis[a[ttx][tty]]=true; a[ttx][tty]=0; } else { find_next(ttx,tty); find_way(ttx,tty,newx,newy,a[ttx][tty]); } } ans.push_back(move(id,ttx,tty)); a[ttx][tty]=id; a[sx][sy]=0; find_way(ttx,tty,tx,ty,id);}int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int k; scanf("%d%d",&n,&k); int i; for (i=0;i<4;i++) { int j; for (j=0;j

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        using namespace std;int a[1005];int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; scanf("%d",&n); int i; for (i=0;i
                        
                         i+1;k--) { swap(a[k],a[k-1]); ans++; } } } } printf("%d\n",ans); return 0;}

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        using namespace std;struct vv{ int x; int y; int id;};vv v[100005];int ans[100005];int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif srand(time(0)); int n; scanf("%d",&n); int nowx=0,nowy=0; int i; for (i=0;i
                        
                         (long long)1500000*1500000) { for (;;) { random_shuffle(v,v+n); int nowx=0,nowy=0; for (i=0;i

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        using namespace std;int a[1<<18];int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,r; scanf("%d%d",&n,&r); int k=(1<