信息学奥赛-提高级 题库
跳石头
【问题描述】
一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。
【输入格式】
输入文件名为 stone.in。
输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
【输出格式】
输出文件名为 stone.out。
输出文件只包含一个整数,即最短跳跃距离的最大值。
【输入输出样例 1】

【输入输出样例 1 说明】
将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。
【数据规模与约定】
对于 20%的数据,0 ≤ M ≤ N ≤ 10。
对于 50%的数据,0 ≤ M ≤ N ≤ 100。
对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。
#include<bits/stdc++.h>
using namespace std; //本题数据量大,采用二分法来减少复杂度,避免超时。先把所有的石头点存入数组a
int l,n,m; //包括起始点0和终点l。这题使用二分答案的思想,顾名思义就是采用二分法查找答案(最短跳跃距离最大值)
int a[100000]; //我们知道,最短跳跃距离必在0-l之间,0和l一开始作为上下界,对于a[mid]用judge进行判断
bool judge(int k){ //如果要达到mid对应最短跳跃距离需要移开石头数count>原有的m,说明实际的答案会比mid小
int count=0,now=0; //就把有边界左移,反之,说明可以达到这个最短跳跃距离,是暂时的最优答案,先保存
for(int i=1;i<n+2;i++){ //然后把左边界右移,试试有没有更优的解,直到上下边界互相跨越
if(a[i]-a[now]<k){
count++;
}else{
now=i; //now是现在脚底下的石头,如果不移石头直接过去要更新
}
}
if(count>m){
return false;
}else{
return true;
}
}
int main(){
cin>>l>>n>>m;
a[0]=0;
a[n+1]=l;
for(int i=1;i<n+1;i++){
cin>>a[i];
}
int left=0,right=l,mid,ans;
while(left<=right){ //二分法
mid=(left+right)/2;
if(judge(mid)){
left=mid+1;
ans=mid;
}else{
right=mid-1;
}
}
cout<<ans;
//system("pause");
return 0;
}
子串
【问题描述】
有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出的位置不同也认为是不同的方案。
【输入格式】
输入文件名为 substring.in。
第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问题描述中所提到的 k,每两个整数之间用一个空格隔开。
第二行包含一个长度为 n 的字符串,表示字符串 A。
第三行包含一个长度为 m 的字符串,表示字符串 B。
【输出格式】
输出文件名为 substring.out。
输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,007 取模的结果。
【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【输入输出样例说明】
所有合法方案如下:(加下划线的部分表示取出的子串)
样例 1:aab aab / aab aab
样例 2:a ab aab / a aba ab / a a ba ab / aab a abaa b aab / aa baa b / aab aa b
样例 3:a a b aab / a a baa b / a ab a a b / a aba a ba a b a a b / a a ba a b / aab a a b
【数据规模与约定】
对于第 1 组数据:1≤n≤500,1≤m≤50,k=1;
对于第 2 组至第 3 组数据:1≤n≤500,1≤m≤50,k=2;
对于第 4 组至第 5 组数据:1≤n≤500,1≤m≤50,k=m;
对于第 1 组至第 7 组数据:1≤n≤500,1≤m≤50,1≤k≤m;
对于第 1 组至第 9 组数据:1≤n≤1000,1≤m≤100,1≤k≤m;
对于所有 10 组数据:1≤n≤1000,1≤m≤200,1≤k≤m。
#include<iostream>
#include<cstring>
#define N 1003
#define M 203
#define mod 1000000007
using namespace std;
int dp[3][N][M]={0};
char A[N],B[M];
int n=0,m=0,K=0;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>K;
cin>>(A+1);cin>>(B+1);
for(int i=0;i<=n;i++) dp[0][i][0]=1;
for(int k=1;k<=K;k++){
memset(dp[k&1],0,sizeof(dp[k&1]));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j>i) break;
dp[k&1][i][j]+=dp[k&1][i-1][j];
dp[k&1][i][j]%=mod;
if(A[i]==B[j]){
dp[k&1][i][j]+=(dp[(k-1)&1][i-1][j-1]+dp[k&1][i-1][j-1])%mod;
dp[k&1][i][j]%=mod;
if(i>1) dp[k&1][i][j]-=dp[k&1][i-2][j-1];
dp[k&1][i][j]%=mod;
dp[k&1][i][j]+=mod;
dp[k&1][i][j]%=mod;
}
dp[k&1][i][j]%=mod;
}
}
}
cout<<dp[K&1][n][m]<<endl;
return 0;
}
运输计划
【问题描述】
公元 2044 年,人类进入了宇宙纪元。
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui号星球沿最快的宇航路径飞行到 vi号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?
【输入格式】
输入文件名为 transport.in。
第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。
接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi和 ti,表示第i 条双向航道修建在 ai与 bi两个星球之间,任意飞船驶过它所花费的时间为 ti。
接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj和 vj,表示第 j 个运输计划是从 uj号星球飞往 vj号星球。
【输出格式】
输出文件名为 transport.out。
共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。
【输入输出样例 1】

【输入输出样例 1 说明】
将第 1 条航道改造成虫洞:则三个计划耗时分别为:11、12、11,故需要花费的时间为 12。
将第 2 条航道改造成虫洞:则三个计划耗时分别为:7、15、11,故需要花费的时间为 15。
将第 3 条航道改造成虫洞:则三个计划耗时分别为:4、8、11,故需要花费的时间为 11。
将第 4 条航道改造成虫洞:则三个计划耗时分别为:11、15、5,故需要花费的时间为 15。
将第 5 条航道改造成虫洞:则三个计划耗时分别为:11、10、6,故需要花费的时间为 11。
故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短,需要花费的时间为 11。
【数据规模与约定】
所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。
#include <bits/stdc++.h>
using namespace std;
const int Max=300005;
int n,m,s,ans,tot,l,r,mid;
int first[Max],son[Max],pos[Max],top[Max],depth[Max],father[Max],size[Max],dis[Max],num[Max],len[Max],val[Max],v[Max];
struct shu{int to,next,len;}edge[Max<<1];
struct bian{int x,y,len;}d[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void build(int x,int y,int z){edge[++s].next=first[x],first[x]=s,edge[s].to=y,edge[s].len=z;}
inline void dfs1(int point,int fa)
{
size[point]=1,father[point]=fa,depth[point]=depth[fa]+1;
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa) continue;
val[to]=edge[u].len,dis[to]=dis[point]+edge[u].len;
dfs1(to,point);
size[point]+=size[to];
if(size[to] > size[son[point]]) son[point]=to;
}
}
inline void dfs2(int point,int fa)
{
if(son[point])
{
pos[son[point]]=++tot,len[tot]=val[son[point]],top[son[point]]=top[point];
dfs2(son[point],point);
}
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(top[to]) continue;
pos[to]=++tot,top[to]=to;
dfs2(to,point);
}
}
inline int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(depth[top[x]] < depth[top[y]]) x^=y,y^=x,x^=y;
x=father[top[x]];
}
if(depth[x] > depth[y]) swap(x,y);
return x;
}
inline bool comp(const bian &a,const bian &b){return a.len>b.len;}
inline void solve(int x,int y)
{
while(top[x]!=top[y])
{
if(depth[top[x]] < depth[top[y]]) x^=y,y^=x,x^=y;
num[pos[top[x]]+1]++,num[pos[x]+1]--;
x=father[top[x]];
}
if(x==y) return;
if(depth[x] > depth[y]) x^=y,y^=x,x^=y;
num[pos[x]+1]++,num[pos[y]+1]--;
}
inline int mx(int x,int y){return x < y ? y : x;}
inline int check(int mid)
{
int k=0,x=0,sum=0;
while(d[k+1].len>mid) k++;
if(v[k]) return v[k];
memset(num,0,sizeof(num));
for(int i=1;i<=k;i++) solve(d[i].x,d[i].y);
for(int i=1;i<=n;i++){sum+=num[i];if(sum == k) x=mx(x,len[i]);}
v[k]=x;
return x;
}
inline void print(int x){if(x>9) print(x/10);putchar('0'+x%10);}
int main()
{
n=get_int(),m=get_int();
for(int i=1;i<=n-1;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y,z),build(y,x,z);
}
top[1]=tot=pos[1]=1;
dfs1(1,0),dfs2(1,0);
for(int i=1;i<=m;i++)
{
d[i].x=get_int(),d[i].y=get_int();
d[i].len=dis[d[i].x]+dis[d[i].y]-2*dis[LCA(d[i].x,d[i].y)];
}
sort(d+1,d+m+1,comp);
l=0,r=d[1].len;
while(l<r)
{
mid=(l+r)>>1;
(d[1].len - check(mid) <= mid) ? r=mid : l=mid+1;
}
print(r);
return 0;
}
生活大爆炸版石头剪刀布
【问题描述】
石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:
斯波克:《星际迷航》主角之一。
蜥蜴人:《星际迷航》中的反面角色。
这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

现在,小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定相等。例如:如果小 A 以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 6 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”,而如果小 B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”
已知小 A 和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分,输的得 0 分;平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。
【输入】
输入文件名为 rps.in。
第一行包含三个整数:N,NA,NB,分别表示共进行 N 次猜拳、小 A 出拳的周期长度,小 B 出拳的周期长度。数与数之间以一个空格分隔。
第二行包含 NA 个整数,表示小 A 出拳的规律,第三行包含 NB 个整数,表示小 B 出拳的规律。其中,0 表示“剪刀”,1 表示“石头”,2 表示“布”,3 表示“蜥蜴人”, 4 表示“斯波克”。数与数之间以一个空格分隔。
【输出】
输出文件名为 rps.out。
输出一行, 包含两个整数,以一个空格分隔,分别表示小 A、小 B 的得分。
【输入输出样例 1】

【输入输出样例 2】

【数据说明】
对于 100%的数据,0 < N ≤ 200,0 < NA ≤ 200, 0 < NB ≤ 200。
#include<bits/stdc++.h>
using namespace std;
int n , a , b , arr[205] , brr[205] , x , y;
int main(){
scanf("%d %d %d" , &n , &a , &b);
for(int i = 0 ; i < a ; i++) cin >> arr[i];
for(int i = 0 ; i < b ; i++) cin >> brr[i];
for(int i = 0 ; i < n ; i++){
if(arr[i % a] == 0 && brr[i % b] == 2 ||
arr[i % a] == 0 && brr[i % b] == 3 ||
arr[i % a] == 1 && brr[i % b] == 0 ||
arr[i % a] == 1 && brr[i % b] == 3 ||
arr[i % a] == 2 && brr[i % b] == 1 ||
arr[i % a] == 2 && brr[i % b] == 4 ||
arr[i % a] == 3 && brr[i % b] == 2 ||
arr[i % a] == 3 && brr[i % b] == 4 ||
arr[i % a] == 4 && brr[i % b] == 0 ||
arr[i % a] == 4 && brr[i % b] == 1)
x++;
else if(arr[i % a] == brr[i % b]) continue;
else y++;
}
cout << x << " " << y;
return 0;
}
联合权值
【问题描述】
无向连通图 G 有 n 个点,n-1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi ,每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v),若它们的距离为 2,则它们之间会产生
的联合权值。
请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?
【输入】
输入文件名为 link.in。
第一行包含 1 个整数 n。
接下来 n-1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和编号为 v 的点之间有边相连。
最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。
【输出】
输出文件名为 link.out。
输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对 10007 取余。
【输入输出样例】

【样例说明】

本例输入的图如上所示,距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。
其联合权值分别为 2、15、2、20、15、20。其中最大的是 20,总和为 74。
【数据说明】

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long n,x,y,v[500001],head[500001],nxt[500001],cnt,w[200001];
long long sum,maxx;
void add(int a,int b)//链式前向星存边,效率高,在图论中有很重要的作用
{
v[++cnt]=b;//v[cnt]表示编号为cnt的边的终点
nxt[cnt]=head[a];//nxt[cnt]表示第cnt条边下一条边是head[a]
head[a]=cnt;//插入链表头部
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&x,&y);
add(x,y);//无向边存两次
add(y,x);
}
for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
for(int i=1;i<=n;i++)
{
long long fix=0,maxn=0;
for(int j=head[i];j;j=nxt[j])
{
sum+=(fix*w[v[j]])%10007;//和之前的数每个相乘再相加,只需加他们的和就好了。
fix+=w[v[j]];//根据乘法分配律,打前缀和
maxx=max(maxx,maxn*w[v[j]]);//打擂台取最大值
maxn=max(maxn,w[v[j]]);
}
}
cout<<maxx<<" "<<sum*2%10007;
return 0;
}
飞扬的小鸟
【问题描述】
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。
为了简化问题,我们对游戏规则进行了简化和改编:
1. 游戏界面是一个长为 n,高为 m 的二维平面,其中有k 个管道(忽略管道的宽度)。
2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
3. 小鸟每个单位时间沿横坐标方向右移的距离为 1,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度 X,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时,上升的高度 X 和下降的高度 Y 可能互不相同。
4. 小鸟高度等于 0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m 时,无法再上升。

现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。
【输入】
输入文件名为 bird.in。
第 1 行有 3 个整数 n,m,k,分别表示游戏界面的长度,高度和水管的数量,每两个整数之间用一个空格隔开;
接下来的 n 行,每行 2 个用一个空格隔开的整数 X 和 Y,依次表示在横坐标位置 0~n-1上玩家点击屏幕后,小鸟在下一位置上升的高度 X,以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度 Y。
接下来 k 行,每行 3 个整数 P,L,H,每两个整数之间用一个空格隔开。每行表示一个管道,其中 P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为 L,H 表示管道缝隙上边沿的高度(输入数据保证 P 各不相同,但不保证按照大小顺序给出)。
【输出】
输出文件名为 bird.out。
共两行。
第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0。
第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。
【输入输出样例 1】

【输入输出样例 2】

【输入输出样例说明】
如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

【数据范围】
对于 30%的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
对于 50%的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
对于 70%的数据:5≤n≤1000,5≤m≤100;
对于 100%的数据:5≤n≤10000,5≤m≤1000,0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H ≤m,L+1<H。
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const ll mod = 1e9 + 7;
int dp[maxn][2005]; // dp[i][j] 表示到 i,j的最小操作
int x[maxn], y[maxn]; // 上升 和 下降
pii lim[maxn]; // 每列的范围
bool vis[maxn]; // 是不是管道
bool check(int i, int x) // 检查 x 是否在 第 i 行范围中
{
return x >= lim[i].first && x <= lim[i].second;
}
int main()
{
IOS();
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
lim[i].first = 1;
lim[i].second = m;
}
lim[0].first = 0;
lim[n].first = 1;
lim[n].second = m;
for(int i = 0; i < k; ++i) {
int p, l, r;
cin >> p >> l >> r;
vis[p] = true;
lim[p].first = l + 1;
lim[p].second = r - 1;
}
me(dp, 0x3f);
for(int i = 0; i <= m; ++i)
dp[0][i] = 0;
int p = 0;
for(int i = 1; i <= n; ++i) {
// 上升完全背包
for(int j = 0; j <= m; ++j) {
// 这里其实是做 01 背包,所以必须要从合法位置转移
if(check(i-1, j-x[i-1]))
dp[i][j] = min(dp[i][j], dp[i-1][j-x[i-1]] + 1);
// 这里才是完全背包,就不需要检查范围
dp[i][j] = min(dp[i][j], dp[i][j-x[i-1]] + 1);
}
// 特判 上届的情况
if(m == lim[i].second) {
for(int j = m-x[i-1]+1; j <= m; ++j) {
if(check(i-1, j))
dp[i][m] = min(dp[i][m], dp[i-1][j] + 1);
if(check(i, j))
dp[i][m] = min(dp[i][m], dp[i][j] + 1);
}
}
// 下降01背包
for(int j = lim[i].first; j <= lim[i].second; ++j) {
if(check(i-1, j+y[i-1]))
dp[i][j] = min(dp[i][j], dp[i-1][j+y[i-1]]);
if(dp[i][j] != INF)
p = i;
}
}
int ans = INF;
for(int i = lim[n].first; i <= lim[n].second; ++i) {
ans = min(ans, dp[n][i]);
}
if(ans != INF) {
cout << "1\n" << ans << endl;
}
else {
int cnt = 0;
for(int i = 0; i <= p; ++i)
if(vis[i]) ++cnt;
cout << "0\n" << cnt << endl;
}
// for(int i = 0; i <= n; ++i) {
// for(int j = 0; j <= m; ++j) {
// cout << (dp[i][j]==INF?-1:dp[i][j]) << " ";
// }
// cout << endl;
// }
return 0;
}
无线网络发射器选址
【问题描述】
随着智能手机的日益普及,人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。
假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状,并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。
东西向街道和南北向街道相交形成路口,规定编号为 x 的南北向街道和编号为 y 的东西向街道形成的路口的坐标是(x, y)。在某些路口存在一定数量的公共场所。
由于政府财政问题,只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心,边长为 2*d 的正方形。传播范围包括正方形边界。
例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器,希望你帮助他们在城市内找出合适的安装地点,使得覆盖的公共场所最多。
【输入】
输入文件名为 wireless.in。
第一行包含一个整数 d,表示无线网络发射器的传播距离。
第二行包含一个整数 n,表示有公共场所的路口数目。
接下来 n 行,每行给出三个整数 x, y, k, 中间用一个空格隔开,分别代表路口的坐标(x, y)以及该路口公共场所的数量。同一坐标只会给出一次。
【输出】
输出文件名为 wireless.out。
输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点方案数,以及能覆盖的最多公共场所的数量。
【输入输出样例】

【数据说明】
对于 100%的数据,1 ≤ d ≤ 20,1 ≤ n ≤ 20, 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤1,000,000。
#include<cstdio>
#include<cstdlib>
int main(){
int ans=0,d,n,x,y,k[129][129],jc=0,sum=0,m1,m2,n1,n2;
bool city[129][129];
scanf("%d",&d);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d%d",&x,&y);
scanf("%d",&k[x][y]);
city[x][y]=true;
}
for (int i=0;i<=128;i++)
for (int j=0;j<=128;j++){
n1=i-d;n2=i+d;m1=j-d;m2=j+d;
if (n1<0) n1=0;if (n2>128) n2=128;
if (m1<0) m1=0;if (m2>128) m2=128;
for (int q=n1;q<=n2;q++)
for (int p=m1;p<=m2;p++)
if (city[q][p]) ans=ans+k[q][p];
if (ans>jc) {jc=ans;
sum=1;}
else if (ans==jc) sum++;
ans=0;
}
printf("%d %d\n",sum,jc);
//system("pause");
return 0;
}
解方程
【问题描述】
已知多项式方程:

【输入】
输入文件名为 equation.in。
输入共 n+2 行。
第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数,依次为
【输出】
输出文件名为 equation.out。
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。
【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【数据说明】

#include<bits/stdc++.h>
#define LL long long
#define mod 1000000007
using namespace std;
inline LL read() {
LL x = 0; int t = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') t = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = ((x << 1) % mod + (x << 3) % mod + ch - '0') % mod; ch = getchar(); }
return x * t;
}
LL a[105];
int n, m, ans[1000005], tot;
inline bool cal(int x) {
LL res = a[n];
for(int i = n - 1; i >= 0; i --)
res = (res * x % mod + a[i]);
return res == 0;
}
int main() {
n = read(); m = read();
for(int i = 0; i <= n; i ++) a[i] = read();
for(int i = 1; i <= m; i ++)
if(cal(i)) ans[++tot] = i;
printf("%d\n", tot);
for(int i = 1; i <= tot; i ++)
printf("%d\n", ans[i]);
return 0;
}
转圈游戏
【问题描述】
n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,……,依此类推。
游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,……,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第n-m+1 号位置上的小伙伴走到第 1 号位置,……,第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。
现在,一共进行了 10k 轮,请问 x 号小伙伴最后走到了第几号位置。
【输入】
输入文件名为 circle.in。
输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。
【输出】
输出文件名为 circle.out。
输出共 1 行,包含 1 个整数,表示 10k 轮后 x 号小伙伴所在的位置编号。
【输入输出样例】

【数据说明】
对于 30%的数据,0 < k < 7;
对于 80%的数据,0 < k < 10^7;
对于 100%的数据,1 < n < 1,000,000,0 < m < n,1 ≤ x ≤ n,0 < k < 10^9。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int x = sc.nextInt();
sc.close();
System.out.println((x + m * f(10, k, n)) % n);
}
public static int f(int y, int k, int n) {
int pingfangshu = y;
int result = 1;
while (k != 0) {
if ((k & 1) == 1) {
result *= pingfangshu;
}
k >>= 1;
pingfangshu = (pingfangshu * pingfangshu) % n;
result %= n;
}
return result;
}
}
火柴排队
【问题描述】
涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:
其中 ai表示第一列火柴中第 i 个火柴的高度,bi表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
【输入】
输入文件为 match.in。
共三行,第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
【输出】
输出文件为 match.out。
输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。
【输入输出样例 1】

【输入输出样例说明】
最小距离是 0,最少需要交换 1 次,比如:交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。
【输入输出样例 2】

【输入输出样例说明】
最小距离是 10,最少需要交换 2 次,比如:交换第 1 列的中间 2 根火柴的位置,再交
换第 2 列中后 2 根火柴的位置。
【数据范围】
对于 10%的数据, 1 ≤ n ≤ 10;
对于 30%的数据,1 ≤ n ≤ 100;
对于 60%的数据,1 ≤ n ≤ 1,000;
对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤
#include <bits/stdc++.h>
using namespace std;
const int mod=99999997;
const int Max=100005;
int n,m,tot,ans;
int sum[Max],c[Max<<1],num[Max];
struct shu{int num,id;};
shu a[Max],b[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='0') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline bool comp(const shu &a,const shu &b){return a.num<b.num;}
inline void pre()
{
sort(c+1,c+tot+1);
m=unique(c+1,c+tot+1)-c-1;
for(int i=1;i<=n;i++) a[i].num=lower_bound(c+1,c+m+1,a[i].num)-c;
for(int i=1;i<=n;i++) b[i].num=lower_bound(c+1,c+m+1,b[i].num)-c;
}
inline void add(int num)
{
for(int i=num;i<=100000;i+=i&(-i)) sum[i]++;
}
inline int Q(int num)
{
int ans=0;
for(int i=num;i;i-=i&(-i)) ans+=sum[i];
return ans;
}
inline void solve()
{
for(int i=1;i<=n;i++) add(num[i]),ans=(ans+i-Q(num[i]))%mod;
cout<<ans<<"\n";
}
int main()
{
n=get_int();
for(int i=1;i<=n;i++) c[++tot]=a[i].num=get_int(),a[i].id=i;
for(int i=1;i<=n;i++) c[++tot]=b[i].num=get_int(),b[i].id=i;
pre();
sort(a+1,a+n+1,comp),sort(b+1,b+n+1,comp);
for(int i=1;i<=n;i++) num[a[i].id]=b[i].id;
solve();
return 0;
}
货车运输
【问题描述】
A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
【输入】
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意:x 不等于 y。
【输出】
输出文件名为 truck.out。
输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。
【输入输出样例】

【数据说明】
对于 30%的数据,0 < n < 1,000,0 < m < 10,000,0 < q < 1,000;
对于 60%的数据,0 < n < 1,000,0 < m < 50,000,0 < q < 1,000;
对于 100%的数据,0 < n < 10,000,0 < m < 50,000,0 < q < 30,000,0 ≤ z ≤ 100,000。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define _for(i,a,b) for (int i=a;i<=b;i++)
using namespace std;
const int N=1e4+5,M=5e4+5;//g[u][j]表示u到f[u][j]这条链上边权的最大值。
int n,m,fa[N],h[N],e[M],ne[M],w[M],idx,d[N],f[N][20],g[N][20];
struct node{
int a,b,w;
bool operator <(const node& rhs) const{
return w>rhs.w;
}
}a[M];
inline void c_plus(){//可以忽略
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
inline void init_list(){//单链表
idx=0;
memset(h,-1,sizeof(h));
}
inline void add(int a,int b,int c){//同上
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
inline void init_set(){//并查集
_for(i,1,n){
fa[i]=i;
}
}
int get(int x){//同上
if (x==fa[x]){
return x;
}
return fa[x]=get(fa[x]);
}
void kruskal(){//kruskal算法
sort(a+1,a+m+1);
_for(i,1,m){
int x=get(a[i].a);
int y=get(a[i].b);
if (x!=y){
fa[y]=x;
add(a[i].a,a[i].b,a[i].w);
add(a[i].b,a[i].a,a[i].w);
}
}
}
void dfs(int u){
d[u]=d[f[u][0]]+1;
for (int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if (j==f[u][0]){
continue;
}
f[j][0]=u;
g[j][0]=w[i];//我们需要在dfs函数里给g[v][0]赋初值,为每个结点v上面那条边的权值。
dfs(j);
}
}
int lca(int x,int y){//LCA算法
if (get(x)!=get(y)){//判断是否合法,在不在一个连通块内
return -1;
}
if (d[x]<d[y]){
swap(x,y);
}
int k=(int)(log2(d[x])),ans=0x7fffffff;//ans存答案
for (int j=k;j>=0;j--){
if (d[f[x][j]]>=d[y]){
ans=min(ans,g[x][j]);//维护最大值
x=f[x][j];
}
}
if (x==y){/
goto output;
}
k=(int)(log2(d[x]));
for (int j=k;j>=0;j--){
if (f[x][j]!=f[y][j]){
ans=min(ans,min(g[x][j],g[y][j]));//维护最大值
x=f[x][j];
y=f[y][j];
}
}
ans=min(ans,min(g[x][0],g[y][0]));//最后还差一步才到达lca,因此还要算上最后两条边的最大值
output:
return ans;
}
int main(){
freopen("truck.in","r",stdin);
freopen("truck.out","w",stdout);
c_plus();
int q,x,y;
cin>>n>>m;
init_list();
init_set();
_for(i,1,m){
cin>>a[i].a>>a[i].b>>a[i].w;
}
kruskal();
_for(i,1,n){
if (d[i]==0){//每个连通块都要遍历
dfs(i);
}
}
for (int j=1;(1<<j)<=n;j++){
_for(i,1,n){
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);//通过动态规划计算g数组剩余的值。
//转移方程很显然,就是把从i到f[i][j]这条链,拆成i到f[i][j-1]和f[i][j-1]到f[i][j]两条链,
//然后取最大值
}
}
cin>>q;
while (q--){
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
return 0;
}
积木大赛
【题目描述】
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦,大厦可以看成由n块宽度为1的积木组成,第i块积木的最终高度需要是hi。
在搭建开始之前,没有任何积木(可以看成n块高度为 0 的积木)。接下来每次操作,小朋友们可以选择一段连续区间[L,R],然后将第L块到第R块之间(含第 L 块和第 R 块)所有积木的高度分别增加1。
小M是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。
【输入】
输入文件为 block.in
输入包含两行,第一行包含一个整数n,表示大厦的宽度。
第二行包含n个整数,第i个整数为hi。
【输出】
输出文件为 block.out
仅一行,即建造所需的最少操作数。
【输入输出样例】

【样例解释】
其中一种可行的最佳方案,依次选择[1,5] [1,3] [2,3] [3,3] [5,5]
【数据范围】
对于 30%的数据,有1 ≤ n ≤ 10;
对于 70%的数据,有1 ≤ n ≤ 1000;
对于 100%的数据,有1 ≤ n ≤ 100000,0 ≤ hi ≤ 10000。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int h[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
int res = 0;
for (int i = 1; i <= n; i ++ ){
if(h[i]-h[i-1]>0)res+=h[i]-h[i-1];
}
cout << res << endl;
return 0;
}
花匠
【问题描述】
花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。
具体而言,栋栋的花的高度可以看成一列整数h1, h2, … , hn。设当一部分花被移走后,剩下的花的高度依次为g1, g2, … , gm,则栋栋希望下面两个条件中至少有一个满足:
条件 A:对于所有的i,g2i > g2i−1,且g2i > g2i+1;
条件 B:对于所有的i,g2i < g2i−1,且g2i < g2i+1。
注意上面两个条件在m = 1时同时满足,当m > 1时最多有一个能满足。
请问,栋栋最多能将多少株花留在原地。
【输入】
输入文件为 flower.in。
输入的第一行包含一个整数n,表示开始时花的株数。
第二行包含n个整数,依次为h1, h2,… , hn,表示每株花的高度。
【输出】
输出文件为 flower.out。
输出一行,包含一个整数m,表示最多能留在原地的花的株数。
【输入输出样例】

【输入输出样例说明】
有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条件 B。
【数据范围】
对于 20%的数据,n ≤ 10;
对于 30%的数据,n ≤ 25;
对于 70%的数据,n ≤ 1000,0 ≤ hi ≤ 1000;
对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ hi ≤ 1,000,000,所有的hi随机生成,所有随机数服从某区间内的均匀分布。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,a[N],ans;
int f[N][2];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
scanf("%d",&a[i]);
f[1][0] = f[1][1] = 1;
for(int i = 2;i <= n;i ++)
{
if(a[i] > a[i - 1])
f[i][1] = max(f[i - 1][1],f[i - 1][0] + 1);
else f[i][1] = f[i - 1][1];
if(a[i] < a[i - 1])
f[i][0] = max(f[i - 1][0],f[i - 1][1] + 1);
else f[i][0] = f[i - 1][0];
}
printf("%d",max(f[n][0],f[n][1]));
return 0;
}
华容道
【问题描述】
小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的:
1. 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;
2. 有些棋子是固定的,有些棋子则是可以移动的;
3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候,空白的格子在第 EXi行第 EYi列,指定的可移动棋子的初始位置为第 SXi行第 SYi列,目标位置为第 TXi行第 TYi列。
假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。
【输入】
输入文件为 puzzle.in。
第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q;
接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开,每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以移动或者该格子是空白的。
接下来的 q 行,每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi,每两个整数之间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。
【输出】
输出文件名为 puzzle.out。
输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无法完成目标则输出−1。
【输入输出样例】

【输入输出样例说明】
棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标棋子。
1. 第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示),游戏的目标是将初始位置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子)上。

2. 第二次游戏,空白格子的初始位置是(1, 2)(图中空白所示),游戏的目标是将初始位置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。

要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,
必然是从位置(2,2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置
的只有当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置,游戏无
法完成。
【数据范围】
对于 30%的数据,1 ≤ n, m ≤ 10,q = 1;
对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10;
对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。
#include <bits/stdc++.h>
using namespace std;
const int Max=35;
const int fx[5]={0,1,0,-1};
const int fy[5]={1,0,-1,0};
int n,m,q,head,tail,tot,ans;
int num[Max][Max],dis[Max][Max][5],move[Max][Max][5][5];
bool vis[Max][Max],v[Max][Max][5];
int p[1000000][5],d[1000000][5];
inline void bfs(int x,int y,int k1,int k2)
{
int sx=x+fx[k1],sy=y+fy[k1],tx=x+fx[k2],ty=y+fy[k2];
if((!num[sx][sy])||(!num[tx][ty])) return;
head=0,tail=1;
p[1][1]=sx,p[1][2]=sy;
memset(vis,0,sizeof(vis));
vis[x][y]=vis[sx][sy]=1;
while(head<tail)
{
head++;
int xx=p[head][1],yy=p[head][2];
for(int i=0;i<=3;i++)
{
int x1=xx+fx[i],y1=yy+fy[i];
if(!vis[x1][y1] && num[x1][y1])
{
vis[x1][y1]=1;
p[++tail][1]=x1,p[tail][2]=y1,p[tail][0]=p[head][0]+1;
if(x1==tx&&y1==ty) {move[x][y][k1][k2]=p[tail][0];return;}
}
}
}
}
inline void pre()
{
memset(move,43,sizeof(move));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(num[i][j])
for(int k=0;k<=3;k++)
for(int l=0;l<=3;l++)
if(l==k) move[i][j][k][l]=0;
else bfs(i,j,k,l);
}
inline void calc(int x,int y,int sx,int sy)
{
head=0,tail=1,tot=0;
p[1][1]=x,p[1][2]=y,p[1][0]=0;
memset(vis,0,sizeof(vis));
vis[x][y]=vis[sx][sy]=1;
while(head<tail)
{
head++;
int xx=p[head][1],yy=p[head][2];
for(int i=0;i<=3;i++)
{
int x1=xx+fx[i],y1=yy+fy[i];
if(num[x1][y1]&&!vis[x1][y1])
{
vis[x1][y1]=1;
p[++tail][0]=p[head][0]+1;
p[tail][1]=x1,p[tail][2]=y1;
}
else if(x1==sx&&y1==sy) d[++tot][1]=x1,d[tot][2]=y1,d[tot][0]=p[head][0],d[tot][3]=(i+2)%4;
}
}
}
inline void SPFA()
{
memset(v,0,sizeof(v));
for(int i=1;i<=tot;i++) dis[d[i][1]][d[i][2]][d[i][3]]=d[i][0],v[d[i][1]][d[i][2]][d[i][3]]=1;
head=0,tail=tot;
while(head<tail)
{
head++;
int x=d[head][1],y=d[head][2];
v[x][y][d[head][3]]=0;
for(int i=0;i<=3;i++)
{
int x1=x+fx[i],y1=y+fy[i];
if(dis[x1][y1][(i+2)%4] > dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1)
{
dis[x1][y1][(i+2)%4]=dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1;
if(!v[x1][y1][(i+2)%4])
{
tail++;
d[tail][1]=x1,d[tail][2]=y1,d[tail][3]=(i+2)%4;
v[x1][y1][(i+2)%4]=1;
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&num[i][j]);
pre();
while(q--)
{
int x,y,sx,sy,tx,ty;
scanf("%d%d%d%d%d%d",&x,&y,&sx,&sy,&tx,&ty);
if(sx==tx&&sy==ty) {cout<<"0\n";continue;}
memset(dis,43,sizeof(dis));
calc(x,y,sx,sy);
SPFA();
ans=dis[0][0][0];
for(int i=0;i<=3;i++) ans=min(ans,dis[tx][ty][i]);
if(ans==dis[0][0][0]) cout<<"-1\n";
else cout<<ans<<"\n";
}
return 0;
}
Vigenère 密码
【问题描述】
16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。Vigenère 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。
在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用C 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 k。 在 Vigenère 密码中,密钥 k 是一个字母串,k=k1k2…kn。当明文 M=m1m2…mn时,得到的密文 C=c1c2…cn,其中 ci=mi®ki,运算®的规则如下表所示:

Vigenère 加密在操作时需要注意:
1. ®运算忽略参与运算的字母的大小写,并保持字母在明文 M 中的大小写形式;
2. 当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。
例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。

【输入】
输入文件名为 vigenere.in。
输入共 2 行。
第一行为一个字符串,表示密钥 k,长度不超过 100,其中仅包含大小写字母。第二行为一个字符串,表示经加密后的密文,长度不超过 1000,其中仅包含大小写字母。
【输出】
输出文件名为 vigenere.out。
输出共 1 行,一个字符串,表示输入密钥和密文所对应的明文。
【输入输出样例】

【数据说明】
对于 100%的数据,输入的密钥的长度不超过 100,输入的密文的长度不超过 1000,且都仅包含英文字母。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int len1, len2;
char s1[10001]; // 秘钥字符串
char s2[10001]; // 密文字符串
void turn(char &x) {
if ('a'<=x && x<='z') { // 将小写字母转为大写字母
x -= 'a'-'A'; // 等同于 x-=32
}
}
int main() {
scanf("%s", s1); // 输入秘钥字符串
len1 = strlen(s1);
for (int i=0; i<len1; i++) { // 等同于 strupr(s1); 将秘钥转为大写字母
turn(s1[i]);
}
scanf("%s", s2); // 输入密文字符串
len2 = strlen(s2);
int j = 0; // 秘钥从头开始解密
for (int i=0; i<len2; i++) { // 密文的每个字符
if (s2[i] <= 'Z') { // 如果密文字符是大写(已知输入密文字符串仅包含大小写字母)
s2[i] -= (s1[j] - 'A');
j++;
if (s2[i] < 'A') { // 若明文小于'A',就从字母表倒叙转换
s2[i] = 'Z' - ('A' - s2[i]) + 1;
}
} else { // 如果密文字符是小写
s2[i] -= s1[j]-'A';
j++;
if (s2[i] < 'a') {
s2[i] = 'z' - ('a' - s2[i]) + 1; // 若明文小于'a',就从字母表倒叙转换
}
}
if (j > len1-1) { // 若明文长度大于秘钥长度,重复使用秘钥
j = 0;
}
}
cout << s2;
return 0;
}
开车旅行
【问题描述】
小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i 的海拔高度为Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即d[i, j] = |Hi − Hj|。
旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 A 和小 B的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 X 公里,他们就会结束旅行。
在启程之前,小 A 想知道两个问题:
1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 0,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
2. 对任意给定的 X=Xi和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。
【输入】
输入文件为 drive.in。
第一行包含一个整数 N,表示城市的数目。
第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即 H1,H2,……,Hn,且每个 Hi都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M,表示给定 M 组 Si和 Xi。
接下来的 M 行,每行包含 2 个整数 Si和 Xi,表示从城市 Si出发,最多行驶 Xi公里。
【输出】
输出文件为 drive.out。
输出共 M+1 行。
第一行包含一个整数 S0,表示对于给定的 X0,从编号为 S0 的城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si 和Xi下小 A 行驶的里程总数和小 B 行驶的里程总数。
【输入输出样例 1】

【输入输出样例 1 说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。
如果从城市 1 出发,可以到达的城市为 2,3,4,这几个城市与城市 1 的距离分别为 1,1,2,但是由于城市 3 的海拔高度低于城市 2,所以我们认为城市 3 离城市 1 最近,城市 2 离城市1 第二近,所以小 A 会走到城市 2。到达城市 2 后,前面可以到达的城市为 3,4,这两个城市与城市 2 的距离分别为 2,1,所以城市 4 离城市 2 最近,因此小 B 会走到城市 4。到达城市 4 后,前面已没有可到达的城市,所以旅行结束。
如果从城市 2 出发,可以到达的城市为 3,4,这两个城市与城市 2 的距离分别为 2,1,由于城市 3 离城市 2 第二近,所以小 A 会走到城市 3。到达城市 3 后,前面尚未旅行的城市为4,所以城市 4 离城市 3 最近,但是如果要到达城市 4,则总路程为 2+3=5>3,所以小 B 会直接在城市 3 结束旅行。
如果从城市 3 出发,可以到达的城市为 4,由于没有离城市 3 第二近的城市,因此旅行还未开始就结束了。
如果从城市 4 出发,没有可以到达的城市,因此旅行还未开始就结束了。
【输入输出样例 2】

【输入输出样例 2 说明】
当 X=7 时,
如果从城市 1 出发,则路线为 1 -> 2 -> 3 -> 8 -> 9,小 A 走的距离为 1+2=3,小 B 走的距离为 1+1=2。(在城市 1 时,距离小 A 最近的城市是 2 和 6,但是城市 2 的海拔更高,视为与城市 1 第二近的城市,所以小 A 最终选择城市 2;走到 9 后,小 A 只有城市 10 可以走,没有第 2 选择可以选,所以没法做出选择,结束旅行)
如果从城市 2 出发,则路线为 2 -> 6 -> 7 ,小 A 和小 B 走的距离分别为 2,4。
如果从城市 3 出发,则路线为 3 -> 8 -> 9,小 A 和小 B 走的距离分别为 2,1。
如果从城市 4 出发,则路线为 4 -> 6 -> 7,小 A 和小 B 走的距离分别为 2,4。
如果从城市 5 出发,则路线为 5 -> 7 -> 8 ,小 A 和小 B 走的距离分别为 5,1。
如果从城市 6 出发,则路线为 6 -> 8 -> 9,小 A 和小 B 走的距离分别为 5,1。
如果从城市 7 出发,则路线为 7 -> 9 -> 10,小 A 和小 B 走的距离分别为 2,1。
如果从城市 8 出发,则路线为 8 -> 10,小 A 和小 B 走的距离分别为 2,0。
如果从城市 9 出发,则路线为 9,小 A 和小 B 走的距离分别为 0,0(旅行一开始就结束了)。
如果从城市 10 出发,则路线为 10,小 A 和小 B 走的距离分别为 0,0。
从城市 2 或者城市 4 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小,但是城市 2 的海拔更高,所以输出第一行为 2。
【数据范围】
对于 30%的数据,有 1≤N≤20,1≤M≤20;
对于 40%的数据,有 1≤N≤100,1≤M≤100;
对于 50%的数据,有 1≤N≤100,1≤M≤1,000;
对于 70%的数据,有 1≤N≤1,000,1≤M≤10,000;
对于 100%的数据,有 1≤N≤100,000,1≤M≤10,000,-1,000,000,000≤Hi≤1,000,000,000,
0≤X0≤1,000,000,000,1≤Si≤N,0≤Xi≤1,000,000,000,数据保证 Hi互不相同。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 2147483647
#define ld long double
#define ll long long
#define N 100010
using namespace std;
int n,m,x,sa,sb,hs,st,nx[N],ls[N],a[N],b[N],c[N],s[N],f[N][19];
ll pra[N][19],prb[N][19];
struct node{int v,id;}h[N];
ld ans=(ld)inf,t;
bool cmp(node x,node y){return x.v<y.v;}
int dis(int x,int y){return abs(h[x].v-h[y].v);}
void get(int x){
b[x]=(ls[x]&&(dis(x,ls[x])<=dis(x,nx[x])||!nx[x]))?ls[x]:nx[x];
if(b[x]==ls[x]){
a[x]=(ls[b[x]]&&(dis(x,ls[b[x]])<=dis(x,nx[x])||!nx[x]))?ls[b[x]]:nx[x];}
else{
a[x]=(ls[x]&&(dis(x,ls[x])<=dis(x,nx[b[x]])||!nx[b[x]]))?ls[x]:nx[b[x]];
}
nx[ls[x]]=nx[x];ls[nx[x]]=ls[x];
}
void work(int s,int x){
sa=sb=0;
for(int i=18;i>=0;i--){
if(x>=pra[s][i]+prb[s][i]){
x-=pra[s][i];x-=prb[s][i];
sa+=pra[s][i];sb+=prb[s][i];
s=f[s][i];
}
}
if(x>=pra[s][0]){x-=pra[s][0];sa+=pra[s][0];}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i].v),h[i].id=i,s[i]=h[i].v;
sort(h+1,h+1+n,cmp);
for(int i=1;i<=n;i++){c[h[i].id]=i;ls[i]=i-1;nx[i]=i+1;}
nx[n]=0;
for(int i=1;i<=n;i++) get(c[i]);
for(int i=1;i<=n;i++){
int x=c[i];
if(b[a[x]]&&a[x])prb[i][0]=abs(h[a[x]].v-h[b[a[x]]].v);
if(a[x]) pra[i][0]=abs(h[x].v-h[a[x]].v);
f[i][0]=h[b[a[x]]].id;
}
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
pra[i][j]=pra[i][j-1]+pra[f[i][j-1]][j-1];
prb[i][j]=prb[i][j-1]+prb[f[i][j-1]][j-1];
}
}
scanf("%d",&x);
for(int i=1;i<=n;i++){
work(i,x);
if(!sb) continue;else t=(ld)sa/sb;
if(ans>t||(ans==t&&s[i]>s[hs])){ans=t;hs=i;}
}
printf("%d\n",hs);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&st,&x);
work(st,x);
printf("%d %d\n",sa,sb);
}
return 0;
}
借教室
【问题描述】
在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份订单,每份订单用三个正整数描述,分别为dj, sj,tj,表示某租借者需要从第sj天到第tj天租借教室(包括第sj天和第tj天),每天需要租借dj个教室。
我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。
现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。
【输入】
输入文件为 classroom.in。
第一行包含两个正整数n, m,表示天数和订单的数量。
第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。
接下来有m行,每行包含三个正整数dj, sj,tj,表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
【输出】
输出文件为 classroom.out。
如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足)输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。
【输入输出样例】

【输入输出样例说明】
第 1 份订单满足后,4 天剩余的教室数分别为 0,3,2,3。第 2 份订单要求第 2 天到
第 4 天每天提供 3 个教室,而第 3 天剩余的教室数为 2,因此无法满足。分配停止,通知第2 个申请人修改订单。
【数据范围】

#include <bits/stdc++.h>
using namespace std;
const int SIZE=2000005;
bool check(int t);
struct node{
int d,s,t;
}a[SIZE];
int r[SIZE],c[SIZE];
int n,m,ans=0;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&r[i]);
for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].d,&a[i].s,&a[i].t);
int L=1,R=m,mid;
while (L<=R){
mid=(L+R)/2;
if (!check(mid)){ //二分搜索
ans=mid;
R=mid-1;
}
else L=mid+1;
}
if (!ans) printf("0");
else printf("-1\n%d",ans);
return 0;
}
bool check(int t)
{
memset(c,0,sizeof(c));
int sum=0;
bool flag=true;
for (int i=1;i<=t;i++){
c[a[i].s]+=a[i].d;
c[a[i].t+1]-=a[i].d; //进行差分检查
}
for (int i=1;i<=n;i++){
sum+=c[i];
if (sum>r[i]){
flag=false;
break;
}
}
return flag;
}
疫情控制
【问题描述】
H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
【输入】
输入文件名为 blockade.in。
第一行一个整数 n,表示城市个数。
接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。
接下来一行一个整数 m,表示军队个数。
接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。
【输出】
输出文件为 blockade.out。
共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
【输入输出样例】

【输入输出样例说明】
第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间为 3 个小时。
【数据范围】
保证军队不会驻扎在首都。

#include <bits/stdc++.h>
using namespace std;
const int Max=50005;
int n,m,size,l,r,mid,tot1,tot2;
int first[Max],num[Max],f[Max][18],d[Max][18],p[Max],vis[Max];
struct bian{int to,next,len;};
bian edge[Max<<1];
struct shu{int id,len;};
shu a[Max],b[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void build(int x,int y,int z)
{
edge[++size].next=first[x];
first[x]=size;
edge[size].to=y,edge[size].len=z;
}
inline void dfs(int point,int fa)
{
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa) continue;
f[to][0]=point,d[to][0]=edge[u].len;
dfs(to,point);
}
}
inline void pre()
{
for(int j=1;j<=16;j++)
for(int i=1;i<=n;i++)
if(f[i][j-1]) f[i][j]=f[f[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[f[i][j-1]][j-1];
}
inline void search(int point,int fa)
{
if(vis[point]) return;
vis[point]=1;int tag=0;
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa) continue;
tag=1;
search(to,point);
vis[point]&=vis[to];
}
if(!tag) vis[point]=0; //叶子节点需特判
}
inline bool comp(const shu &a,const shu &b){return a.len<b.len;}
inline bool check(int mid)
{
tot1=tot2=0;
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=m;i++)
{
int sum=0,x=p[i];
for(int k=16;k>=0;k--)
if(f[x][k]>1&&sum+d[x][k]<=mid) sum+=d[x][k],x=f[x][k];
if(f[x][0]==1&&sum+d[x][0]<=mid) a[++tot1].len=mid-sum-d[x][0],a[tot1].id=x;
else vis[x]=1;
}
search(1,0);
if(vis[1]) return 1;
for(int u=first[1];u;u=edge[u].next)
if(!vis[edge[u].to]) b[++tot2].len=edge[u].len,b[tot2].id=edge[u].to;
sort(a+1,a+tot1+1,comp),sort(b+1,b+tot2+1,comp);
if(tot1<tot2) return 0;
int tag=1;
for(int i=1;i<=tot1;i++)
{
if(!vis[a[i].id]) vis[a[i].id]=1; //题解中的优先覆盖
else if(a[i].len>=b[tag].len) vis[b[tag].id]=1;
while(tag<=tot2&&vis[b[tag].id]) tag++;
if(tag>tot2) return 1;
}
return tag>tot2;
}
int main()
{
n=get_int();
for(int i=1;i<n;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y,z),build(y,x,z);
}
m=get_int();
for(int i=1;i<=m;i++) p[i]=get_int();
dfs(1,0);
pre();
l=0,r=1e9;int tag=0;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) tag=1,r=mid;
else l=mid+1;
}
if(tag) cout<<r<<"\n";
else cout<<"-1\n";
return 0;
}
铺地毯
【问题描述】
为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】
输入文件名为 carpet.in。
输入共 n+2 行。
第一行,一个整数 n,表示总共有 n 张地毯。
接下来的 n 行中,第 i+1 行表示编号 i 的地毯的信息,包含四个正整数 a,b,g,k,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在 x轴和 y 轴方向的长度。
第 n+2 行包含两个正整数 x 和 y,表示所求的地面的点的坐标(x,y)。
【输出】
输出文件名为 carpet.out。
输出共 1 行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出-1。
【输入输出样例 1】

【输入输出样例说明】
如下图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点(2,2)的最上面一张地毯是 3 号地毯。

【输入输出样例 2】

【输入输出样例说明】
如上图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,点(4,5)没有被地毯覆盖,所以输出-1。
【数据范围】
对于 30%的数据,有 n≤2;
对于 50%的数据,0≤a, b, g, k≤100;
对于 100%的数据,有 0≤n≤10,000,0≤a, b, g, k≤100,000。
#include<iostream>
using namespace std;
int ditan[1000005][5];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=4;j++)
{
cin>>ditan[i][j];
}
}
int x,y,flag=0;
cin>>x>>y;
for(int i=n;i>=1;i--)
{
if(ditan[i][1]<=x&&ditan[i][1]+ditan[i][3]>=x&&ditan[i][2]<=y&&ditan[i][2]+ditan[i][4]>=y)//判断是否覆盖此点
{
cout<<i<<endl;
flag=1;
break;
}
}
if(!flag) cout<<"-1"<<endl;
return 0;
}
选择客栈
【问题描述】
丽江河边有 n 家很有特色的客栈,客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰(总共 k 种,用整数 0 ~ k-1 表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过 p。
他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。
【输入】
输入文件 hotel.in,共 n+1 行。
第一行三个整数 n,k,p,每两个整数之间用一个空格隔开,分别表示客栈的个数,色调的数目和能接受的最低消费的最高值;
接下来的 n 行,第 i+1 行两个整数,之间用一个空格隔开,分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。
【输出】
输出文件名为 hotel.out。
输出只有一行,一个整数,表示可选的住宿方案的总数。
【输入输出样例 1】

【输入输出样例说明】

2 人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,
但是若选择住 4、5 号客栈的话,4、5 号客栈之间的咖啡店的最低消费是 4,而两人能承受的最低消费是 3 元,所以不满足要求。因此只有前 3 种方案可选。
【数据范围】
对于 30%的数据,有 n≤100;
对于 50%的数据,有 n≤1,000;
对于 100%的数据,有 2≤n≤200,000,0<k≤50,0≤p≤100, 0≤最低消费≤100。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=2e6+10;
4 const int maxc=55;
5 int n,k,p;
6 long long ans;
7 int clo[maxn],val[maxn];
8 int closum[maxc],last[maxn];
9 int main()
10 {
11 scanf("%d%d%d",&n,&k,&p);
12 for(int i=1;i<=n;++i)scanf("%d%d",clo+i,val+i);
13 last[n+1]=0x7fffffff;
14 for(int i=n;i>0;--i)last[i]=val[i]<=p?i:last[i+1];
15 int cur=n;
16 for(int i=n-1;i>=1;--i)
17 {
18 while(cur>=last[i]&&cur>i)
19 {
20 closum[clo[cur]]++;
21 --cur;
22 }
23 ans+=closum[clo[i]];
24
25 }
26 cout<<ans;
27 return 0;
28 }