多校联合（6）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4350

以为移动的都是 0 到 r - 1 内的牌，所以直接模拟就行了

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#define N 60
#define _clr(a,val) (memset(a,val,sizeof(a)))

using namespace std;

typedef long long ll;

struct node
{
    int ind;
    int data;
}p[N],tp[N];
int da[N];
int main()
{
    int i;
    int t;
    int n,l,r;
    int cs = 0;
    //freopen("data.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        _clr(da,0);
        for(i = 0; i < 52; i++)
        {
            scanf("%d",&p[i].data);
            p[i].ind = i;
        }
        scanf("%d%d%d",&n,&l,&r);
        printf("Case #%d: ",++cs);
        for(i = 0; i < r; i++)
        {
            ll temp = (ll)((ll)n * (r - l + 1) % r);
            int kemp = (i % r + temp) % r;
            da[kemp] = p[i].data;
        }
        printf("%d",da[0]);
        for(i = 1; i < r; i++)
        printf(" %d",da[i]);
        for(i = r; i < 52; i++)
        printf(" %d",p[i].data);
        printf("\n");
    }
    return 0;
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4355

这道题不知道的时候想用枚举，知道了是三分模板时，就觉得自己真够可以的，很简单的一个三分，但是感觉时间好卡，精度开的是 1e-6，然后怎么都TLE后来看见有人开2e-4可以过掉，不过跑的很慢 ，1800+ms,估计数据再强点又超了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#define N 50010
#define exp 2e-4
#define _clr(a,val) (memset(a,val,sizeof(a)))

using namespace std;

struct node
{
    double x;
    double w;
}s[N];
int n,m;
double dist(double key)
{
    double sum = 0;
    for(int i = 0; i < n; i++)
    {
        double d = fabs(s[i].x - key);
        sum += (d * d * d * s[i].w);
    }
    return sum;
}
int main()
{
    int i,t;
    int cs = 0;
    //freopen("data.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i = 0; i < n; i++)
        scanf("%lf%lf",&s[i].x,&s[i].w);
        double r = s[n - 1].x;
        double l = s[0].x;
        double lmid,rmid;
        double sum1 = 0.0,sum2 = 0.0;
        while(r - l > exp)
        {
            lmid = (l * 2.0 + r) / 3.0;
            rmid = (l + 2.0 * r) / 3.0;

            if(dist(lmid) < dist(rmid))
            {
                r = rmid;
            }
            else
            {
                l = lmid;
            }
        }
        printf("Case #%d: %d\n",++cs,(int)(dist(r) + 0.5));
    }
    return 0;
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4357

这个题很后悔，当时LM猜出了两个字符串差值是偶数时应该就可以，然后我们就开始写，可是我写特判 长度是2时竟然想简单了，没有模拟交换，而是直接判相等了（对自己很无语），导致我们错了一次后就换思路了

因为每有一个字符变动时对与第一个字符串整体改变是 2 所以只要上下差值取余为零就可以转变，当然，长度是 2 时要特判

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#define N 100
#define _clr(a,val) (memset(a,val,sizeof(a)))

using namespace std;

typedef long long ll;

int main()
{
    char str[N],sbr[N];
    int t;
    int cs = 0;
    //freopen("data.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>str>>sbr;
        int len1 = strlen(str);
        printf("Case #%d: ",++cs);
        if(len1 == 2)
        {
            int flag = 0;
            for(int i = 0; i < 26; i++)
            {
                if(!strcmp(str,sbr))
                {
                    flag = 1;
                    break;
                }
                swap(str[0],str[1]);
                if(str[0] == 'z') str[0] = 'a';
                else
                str[0]++;
                //if(str[0] > 'z') str[0] = str[0] - 'z' + 'a' - 1;
                //str[1]++;
                if(str[1] == 'z') str[1] = 'a';
                else
                str[1]++;
                //if(str[1] > 'z') str[1] = str[1] - 'z' + 'a' - 1;
            }
            if(flag) printf("YES\n");
            else printf("NO\n");
        }
        else
        {
            int sum = 0;
            for(int i = 0; i < len1; i++)
            sum += (sbr[i] - str[i]);
            if(sum % 2 == 0) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4359

恩，这个是看的解题报告   

解题报告：根节点不受限制。所以N 个元素里面任选。还剩N − 1个。
除根节点外最大的元素必然在根节点的右子树上。   然后假设深度D−1在右子树上,依次枚举左子树元素个数和深度≤ D−1的   所有情况(此处要用前缀和优化)DP 即可
深度D − 1在左子树上同理可得。  (枚举时注意根节点和除根节点外最大数已被选,还有深度D − 1同时出现在两颗子树上的情况算了两次要剪掉一次

左子树和<右子树和等价于左子树最大值<右子树最大值，这样下面枚举左子树时，如果左子树有 i 个节点，那么除去根节点和最大的那个右子树上就有 num - i - 1个节点

参考代码链接 http://blog.csdn.net/cyberzhg/article/details/7848420

上午看这个代码，没有详细看标程，只是看了一下c[i][j]数组的求法，还以为是按解题报告给的思路写的，下午童鞋跟我说思路是不一样的

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 370
#define mod 1000000007
#define _clr(a,val) (memset(a,val,sizeof(a)))

using namespace std;

typedef long long ll;
int c[N][N];  // 计算i 个节点 选 j个的组合数
ll tree[N][N]; // 节点为 i 深度为  1 到 j 时的总数 
bool vis[N][N]; // 标记访问
void init()
{
    int i,j;
    for(i = 0; i < N; i++) c[i][0] = 1;
    for(i = 1; i < N; i++)
    {
        for(j = 1; j < N; j++)
        {
            if(i == j) c[i][j] = 1;
            else
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;  // 看的解题报告上写的，随时取余，以免超 long long
        }
    }
}
ll dfs(ll num,ll dep)
{
    if(dep == 0) return 0;
    if(num == 1) return 1;
    if(vis[num][dep])
    {
        return tree[num][dep];
    }
    ll res = (num * ((dfs(num - 1,dep - 1) * 2) % mod)) % mod;  // 左 或 右为空时
    //cout<<"res = "<<res<<endl;
    for(ll i = 1; i < num - 1; i++)
    {
        res += (num * (c[num - 2][num - i - 1] * ((dfs(i,dep - 1) * dfs(num - i - 1,dep - 1)) % mod) % mod)) % mod; 
        res %= mod;
    }
    vis[num][dep] = true;
    return tree[num][dep] = res;
}
int main()
{
    int t,cs = 0;
    init();
    //freopen("data.txt","r",stdin);
    int n,d;
    scanf("%d",&t);
    while(t--)
    {
        //_clr(vis,0);  // 如果加上会超的，但是不加用过vis一次后不会对以后有影响吗？
        scanf("%d%d",&n,&d);
        ll ans = (dfs(n,d) - dfs(n,d - 1) + mod) % mod; // 层数从 1 到 d 的数 - 层数从 1 到 （d - 1）的数为 深度 为 d 的数
        printf("Case #%d: %I64d\n",++cs,ans);
        //cout<<ans<<endl;
    }
    return 0;
}