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

第一次组队打比赛，不过也基本是各想各的..比赛难度比较大，如果单凭自己实力撑死A三题，全英文题面读题实在太累了，在卡题的状态下开新题非常艰难

A. Srdce and Triangle

如图，D是正三角形ABC内任意一点,连接DC,DA,DB。已知三个角CDB,BDA,ADC,求问若三条边DA,DB,DC能组成三角形，这个三角形的三个角的大小。若不能，则输出-1.

以AD为边做正三角形PAD，连结PA,PC,PD。 可以证明三角形APC和三角形ADB全等。所以三角形PDC就是以DA,DB,DC三条边组成的三角形。易得三个角都为原角度减去60度

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    double a[3];
    while(cin >>a[0] >> a[1] >> a[2]){
        sort(a, a+3);
        if(a[0]-60<1e-9){
            cout << -1 << " " << -1 << ' ' << -1 << endl;
        }
        else{
            printf("%.4f %.4f %.4f\n", a[0]-60, a[1]-60, a[2]-60);
        }
    }
}

吐槽下，这类题完全不知道怎么解..当时是场外谜之声提示的..

D. Who killed Cock Robin

给出n个数，它们之间有n-1条边形成一个树形结构，求它的连通子图有多少个，结果mod 1e10+7

这个题一看就是树形DP。分析可得以5,6,7节点为根的连通子图只有它们本身。以2为根的连通子图有2,5,6,2-5,2-6,5-2-6
六种，这是根据乘法定理得到的。假设以2，3，4为根的连通子图分别为A,B,C。那么以1为根的连通子图就有1+A+B+C+AB+AC+BC+ABC种。这很好理解(比赛的时候我想出来了)
但是我竟然没有得出算这个的公式……数感太差了
这里给出公式(A+1)(B+1)(C+1) = 1+A+B+C+AB+AC+BC+ABC
很显然就是取与不取的问题。如果2，3，4节点都不取，那么以1为根的子图只有它本身一种。如果都取就有ABC种。

这是我遇到的第一个问题，还有一个问题是题目的输入是随意给出两个点的连接..所以我不知道根在哪里，所以没想好怎么dfs，我本来想先找到根再往下dfs的…但是！我发现不管是从哪个点为根，都是可以组成一棵树的orz 所以随便找一个节点作为根往下dfs就行了…

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn = 200000 + 10;
const int modd = 10000007;
vector<int> mat[maxn];
LL sum = 0;
LL dfs(int node,int pre)
{
  LL ans = 1;
  for(int i=0;i<mat[node].size();i++)
  {
    if(mat[node][i] == pre) continue;
    ans = ans * (dfs(mat[node][i],node) + 1);
    ans %= modd;
  }
  sum += ans;
  sum %= modd;
  return ans;
}

int main()
{
  int n,a,b;
  cin >> n;
  for(int i=1;i<n;i++)
  {
    cin >> a >> b;
    mat[a].push_back(b);
    mat[b].push_back(a);
  }
  dfs(1,-1);
  cout << sum % modd << endl;
}

F. Flower Road

这题不知道为什么过的人很少，我以为是一道很难的题，队友说这就是个简单的DP，看了一下过了。但是这反映出了一个很大的问题，就是英文题面下真的很难照顾到所有题目..一大半的题连读都没读过。

题意是给出一个边长为n的方阵，然后对这个矩阵进行m次操作。每次操作输入一个坐标和一个长度值，然后对方阵的部分进行顺时针旋转。如图就是输入1 1 2后得到的结果。
m次操作完毕后，求从(1,1)到(n,n)最大的数字之和。
非常简单啊，旋转的过程注意一下细节就行了
求最大和用DP DP[i][j] = max(dp[i][j+1],dp[i+1][j]) + mat[i][j] //mat[i][j]指这个方阵的值注意一下边界情况

H. GSS and Simple Math Problem

求累乘，大数签到题..唯一一道我秒杀的题…

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner
public class Main {
public static void main(String agrs[]){
   Long n;
   BigInteger a,ans;
   ans = BigInteger.valueOf(1);
   Scanner scan = new Scanner(System.in);
   n = scan.nextLong();
   for(int i=0;i<n;i++)
   {
       a = scan.nextBigInteger();
       ans = ans.multiply(a);
   }
   System.out.println(ans);
 }
}

I. Five Day Couple

这道题是给出长度为n的一个数列，然后进行m次询问。每次询问给出数列的区间和一个数bi,求bi在这个区间内异或的最大值。
这道题暴力复杂度是O(nm)，被最后一组数据卡掉了…
看题解要用到01字典树，有想法但是这东西还没有认真学过。主要是还没搞明白怎么建树..留坑吧。