250pt
题意：
有左，中，右三个位置，一个球占据其中的一个，移动球到相邻的位置称为一次移动，求n次移动后球最可能在哪个位置（相同则字典序最小）？
分析：给力的250pt，还以为要用动态规划做，因为只有三个位置，可枚举。
0，移动次数为0肯定在原位置
1，球不在中间时，第一步肯定移到中间，
2，球中间时，剩余的移动数如果为偶数，肯定会回到中间，奇数的数，因为左右对称，左边50%，右边50%，字典序小，所以是左边
View Code
class BallAndHats { public: int getHat(string hats, int numSwaps) { int k; for(k=0;k<3;k++) if(hats[k]=='o') break; if(!numSwaps) return k; if(k!=1) numSwaps--,k=1; if(numSwaps&1) return 0; return 1; } };
500pt
题意：
给定若干个顶部圆锥和若干个底部圆锥，一个顶部圆锥堆在底部圆锥上组成一个帽子，求最多能组成多少个帽子
分析：500pt的题居然是二分匹配题
组成帽子的前提是顶圆锥(高:th，半径:tr)能堆在底圆锥(高:bh，半径:br)上。两个条件：
(1)，顶半径大于底半径tr<br
(2)，顶圆锥顶点高于底圆锥顶点(tr*bh/br)<th
剩下的是求最大二分匹配，套的是模板。忘了，默写不出来，又重新复习了一遍。
View Code
class PointyWizardHats { public: bool can[55][55],vis[55]; int link[55],n,m; bool find(int v) { for(int w=0;w<m;w++) if(!vis[w] && can[v][w]) { vis[w]=true; if(link[w]==-1||find(link[w])) { link[w]=v; return true; } } return false; } int getNumHats(vector <int> th, vector <int> tr, vector <int> bh, vector <int> br) { int i,j,k; memset(can,false,sizeof(can)); memset(link,-1,sizeof(link)); n=th.size(); m=bh.size(); for(i=0;i<n;puts(""),i++) for(j=0;j<m;j++) { if(tr[i]<br[j]&&(th[i]>(1.0*tr[i]*bh[j]/br[j]))) can[i][j]=true; printf("%d ",can[i][j]?1:0); } for(i=k=0;i<n;i++) { memset(vis,false,sizeof(vis)); if(find(i)) k++; } return k; } };
1000pt
题意：
给定一幅至多20个点的有向图，求至少要删除多少条边才能变成无环图。
分析：
若已求得结果，那么结果一定存在一个顶点的排列(V0,V1,V2....Vn-1)使任意j>=i不存在边VjVi。
顶点个数极少，无后续性（加一个点到集合中时不会影响原集合元素之间的关系），重叠子问题（每次都是加一个点到集合中）可用集合DP做,
集合的元素压缩成状态s的二进制位，为了方便计算,s中0表示含有对应二进制位的元素,1则相反，f[s]表示使集合状态为s无环化所需最少删边数。
结：又是一道不敢写的深搜题
View Code
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <iomanip> #include <bitset> #include <list> #include <strstream> using namespace std; #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) #define INF (1<<20) typedef vector<int> VI; typedef vector<double> VD; typedef long long LL; int dp[1<<20]; class OrderOfTheHats { public: int a[22],n; int Count(int x) { int i=0; for(;x;x>>=1) i+=(x&1); return i; } int F(int s) { int i,k,t,ret=INF; if(s==(1<<n)-1) return 0; if(dp[s]!=-1) return dp[s]; for(i=0;i<n;i++) if((s&(1<<i))==0) { k=Count(a[i]&s); if(a[i]&(1<<i)) k++; t=F(s|(1<<i)); if(ret>k+t) ret=k+t; } return dp[s]=ret; } int minChanged(vector <string> spellChart) { int i,j; n=spellChart.size(); memset(dp,-1,sizeof(dp)); for(i=0;i<n;i++) for(j=a[i]=0;j<n;j++) if(spellChart[i][j]=='Y') a[i]|=(1<<j); return F(0); } };