Loading... ## 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}$ ### 源代码 ```cpp #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](https://www.luogu.org/problemnew/show/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$ ### 代码 ```cpp #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$ ### 代码 ```cpp #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](https://www.luogu.org/problemnew/show/P2701)。 ### 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: ![D.png][1] 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 ### 输入输出 #### 输入格式 第一行包含两个由空格分割开的正整数,分别表示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$ ### 代码 ```cpp #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; } ``` [1]: https://www.oss.starroad.top/usr/uploads/2019/06/1274420540.png<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/233.html">https://www.starroad.top/archives/233.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:June 23rd, 2019 at 05:10 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat