问题 A: 海岸线
-
题目描述
一个王国分成n*m个六边形区域，每个区域内是陆地或者是水。如果一条边两侧为陆地和水，则该条边成为海岸线，求这个王国海岸线的长度。 -
输入
第一行两个整数N,M。
以下N行每行M个字符，“.”表示水，“#”表示陆地。偶数行需要向右移半格，具体见样例。 -
输出
一个整数，海岸线的长度。 -
样例输入 Copy
3 6
…#.##
.##.#.
#.#… -
样例输出 Copy
19 -
提示
数据表示如下图像：
可以看出，海岸线长度为19。 -
【数据范围】
对100%的数据1<=N,M<=50。 -
题意分析：就是把图形转化成六边形，求海岸线长度；
-
思路分析 ：很明显，你不能只考虑上下左右，因为它的两行是错开的
-
所以要换种思路考虑，如上图，我么可以看到，奇数行都是向左错开，偶数行就是向有错开，我们细心点可一发现<mark>向左错开的相邻的六个分别是上，下，左，右，右上和右下；而向右错开的相邻的六个分别是上，下，左，右，左上和左下</mark>知道这些剩下的就简单多了。
-
代码
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=300006;
ll n,q,m,t,p,l,r,sum,c[maxn];
ll a[maxn],b[maxn];
char str[1000][1000];
int main () {
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>str[i]+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(str[i][j]=='#'){
if(i%2==0){
if(str[i][j-1]=='.')
sum++;
if(str[i][j+1]=='.')
sum++;
if(str[i+1][j]=='.')
sum++;
if(str[i-1][j]=='.')
sum++;
if(str[i+1][j+1]=='.')
sum++;
if(str[i-1][j+1]=='.')
sum++;
}
else {
if(str[i][j-1]=='.')
sum++;
if(str[i][j+1]=='.')
sum++;
if(str[i+1][j]=='.')
sum++;
if(str[i-1][j]=='.')
sum++;
if(str[i+1][j-1]=='.')
sum++;
if(str[i-1][j-1]=='.')
sum++;
}
}
cout<<sum<<endl;
return 0;
}
问题 B: 最大子序和
题目描述
输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。
例如 1，-3,5,1，-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6
输入
第一行两个数n,m
第二行有n个数，要求在n个数找到最大子序和
输出
一个数，数出他们的最大子序和
样例输入 Copy
6 4
1 -3 5 1 -2 3
样例输出 Copy
7
提示
30%满足 n,m<=100
50%满足 n,m<=3000
100%满足n,m<=300000
-
思路分析：
单调队列
需要满足两个性质： -
队列内具有一定的单调性（优先队列）。
满足普通队列性质，一端进，另一端出，不可以中间插队。
但是这样就会现矛盾了，例如一个单调增的队列：1,5,8,9，我们要插入4，这时如果只能从尾端进去的话就打破了其单调性，呢么这时的做法就是从队尾到队头，把大于4的全部T了，然后插入后的队列就变成了1,4。 -
应用
常用于优化动态规划（DP）问题。
代码
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=300006;
ll n,q,m,t,p,l,r,sum,c[maxn];
ll a[maxn],b[maxn];
int main () {
cin>>n>>m;
b[0]=0;
for(int i=1; i<=n; i++) {
cin>>b[i];
b[i]+=b[i-1];
}
l = 1, r = 1, sum= -maxn;
c[1] = 0;
for (int i = 1; i <= n; i++) {
while (l <= r && c[l] < i - m) l++;
sum = max(sum, b[i] - b[c[l]]);
while (l <= r && b[c[r]] >= b[i]) r--;
c[++r] = i;
}
cout<<sum<<endl;
return 0;
}
问题 C: 小猴打架
题目描述
一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。
现在的问题是，总共有多少种不同的打架过程。
比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。
输入
一个整数N。
输出
一行，方案数mod 9999991。
样例输入 Copy
4
样例输出 Copy
96
提示
50%的数据N<=10^3。
100%的数据N<=10^6。
- 思路分析：
组合数问题，就是（n-1）！*nn-2;叫啥什么定理
代码
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=300006;
ll n,q,m,t,p,l,r,sum,c[maxn];
ll a[maxn],b[maxn];
int main () {
cin>>n;
sum=1;
for(int i=1;i<=n-2;i++)
sum=sum*n%9999991;
for(int i=1;i<=n-1;i++)
sum=sum*i%9999991;
cout<<sum<<endl;
return 0;
}
问题 D: 排队
题目描述
每天,农夫John的N(1 <= N <= 50,000)头牛总是按同一序列排队.有一天,John决定让一些牛们玩一场飞盘比赛.他准备找一群在对列中位置连续的牛来进行比赛.但是为了避免水平悬殊,牛的身高不应该相差太大.
John准备了Q (1 <= Q <= 180,000)个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.
注意: 在最大数据上, 输入和输出将占用大部分运行时间.
输入
第1行: N 和 Q.
第2…N+1行: 第i+1行是第i头牛的身高.
第N+2…N+Q+1行: 每行两个整数A和B(1 <= A <= B <= N), 表示从A到B的所有牛.
输出
第1…Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.
样例输入 Copy
6 3
1
7
3
4
2
5
1 5
4 6
2 2
样例输出 Copy
6
3
0
提示
10%的数据 N,Q<=10
30%的数据 N,Q<=2000
- 思路分析：
线段树问题吧，好像还有其他思路没大想出来。就是写了啷个查询函数，一个查最小值，一个查最大值。
代码：
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=300006;
ll n,q,m,t,p,l,r,sum,c[maxn];
ll a[maxn],b[maxn];
char str[1000][1000];
inline int read() {//读入挂
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct node {
int l,r,maxx,minn;
} tree[maxn*4];
inline void build(int i,int l,int r) { //递归建树
tree[i].l=l;
tree[i].r=r;
if(l==r) { //如果这个节点是叶子节点
tree[i].maxx=a[l];
tree[i].minn=a[l];
return ;
}
int mid=(l+r)>>1;//mid=(l+r)/2;
build(i*2,l,mid);//分别构造左子树和右子树
build(i*2+1,mid+1,r);
tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);//刚才我们发现的性质return ;
tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
}
/* inline void add(int i,int dis,int k) { //dis 为第几位; if(tree[i].l==tree[i].r) { //如果是叶子节点，那么说明找到了 tree[i].maxx=k; tree[i].minn=k; return ; } ll mid=(tree[i].l+tree[i].r)/2; if(dis<=mid) add(i*2,dis,k);//在哪往哪跑 else add(i*2+1,dis,k); tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);//返回更新 tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn); return; } */
inline ll search(ll i,ll l,ll r) { //区间查询
if(tree[i].l==l && tree[i].r==r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
return tree[i].maxx;
ll mid=(tree[i].l+tree[i].r)/2;
if(r<=mid) return search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
else if(l>mid) return search(i*2+1,l ,r);
else return max(search(i*2,l,mid),search(i*2+1,mid+1,r));//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
}
inline ll search1(ll i,ll l,ll r) { //区间查询
if(tree[i].l==l && tree[i].r==r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
return tree[i].minn;
ll mid=(tree[i].l+tree[i].r)/2;
if(r<=mid) return search1(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
else if(l>mid) return search1(i*2+1,l ,r);
else return min(search1(i*2,l,mid),search1(i*2+1,mid+1,r));//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
}
int main () {
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&p,&t);
printf("%lld\n",search(1,p,t)-search1(1,p,t));
}
return 0;
}
问题 I: Right Triangle
题目描述
There is a right triangle ABC with ∠ABC=90°.
Given the lengths of the three sides, |AB|,|BC| and |CA|, find the area of the right triangle ABC.
It is guaranteed that the area of the triangle ABC is an integer.
Constraints
·1≤|AB|,|BC|,|CA|≤100
·All values in input are integers.
·The area of the triangle ABC is an integer.
输入
Input is given from Standard Input in the following format:
|AB| |BC| |CA|
输出
Print the area of the triangle ABC.
样例输入 Copy
3 4 5
样例输出 Copy
6
题意分析：不分析了水题一个
思路分析：略
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=2e5+10;
char str[maxn],ss[maxn];
//int isPrime[1e8+10],Prime[maxn];//不能用 int 数组开不出来
ll Prime[maxn];
ll n,q;
ll a[maxn],b[maxn];
int main () {
for(int i=1;i<=3;i++)
cin>>a[i];
sort(a+1,a+1+3);
cout<<a[1]*a[2]/2<<endl;
return 0;
}
问题 J: Collatz Problem
题目描述
A sequence a={a1,a2,a3,…} is determined as follows:
The first term s is given as input.
Let f(n) be the following function:
f(n)=n/2 if n is even, and f(n)=3n+1 if n is odd.
ai=s when i=1, and ai=f(ai−1) when i>1.
Find the minimum integer m that satisfies the following condition:
There exists an integer n such that am=an(m>n).
Constraints
·1≤s≤100
·All values in input are integers.
·It is guaranteed that all elements in a and the minimum m that satisfies the condition are at most 1000000.
输入
Input is given from Standard Input in the following format:
s
输出
Print the minimum integer m that satisfies the condition.
样例输入 Copy
8
样例输出 Copy
5
提示
a={8,4,2,1,4,2,1,4,2,1,…}. As a5=a2, the answer is 5.
题意分析：
思路分析：
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=2e5+10;
char str[maxn],ss[maxn];
//int isPrime[1e8+10],Prime[maxn];//不能用 int 数组开不出来
ll Prime[maxn];
ll n,q;
ll a[maxn],b[maxn];
int main () {
cin>>a[1];
b[a[1]]=1;
for(int i=2;; i++) {
if(a[i-1]%2==0) a[i]=a[i-1]/2;
else a[i]=3*a[i-1]+1;
b[a[i]]++;
if(b[a[i]]==2) {
cout<<i<<endl;
break;
}
}
return 0;
}
问题 K: Grand Garden
- 题目描述
In a flower bed, there are N flowers, numbered 1,2,…,N. Initially, the heights of all flowers are 0. You are given a sequence h={h1,h2,h3,…} as input. You would like to change the height of Flower k to hk for all k (1≤k≤N), by repeating the following “watering” operation:
Specify integers l and r. Increase the height of Flower x by
1 for all x such that l≤x≤r.
Find the minimum number of watering operations required to satisfy the condition.
Constraints
·1≤N≤1000≤hi≤100
·All values in input are integers.
输入
Input is given from Standard Input in the following format:
N
h1 h2 h3 … hN
- 输出
Print the minimum number of watering operations required to satisfy the condition. - 样例输入 Copy
4
1 2 2 1 - 样例输出 Copy
2 - 提示
The minimum number of watering operations required is 2. One way to achieve it is:
Perform the operation with (l,r)=(1,3).
Perform the operation with (l,r)=(2,4). - 代码
#include<iostream>//线性筛素数
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=300006;
ll n,q,m,t,p,l,r,sum,c[maxn];
ll a[maxn],b[maxn];
int main () {
cin>>n;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
m=a[1];
for(int i=1;i<=n;i++)
{
if(i!=n){
if(a[i]>=m)
m=a[i];
else
{
sum+=(m-a[i]);
m=a[i];
}
}
else {
if(a[i]>=m)
sum+=a[i];
else
sum+=m;
}
}
cout<<sum<<endl;
return 0;
}
京公网安备 11010502036488号