ZOJ 3605 Find the Marble

Description

Alice and Bob are playing a game. This game is played with several identical pots and one marble. When the game starts, Alice puts the pots in one line and puts the marble in one of the pots. After that, Bob cannot see the inside of the pots. Then Alice makes a sequence of swappings and Bob guesses which pot the marble is in. In each of the swapping, Alice chooses two different pots and swaps their positions.

Unfortunately, Alice's actions are very fast, so Bob can only catch k of m swappings and regard these k swappings as all actions Alice has performed. Now given the initial pot the marble is in, and the sequence of swappings, you are asked to calculate which pot Bob most possibly guesses. You can assume that Bob missed any of the swappings with equal possibility.

Input

There are several test cases in the input file. The first line of the input file contains an integer N (N ≈ 100), then N cases follow.

The first line of each test case contains 4 integers n, m, k and s(0 < s ≤ n ≤ 50, 0 ≤ k ≤ m ≤ 50), which are the number of pots, the number of swappings Alice makes, the number of swappings Bob catches and index of the initial pot the marble is in. Pots are indexed from 1 ton. Then m lines follow, each of which contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n), telling the two pots Alice swaps in the i-th swapping.

Outout

For each test case, output the pot that Bob most possibly guesses. If there is a tie, output the smallest one.

Sample Input

3 3 1 1 1 1 2 3 1 0 1 1 2 3 3 2 2 2 3 3 2 1 2

Sample Output

2 1

3

猜弹珠在哪个杯子里的游戏，总共交换了m次，但是只看见了k次。

只要把所有的情况都写出来即可，C(m,k)

用动规来实现，最后只要找出最多的那个数就好了。

注意数字可能很大，int会爆炸。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 55;
long long f[maxn][maxn][maxn];
int T, n, M, m, s, x, y, Max;

int use(int u)
{
  if (u == x) return y;
  if (u == y) return x;
  return u;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d%d%d", &n, &M, &m, &s);
    memset(f, 0, sizeof(f));
    for (int i = 0; i <= M; i++) f[i][0][s] = 1;
    for (int i = 1; i <= M; i++)
    {
      scanf("%d%d", &x, &y);
      for (int j = 1; j <= min(i, m); j++)
        for (int k = 1; k <= n; k++)
          f[i][j][k] = f[i - 1][j][k] + f[i - 1][j - 1][use(k)];
    }
    for (int i = Max = 1; i <= n; i++)
      if (f[M][m][Max] < f[M][m][i]) Max = i;
    cout << Max << endl;
  }
  return 0;
}

温故而知新

#include<map>
#include<cmath>    
#include<queue>    
#include<vector>
#include<cstdio>    
#include<cstring>    
#include<algorithm>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))    
#define rep(i,j,k) for(int i=j;i<=k;i++)    
#define per(i,j,k) for(int i=j;i>=k;i--)    
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])    
#define inone(x) scanf("%d",&x)    
#define intwo(x,y) scanf("%d%d",&x,&y)    
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)    
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 50 + 10;
int T, n, m, mm, s, x, y;
double dp[N][N][N];

int main()
{
  for (inone(T); T--;)
  {
    intwo(n, m); intwo(mm, s);
    ms(dp, 0);
    dp[0][0][s] = 1;
    rep(i, 1, m)
    {
      intwo(x, y);
      rep(j, 1, n)
      {
        dp[i][0][j] = j == s;
        if (j != x && j != y)
        {
          rep(k, 1, i) dp[i][k][j] = dp[i - 1][k][j] + dp[i - 1][k - 1][j];
        }
        else if (j == x)
        {
          rep(k, 1, i) dp[i][k][x] = dp[i - 1][k][x] + dp[i - 1][k - 1][y];
        }
        else
        {
          rep(k, 1, i) dp[i][k][y] = dp[i - 1][k][y] + dp[i - 1][k - 1][x];
        }
      }
    }
    int k = 1;
    rep(i, 1, n) if (dp[m][mm][i] > dp[m][mm][k]) k = i;
    printf("%d\n", k);
  }
  return 0;
}