昨天打了场cf,只做出第一道水题，而和我同级的队员都做出三道题，有点难过，落下太多，剩下的唯有好好补题。
昨天比赛时候写的BFS,到最后不好对上面有没有进行判断。
今天早上花一个半小时软磨硬泡出来的DFS
1 #include <bits/stdc++.h> 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<n;i++) 64 { 65 cin>>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<n;i++) 71 { 72 for(int j=0;j<m;j++) 73 { 74 maze[i][j] = temp[v][j]-'0'; 75 if(maze[i][j]==1) 76 { 77 l[i] = min(l[i],j); 78 r[i] = max(r[i],j); 79 } 80 } 81 v--; 82 } 83 int cost = dfs(0,0); 84 if(cost>0) 85 { 86 cout<<cost-1<<endl; 87 } 88 else 89 { 90 cout<<0<<endl; 91 } 92 return 0; 93 } 94 /* 95 4 3 96 00000 97 00100 98 00000 99 00000 100 */
膜一下Q老师的DFS，从上往下扫，up和 if(!flag)l[i]=m+1,r[i]=0 省去了大量代码。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> 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<n;i++) scanf("%s",s[i]); int up=-1; for(int i=0;i<n;i++) { bool flag=0; for(int j=0;j<m+2;j++) if(s[i][j]=='1')r[i]=j,flag=1; for(int j=m+1;j>=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 <bits/stdc++.h> 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 //枚举k 16 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 else 38 { 39 r = mid-1; 40 } 41 } 42 cout<<k<<" "<<T<<endl; 43 return 0; 44 }
初次接触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 <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5+5; 4 typedef long long ll; 5 map<int,int>blue; 6 map<int,int>red; 7 int arr[maxn]; 8 vector<int> 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<t;i++) 24 { 25 ans = DFS(son[u][i]); 26 } 27 if(ans) //统计red节点的个数 28 { 29 rednum++; 30 red[arr[u]]++; 31 } 32 else 33 { 34 s ^= arr[u]; 35 blue[arr[u]]++; 36 bluenum++; 37 } 38 return !ans; 39 } 40 int main() 41 { 42 int n; 43 cin>>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<int,int>::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 else 66 { 67 for(map<int,int>::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<<sum<<endl; 78 return 0; 79 }