成都外国语学校信息学夏令营状压考试

Author：薇薇安
发布时间：June 23, 2019
30 views
No comments
6566 字数
Categories：题解

Problem A 鹏

题面

题目描述

化而为鸟，其名为鹏。鹏之背，不知其几千里也。——《庄子·逍遥游》

HtBest的小鲲长大变成了大鹏，大鹏在天际翱翔，看到了一片绵延的山脉，每座山都有自己的高度，大鹏想穿过这片山脉。由于他只能紧贴地面飞行，他想知道他一共要翻越几次大山（上升->平飞->下降算一次，其中平飞可以没有）。开始时，大鹏在山脉的左端。

输入描述

第一行一个正整数$n$，表示山脉被分为$n$段。
第二行有$n$个正整数$a_i$,两两之间用空格分开，$a_i$表示山脉第$i$段的高度。

输出描述

一行，包含一个正整数ans，表示大鹏需要翻越几次大山。

样例

样例编号	输入	输出	解释
1	3<br/>1 2 1	1	大鹏先上升一次，再下降一次，共翻越1次。
2	3<br/>3 1 2	0	大鹏先下降一次，再上升一次，共翻越0次。
3	3<br/>1 2 3	0	大鹏只需要上升一次，不需要下降，共翻越0次

数据范围

$30\%$数据：$1 \leq n \leq 5 \times 10^3$
$70\%$数据：$1 \leq n \leq 5 \times 10^6$
$100\%$数据：$1 \leq n \leq 10^6,1 \leq a_i \leq 10^{10}$

源代码

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
#ifndef OFF_LINE
    freopen("peng.in","r",stdin);
    freopen("peng.out","w",stdout);
#endif
    int n,ans=0,pre;
    bool c=false;
    ios::sync_with_stdio(false);
    cin>>n>>pre;
    n--;
    while(n--){
        int t;
        cin>>t;
        if(t>pre){
            c=true;
        }
        else{
            if(t<pre&&c){
                ans++;
                c=false;
            }
        }
        pre=t;
    }
    cout<<ans<<endl;
}

Problem B 食物链

这道题是NOI 2001的题目，参见洛谷P2024。

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是“1 X Y”，表示 X 和 Y 是同类。
第二种说法是“2 X Y”，表示 X 吃 Y 。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真

的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话
当前的话中 X 或 Y 比 N 大，就是假话
当前的话表示 X 吃 X，就是假话

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入输出格式

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

输入输出样例

输入样例#1：

输出样例#1：

说明

$1 \leq N \leq 5 \times 10^4$
$1 \leq K \leq 10^5$

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=150005;
long long m[MAXN];
long long find(int i){
    return m[i]==i?i:m[i]=find(m[i]);
}
int main(){
    long long n,k,ans=0;
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=0;i<=3*n;i++){
        m[i]=i;
    }
    while(k--){
        long long opt,x,y;
        cin>>opt>>x>>y;
        if(x>n||y>n){
            ans++;
            continue;
        }
        if(opt==1){
            if(find(x+n)==find(y)||find(y+n)==find(x)){
                ans++;
            }
            else{
                m[find(x)]=find(y);
                m[find(x+n)]=find(y+n);
                m[find(x+(n<<1))]=find(y+(n<<1));
            }
        }
        else{
            if(find(x)==find(y)||find(x)==find(y+n)){
                ans++;
            }
            else{
                m[find(x+n)]=find(y);
                m[find(x+(n<<1))]=find(y+n);
                m[find(x)]=find(y+(n<<1));
            }
        }
    }
    cout<<ans<<endl;
}

Problem C 广场铺砖问题

题目描述

有一个$w$行$h$列的广场，需要用$1 \times 2$小砖铺盖，小砖之间互相不能重叠，问有多少种不同的铺法？

输入格式

只有一行$2$个整数，分别为$w$和$h$。

输出格式

只有$1$个整数，为所有的铺法数。

输入输出样例

输入样例#1

2 4

输出样例#1

说明

$1 \leq w \leq 11$
$1 \leq h \leq 11$

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int e[MAXN][MAXN];
int main( void ) {
    int test;
    cin >> test;
    while ( test-- ) {
        int n, m;
        int u, v;
        int ans = 0;
        memset( e, 0, sizeof( e ) );
        cin >> n >> m;
        for ( int i = 1; i <= m; i++ ) {
            cin >> u >> v;
            e[u][v] = 1;
        }
        for ( int k = 1; k <= n; k++ )
            for ( int i = 1; i <= n; i++ ) {
                if ( e[i][k] ) {
                    for ( int j = 1; j <= n; j++ ) {
                        if ( e[k][j] )
                            e[i][j] = 1;
                    }
                }
            }
        for ( int i = 1; i <= n; i++ )
            for ( int j = i + 1; j <= n; j++ )
                if ( e[i][j] == 0 && e[j][i] == 0 )
                    ans++;
        cout << ans << endl;
    }
    return 0;
}

Problem D 炮兵阵地

这道题是NOI 2001的题目，参见洛谷P2701。

题目描述

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入输出

输入格式

第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。

一行，一个整数，表示假话的总数。

输出格式

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

输入输出样例

输入样例#1：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例#1：

说明

$1 \leq N \leq 100$
$1 \leq M \leq 10$

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std ;
const int maxm=500,maxn=105 ;
int dp[3][maxm][maxm];
int st[maxn],num[maxn],ans,map[maxn],M,N;
bool judge1(int state){ 
    return (state&(state<<1)||state&(state<<2)) ;
}
bool judge2(int index,int i){
    return map[i]&st[index] ; 
}
inline int cntnum(int state){
    int ans=0 ;
    while(state>0){
        if(state&1) ans++ ;
        state>>=1 ;
    }
    return ans ;
} 
int main(){
    memset(dp,-1,sizeof(dp)) ;
    char mp;
    cin>>N>>M ;
    for(int i=1;i<=N;i++){
        for(int j=M;j>=1;j--){
            cin>>mp ;
            if(mp=='H') map[i]+=1<<j-1 ;
        }
    }
    int top=0 ;
    for(int j=0;j<=(1<<M)-1;j++){
        if(!judge1(j)){
            st[++top]=j ;
            num[top]=cntnum(j) ;
        }
    }
    for(int i=1;i<=top;i++){
        if(!judge2(i,1)){
            dp[1][i][1]=num[i] ;
        }
    }
    for(int j=1;j<=top;j++){
        if(judge2(j,2)) continue ;
        for(int k=1;k<=top;k++){
            if(judge2(k,1)||st[k]&st[j]) continue ;
            dp[2][j][k]=num[j]+num[k] ;
        }
    }
    for(int i=3;i<=N;i++){
        for(int j=1;j<=top;j++){ 
            if(judge2(j,i)) continue ;
            for(int k=1;k<=top;k++){
                if(judge2(k,i-1)||st[k]&st[j]) continue ;
                for(int t=1;t<=top;t++){ 
                    if(judge2(t,i-2)||st[t]&st[k]||st[t]&st[j]) continue ;
                    dp[i%3][j][k]=max(dp[i%3][j][k],dp[(i-1)%3][k][t]+num[j]) ;
                }
            }
        }
    }
    for(int j=1;j<=top;j++){
        for(int k=1;k<=top;k++){
            ans=max(ans,dp[N%3][j][k]) ;
        }
    }
    cout<<ans<<endl ;
    return 0;
}

版权属于：来自星星的薇薇安
本文链接：https://www.starroad.top/archives/233.html
如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！

Last modification：June 23rd, 2019 at 05:10 pm

如果您觉得我的文章有用，请赏一颗糖糖。

成都外国语学校信息学夏令营状压考试

薇薇安 • 2019 年 08 月 21 日

Problem A 鹏

题面

题目描述

化而为鸟，其名为鹏。鹏之背，不知其几千里也。——《庄子·逍遥游》

输入描述

第一行一个正整数$n$，表示山脉被分为$n$段。
第二行有$n$个正整数$a_i$,两两之间用空格分开，$a_i$表示山脉第$i$段的高度。

输出描述

一行，包含一个正整数ans，表示大鹏需要翻越几次大山。

样例

样例编号	输入	输出	解释
1	3<br/>1 2 1	1	大鹏先上升一次，再下降一次，共翻越1次。
2	3<br/>3 1 2	0	大鹏先下降一次，再上升一次，共翻越0次。
3	3<br/>1 2 3	0	大鹏只需要上升一次，不需要下降，共翻越0次

数据范围

$30\%$数据：$1 \leq n \leq 5 \times 10^3$
$70\%$数据：$1 \leq n \leq 5 \times 10^6$
$100\%$数据：$1 \leq n \leq 10^6,1 \leq a_i \leq 10^{10}$

源代码

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
#ifndef OFF_LINE
    freopen("peng.in","r",stdin);
    freopen("peng.out","w",stdout);
#endif
    int n,ans=0,pre;
    bool c=false;
    ios::sync_with_stdio(false);
    cin>>n>>pre;
    n--;
    while(n--){
        int t;
        cin>>t;
        if(t>pre){
            c=true;
        }
        else{
            if(t<pre&&c){
                ans++;
                c=false;
            }
        }
        pre=t;
    }
    cout<<ans<<endl;
}

Problem B 食物链

这道题是NOI 2001的题目，参见洛谷P2024。

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是“1 X Y”，表示 X 和 Y 是同类。
第二种说法是“2 X Y”，表示 X 吃 Y 。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真

的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话
当前的话中 X 或 Y 比 N 大，就是假话
当前的话表示 X 吃 X，就是假话

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入输出格式

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

输入输出样例

输入样例#1：

输出样例#1：

说明

$1 \leq N \leq 5 \times 10^4$
$1 \leq K \leq 10^5$

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=150005;
long long m[MAXN];
long long find(int i){
    return m[i]==i?i:m[i]=find(m[i]);
}
int main(){
    long long n,k,ans=0;
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=0;i<=3*n;i++){
        m[i]=i;
    }
    while(k--){
        long long opt,x,y;
        cin>>opt>>x>>y;
        if(x>n||y>n){
            ans++;
            continue;
        }
        if(opt==1){
            if(find(x+n)==find(y)||find(y+n)==find(x)){
                ans++;
            }
            else{
                m[find(x)]=find(y);
                m[find(x+n)]=find(y+n);
                m[find(x+(n<<1))]=find(y+(n<<1));
            }
        }
        else{
            if(find(x)==find(y)||find(x)==find(y+n)){
                ans++;
            }
            else{
                m[find(x+n)]=find(y);
                m[find(x+(n<<1))]=find(y+n);
                m[find(x)]=find(y+(n<<1));
            }
        }
    }
    cout<<ans<<endl;
}

Problem C 广场铺砖问题

题目描述

有一个$w$行$h$列的广场，需要用$1 \times 2$小砖铺盖，小砖之间互相不能重叠，问有多少种不同的铺法？

输入格式

只有一行$2$个整数，分别为$w$和$h$。

输出格式

只有$1$个整数，为所有的铺法数。

输入输出样例

输入样例#1

2 4

输出样例#1

说明

$1 \leq w \leq 11$
$1 \leq h \leq 11$

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int e[MAXN][MAXN];
int main( void ) {
    int test;
    cin >> test;
    while ( test-- ) {
        int n, m;
        int u, v;
        int ans = 0;
        memset( e, 0, sizeof( e ) );
        cin >> n >> m;
        for ( int i = 1; i <= m; i++ ) {
            cin >> u >> v;
            e[u][v] = 1;
        }
        for ( int k = 1; k <= n; k++ )
            for ( int i = 1; i <= n; i++ ) {
                if ( e[i][k] ) {
                    for ( int j = 1; j <= n; j++ ) {
                        if ( e[k][j] )
                            e[i][j] = 1;
                    }
                }
            }
        for ( int i = 1; i <= n; i++ )
            for ( int j = i + 1; j <= n; j++ )
                if ( e[i][j] == 0 && e[j][i] == 0 )
                    ans++;
        cout << ans << endl;
    }
    return 0;
}

Problem D 炮兵阵地

这道题是NOI 2001的题目，参见洛谷P2701。

题目描述

输入输出

输入格式

第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。

一行，一个整数，表示假话的总数。

输出格式

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

输入输出样例

输入样例#1：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例#1：

说明

$1 \leq N \leq 100$
$1 \leq M \leq 10$

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std ;
const int maxm=500,maxn=105 ;
int dp[3][maxm][maxm];
int st[maxn],num[maxn],ans,map[maxn],M,N;
bool judge1(int state){ 
    return (state&(state<<1)||state&(state<<2)) ;
}
bool judge2(int index,int i){
    return map[i]&st[index] ; 
}
inline int cntnum(int state){
    int ans=0 ;
    while(state>0){
        if(state&1) ans++ ;
        state>>=1 ;
    }
    return ans ;
} 
int main(){
    memset(dp,-1,sizeof(dp)) ;
    char mp;
    cin>>N>>M ;
    for(int i=1;i<=N;i++){
        for(int j=M;j>=1;j--){
            cin>>mp ;
            if(mp=='H') map[i]+=1<<j-1 ;
        }
    }
    int top=0 ;
    for(int j=0;j<=(1<<M)-1;j++){
        if(!judge1(j)){
            st[++top]=j ;
            num[top]=cntnum(j) ;
        }
    }
    for(int i=1;i<=top;i++){
        if(!judge2(i,1)){
            dp[1][i][1]=num[i] ;
        }
    }
    for(int j=1;j<=top;j++){
        if(judge2(j,2)) continue ;
        for(int k=1;k<=top;k++){
            if(judge2(k,1)||st[k]&st[j]) continue ;
            dp[2][j][k]=num[j]+num[k] ;
        }
    }
    for(int i=3;i<=N;i++){
        for(int j=1;j<=top;j++){ 
            if(judge2(j,i)) continue ;
            for(int k=1;k<=top;k++){
                if(judge2(k,i-1)||st[k]&st[j]) continue ;
                for(int t=1;t<=top;t++){ 
                    if(judge2(t,i-2)||st[t]&st[k]||st[t]&st[j]) continue ;
                    dp[i%3][j][k]=max(dp[i%3][j][k],dp[(i-1)%3][k][t]+num[j]) ;
                }
            }
        }
    }
    for(int j=1;j<=top;j++){
        for(int k=1;k<=top;k++){
            ans=max(ans,dp[N%3][j][k]) ;
        }
    }
    cout<<ans<<endl ;
    return 0;
}

版权属于：来自星星的薇薇安
本文链接：https://www.starroad.top/archives/233.html
如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！

Problem A 鹏

题面

题目描述

输入描述

输出描述

样例

数据范围

源代码

Problem B 食物链

题目描述

输入输出格式

输入格式

输出格式

输入输出样例

输入样例#1：

输出样例#1：

说明

代码

Problem C 广场铺砖问题

题目描述

输入格式

输出格式

输入输出样例

输入样例#1

输出样例#1

说明

代码

Problem D 炮兵阵地

题目描述

输入输出

输入格式

输出格式

输入输出样例

输入样例#1：

输出样例#1：

说明

代码