“今日头条杯”首届湖北省大学程序设计竞赛现场赛

将△ACD逆时针旋转60度：
这里写图片描述
得到△BDD’就是所要求的结果。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    double a,b,c;
    while(cin>>a>>b>>c)
    {
        double jiao[4];
        jiao[0]=a-60;
        jiao[1]=b-60;
        jiao[2]=c-60;
        sort(jiao,jiao+3);
        cout<<fixed<<setprecision(4)<<jiao[0]<<" "<<jiao[1]<<" "<<jiao[2]<<endl;
    }

    return 0;
}

B. Salty Fish Go!

一个考验数学概率论与数理统计的题目。
答案其实就是路程除以平均速度，再考虑捡珠宝的问题，题解说对于次序统计量的期望，n个数独立均匀分布的随机变量的最大值是n/(n+1)。
所以答案就是

l / a v e S p e e d * m / (m + 1)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    double v,l,n,m;
    while(cin>>v>>l>>n>>m)
    {
        double vi,aveSpeed=0;
        for(int i=0;i<v;i++)
        {
            cin>>vi;
            aveSpeed+=(double)vi;
        }
        aveSpeed=aveSpeed/(double)v;
        double result=((double)l*(double)m)/((double)aveSpeed*(double)(m+1));
        cout<<fixed<<setprecision(9)<<result<<endl;
    }
    return 0;
}

C.Mice

TQM had a bottle of poison mixed with $m - 1$ bottles of water ( $2 \leq m \leq 10^{6}$ ), so she bought n mice and was ready to doing experiment to find out the poison.

What is known:

This $m$ bottles of liquid is lined up one by one, numbered from $0$ to $m - 1$ , but TQM doesn’t know which bottle contains poison. These n mice are numbered from $0$ to $n - 1$ . If a mouse drinks poison, it will die, otherwise, nothing will happen.

Now you need to give TQM an experimental plan to help her find out the poison.

Interaction Protocol

First you should read two integers from standard input (separated by
space), stand for $n, m$

Next you should set your plan by writting groups of data to standard output. A group is a pair of integer like %m %b, %m is the mouse number and %b is the bottle number, means the NO.%m mouse will drink NO.%b bottle. Each group should be separated by ‘ ’. To finish your plan, print ‘-1 -1 ’ to standard output, do not forget to flush the buffer of output.

Then you can read $n$ space-separated integer from standard input, stand for the status of mice. 0 means alive, 1 means died

Finally you should print a single number with ‘ ’ stands for the answer (the number of bottle contains poison)

It is ensure that there is a reasonable plan to find the poison bottle number

Note

Please be aware of the speed of input and output!


//采用二进制，第i个老鼠和对应瓶子二进制第i位为1的瓶子。如果第i个老鼠死了，说明第i位为1的瓶子是有毒的。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,d,ans=0;
    cin>>n>>m;
    int mn=min(20,n);

    for(int i=0;i<mn;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(j&(1<<i))
                printf("%d %d
",i,j);
        }
    }
    printf("-1 -1
");
    fflush(stdout);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&d);
        if(d)
        {
            ans+=(1<<i);
        }
    }
    cout<<ans<<endl;
    return 0;
}

D. Who killed Cock Robin

一个简单的树形DP题。
DP状态转移方程式为： $d p [i] = \prod_{(j 是 i 的儿子节点)} (d p [j] + 1)$
ans= $\sum d p [i]$

#include <bits/stdc++.h>

using namespace std;
#define LL long long
const int MOD=1e7+7;
const int MAXN=2e5+5;

vector<int>tree[MAXN];
bool visit[MAXN];
int dp[MAXN];

int dfs(int root)
{
    LL tmp=1;
    visit[root]=true;
    for(vector<int>::iterator it=tree[root].begin();it!=tree[root].end();it++)
    {
        int to=*it;
        if(visit[to])
        {
            continue;
        }
        dfs(to);
        tmp=(tmp*(dp[to]+1))%MOD;
    }
    dp[root]=tmp%MOD;
    return 0;
}

int main()
{
    int n;
    cin>>n;
    int head,tail;
    for(int i=0;i<n-1;i++)
    {
        cin>>head>>tail;
        tree[head].push_back(tail);
        tree[tail].push_back(head);
    }
    dfs(1);
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=dp[i];
        ans%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

F. Flower Road

设计好旋转操作，然后最短路的状态转移为：

d p [i] [j] = m a x (d p [i] [j], m a x (d p [i - 1] [j] + a [i] [j], d p [i] [j - 1] + a [i] [j]))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1505;
int a[N][N],n;
ll dp[N][N];
ll DP()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dp[i][j]=max(dp[i][j],max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]));
    return dp[n][n];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>a[i][j];
    while(m--)
    {
        int xi,yi,li;
        cin>>xi>>yi>>li;
        for(int i=0; i<li; i++)
            for(int j=0; j<li; j++)
            {
                int t=a[xi+i][yi+j];
                a[xi+i][yi+j]=a[xi+li+i][yi+j];
                a[xi+li+i][yi+j]=a[xi+li+i][yi+li+j];
                a[xi+li+i][yi+li+j]=a[xi+i][yi+j+li];
                a[xi+i][yi+j+li]=t;
            }
    }
    cout<<DP();
    return 0;
}

H. GSS and Simple Math Problem

现场赛的时候JAVA卡了MLE，搞了好久，搞崩了ORZ。现在JAVA跟python都能过

n=int(input())
sum=1
for i in range(n):
    a=int(input())
    sum*=a
print(sum)

I. Five Day Couple

01字典树处理，变化是增加了区间范围：

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn = 1e5 + 10;
int head[maxn],son[maxn*31][2],num[maxn*31][2]; // 一个数为30位，再加上一位头节点，最多为 31 位，所以乘上31
int n,m,x,a[35],l,r,sz = 0;
void add(int now,int be,int pos){ // now 表示当前时间的 ，be 表示上一个时间
    if(pos>30) return;
    int val = a[pos];
    son[now][val] = ++sz;
    num[now][val] = num[be][val] + 1; // 当前的个数 = 之前的个数 + 1
    if(num[be][val^1]>0){ //在之前另一边有子树，加入当前树
        son[now][val^1] = son[be][val^1];
        num[now][val^1] = num[be][val^1];
    }
    add(sz, son[be][val], pos+1);
}

void query(int L,int R,int pos){
    if(pos>30) return;
    int val = a[pos]^1; // 将01互换
    if(num[R][val]-num[L][val]>0){ // 说明在所给区间里有和该位相反的数
        //判断下一位
        query(son[L][val], son[R][val], pos+1);
        a[pos] = 1; //所以取这个数，它们异或的结果为1
    }else{
        // 区间内不存在与该位相反的数
        query(son[L][a[pos]], son[R][a[pos]], pos+1);
        a[pos] = 0;
    }
}
void get(){
    for(int j=30;j>=1;j--){
        a[j] = x % 2; x /= 2;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        get(); // 得到x的二进制的每一位数 存入数组中
        head[i] = ++sz; // 建立第i个‘时间’的头节点
        add(sz,head[i-1],1); // 在第‘i-1’个时间的基础上，插入该数
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&l,&r);
        get();
        query(head[l-1],head[r],1);
        x = 0;
        for(int j=1;j<=30;j++) x = x * 2 + a[j];
        printf("%d
",x);
    }
    return 0;
}