NOIP2016提高组复赛C 愤怒的小鸟

题目大意：

　　太长了不想概括。。。
分析：

　　状压DP的模板题，把所有可能的抛物线用二进制表示，然后暴力枚举所有组合，详情见代码内注释
代码如下：

  1 #pragma GCC optimize("Ofast")
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 
  5 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0);
  6 #define Rep(i,n) for (int i = 0; i < (n); ++i)
  7 #define For(i,s,t) for (int i = (s); i <= (t); ++i)
  8 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
  9 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
 10 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
 11 
 12 #define pr(x) cout << #x << " = " << x << "  "
 13 #define prln(x) cout << #x << " = " << x << endl
 14 
 15 #define LOWBIT(x) ((x)&(-x))
 16 
 17 #define ALL(x) x.begin(),x.end()
 18 #define INS(x) inserter(x,x.begin())
 19 
 20 #define ms0(a) memset(a,0,sizeof(a))
 21 #define msI(a) memset(a,inf,sizeof(a))
 22 #define msM(a) memset(a,-1,sizeof(a))
 23 
 24 #define pii pair<int,int> 
 25 #define piii pair<pair<int,int>,int> 
 26 #define MP make_pair
 27 #define PB push_back
 28 #define ft first
 29 #define sd second
 30 
 31 template<typename T1, typename T2>
 32 istream &operator>>(istream &in, pair<T1, T2> &p) {
 33     in >> p.first >> p.second;
 34     return in;
 35 }
 36 
 37 template<typename T>
 38 istream &operator>>(istream &in, vector<T> &v) {
 39     for (auto &x: v)
 40         in >> x;
 41     return in;
 42 }
 43 
 44 template<typename T1, typename T2>
 45 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
 46     out << "[" << p.first << ", " << p.second << "]" << "
";
 47     return out;
 48 }
 49 
 50 inline int gc(){
 51     static const int BUF = 1e7;
 52     static char buf[BUF], *bg = buf + BUF, *ed = bg;
 53     
 54     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
 55     return *bg++;
 56 } 
 57 
 58 inline int ri(){
 59     int x = 0, f = 1, c = gc();
 60     for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
 61     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
 62     return x*f;
 63 }
 64 
 65 typedef long long LL;
 66 typedef unsigned long long uLL;
 67 typedef pair< double, double > PDD;
 68 typedef set< int > SI;
 69 typedef vector< int > VI;
 70 const double EPS = 1e-10;
 71 const int inf = 1e9 + 9;
 72 const LL mod = 1e9 + 7;
 73 const int maxN = 1e5 + 7;
 74 const LL ONE = 1;
 75 
 76 int sgn(double x) {
 77     if(fabs(x) < EPS) return 0;
 78     return x > 0 ? 1 : -1;
 79 }
 80 
 81 struct Matrix{
 82     double m[3][3];
 83     
 84     Matrix(){}
 85     Matrix(double x11, double x12, double x21, double x22) {
 86         m[1][1] = x11;
 87         m[1][2] = x12;
 88         m[2][1] = x21;
 89         m[2][2] = x22;
 90     }
 91     
 92     double det() {
 93         return m[1][1] * m[2][2] - m[1][2] * m[2][1];
 94     }
 95 };
 96 
 97 int T, n, m, ans;
 98 PDD pig[20];
 99 // 用n位二进制数记录一条抛物线可能穿过的点的状态 
100 // 比如抛物线过1号，5号，7号点，那么数值为 ：000000000001010001 
101 VI state; 
102 SI si;
103 // f[i]为当前状态的最小步数 
104 int f[1 << 18]; 
105 
106 int bitcount32(int bits) {
107     bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
108     bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
109     bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
110     bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
111     return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
112 }
113 
114 // 通过2个点算抛物线参数[a, b]
115 bool calcAB(PDD x, PDD y, PDD &para) {
116     Matrix D = Matrix(x.ft * x.ft, x.ft, y.ft * y.ft, y.ft);
117     if(sgn(D.det()) == 0) return false;
118     Matrix D1 = Matrix(x.sd, x.ft, y.sd, y.ft);
119     Matrix D2 = Matrix(x.ft * x.ft, x.sd, y.ft * y.ft, y.sd);
120     
121     para.ft = D1.det() / D.det();
122     if(sgn(para.ft) >= 0) return false; 
123     para.sd = D2.det() / D.det();
124     return true;
125 }
126 
127 // 验证点x是否符合抛物线
128 bool check(PDD x, PDD &para) {
129     if(sgn(para.ft * x.ft * x.ft + para.sd * x.ft - x.sd) == 0) return true;
130     return false;
131 }
132 
133 void solve() {
134     int ret = 0;
135     
136     // 枚举所有点对 
137     For(i, 1, n) {
138         For(j, i + 1, n) {
139             PDD p;
140             if(!calcAB(pig[i], pig[j], p)) continue;
141             // 看是否有其他点也经过这条抛物线
142             int st = 0;
143             st |= 1 << (i - 1);
144             st |= 1 << (j - 1);
145             For(k, 1, n) {
146                 if(k == i || k == j) continue;
147                 if(check(pig[k], p)) st |= 1 << (k - 1);
148             }
149             if(si.find(st) == si.end()) {
150                 si.insert(st);
151                 state.PB(st);
152             }
153         }
154     }
155     // 把只过一个点的抛物线也存一下
156     Rep(i, n) state.PB(1 << i);
157     // 把所有抛物线都得到后，问题就变成在这些抛物线中最少能选取几条，进行或运算后二进制1~n位全为1 
158     msI(f);
159     f[0] = 0;
160     int len = state.size();
161     
162     Rep(i, 1 << n) {
163         // 当枚举到f[i]时，f[i]已经是最优解了 
164         Rep(j, len) {
165             f[i | state[j]] = min(f[i | state[j]], f[i] + 1);
166         }
167     }
168     
169     ans = f[(1 << n) - 1];
170 }
171 
172 int main(){
173     INIT(); 
174     cin >> T;
175     while(T--) {
176         state.clear();
177         si.clear();
178         cin >> n >> m;
179         For(i, 1, n) cin >> pig[i];
180         solve();
181         
182         cout << ans << endl;
183     }
184     
185     return 0;
186 }
View Code