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
