昨天打了场cf,只做出第一道水题，而和我同级的队员都做出三道题，有点难过，落下太多，剩下的唯有好好补题。

昨天比赛时候写的BFS,到最后不好对上面有没有进行判断。

今天早上花一个半小时软磨硬泡出来的DFS

1 #include 
      
         2 using namespace std;  3 int n,m;  4 char temp[16][105];  5 int maze[16][105];  6 int l[16];  7 int r[16];  8 const int inf = 0x3f3f3f3f;  9 int dfs(int curfloor,int stairs) 10 { 11     if(curfloor>=n-1) 12     { 13         if(l[n-1]==inf) 14         { 15             return 0; 16         } 17         else 18         { 19             if(!stairs) 20             { 21                 return r[n-1] + 1; //末尾加1上1台阶 22             } 23             else 24             { 25                 return m - 1 - l[n-1] + 1; 26             } 27         } 28     } 29     if(l[curfloor]==inf)    //本楼道没有灯亮，就不用走了 30     { 31         int cost = dfs(curfloor+1,stairs); 32         if(cost) 33         { 34             return cost+1; 35         } 36         else 37         { 38             return cost; 39         } 40     } 41     else                       //有灯则继续考虑 42     { 43         int same = dfs(curfloor+1,stairs);              //先往上走走试试 44         int different = dfs(curfloor+1,!stairs); 45         int cost = 0; 46         if(!stairs)  //0表示我是从下一层从左上来的 47         { 48             cost = same+r[curfloor]*(same>0?2:1)+1; //如果以后没有，我就停在最后的位置，不用绕回来了 49             cost = min(cost,different+r[curfloor]+(m-1-r[curfloor])*(different>0?1:0)+1); //+1表示上到现在的台阶 50         } 51         else    //从右上 52         { 53             cost = same+(m-1-l[curfloor])*(same>0?2:1)+1; 54             cost = min(cost,different+m-1-l[curfloor]+l[curfloor]*(different>0?1:0)+1); 55         } 56         return cost; 57     } 58 } 59 int main() 60 { 61     cin>>n>>m; 62     m += 2; 63     for(int i=0;i
       
        >temp[i]; 66     } 67     int v = n-1; 68     memset(l,inf,sizeof(l)); 69     memset(r,0,sizeof(r)); 70     for(int i=0;i
        
         0) 85     { 86         cout<
         
          <
         
        
       
      

 膜一下Q老师的DFS，从上往下扫，up和 if(!flag)l[i]=m+1,r[i]=0 省去了大量代码。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;char s[25][155];int n,m,res,l[25],r[25];void dfs(int dep,int up,int lr,int now){ if(dep==up) { if(lr==0)res=min(res,now+r[dep]); else res=min(res,now+m+1-l[dep]); return; } dfs(dep-1,up,lr^1,now+m+2); if(lr==0)dfs(dep-1,up,lr,now+2*r[dep]+1); else dfs(dep-1,up,lr,now+2*(m+1-l[dep])+1);}int main(){ scanf("%d%d",&n,&m); for(int i=0;i
            
             =0;j--) if(s[i][j]=='1')l[i]=j,flag=1; if(flag && up<0)up=i; if(!flag)l[i]=m+1,r[i]=0; } if(up<0)return 0*printf("0"); res=n*(m+2); dfs(n-1,up,0,0); return 0*printf("%d",res);}
            
           
          
         
        
       
      

 

二分满足我们要求的最大K. + sort ，复杂度 nlog2n

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e5+5; 4 typedef long long ll; 5 ll arr[maxn]; 6 ll res[maxn]; 7 int main() 8 { 9     ll n,S;10     cin>>n>>S;11     for(int i=1;i<=n;i++)12     {13         cin>>arr[i];14     }15     //枚举k16     ll l = 1,r = n,mid = 0;17     int k = 0,T = 0;18     while(l<=r)19     {20         mid = (r-l)/2+l;21         for(int i=1;i<=n;i++)22         {23             res[i] = arr[i] + i*mid;24         }25         sort(res+1,res+n+1);26         ll sum = 0;27         for(int i=1;i<=mid;i++)28         {29             sum += res[i];30         }31         if(sum<=S)32         {33             k = mid;34             T = sum;35             l = mid+1;36         }37         else38         {39             r = mid-1;40         }41     }42     cout<
       
        <<" "<
        
         <
        
       
      

 

 

初次接触Nim博弈。

有a1,a2,a3,,,,an堆石子，如果s = a1^a2^a3^...^an = 0，那么就是后手赢，否则先手赢。

其实挺好理解的，比如1 4 5，二进制是1，100，101，每个位置的1都是成对出现，那么先手怎么取后手重复就行啦。

本题变了下形。 底部设为蓝色节点，蓝色节点的父亲节点设为红色节点。红色节点的父亲节点设为蓝色节点，以此类推。

我们只需要判断蓝色节点的异或是否=0就可以了。因为先手只要一挪动红色节点上的苹果，我们就从蓝色节点上拿掉相应的苹果就可以了。

1.s = 0,我们交换红色之间的，蓝色之间的，红色和蓝色相等的数量的。

2.s!=0，我们设红色节点为num1,蓝色为num2.s^num1^num2=0就可以啦。

1 #include 
      
        2 using namespace std; 3 const int maxn = 1e5+5; 4 typedef long long ll; 5 map
       
        blue; 6 map
        
         red; 7 int arr[maxn]; 8 vector
         
           son[maxn]; 9 int s = 0;10 ll bluenum = 0;11 ll rednum = 0;12 int DFS(int u)13 {14     int t = son[u].size();15    if(!t)           //统计叶子节点的个数16    {17        blue[arr[u]]++;18        bluenum++;19        s ^= arr[u];20        return 1;21    }22    int ans = 0;23    for(int i=0;i
          
           >n;44     for(int i=1;i<=n;i++) cin>>arr[i];45     for(int i=2;i<=n;i++)46     {47         int x;48         cin>>x;49         son[x].push_back(i);50     }51     DFS(1);52     ll sum = 0;53     if(s==0)54     {55         sum += bluenum*(bluenum-1LL)/2LL+rednum*(rednum-1LL)/2LL;56         for(map
           
            ::iterator blueit = blue.begin();blueit!=blue.end();blueit++)57 {58 int num = blueit->first;59 if(red.count(num))60 {61 sum += (ll)blueit->second*(ll)(red[num]);62 }63 }64 }65 else66 {67 for(map
            
             ::iterator blueit = blue.begin();blueit!=blue.end();blueit++)68 {69 int num1 = blueit->first;70 int num2 = s^num1;71 if(red.count(num2))72 {73 sum += (ll)blue[num1]*(ll)red[num2];74 }75 }76 }77 cout<
             
              <