文章目录
  1. 1. B - 排序 HDU - 1106
    1. 1.1. 有趣的解法
    2. 1.2. 有趣的解法2
  2. 2. G - Special sort HDU - 3877
  3. 3. H - 确定比赛名次 HDU - 1285
  4. 4. I - 前m大的数 HDU - 1280
  5. 5. J - K.Bro Sorting HDU - 5122
    1. 5.1. 类似堆排序思想

引言:前面的还没补,排序又来了。本文B题将介绍几个有趣的做法,还有一个一直很想学的拓扑排序。


B - 排序 HDU - 1106

有趣的解法

  • 看到这个题我就想到了之前写工程的时候用的strtok函数了,然而之前只用过一次,对这个函数的用法忘掉了,所以这道题也卡了不少时间。如果熟悉这个函数,这道题3分钟就能码出来。

  • 函数原型:

    • char *strtok(char *strToken, const char *strDelimit);

    • 参数

      strToken
      待分割字符串,填NULL默认为上次分割时剩余的字符串。

      strDelimit
      分割字符。

    • 返回值

      函数将strToken分割为分组A分割字符分组B返回一个指向分组A的指针。 无法分割时返回NULL。 每次调用均会修改strToken为分组B。

  • 上述内容摘自msdn并进行了修改解读。理解它你需要看这道题并对比我的代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #define _CRT_SECURE_NO_WARNINGS
    #pragma comment (linker,"/STACK:102400000,102400000")
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cctype>
    #include<cstring>
    #include<algorithm>
    typedef long long ll;
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MOD (ll)(1e9+7)
    char str[1010];
    int a[1010];
    int func(char *str)
    {
    char *p=str;
    int ret=0;
    while(*p)
    {
    ret=ret*10+*p-'0';
    p++;
    }
    return ret;
    }
    int main(void)
    {
    while(scanf("%s",str)==1)
    {
    int cnt=0;
    char *p=strtok(str,"5");
    while(p)
    {
    a[cnt++]=func(p);
    p=strtok(NULL,"5");
    }
    sort(a,a+cnt);
    for(int i=0;i<cnt;i++)
    printf(i==0?"%d":" %d",a[i]);
    putchar('\n');
    }
    return 0;
    }

有趣的解法2

  • 果然梁神也很吊的啊,教了我一个stringstream函数。

  • stringstream函数原型太恶心了,不学了,了解一下普通用法吧。

  • 用法:stringstream 流名称(用来初始化流的字符串)

  • 然后就可以把它当成流来用了。举个栗子,本题:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    //关键代码
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<sstream>
    using namespace std;
    int main(void)
    {
    string str;
    cin>>str;
    for(int i=0;i<str.length();i++)
    if(str[i]=='5')str[i]=' ';
    stringstream ss(str);
    int num;
    vector<int> vec;
    while(ss>>num)
    vec.push_back(num);
    sort(vec.begin(),vec.end());
    for(int i=0;i<vec.size();i++)
    printf(!i?"%d":" %d",vec[i]);
    putchar('\n');
    return 0;
    }

G - Special sort HDU - 3877

  • 这道题就get到一个点,stable_sort挺好使的。

H - 确定比赛名次 HDU - 1285

  • (摩拳擦掌)H题是一道拓扑排序(流口水)。

  • 拓扑排序就是说,一开始将所有入度为0的点入队,它们肯定是名次最靠后的,如果它们有多个,就说明不确定他们之间的名次(可以自己举例推着理解一下)。然后将他们的所指的点的入度减少一,就相当于把他们这些点及它连的边都去掉。然后再把所有入度为0的点入队,以此类推直到排好。

  • 邻接矩阵版:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #define _CRT_SECURE_NO_WARNINGS
    #pragma comment (linker,"/STACK:102400000,102400000")
    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<cstdlib>
    #include<cctype>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<ctime>
    typedef long long ll;
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MOD (ll)(1e9+7)
    inline int read()
    {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
    while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
    return a*f;
    }
    inline ll read2()
    {
    ll a=0, f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
    while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
    return a*f;
    }
    int in[510];
    bool MAP[510][510];
    int N,M;
    void topo()
    {
    priority_queue<int,vector<int>,greater<int> > q;
    for (int i = 1; i <= N; i++)
    {
    if (in[i] == 0)
    {
    q.push(i);
    }
    }
    int cnt=0;
    int temp;
    while (!q.empty())
    {
    temp = q.top();
    q.pop();
    printf(!cnt++?"%d":" %d",temp);
    for (int i = 1; i <= N; i++)
    {
    if (MAP[temp][i])
    {
    in[i]--;
    if (!in[i])
    q.push(i);
    }
    }
    }
    }
    int main(void)
    {
    while(scanf("%d %d",&N,&M)==2)
    {
    memset(in,0,sizeof(in));
    memset(MAP,0,sizeof(MAP));
    for(int i=0;i<M;i++)
    {
    int P1=read(),P2=read();
    if(MAP[P2][P1])
    continue;
    in[P1]++;
    MAP[P2][P1]=1;
    }
    topo();
    putchar('\n');
    }
    }

I - 前m大的数 HDU - 1280

  • 这道题虽然很简单,但如果题目改一下,压一下空间,那就得用这个很妙的想法了。
  • 找到两两相加最大的M个数,其中M<=1000,那铁定是大加大才大啊,只需要找到前100个数两两相加存起来,排个序就好了。

J - K.Bro Sorting HDU - 5122

类似堆排序思想

  • 这道题很类似堆排序。从堆顶往下,比父亲大的就交换上去,直到交换到比父亲小的位置,从堆顶一直往下这么走,完成排序。
  • 知道这样一个排序思想之后,模拟一遍,最右肯定是堆顶了,我们从右往左扫。

573218945732189457321849573214895732148957312489571234895123478912345789\begin{matrix} 5&7&3&2&1&8&9&\color{blue}4\\ 5&7&3&2&1&8&\color{blue}9&4\\ 5&7&3&2&1&\color{blue}8&4&\color{lightgreen}9\\ 5&7&3&2&\color{blue}1&4&\color{lightgreen}8&9\\ 5&7&3&\color{blue}2&1&4&8&9\\ 5&7&\color{blue}3&1&\color{lightgreen}2&4&8&9\\ 5&\color{blue}7&1&2&\color{lightgreen}3&4&8&9\\ \color{blue}5&1&2&3&4&\color{lightgreen}7&8&9\\ 1&2&3&4&\color{lightgreen}5&7&8&9 \end{matrix}

可以看到一开始9、8换了一轮,到1就不换了,是因为1比它父亲它爷爷它祖宗都小,上不了位啊,所以从右往左扫的过程中每次记录所遇到的最小值,当最小值不更新就cnt++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)
inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
inline ll read2()
{
ll a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
int a[1000010];
int main(void)
{
int T=read();
int k=0;
while(T--)
{
int n=read();
int cnt=0;
for(int i=0;i<n;i++)
{
a[i]=read();
}
int minx=a[n-1];
for(int i=n-2;i>=0;i--)
{
if(a[i]>minx)
cnt++;
else
minx=a[i];
}
printf("Case #%d: %d\n",++k,cnt);
}
}
文章目录
  1. 1. B - 排序 HDU - 1106
    1. 1.1. 有趣的解法
    2. 1.2. 有趣的解法2
  2. 2. G - Special sort HDU - 3877
  3. 3. H - 确定比赛名次 HDU - 1285
  4. 4. I - 前m大的数 HDU - 1280
  5. 5. J - K.Bro Sorting HDU - 5122
    1. 5.1. 类似堆排序思想