SRM470

250pt

给定1个最多16颜色的字符串(颜色可以重复)，甲在最左边，乙在最右边。轮流操作，每次可以消除一种颜色。

给定一个k，问谁能最先消除完到位置k之间的障碍。

思路：

每个人肯定优先取对方没有的，，所以直接模拟即可

 #line 7 "DoorsGame.cpp"

 #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 <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define PB push_back

 #define MP make_pair

 #define two(i) (1 << i)

 #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)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long LL;

 typedef pair<int,int> PII;

 class DoorsGame

 {

         public:

         int determineOutcome(string s, int p)

         {

              int n = s.size(), S = ,  S1 = ;

              for (int i = ; i < p; ++i)

                 S |= ( << (s[i] - 'A'));

              for (int i = p; i < n; ++i)

                 S1 |= ( << (s[i] - 'A'));

              int same = S & S1;

              int ans = , j;

              while (){

                   j = -;

                   for (int i = ; i < ; ++i)

                      if (S & two(i)){

                           if (j == - || !(two(i) & same)) j = i;

                      }

                   S -= two(j);

                   if (S1 & two(j)) S1 -= two(j);

                   ++ans;

                   if (S == ){

                        if (S1 == ) return ;

                        return ans;

                   }

                   j = -;

                   for (int i = ; i < ; ++i)

                      if (S1 & two(i)){

                           if (j == - || !(two(i) & same)) j = i;

                      }

                   S1 -= two(j);

                   if (S & two(j)) S -= two(j);

                   ++ans;

                   if (S1 == ){

                        if (S == ) return ;

                        return -ans;

                   }

              }

              return ;

         }

 };

500pt

两排点,每排n个.上排的和下排的连线.事先已经有些线连好了.求考虑所有的连线方案时,连线交点个数的期望

思路：
        三类计数:事先已经连好的线间的交点数.新增连线和原有连线的交点数期望.新增连线之间交点期望.

 // BEGIN CUT HERE

 /*

 */

 // END CUT HERE

 #line 7 "DrawingLines.cpp"

 #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 <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define PB push_back

 #define MP make_pair

 #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)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long LL;

 typedef pair<int,int> PII;

 class DrawingLines

 {

         public:

         double countLineCrossings(int n, vector <int> s, vector <int> t)

         {

              int m = s.size();

              double ret = (n - m) * (n - m - 1.0) / 4.0;

              for (int i = ; i < m; ++i)

                for (int j = i + ; j < m; ++j)

                  if ((s[i] < s[j] && t[i] > t[j]) || (s[i] > s[j] && t[i] < t[j])) ret += 1.0;

              for (int i = ; i < m; ++i){

                    double s1 = s[i] - ,  s2 = n - s[i], t1 = t[i] - , t2 = n - t[i];

                    for (int j = ; j < m; ++j){

                         if (s[j] < s[i]) --s1;

                         if (s[j] > s[i]) --s2;

                         if (t[j] < t[i]) --t1;

                         if (t[j] > t[i]) --t2;

                    }

                    ret += (s1 * t2 + s2 * t1) / (t1 + t2);

              }

              return ret;

         }

 };