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：
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”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入输出
输入格式
第一行包含两个由空格分割开的正整数，分别表示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;
}版权属于：淡淡的路瑶
本文链接：https://www.starroad.top/archives/233.html
如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！
