快手笔试

# 第一题

给一个射线以及一个长方体，判断是否相交

思路：口胡的，具体原理说不清

当然，可以直接骗分，全输出0，得40%,全输出1，得60%

#include<iostream>
using namespace std;
double dirx,diry,dirz;
double poix,poiy,poiz;
double recxl,recyl,reczl;
double recxr,recyr,reczr;
void in(){
    cin>>dirx>>diry>>dirz;
    cin>>poix>>poiy>>poiz;
    cin>>recxl>>recyl>>reczl;
    cin>>recxr>>recyr>>reczr;
}
bool solve(){
    if(dirx<0 && recxl>=poix)  return false;
    if(diry<0 && recyl>=poiy)  return false;
    if(dirz<0 && reczl>=poiz)  return false;
    if(dirx>0 && recxr<=poix)  return false;
    if(diry>0 && recyr<=poiy)  return false;
    if(dirz>0 && reczr<=poiz)  return false;
    if(dirx==0 || diry==0 || dirz==0)  return false;
    return true;
}
int main(){
    in();
    if(solve())  cout<<1<<"\n";
    else  cout<<0<<"\n";
    return 0;
}

# 第二题

一个三角形，从上往下走到底，求路径最大值，规定只能往下走或往右斜走

思路：动态规划，

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+val[i][j]; 
其中i,j分别表示点的坐标，dp[i][j]就表示到此点的最大路径值，val[i][j]为此点的值

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=33;
int n;
int val[33][33];
int dp[33][33];
void solve(){
    int ans=0;
    dp[1][1]=val[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(j==1){
                dp[i][j]=dp[i-1][j]+val[i][j];
            }
            else if(j==i){
                dp[i][j]=dp[i-1][j-1]+val[i][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+val[i][j];
            }
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    //有没有负数
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>val[i][j];
        }
    }
    solve();
    return 0;
}

# 第三题

一个无环连通图，每个点最多与3个点相连，对于a点，将a点去掉后，图将分为1~3部分，那么a点的重要度就=各部分点的数量的乘积

思路：可以看做一个二叉树，那么对于点a，可以分为3部分，左子树x、右子树y、剩下的z。

z可以通过n-x-y-1来求

所以我们只需要求出其左子树x就可以了（右子树同理）

那么我们采用递归的思想，公式为：子树x=x的左子树+x的右子树+1（x自身）

#include<iostream>
using namespace std;
typedef long long ll;
const ll maxn=1e6;
const ll maxm=1e6;
ll n,cnt=1,ans=0,ans_cnt=0;
ll head[maxn],nex[maxm],to[maxm];
void add(ll x,ll y){
    nex[++cnt]=head[x];
    to[cnt]=y;
    head[x]=cnt;
}
void in(){
    cin>>n;
    for(ll i=0;i<n-1;i++){
        ll a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
}
ll dfs(ll x,ll fa){
    ll sum=1;
    ll res=1;
    for(ll i=head[x];i!=0;i=nex[i]){
        if(to[i]!=fa){
            ll ttt=dfs(to[i],x);
            res=res*ttt;
            sum+=ttt;
        }
    }
    if(fa!=-1)  res=res*(n-sum);
//     cout<<res<<endl;
    if(res==ans){
        ans_cnt++;
    }
    if(res>ans){
        ans=res;
        ans_cnt=1;
    }
    
    return sum;
}

int main(){
    in();
    dfs(0,-1);
    cout<<ans_cnt<<" "<<ans%1000000007<<"\n";
    return 0;
}

#快手笔试#