计蒜客初赛3练习赛

计蒜客初赛5之前选了初赛3的题强行练手，确实这道题对思维的要求不低，要求转换思路，价值挺大。初赛5成功晋级后，将未完成的代码补完，完结此次初赛之旅。

 A. 腾讯课堂的物理实验

思路：这题明显是个模拟题，模拟两个小车的位置。不过，一开始准备写个程序专门判断小车位置，考虑到小车方向，时间，并单独处理碰撞和碰墙情况，由于还看存在半点碰撞和位置重合的情况，这样模拟十分复杂。

然而，如果换个思路，由于均为弹性碰撞，根据弹性碰撞性质（不要被题目的胡扯所干扰，大小相等方向相反只是巧合，正常情况应该为两车交换速度），碰后相当于a，b两车交换，而运动状态未发生任何变化，不影响两车之间的距离，因此，单独模拟两车运动，完全可能不用考虑碰撞

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int l;

int drive(int p,int t,int d)
{
    while(t--)
    {
        p += d;
        if(p==0||p==l)
        {
            d = d * (-1);
        }
    }
    return p;
}

int main()
{
    int ts,tt;
    while(scanf("%d%d%d",&l,&ts,&tt)!=EOF)
    {
        int a = drive(0,tt,1);
        int b = drive(l,tt-ts,-1);
        //cout << a << "*" << b << endl;
        int dis = (a-b);
        if(dis<0)
        {
            dis = dis * (-1);
        }
        printf("%d\n",dis);
    }
    return 0;
}

 B. 腾讯狼人杀（简单）

思路：这题以狼人杀为背景，长篇描述狼人杀，对于我这种不怎么玩这个游戏的人来说，莫名感到有点方，然而，读完题后才发现这题和狼人杀没有任何关系，只是一个组合匹配问题

注意到这题n仅为20，O（2^n）的复杂度完全没有问题，于是考虑到枚举所有组合方式，并用dfs实现以下就ok了，最后注意一下stl中stack的遍历

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;

const int maxn = 25;

int n,m;

double maxsum;

int w[maxn][maxn];

bool p[maxn];

stack<int> con;

void dfs(int t,int fig)
{
    if(t==n)
    {
        double money = con.size() * (2 * n - con.size());
        double sum = double(fig) / money;
        //cout << sum << "*"<<fig<<"*"<<money<<"*" <<maxsum << endl;
        if(sum > maxsum)
        {
            maxsum = sum;
        }
        return ;
    }
    if(!p[t])
    {
        dfs(t+1,fig);
    }
    stack <int> temp;
    while(!con.empty())
    {
        int i = con.top();
        fig += w[i][t];
        con.pop();
        temp.push(i);
    }
    while(!temp.empty())
    {
        int i = temp.top();
        temp.pop();
        con.push(i);
    }
    con.push(t);
    dfs(t+1,fig);
    con.pop();
    return ;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(w,0,sizeof(w));
        while(!con.empty())
        {
            con.pop();
        }
        maxsum = 0;
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            scanf("%d",&w[u-1][v-1]);
            w[v-1][u-1] = w[u-1][v-1];
        }
        /*for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout << w[i][j]<< " ";
            }
            cout << endl;
        }*/
        for(int i=0;i<n;i++)
        {
            int temp;
            scanf("%d",&temp);
            if(temp == 1)
            {
                p[i] = true;
            }
            else
            {
                p[i] = false;
            }
        }
        dfs(0,0);
        printf("%.4f\n",maxsum);
    }
    return 0;
}