信息学奥赛-提高级 题库
铺设道路
【问题描述】
春春是一名道路工程师,负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di 。
春春每天可以选择一段连续区间 [L, R] ,填充这段区间中的每块区域,让其下陷深度减少 1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 。
春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0 。
【输入格式】
输入文件名为 road.in。
输入文件包含两行,第一行包含一个整数 n,表示道路的长度。
第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。
【输出格式】
输出文件名为 road.out。
输出文件仅包含一个整数,即最少需要多少天才能完成任务。
【输入输出样例 1】

【样例解释】
一种可行的最佳方案是,依次选择:
[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。
【数据规模与约定】
对于 30% 的数据,1 ≤ n ≤ 10 ;
对于 70% 的数据,1 ≤ n ≤ 1000 ;
对于 100% 的数据,1 ≤ n ≤ 100000 ,0 ≤ di ≤ 10000 。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int ans,d[100001],N;
int partition1(int left, int right) //分治(实现这一片区域的操作)
{ int sum1=0;
if(left>=right) //当不能再分时返回
{
if(left==right) //如果区域是单个数
{ int t=d[left];
d[left]=0; //清0
return t; //直接返回里面的值(它里面的值代表这个单个区域需要的天数)
}
else
return 0;
}
int min1=inf,l=left;
for (int i=left; i<=right;i++) //求出这片区域的最小值
min1=min(d[i],min1);
sum1+=min1;//先把最小值加上
for(int i=left; i<=right; i++)
{ d[i]-=min1; //每个都减去最小值
if(d[i]==0&&d[i-1]!=0) //如果遇到0分界线
{
sum1+=partition1(l,i-1);//把之前的区域分治
}
if(d[i]!=0&&d[i-1]==0) l=i;//如果在0之后遇到新的左端点,更新
}
if(d[right]!=0)//不要忘掉最后一块区域
sum1+=partition1(l,right);
return sum1;
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>N;
for(int i=1;i<=N;i++)
cin>>d[i];
ans=partition1(1,N);
cout<<ans;
return 0;
}
货币系统
【问题描述】
在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作 (n,a)。
在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b),满足(m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的 m。
【输入格式】
输入文件名为 money.in。
输入文件的第一行包含一个整数 T,表示数据的组数。接下来按照如下格式分别给出 T 组数据。
每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数a[i]。
【输出格式】
输出文件名为 money.out。
输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等价的货币系统 (m,b) 中,最小的 m。
【输入输出样例 1】

【输入输出样例 1 说明】
在第一组数据中,货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价,并可以验证不存在 m < 2 的等价的货币系统,因此答案为 2。
在第二组数据中,可以验证不存在 m < n 的等价的货币系统,因此答案为 5。
【数据规模与约定】

对于 100% 的数据,满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 25005
using namespace std;
bool dp[N]={0};
int a[103]={0};
int T=0,n=0;
int ret=0;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
ret=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(dp[a[i]])
continue;
ret++;
for(int j=a[i];j<=a[n];j++)
{
dp[j]|=dp[j-a[i]];
}
}
cout<<ret<<endl;
}
return 0;
}
赛道修建
【问题描述】
C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建m 条赛道。
C 城一共有 n 个路口,这些路口编号为 1,2, … , n,有 n − 1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为 ai和 bi,该道路的长度为 li。借助这 n − 1 条道路,从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e1, e2, … , ek,满足可以从某个路口出发,依次经过道路 e1, e2, … , ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。
【输入格式】
输入文件名为 track.in。
输入文件第一行包含两个由空格分隔的正整数 n, m,分别表示路口数及需要修建的赛道数。
接下来 n − 1 行,第 i 行包含三个正整数 ai, bi, li,表示第 i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n − 1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
【输出格式】
输出文件名为 track.out。
输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。
【输入输出样例 1】

【输入输出样例 1 说明】
所有路口及适合于修建赛道的道路如下图所示:

道路旁括号内的数字表示道路的编号,非括号内的数字表示道路长度。
需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道(从路口 4 到路口 7),则该赛道的长度为 9 + 10 + 5 + 7 = 31,为所有方案中的最大值。
【输入输出样例 2】

【输入输出样例 2 说明】
所有路口及适合于修建赛道的道路如下图所示:

需要修建 3 条赛道。可以修建如下 3 条赛道:
1. 经过第 1,6 条道路的赛道(从路口 1 到路口 7),长度为 6 + 9 = 15;
2. 经过第 5,2,3,8 条道路的赛道(从路口 6 到路口 9),长度为 4 + 3 + 5 + 4 = 16;
3. 经过第 7,4 条道路的赛道(从路口 8 到路口 5),长度为 7 + 10 = 17。
长度最小的赛道长度为 15,为所有方案中的最大值。
【数据规模与约定】
所有测试数据的范围和特点如下表所示

其中,“分支不超过 3”的含义为:每个路口至多有 3 条道路与其相连。对于所有的数据,2 ≤ n≤ 50,000,1 ≤ m ≤ n − 1,1 ≤ ai, bi ≤ n,1 ≤ li ≤ 10,000。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
int head[50100],to[100100],nex[100100],val[100100];
int n,waysnumber,m,edges;
multiset <int> :: iterator it;
int dfs(int now,int father,int x){
multiset <int> son;
for (int v = head[now]; v ; v = nex[v])
if (to[v] != father){
int tmpways = dfs(to[v],now,x) + val[v];
if (tmpways >= x) ++waysnumber;
else son.insert(tmpways);
}
//对当前点now的所有子路径进行组合,用刚好能满足≥x的最小的边组合
//并返回所有儿子中最长的无法被组合成满足条件路的点
int maxwaylen = 0;
while (son.size() > 1){
it = son.lower_bound(x - *son.begin());
if (it == son.begin()) it++; //若最短的边≥x的时候,则用最短的两条边组合
if (it == son.end()){ //当前最短的边没办法找到够长的边组合出满足条件的路
//挑一条最长的子边返回
maxwaylen = max(maxwaylen,*son.begin());
son.erase(son.begin());
}
else{
//成功组合出了满足条件的边
++waysnumber;
son.erase(it);
son.erase(son.begin());
}
}
if (son.size() == 1) maxwaylen = max(maxwaylen,*son.begin());
return maxwaylen;
}
bool check(int x){
waysnumber = 0;
dfs(1,0,x);
if (waysnumber >= m) return true;
else return false;
}
void addedge(int u,int v,int c){
nex[++edges] = head[u], head[u] = edges, to[edges] = v, val[edges] = c;
}
int main()
{
edges = 0;
scanf("%d%d",&n,&m);
long long all = 0;
for (int i = 1 ; i < n ; ++i){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
all += c;
}
int l = 0 , r = all / m,mid,ans; //这里存在一个坑,对于ai = 1的图,如果这里的 r 使用极大值500000000,就会超时
while (l <= r){
mid = (l + r) >> 1;
if (check(mid)) ans = mid,l = mid + 1;
else r = mid - 1;
}
printf("%d\n",ans);
return 0;
}
旅行
【问题描述】
小 Y 是一个爱好旅行的 OIer。她来到 X 国,打算将各个城市都玩一遍。
小 Y 了解到,X 国的n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路,也不存在一条连接一个城市和它本身的道路。并且,从任意一个城市出发,通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。
小 Y 的旅行方案是这样的:任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y 回到起点时,她可以选择结束这次旅行或继续旅行。需要注意的是,小 Y 要求在旅行方案中,每个城市都被访问到。
为了让自己的旅行更有意义,小 Y 决定在每到达一个新的城市(包括起点)时,将它的编号记录下来。她知道这样会形成一个长度为n 的序列。她希望这个序列的字典序最小,你能帮帮她吗?
对于两个长度均为 n 的序列 A 和 B,当且仅当存在一个正整数 x,满足以下条件时,我们说序列 A 的字典序小于 B。
⚫ 对于任意正整数 1 ≤ i < x,序列 A 的第 i 个元素 Ai 和序列 B 的第 i 个元素Bi 相同。
⚫ 序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。
【输入格式】
输入文件名为 travel.in。
输入文件共 m + 1 行。第一行包含两个整数 n, m(m ≤ n) ,中间用一个空格分隔。
接下来 m 行,每行包含两个整数 u, v (1 ≤ u, v ≤ n) ,表示编号为 u 和 v 的城市之间有一条道路,两个整数之间用一个空格分隔。
【输出格式】
输出文件名为 travel.out。
输出文件包含一行,n 个整数,表示字典序最小的序列。相邻两个整数之间用一个空格分隔。
【输入输出样例 1】

【输入输出样例 2】

【数据规模与约定】
对于 100% 的数据和所有样例,1 ≤ n ≤ 5000 且 m = n − 1 或 m = n 。
对于不同的测试点,我们约定数据的规模如下:

#include<bits/stdc++.h>
#define maxn 50500
using namespace std;
inline int read() {
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,m,cnt,del;
int ans[maxn],start[maxn],to[maxn],cur[maxn];
vector<int> v[maxn];
inline bool check() {
if(cnt != n) return false;
for(int i=1;i<=n;i++) if(cur[i]!=ans[i]) return ans[i]>cur[i];
}
void dfs(int u,int f) {
if(cnt>n) return ;
cur[++cnt]=u;
for(int i=0;i<v[u].size();i++) {
if(v[u][i]==f || (u==start[del]&&v[u][i]==to[del]) || (v[u][i]==start[del]&&u==to[del])) continue;
dfs(v[u][i],u);
}
}
int main() {
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
memset(ans,64,sizeof(ans));
n=read(),m=read();
for(int i=1;i<=m;i++) {
int x=read(),y=read();
v[x].push_back(y);
v[y].push_back(x);
start[i]=x;to[i]=y;
}
for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
if(m==n-1) {
del=0;cnt=0;
dfs(1,0);
memcpy(ans,cur,sizeof(cur));
} else {
for(int i=1;i<=m;i++) {
memset(cur,0,sizeof(cur));
del=i;cnt=0;
dfs(1,0);
if(check() ) {
memcpy(ans,cur,sizeof(cur));
}
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
填数游戏
【问题描述】
小 D 特别喜欢玩游戏。这一天,他在玩一款填数游戏。
这个填数游戏的棋盘是一个n × m的矩形表格。玩家需要在表格的每个格子中填入一个数字(数字 0 或者数字 1),填数时需要满足一些限制。
下面我们来具体描述这些限制。
为了方便描述,我们先给出一些定义:
• 我们用每个格子的行列坐标来表示一个格子,即(行坐标,列坐标)。(注意:行列坐标均从 0 开始编号)
• 合法路径 P:一条路径是合法的当且仅当:
1. 这条路径从矩形表格的左上角的格子(0,0)出发,到矩形的右下角格子(n − 1, m − 1)结束;
2. 在这条路径中,每次只能从当前的格子移动到右边与它相邻的格子,或者从当前格子移动到下面与它相邻的格子。
例如:在下面这个矩形中,只有两条路径是合法的,它们分别是p1:(0,0) → (0,1) →(1,1)和p2:(0,0) → (1,0) → (1,1)。

对于一条合法的路径 P,我们可以用一个字符串w(P)来表示,该字符串的长度为n +m − 2,其中只包含字符“R”或者字符“D”,第 i 个字符记录了路径 P 中第 i 步的移动方法,“R”表示移动到当前格子右边与它相邻的格子,“D”表示移动到当前格子下面与它相邻的格子。例如,上图中对于路径p1,有w(P1) = "RD";而对于另一条路径p2,有w(P2) = "DR"。
同时,将每条合法路径 P 经过的每个格子上填入的数字依次连接后,会得到一个长度为n + m − 1的 01 字符串,记为 s(P)。例如,如果我们在格子(0,0)和(1,0)上填入数字0,在格子(0,1)和(1,1)上填入数字 1(见上图红色数字)。那么对于路径p1,我们可以得到s(P1) = "011",对于路径p2,有s(P2) = "001"。
游戏要求小 D 找到一种填数字 0、1 的方法,使得对于两条路径p1,P2,如果w(P1) >w(P2),那么必须s(P1) ≤ s(P2)。我们说字符串 a 比字符串 b 小,当且仅当字符串 a 的字典序小于字符串 b 的字典序,字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心,小 D 更想知道这个游戏有多少种玩法,也就是说,有多少种填数字的方法满足游戏的要求?
小 D 能力有限,希望你帮助他解决这个问题,即有多少种填 0、1 的方法能满足题目要求。由于答案可能很大,你需要输出答案对109 + 7取模的结果。
【输入格式】
输入文件名为 game.in。
输入文件共一行,包含两个正整数 n、m,由一个空格分隔,表示矩形的大小。其中 n 表示矩形表格的行数,m 表示矩形表格的列数。
【输出格式】
输出文件名为 game.out。
输出共一行,包含一个正整数,表示有多少种填 0、1 的方法能满足游戏的要求。
注意:输出答案对 10^9+7 取模的结果。
【输入输出样例 1】

【样例解释】

对于2 × 2棋盘,有上图所示的 12 种填数方法满足要求。
【输入输出样例 2】

【输入输出样例 3】

【数据规模与约定】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define P 1000000007
using namespace std;
int n,m,inv128=570312504,inv384=190104168;
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1ll*x*y%P;}
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
if(n==1) printf("%d\n",power(2,m));
else if(n==2) printf("%d\n",mul(4,power(3,m-1)));
else if(n==3) printf("%d\n",mul(112,power(3,m-3)));
else{
if(m==n) printf("%d\n",(83ll*power(8,n)%P+5ll*power(2,n+7)%P)*inv384%P);
else printf("%d\n",(83ll*power(8,n)%P+power(2,n+8))*power(3,m-n-1)%P*inv128%P);
}
return 0;
}
奶酪
【问题描述】
现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为z = 0,奶酪的上表面为z = h。
现在,奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交,Jerry 则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?

【输入格式】
输入文件名为 cheese.in。
每个输入文件包含多组数据。
输入文件的第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。
接下来是 T 组数据,每组数据的格式如下:
第一行包含三个正整数 n,h 和 r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。
接下来的 n 行,每行包含三个整数 x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(x, y, z)。
【输出格式】
输出文件名为 cheese.out。
输出文件包含 T 行,分别对应 T 组数据的答案,如果在第 i 组数据中,Jerry 能从下
表面跑到上表面,则输出“Yes”,如果不能,则输出“No”(均不包含引号)。
【输入输出样例 1】

【输入输出样例 1 说明】

【数据规模与约定】
对于 20%的数据,n = 1,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 40%的数据,1 ≤ n ≤ 8, 1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 80%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 1,000,000,000,T ≤ 20,坐标的绝对值不超过 1,000,000,000。
#include<bits/stdc++.h>
#define rg register int
using namespace std;
long long T, n, h, r, x[1005], y[1005], z[1005], f[1005][1005], bz[1005], ans;
int dist(int i, int j) {
double s = sqrt((x[i] - x[j]) * 1.0 * (x[i] -x [j])*1.0 + (y[i] - y[j]) * 1.0 * (y[i] - y[j])*1.0 + (z[i] - z[j]) * 1.0 * (z[i] -z [j]) * 1.0) * 1.0;
if (s > (int)s) s++;
return s;
}
void dfs(int x) {
if (x == n + 1) {
ans = 1;
return;
}
bz[x] = 1;
for (rg i = 1; i <= n + 1; i++)
if (f[x][i] && (!bz[i])) {
dfs(i);
if (ans == 1)
return;
}
}
int main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &h, &r), ans = 0;
for (rg i = 1; i <= n; i++)
scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
for (rg i = 0; i <= n; i++)
for(rg j = i + 1; j <= n+1; j++)
f[i][j] = f[j][i] = 0;
for (rg i = 1; i <= n; i++)
for (rg j = i + 1; j <= n; j++)
if (dist(i,j) <= r * 2) f[i][j] = f[j][i] = 1;
for (rg i = 1; i <= n; i++) {
bz[i] = 0;
if (h - z[i] <= r) f[i][n + 1] = f[n + 1][i] = 1;
if (z[i] <= r) f[i][0] = f[0][i] = 1;
}
dfs(0);
if (ans) printf("Yes\n");
else printf("No\n");
}
return 0;
}
列队
【问题描述】
Sylvia 是一个热爱学习的女孩子。
前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。Sylvia所在的方阵中有n × m名学生,方阵的行数为 n,列数为 m。
为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 1 到 n × m 编上了号码(参见后面的样例)。
即:初始时,第 i 行第 j 列的学生的编号是(i − 1) × m + j。
然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x, y) (1≤x≤n, 1≤y≤m)描述,表示第 x 行第 y 列的学生离队。
在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:
1. 向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条指令之后,空位在第 x 行第 m 列。
2. 向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条指令之后,空位在第 n 行第 m 列。
教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后,下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 n 行第 m 列一个空位,这时这个学生会自然地填补到这个位置。
因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学的编号是多少。
注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。
【输入格式】
输入文件名为 phalanx.in。
输入共 q+1 行。
第 1 行包含 3 个用空格分隔的正整数 n, m, q,表示方阵大小是 n 行 m 列,一共发生了 q 次事件。
接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x, y,用一个空格分隔,表示这个离队事件中离队的学生当时排在第 x 行第 y 列。
【输出格式】
输出文件名为 phalanx.out。
按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学生的编号。
【输入输出样例 1】

【输入输出样例 1 说明】

列队的过程如上图所示,每一行描述了一个事件。
在第一个事件中,编号为 1 的同学离队,这时空位在第一行第一列。接着所有同学向左标齐,这时编号为 2 的同学向左移动一步,空位移动到第一行第二列。然后所有同学向上标齐,这时编号为 4 的同学向上一步,这时空位移动到第二行第二列。最后编号为 1 的同学返回填补到空位中。
【数据规模与约定】

数据保证每一个事件满足 1≤x≤n,1≤y≤m。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=300005;
int n,m,q,sum,tot;
int tree[Max*20],lc[Max*20],rc[Max*20],rt[Max];
vector<ll>num[Max];
inline int get_int()
{
int x=0;char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
inline void print(ll x)
{
if(x>9) print(x/10);
putchar('0'+x%10);
}
inline void add(int &now,int l,int r,int pos)
{
if(!now) now=++tot;tree[now]++;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) add(lc[now],l,mid,pos);
else add(rc[now],mid+1,r,pos);
}
inline int Q(int root,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>1,sum=(mid-l+1)-tree[lc[root]];
if(sum>=k) Q(lc[root],l,mid,k);
else Q(rc[root],mid+1,r,k-sum);
}
inline ll Qr(int x,ll v)
{
int pos=Q(rt[n+1],1,sum,x);add(rt[n+1],1,sum,pos);
ll ans=pos<=n?(ll)m*pos:num[n+1][pos-n-1];
return num[n+1].push_back(v?v:ans),ans;
}
inline ll Ql(int x,int y)
{
int pos=Q(rt[x],1,sum,y);add(rt[x],1,sum,pos);
ll ans=pos<m?(ll)(x-1)*m+pos:num[x][pos-m];
return num[x].push_back(Qr(x,ans)),ans;
}
int main()
{
n=get_int(),m=get_int(),q=get_int(),sum=max(n,m)+q;
while(q--)
{
int x=get_int(),y=get_int();
if(y==m) print(Qr(x,0)),putchar('\n');
else print(Ql(x,y)),putchar('\n');
}
return 0;
}
信息传递
【问题描述】
有 n 个同学(编号为 1 到 n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为Ti的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
【输入格式】
输入文件名为 message.in。
输入共 2 行。
第 1 行包含 1 个正整数 n,表示 n 个人。
第 2 行包含 n 个用空格隔开的正整数 T1, T2, … … , Tn,其中第i 个整数Ti表示编号为 i
的同学的信息传递对象是编号为 Ti 的同学, Ti ≤ n 且 Ti ≠ i。
数据保证游戏一定会结束。
【输出格式】
输出文件名为 message.out。
输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。
【输入输出样例 1】

【输入输出样例 1 说明】

游戏的流程如图所示。当进行完第 3 轮游戏后,4 号玩家会听到 2 号玩家告诉他自己的生日,所以答案为 3。当然,第 3 轮游戏后,2 号玩家、3 号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。
【数据规模与约定】
对于 30%的数据,n ≤ 200;
对于 60%的数据,n ≤ 2500;
对于 100%的数据,n ≤ 200000。
#include <bits/stdc++.h>
using namespace std;
const int maxn=200010;
int n, fa[maxn],ans=0x3f3f3f3f;
int get(int x, int &cnt){
cnt++;
if(fa[x]==x)return x;
else return get(fa[x], cnt);
}
int main () {
cin>>n;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=n;i++) {
int cnt=0,f;
cin>>f;
if(get(f,cnt)==i){
ans=min(ans,cnt);
}else{
fa[i]=f;
}
}
cout<<ans;
return 0;
}
跳石头
【问题描述】
一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 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;
}
运输计划
【问题描述】
公元 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;
}
火柴排队
【问题描述】
涵涵有两盒火柴,每盒装有 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;
}
积木大赛
【题目描述】
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为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;
}