HHU寒假集训第一周题解

**训练地址：**[HHU2019寒假第一周][1]
**密码：** `HHU201901`

## A. collect more jewels (hdu 1044) #bfs&dfs

暂未通过。

## B. To the max (hdu 1081) #暴力 #前缀和 #dp

题意：找到题目所给的矩阵最大子矩阵和。
因为题目所给的数据比较小，所以我们可以用 O($$^?$) 的算法通过这个题目。
写法主要就是先通过存一行或者一列的前缀和，之后再暴力枚举所截取的行（列）宽，每次枚举一个宽度就可以对这些做一次最大连续子序列和，之后取 Max 就可以得到答案了。

代码：

## C. 排序 (hdu 1106, hhuoj1349) #字符串 #排序

这题刚出来的时候觉得很熟悉，自己去 hhuoj 翻了一下，发现这题果然写过，出题重复了确实有点小尴尬。
这题也是签到题，思路很简单，只要把数字分隔好了，再 `sort` 排个序就 OK 了。
（话说用 multiset 也能写，逃）

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
#define connect(a,b) a##b
#define tostring(a) #a
using namespace std;
//ios::sync_with_stdio(false);
const int INF = 0x7fffffff;
const int E5 = 1e5+5;
typedef long long ll;
ll num[10001],cnt=0;
void init()
{
    memset(num,0,sizeof num);
    cnt=0;
}
void tonum(char * in)
{
    ll ans=0,len=strlen(in);
    for(int i = 0;i < len&&isdigit(in[i]);i++){
        ans*=10;
        ans+=in[i]-'0';
    }
    num[cnt++]=ans;
}
void spilt(char * in,char sp)
{
    char get[28];
    bool ch = false;
    int idx=0;
    int len = strlen(in);
    for(int i = 0;i < len;i++){
        //printf("now judge %c\n",in[i]);
        if(in[i]==sp) {idx=0;if(ch) {ch=false;tonum(get);memset(get,0,sizeof get);}continue;}
        else {ch=true;get[idx++]=in[i];}
    }
    if(ch) tonum(get);
}
char chi[1024];
int main()
{
    while(~scanf("%s",chi))
    {
        spilt(chi,'5');
        sort(num,num+cnt);
        for(int i = 0;i < cnt;i++){
            printf("%lld%c",num[i],i==cnt-1?'\n':' ');
        }
        init();
    }
    return 0;
}
```

## D. Rank of tetris (hdu 1811) #拓扑排序

这个算是一道拓扑排序的模板题，第一周的时候还学，之后这一周结束就补习了一下拓扑排序的知识。

## E. 亲和串 (hdu 2203) #字符串 #匹配

本场最简单的签到题（其实还是有一个坑的），题目所谓的循环移位解决方式也就是把 `s1` 串乘 2 再进行匹配，来达到一个循环的目的，很多的题目也是这样做的，这是一个常见的解题方式。
坑点：`s1:A  s2:AA`

## F. 数学题（矩阵快速幂）

这部分代码内容较长，保留核心实现：

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
typedef long long ll;
using namespace std;
const int mod=123456789;
int n,a,b,c,Mod;
struct Mat{
    ll a[3][3]={{0,1,1},{1,0,0},{0,0,1}};
}e,k;
Mat Mul(Mat a,Mat b,ll md)
{
    Mat c;
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            c.a[i][j]=0;
        }
    }
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            for(int k = 0;k < 3;k++){
                c.a[i][j]=c.a[i][j]%md+a.a[i][k]*b.a[k][j]%md;
                c.a[i][j]%=md;
            }
        }
    }
    return c;
}
Mat qpow(Mat a,ll p,ll md)
{
    Mat ans=k;
    while(p)
    {
        if(p&1) ans=Mul(ans,a,md);
        a=Mul(a,a,md);
        p>>=1;
    }
    return ans;
}
ll qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans*=a;
        ans%=p;
        a*=a;
        a%=p;
        b>>=1;
        //printf("now ans = %lld\n",ans);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            if(i==j) k.a[i][i]=1;
            else k.a[i][j]=0;
        }
    }
    while(t--)
    {
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&Mod);
        memset(e.a,0,sizeof e.a);
        e.a[0][0]=c;
        e.a[0][3]=1;
        e.a[0][2]=1;
        e.a[1][0]=1;
        e.a[2][2]=1;
        ll d=qpow(a,b,Mod);
        if(n==1) puts("1");
        else if(n==2) printf("%lld\n",d);
        else if(a%Mod==0) puts("0");
        else{
            ll md2=Mod-1;
            //printf("md2 =  %lld\n",md2);
            e=qpow(e,n-2,md2);
            ll pw=e.a[0][0]+e.a[0][2];
            //cout << "pw==" << pw << endl;
            //printf("e= %lld %lld %lld\n",e.a[0][0],e.a[0][4],e.a[0][2]);
            pw%=md2;
            //printf("%lld  %lld %lld\n",d,pw,Mod);
            ll ans=qpow(d,pw,Mod);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
```

## G. Special Tetrahedron (hdu 5839) #计算几何 #暴力

题意：
给你 n 个三维空间的点，问这些点可以构成多少个特殊四面体。
特殊四面体的定义如下：
1. 有四条长度相同的边
2. 如果它仅有四条相同的边，那么它剩余的两条边不相邻

题解：
因为每组的点数只有最多 200 个，所以我们可以采取一些比较暴力的算法：
暴力枚举每两个点的组合，再通过计算出剩余的点中到这两个点距离相同的点，然后在数组里面挑选符合条件的组合。
注意判断一下正四面体和四点在同一平面的情况。

代码：

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
using namespace std;
//ios::sync_with_stdio(false);
const int MINF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int Maxn = 1e5+5;
typedef long long ll;
struct Point{
    int x,y,z;
    void input()
    {
        scanf("%d%d%d",&x,&y,&z);
    }
}pt[233];
int dis(Point a,Point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
Point xmult(Point u,Point v){
    Point ret;
    ret.x=u.y*v.z-v.y*u.z;
    ret.y=u.z*v.x-u.x*v.z;
    ret.z=u.x*v.y-u.y*v.x;
    return ret;
}
int dmult(Point u,Point v)
{
    return u.x*v.x+u.y*v.y+u.z*v.z;
}
Point subt(Point u,Point v)
{
    Point ret;
    ret.x=u.x-v.x;
    ret.y=u.y-v.y;
    ret.z=u.z-v.z;
    return ret;
}
Point pvec(Point s1,Point s2,Point s3)
{
    return xmult(subt(s1,s2),subt(s2,s3));
}
bool dots_onplane(Point a,Point b,Point c,Point d)
{
    return dmult(pvec(a,b,c),subt(d,a));
}
int main()
{
    //cout << dots_onplane({0,0,0},{0,1,0},{1,0,0},{1,1,0}) << endl;
    int t,tp;
    scanf("%d",&t);
    tp=t;
    while(t--)
    {
        int n,ct1=0,ct2=0;
        scanf("%d",&n);
        for(int i = 0;i < n;i++) pt[i].input();
        for(int i = 0;i < n-1;i++){
            for(int j = i+1;j < n;j++){
                int cnt[202],index=0;
                for(int k = 0;k < n;k++){
                    if(k==i||k==j) continue;
                    if(dis(pt[i],pt[k])==dis(pt[j],pt[k])) cnt[index++]=k;
                }
                if(index>1){
                    for(int p = 0;p < index-1;p++){
                        for(int q= p+1;q < index;q++){
                            if(dis(pt[cnt[p]],pt[i])!=dis(pt[cnt[q]],pt[i])) continue;
                            else if(!dots_onplane(pt[i],pt[j],pt[cnt[p]],pt[cnt[q]])) continue;
                            else if((dis(pt[i],pt[j])==dis(pt[i],pt[cnt[q]]))&&(dis(pt[i],pt[j])==dis(pt[cnt[p]],pt[cnt[q]]))) ct1++;
                            else ct2++;
                        }
                    }
                }
            }
        }
        printf("Case #%d: %d\n",tp-t,ct1/6+ct2/2);
    }
    return 0;
}
```

[1]: https://vjudge.net/contest/280338
[2]: https://hodam.top/myfile/image/euler.png
[3]: https://hodam.top/myfile/image/euler.png
[4]: https://hodam.top/myfile/image/euler.png

**训练地址：**[HHU2019寒假第一周][1]
**密码：** `HHU201901`

## A. collect more jewels (hdu 1044) #bfs&dfs

暂未通过。

## B. To the max (hdu 1081) #暴力 #前缀和 #dp

代码：

## C. 排序 (hdu 1106, hhuoj1349) #字符串 #排序

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
#define connect(a,b) a##b
#define tostring(a) #a
using namespace std;
//ios::sync_with_stdio(false);
const int INF = 0x7fffffff;
const int E5 = 1e5+5;
typedef long long ll;
ll num[10001],cnt=0;
void init()
{
    memset(num,0,sizeof num);
    cnt=0;
}
void tonum(char * in)
{
    ll ans=0,len=strlen(in);
    for(int i = 0;i < len&&isdigit(in[i]);i++){
        ans*=10;
        ans+=in[i]-'0';
    }
    num[cnt++]=ans;
}
void spilt(char * in,char sp)
{
    char get[28];
    bool ch = false;
    int idx=0;
    int len = strlen(in);
    for(int i = 0;i < len;i++){
        //printf("now judge %c\n",in[i]);
        if(in[i]==sp) {idx=0;if(ch) {ch=false;tonum(get);memset(get,0,sizeof get);}continue;}
        else {ch=true;get[idx++]=in[i];}
    }
    if(ch) tonum(get);
}
char chi[1024];
int main()
{
    while(~scanf("%s",chi))
    {
        spilt(chi,'5');
        sort(num,num+cnt);
        for(int i = 0;i < cnt;i++){
            printf("%lld%c",num[i],i==cnt-1?'\n':' ');
        }
        init();
    }
    return 0;
}
```

## D. Rank of tetris (hdu 1811) #拓扑排序

这个算是一道拓扑排序的模板题，第一周的时候还学，之后这一周结束就补习了一下拓扑排序的知识。

## E. 亲和串 (hdu 2203) #字符串 #匹配

## F. 数学题（矩阵快速幂）

这部分代码内容较长，保留核心实现：

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
typedef long long ll;
using namespace std;
const int mod=123456789;
int n,a,b,c,Mod;
struct Mat{
    ll a[3][3]={{0,1,1},{1,0,0},{0,0,1}};
}e,k;
Mat Mul(Mat a,Mat b,ll md)
{
    Mat c;
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            c.a[i][j]=0;
        }
    }
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            for(int k = 0;k < 3;k++){
                c.a[i][j]=c.a[i][j]%md+a.a[i][k]*b.a[k][j]%md;
                c.a[i][j]%=md;
            }
        }
    }
    return c;
}
Mat qpow(Mat a,ll p,ll md)
{
    Mat ans=k;
    while(p)
    {
        if(p&1) ans=Mul(ans,a,md);
        a=Mul(a,a,md);
        p>>=1;
    }
    return ans;
}
ll qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans*=a;
        ans%=p;
        a*=a;
        a%=p;
        b>>=1;
        //printf("now ans = %lld\n",ans);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            if(i==j) k.a[i][i]=1;
            else k.a[i][j]=0;
        }
    }
    while(t--)
    {
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&Mod);
        memset(e.a,0,sizeof e.a);
        e.a[0][0]=c;
        e.a[0][3]=1;
        e.a[0][2]=1;
        e.a[1][0]=1;
        e.a[2][2]=1;
        ll d=qpow(a,b,Mod);
        if(n==1) puts("1");
        else if(n==2) printf("%lld\n",d);
        else if(a%Mod==0) puts("0");
        else{
            ll md2=Mod-1;
            //printf("md2 =  %lld\n",md2);
            e=qpow(e,n-2,md2);
            ll pw=e.a[0][0]+e.a[0][2];
            //cout << "pw==" << pw << endl;
            //printf("e= %lld %lld %lld\n",e.a[0][0],e.a[0][4],e.a[0][2]);
            pw%=md2;
            //printf("%lld  %lld %lld\n",d,pw,Mod);
            ll ans=qpow(d,pw,Mod);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
```

## G. Special Tetrahedron (hdu 5839) #计算几何 #暴力

代码：

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
using namespace std;
//ios::sync_with_stdio(false);
const int MINF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int Maxn = 1e5+5;
typedef long long ll;
struct Point{
    int x,y,z;
    void input()
    {
        scanf("%d%d%d",&x,&y,&z);
    }
}pt[233];
int dis(Point a,Point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
Point xmult(Point u,Point v){
    Point ret;
    ret.x=u.y*v.z-v.y*u.z;
    ret.y=u.z*v.x-u.x*v.z;
    ret.z=u.x*v.y-u.y*v.x;
    return ret;
}
int dmult(Point u,Point v)
{
    return u.x*v.x+u.y*v.y+u.z*v.z;
}
Point subt(Point u,Point v)
{
    Point ret;
    ret.x=u.x-v.x;
    ret.y=u.y-v.y;
    ret.z=u.z-v.z;
    return ret;
}
Point pvec(Point s1,Point s2,Point s3)
{
    return xmult(subt(s1,s2),subt(s2,s3));
}
bool dots_onplane(Point a,Point b,Point c,Point d)
{
    return dmult(pvec(a,b,c),subt(d,a));
}
int main()
{
    //cout << dots_onplane({0,0,0},{0,1,0},{1,0,0},{1,1,0}) << endl;
    int t,tp;
    scanf("%d",&t);
    tp=t;
    while(t--)
    {
        int n,ct1=0,ct2=0;
        scanf("%d",&n);
        for(int i = 0;i < n;i++) pt[i].input();
        for(int i = 0;i < n-1;i++){
            for(int j = i+1;j < n;j++){
                int cnt[202],index=0;
                for(int k = 0;k < n;k++){
                    if(k==i||k==j) continue;
                    if(dis(pt[i],pt[k])==dis(pt[j],pt[k])) cnt[index++]=k;
                }
                if(index>1){
                    for(int p = 0;p < index-1;p++){
                        for(int q= p+1;q < index;q++){
                            if(dis(pt[cnt[p]],pt[i])!=dis(pt[cnt[q]],pt[i])) continue;
                            else if(!dots_onplane(pt[i],pt[j],pt[cnt[p]],pt[cnt[q]])) continue;
                            else if((dis(pt[i],pt[j])==dis(pt[i],pt[cnt[q]]))&&(dis(pt[i],pt[j])==dis(pt[cnt[p]],pt[cnt[q]]))) ct1++;
                            else ct2++;
                        }
                    }
                }
            }
        }
        printf("Case #%d: %d\n",tp-t,ct1/6+ct2/2);
    }
    return 0;
}
```

[1]: https://vjudge.net/contest/280338
[2]: https://hodam.top/myfile/image/euler.png
[3]: https://hodam.top/myfile/image/euler.png
[4]: https://hodam.top/myfile/image/euler.png

Last modification：March 1, 2019

如果觉得我的文章对你有用，请随意赞赏

HHU寒假集训第一周题解

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

hhuoj 1300-1309题解/oj入门教程

广东工业大学第十四届程序设计竞赛题解

14讲二叉排序树习题解析

博客搭建全过程

shadowsocks安装教程(重置版)

HHU寒假集训第二周题解

快速幂/快速乘(取模)

hhuoj1310

程序设计方法学作业#1

13讲字典的顺序表示与散列表示习题解析

HHU寒假集训第一周题解

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

HHU寒假集训第一周题解

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款