信息学奥赛-提高级 题库
飞扬的小鸟
【问题描述】
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;
}
寻找道路
【问题描述】
在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
2.在满足条件 1 的情况下使路径最短。
注意:图 G 中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。
【输入】
输入文件名为 road.in。
第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x、y,之间用一个空格隔开,表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s、t,表示起点为 s,终点为 t。
【输出】
输出文件名为 road.out。
输出只有一行,包含一个整数,表示满足题目᧿述的最短路径的长度。如果这样的路径不存在,输出-1。
【输入输出样例 1】

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通,所以满足题目描述的路径不存在,故输出-1。
【输入输出样例 2】

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2连了一条边到点 6,而点 6 不与终点 5 连通。
【数据说明】

#include<bits/stdc++.h>
#define ll long long
#define MAXN 500010
#define N 201
#define INF 0x7f7f7f7f
#define gtc() getchar()
using namespace std;
template <class T>
inline void read(T &s){
s = 0; T w = 1, ch = gtc();
while(!isdigit(ch)){if(ch == '-') w = -1; ch = gtc();}
while(isdigit(ch)){s = s * 10 + ch - '0'; ch = gtc();}
s *= w;
}
template <class T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar(x % 10 + '0');
}
struct node{
int y, ne, z;
}e[MAXN];
int lin[MAXN], len = 0;
inline void add(int x, int y, int z){
e[++len].y = y, e[len].ne = lin[x], lin[x] = len;
e[len].z = z;
}
int n, m;
int st, ed;
int col[MAXN], vis[MAXN];
void bfs(int u){
queue<int> q;
q.push(u);
vis[u] = 1;
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = lin[x]; i; i = e[i].ne){
int y = e[i].y;
if(e[i].z == 1) continue;
if(vis[y]) continue;
vis[y] = 1;
q.push(y);
}
}
}
void bfs2(int u){//这个不是bfs,之前写错写成bfs,后来直接在这个函数里改了。
col[u] = 1;
for(int i = lin[u]; i; i = e[i].ne){
int y = e[i].y;
if(e[i].z == 1) continue;
if(col[y]) continue;
col[y] = 1;
q.push(y);
}
}
int dis[MAXN];
void bfs3(int u){
memset(dis, INF, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = lin[x]; i; i = e[i].ne){
int y = e[i].y;
if(e[i].z == 2) continue;
if(col[y]) continue;
if(dis[y] != INF) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
int main()
{
read(n), read(m);
int x, y;
for(int i = 1; i <= m; ++i){
read(x), read(y);
add(x, y, 1); add(y, x, 2);//1为正边,2为负边
}
read(st), read(ed);
bfs(ed);
for(int i = 1; i <= n; ++i){
if(!vis[i]){
bfs2(i);
}
}
bfs3(st);
if(dis[ed] == INF) puts("-1");
else printf("%d\n", dis[ed]);
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;
}
国王游戏
【问题描述】
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
【输入】
输入文件为 game.in。
第一行包含一个整数 n,表示大臣的人数。
第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
【输出】
输出文件名为 game.out。
输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
【输入输出样例】

【输入输出样例说明】
按 1、2、3 号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 1、3、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 2、1、3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 2、3、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9;
按 3、1、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 3、2、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9。
因此,奖赏最多的大臣最少获得 2 个金币,答案输出 2。
【数据范围】
对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8;
对于 40%的数据,有 1≤ n≤20,0 < a、b < 8;
对于 60%的数据,有 1≤ n≤100;
对于 60%的数据,保证答案不超过
对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int len = 1;//表示高精度数据的长度
int sum[100001] = {0,1};//高精度数据计算结果
struct minister{
ll left;
ll right;
} m[1000001];
bool cmp(minister a,minister b){
return a.left * a.right < b.left * b.right;
}
void multiplicative(ll x){//高精度乘法
for(int i = 1;i <= len; i++){
sum[i] *= x; //各位数乘x,如1111×20 = (1000+100+10+1)×20
}
for(int i = 1;i <= len; i++){
sum[i + 1] += sum[i] / 10;//获得进位,因为相乘结果可能为 10 3 13 4,需转化为 1 0 4 3 4
sum[i] %= 10;
}
len++;//因为是sum[i+1],所以肯定会计算到sum[len+1],所以需要len++
while(sum[len] / 10){//观察最高位是否有进位,因为可能有经过前面的操作后可能有 100 3的情况
sum[len + 1] = sum[len] / 10;
sum[len] %= 10;
len++;
}
//经过前面的一波操作后,最后可能会导致sum[len]的位置上有0,若为0则需要消除
if(sum[len] == 0)
len--;
}
void division(){//高精度除法,这里只需要进行一次操作,所以不需要参数
//思路依旧很简单,如2345/5=(2000+300+40+5)/5,小学生除法
//->2 3 4 5 ->0 23(3 + 2%5*10) 4 5 -> 0 4 34(4 + 23%5*10) 5 -> 0 4 6 45(5 + 34%5*10)
for(int i = len; i >= 1; i--){
sum[i - 1] += (sum[i] % m[n].right * 10);
sum[i] /= m[n].right;
}
//这波操作必然导致一堆前导0,需消除
while(!sum[len]){
len--;
}
//防止除完了
if(len == 0) cout << "1" << endl;
}
int main(){
cin >> n;
cin >> m[0].left >> m[0].right;
for(int i = 1;i <= n; i++)
cin >> m[i].left >> m[i].right;
sort(m + 1, m + 1 + n, cmp);
for(int i = 0;i < n; i++){
multiplicative(m[i].left);
}
division();
for(int i = len; i >= 1; i--)
cout << sum[i];
}
开车旅行
【问题描述】
小 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;
}
同余方程
【问题描述】
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
【输入】
输入文件为 mod.in。
输入只有一行,包含两个正整数 a, b,用一个空格隔开。
【输出】
输出文件为 mod.out。
输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。
【输入输出样例】

【数据范围】
对于 40%的数据,2 ≤b≤ 1,000;
对于 60%的数据,2 ≤b≤ 50,000,000;
对于 100%的数据,2 ≤a, b≤ 2,000,000,000。
#include <stdio.h>
long long a,b,x,y,k;
void exgcd(long long a,long long b)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b);
long long int temp_x = x;
x=y;
y = temp_x - a/b *y;
return;
}
int main()
{
scanf("%lld %lld\n",&a,&b);
exgcd(a,b);
x = (x%b + b)%b;
printf("%lld\n",x);
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 }
Mayan 游戏
【问题描述】
Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行 5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:
1、 每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图 6 到图 7);如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图 1 和图 2);

2、 任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参见图 1 到图 3)。
注意:
a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图 4,三个颜色为 1 的方块和三个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块)。
b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除(例如下面图 5 所示的情形,5 个方块会同时被消除)。
3、 方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。
上面图 1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0, 0),将位于(3, 3)的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态,此时在一竖列上有连续三块颜色为 4 的方块,满足消除条件,消除连续 3 块颜色为 4 的方块后,上方的颜色为 3 的方块掉落,形成图 3 所示的局面。
【输入】
输入文件 mayan.in,共 6 行。
第一行为一个正整数 n,表示要求游戏通关的步数。
接下来的 5 行,描述 7*5 的游戏界面。每行若干个整数,每两个整数之间用一个空格隔开,每行以一个 0 结束,自下向上表示每竖列方块的颜色编号(颜色不多于 10 种,从 1 开始顺序编号,相同数字表示相同颜色)。
输入数据保证初始棋盘中没有可以消除的方块。
【输出】
输出文件名为 mayan.out。
如果有解决方案,输出 n 行,每行包含 3 个整数 x,y,g,表示一次移动,每两个整数之间用一个空格隔开,其中(x,y)表示要移动的方块的坐标,g 表示移动的方向,1 表示向右移动,-1 表示向左移动。注意:多组解时,按照 x 为第一关健字,y 为第二关健字,1优先于-1,给出一组字典序最小的解。游戏界面左下角的坐标为(0,0)。
如果没有解决方案,输出一行,包含一个整数-1。
【输入输出样例 1】

【输入输出样例说明】
按箭头方向的顺序分别为图 6 到图 11

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是:(2,1)处的方格向右移动,(3,1)处的方格向右移动,(3,0)处的方格向右移动,最后可以将棋盘上所有方块消除。
【数据范围】
对于 30%的数据,初始棋盘上的方块都在棋盘的最下面一行;
对于 100%的数据,0 < n≤5。
int main()
{
//freopen("mayan.in","r",stdin);
//freopen("mayan.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=5;i++)
{
for(int j=1;j<=8;j++)
{
int x;scanf("%d",&x);
if(x==0)break;//毒瘤出题人弄我输入我去
map[i][j]=x;
}
}
memset(ans,-1,sizeof(ans));
dfs(1);
printf("-1\n");//没有解输出-1.直接输出只能有20分
return 0;
}
计算系数
【问题描述】
给定一个多项式
请求出多项式展开后
项的系数。
【输入】
输入文件名为 factor.in。
共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。
【输出】
输出文件名为 factor.out。
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取模后的结果。
【输入输出样例】

【数据范围】
对于 30%的数据,有 0≤k≤10;
对于 50%的数据,有 a = 1,b = 1;
对于 100%的数据,有 0≤k≤1,000,0≤n, m≤k,且 n + m = k,0≤a,b≤1,000,000。
#include<iostream>
using namespace std;
long long mod=10007;
long long Mood(long long a,long long b){
long long sum=1;
a%=mod;
while(b){
if(b&1)
sum=sum*a%mod;
a=a*a%mod;
b=b>>1;
}
return sum;
}
int a,b,k,n,m;
long long ans=0;
int main(){
cin>>a>>b>>k>>n>>m;
ans=Mood(a,n)*Mood(b,m)%mod;
for(int i=1,j=k;i<=n;i++,j--){//逆元
ans=ans*j%mod;
ans=ans*Mood(i,mod-2)%mod;
}
cout<<ans<<endl;
return 0;
}