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

Problem A 鹏

题面

题目描述

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

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

输入描述

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

输出描述

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

样例

样例编号输入输出解释
13<br/>1 2 11大鹏先上升一次,再下降一次,共翻越1次。
23<br/>3 1 20大鹏先下降一次,再上升一次,共翻越0次。
33<br/>1 2 30大鹏只需要上升一次,不需要下降,共翻越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:

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出样例#1:

3

说明

  • $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

5

说明

  • $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”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示:

D.png

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

输入输出

输入格式

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

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

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

输出格式

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

输入输出样例

输入样例#1:

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例#1:

6

说明

  • $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;
}
Last modification:June 23rd, 2019 at 05:10 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment