文章目录
  1. 1. A - 水陆距离 HihoCoder - 1478
  2. 2. D - 4个数和为0 51Nod - 1267
  3. 3. H - 抽彩球 51Nod - 1453
  4. 4. I - 斜率最大 51Nod - 1100
  5. 5. L - Ignatius and the Princess III HDU - 1028
  6. 6. M - CARDS POJ - 1721

引言:
2017 SHU 8.12 个人赛的部分题的总结。涉及BFS、夹逼思想、组合数、DP、置换群等算法思想,总体难度不高(只是我不会而已)。

  • A - 水陆距离
  • D - 4个数和为0
  • H - 抽彩球
  • I - 斜率最大
  • L - Ignatius and the Princess III
  • M - CARDS

A - 水陆距离 HihoCoder - 1478

只要做过Fire那道题,这道题就是个签到题。

还是要注意,BFS有很多需要注意的点,这里还是将它们总结一下吧。

  1. 在读入数据的时候,建议外层函数为i,代表行数;内层函数为j,代表列数。将所有数组读入时关于ij的写作 数组[i][j],而关于xy的写作 数组[y][x],如此便不会混淆。口诀:ijijyxyx
  2. 为了避免混乱,我喜欢将vis单独开一个数组,而不是将其和step数组合并。也就是说开maze、step和vis三个数组,分别存地图、步数、是否已走过。
  3. 像这种读入格式里面没空格的,可以用scanf("%1d")读入。或者就用char数组存放。

废话不多说了,这道题其实就是一开始将所有的水池都push到队列里,然后开始BFS存放步数就好了。

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
82
83
84
85
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#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;
}
int n,m;
int nx[]={0,-1,0,1};
int ny[]={1,0,-1,0};
char maze[810][810];
int vis[810][810];
int step[810][810];
struct coo
{
int x,y,step;
};
queue<coo> q;
void bfs()
{
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
while(!q.empty())
{
coo nq=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=nq.x+nx[i],y=nq.y+ny[i];
if(vis[y][x] || maze[y][x]=='0' || x>=m || x<0 || y>=n || y<0)
continue;
vis[y][x]=1;
step[y][x]=nq.step+1;
q.push(coo{x,y,nq.step+1});
}
}
}
int main(void)
{

while(scanf("%d %d",&n,&m)==2)
{
getchar();
if(!q.empty())
q.pop();
for(int i=0;i<n;i++)
{
gets(maze[i]);
for(int j=0;j<m;j++)
{
if(maze[i][j]=='0')
{
q.push(coo{j,i,0});
vis[i][j]=1;
}
}
}
bfs();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf(!j?"%d":" %d",step[i][j]);
putchar('\n');
}

}
return 0;
}

D - 4个数和为0 51Nod - 1267

  • 这道题网上很多人说是二分,瞎说的吧,二分长这样?好吧二分还跟它真的像,但我担保不是二分。我叫它夹逼思想。

  • 解题思路:看数据范围,O(n4)O(n^4)的直观做法肯定是会TLE的,我们最多考虑O(n3)O(n^3)

    首先我们将读入数组从小到大排序,选两个数iijj,确保j>ij>i,这是O(n2)O(n^2)的,然后我们设sum=a[i]+a[j]sum=a[i]+a[j],令l=j+1l=j+1r=n1r=n-1,也就是说从jj的右一位到数组末开始找第三个和第四个数,由于排过序了,这样的a[l]a[l]a[r]a[r]肯定是我们要找的范围内的最小和最大的数。如果a[l]+a[r]+sum==0a[l]+a[r]+sum==0,则llrr恰好是我们要找的数,如果a[l]+a[r]+sum<0a[l]+a[r]+sum<0,说明a[l]a[l]小了,我们让ll++,为什么不让rr++呢?因为rr已经最大了,没办法++了。同理,如果a[l]+a[r]+sum>0a[l]+a[r]+sum>0,我们让rr--。这是O(n)O(n)的。乘起来是O(n3)O(n^3),满足复杂度要求。

  • 验证算法的正确性:

    1. 从下标j+1j+1开始夹逼,不会漏掉答案吗?为什么不从11开始夹逼?这个好想明白,我就不严格证明了,丢一个类比一下就知道了:如果暴力,则是jji+1i+1开始循环,kkj+1j+1开始循环,llk+1k+1开始循环,也就是说我已经假设了第二个数下标比第一个数大,第三个数下标比第二个数大,第四个数下标比第三个数大了。

    2. O(n)O(n)的夹逼思想是否正确?

      我们假设bbcc是第三个和第三个数的正确答案:

      a b\color{red}{b} c\color{red}{c} d
      l所在位置 r所在位置

      即有a[b]+a[c]+sum==0a[b]+a[c]+sum==0。我们要证明的是ll不可能大于bb,且rr不可能小于cc

      考虑当l==bl==br>cr>c时,必有a[l]+a[r]+sum>0a[l]+a[r]+sum>0,则r--直到触及正确答案。当r==cr==cl<bl<b时,必有a[l]+a[r]+sum<0a[l]+a[r]+sum<0,则l++l++直到触及正确答案。

  • AC代码:

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
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#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 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;
}
ll a[1010];
int main(void)
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++)
a[i]=read2();
sort(a,a+n);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
ll sum=a[i]+a[j];
int l=j+1,r=n-1;
while(l<r)
{
if(a[l]+a[r]+sum==0)
{
puts("Yes");
goto NEXT;
}
else if(a[l]+a[r]+sum<0)
l++;
else
r--;
}
}
puts("No");
NEXT:
continue;
}
return 0;
}

H - 抽彩球 51Nod - 1453

  • 这是一道组合数的题目,很有意思。样例的意思是从左到右拿球顺序,比如第一个方案拿球顺序是1 2 1 2 3.

  • 解题思路:

    “他的最后一个球总是在编号比他大的球拿完之前拿完”,什么叫拿完呢,就是说最后一个球被拿走了,那么题目就是说编号1的最后一个球肯定在编号2最后一个球的前面,编号2最后一个球肯定在编号3最后一个球的前面……只需要保证这个条件即可,其他都是自由的。但如何保证?

    比如样例吧,给了我5个球。让我放到5个盘子里,代表拿出顺序,1号盘子的球先拿。

    盘子1 盘子2 盘子3 盘子4 盘子5
    (空) (空) (空) (空) (空)

    首先我要满足“最后一个球”这个条件。那么我把所有的x编号的球都丢进去先,不就能考虑这个编号的最后一个球了吗?而按照推理,我肯定先放大编号的球,不然我咋保证小编号的在大编号的前面啊?

    好,先放编号3的,它只有一个,也是最后一个,它只能放到最后一个盘子里,不然肯定会有编号小的放到了最后的盘子 。再放编号2的,我要让其中一个编号2的球占据倒数第二个盘子,不然肯定会有编号比2小的放到了倒数第二个盘子,其他的随便排。

    也就是说,我每次都要让本编号的一个球放到尽可能靠右的盘子,以防被小编号的占了去,这就行了。

    那么影响情况数的,就是除了每个编号占盘子的那个球以外的其他球的排法。样例ans=1C401C311C11=3ans = 1 * C_4^0 * 1 * C_3^1 * 1 * C_1^1 = 3,答案用乘法逆元取模即可。

  • AC代码:

    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
    #define _CRT_SECURE_NO_WARNINGS
    #pragma comment (linker,"/STACK:102400000,102400000")
    #include<iostream>
    #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;
    }
    ll a[1010];
    ll jc[1010];
    void init()
    {
    jc[0]=jc[1]=1;
    for(ll i=2;i<1005;i++)
    jc[i]=jc[i-1]*i%MOD;
    }
    ll qpow(ll a,ll b,ll mod)
    {
    ll ret=1,base=a;
    while(b)
    {
    if(b&1)ret=ret*base%mod;
    base=base*base%mod;
    b>>=1;
    }
    return ret;
    }
    int main(void)
    {
    int n;
    init();
    while(scanf("%d",&n)==1)
    {
    int sum=0;
    for(int i=0;i<n;i++)
    {
    a[i]=read();
    sum+=a[i];
    }
    ll ans=1;
    for(int i=n-1;i>=0;i--)
    {
    ans=ans*jc[sum-1]%MOD*qpow(jc[a[i]-1],MOD-2,MOD)%MOD*qpow(jc[sum-a[i]],MOD-2,MOD)%MOD;
    sum-=a[i];
    }
    printf("%lld\n",ans);
    }
    return 0;
    }

    对了,上次我试的一道题费马小定理快速幂比辗转相除要快一点,但听说某个题辗转相除比快速幂快,所以如果类似题目TLE了可以换个乘法逆元的求法碰碰运气。

I - 斜率最大 51Nod - 1100

  • 这道题数据太小,怎么做都能过的,但我一开始O(n2)O(n^2)做法有个细节没搞对,一直WA在第十个数据,于是很不情愿的先怒刷了另外一道题回过头换了个O(nlogn)O(nlogn)的做法做这道。

  • 斜率最大的直线必定产生于xx坐标相邻的两点之间,这里不做证明,画图验证一下就知道了。那么我们将xx坐标进行排序,在两两之间计算斜率即可。

  • AC代码:

    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
    #define _CRT_SECURE_NO_WARNINGS
    #pragma comment (linker,"/STACK:102400000,102400000")
    #include<iostream>
    #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;
    }
    struct node
    {
    int x,y,index;
    }a[10010];
    int cmp(node t,node y)
    {
    return t.x<y.x;
    }
    int main(void)
    {
    int n;
    while(scanf("%d",&n)==1)
    {
    for(int i=0;i<n;i++)
    {
    a[i].x=read();
    a[i].y=read();
    a[i].index=i+1;
    }
    sort(a,a+n,cmp);
    double maxk=0;
    vector<node> vec;
    for(int i=1;i<n;i++)
    {
    double k=(a[i].y-a[i-1].y)/(a[i].x-a[i-1].x);
    if(k-maxk>1e-12)
    {
    maxk=k;
    vec.clear();
    vec.push_back(node{a[i-1].index,a[i].index});
    }
    else if(fabs(k-maxk)<1e-12)
    {
    vec.push_back(node{a[i-1].index,a[i].index});
    }
    }
    for(int i=0;i<vec.size();i++)
    printf("%d %d\n",vec[i].x,vec[i].y);

    }
    return 0;
    }

L - Ignatius and the Princess III HDU - 1028

  • 这道题是很经典的模型题。它可以转化为赤裸裸的mm个盘子里放nn个苹果有几种方法的问题,也可以转化为nn个小球mm个盒子,盒子可以为空,球相同,盒子相同,求有几种放法的球盒问题。

  • 先贴个递归版本:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    ll solve(ll m,ll n)//m个球放入n个盒子,球相同,盒子相同,盒子可以为空。模型还可以应用为拆数问题:http://acmoj.shu.edu.cn/contest/5/problem/24/
    {
    if(m<=1 || n<=1)
    return 1;
    if(m>=n)
    return solve(m-n,n)+solve(m,n-1);
    else
    return solve(m,m);
    }

    这个应该是可以转成记忆化递归的。

  • 然后是本题的DP做法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int dp[200][200];
    int solve(int m,int n)
    {
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
    if(i==1 || j==1)
    dp[i][j]=1;
    else if(i==j)
    dp[i][j]=1+dp[i-1][j];
    else if(i>j)
    dp[i][j]=dp[j][j];
    else if(i<j)
    dp[i][j]=dp[i][j-i]+dp[i-1][j];
    }
    return dp[m][n];
    }
  • DP状态转移方程:

    • m>nm>n时,dp(m,n)=dp(n,n)dp(m,n)=dp(n,n)
    • m==nm==n时,dp(m,n)=dp(m1,n)+1dp(m,n)=dp(m-1,n)+1
    • m<nm<n时,dp(m,n)=dp(m,nm)+dp(m1,n)dp(m,n)=dp(m,n-m)+dp(m-1,n)
    • 解释:
      • m>nm>n时即mm个盘子放nn个苹果,等价于nn个盘子放nn个苹果
      • m==nm==n时,要么所有盘子各放11个,为11种放法,要么去掉一个盘子
      • m<nm<n时,要么先让所有盘子各放11个,要么去掉一个盘子

M - CARDS POJ - 1721

  • 这是一个最简单的置换群。题意是说给NN个数代表一个序列,说给的这个序列其实是已经按照某种变换进行了SS次得到的了,让你求最初的序列。变换方式为:a[i]=ja[i]=j,而a[j]=ka[j]=k,故将a[i]=ka[i]=k,即令a[i]=a[a[i]]a[i]=a[a[i]].

    按照题意猜测,经过一个循环节rr,必定可以回到相同的序列,我们按照这个方法求出循环节rr。已经给出了从最初的序列到所示序列的变换次数了,我们只要再将它变换rS%rr-S\%r次就可以了。

    我的做法记录了一个循环节的所有变换序列。

  • AC代码:

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
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#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;
}
int orgin[1010];
int o[1010][1010];
int main(void)
{
int N,S;
while(scanf("%d %d",&N,&S)==2)
{
for(int i=0;i<N;i++)
{
orgin[i]=o[0][i]=read()-1;
}
int r=0;
for(int i=1;i<1005;i++)
{
for(int j=0;j<N;j++)
o[i][j]=o[i-1][o[i-1][j]];
if(o[i][0]==orgin[0])
{
r=i;
break;
}
}
int k=r-S%r;
for(int i=0;i<N;i++)
printf("%d\n",o[k][i]+1);
}
return 0;
}
comments powered by HyperComments
文章目录
  1. 1. A - 水陆距离 HihoCoder - 1478
  2. 2. D - 4个数和为0 51Nod - 1267
  3. 3. H - 抽彩球 51Nod - 1453
  4. 4. I - 斜率最大 51Nod - 1100
  5. 5. L - Ignatius and the Princess III HDU - 1028
  6. 6. M - CARDS POJ - 1721