信息学奥赛-入门级 题库
从 1 到 2018 这 2018 个数中,共有__________个包含数字 8 的数。
包含数字 8 的数是指有某一位是“8”的数, 例如“2018”与“188”。
答:544
#include <cstdio>
char st[100];
int main() {
scanf("%s", st);
for (int i = 0; st[i]; ++i) {
if ('A' <= st[i] && st[i] <= 'Z')
st[i] += 1;
}
printf("%s\n", st);
return 0;
}
输入:QuanGuoLianSai
输出:_________
答:RuanHuoMianTai
#include <cstdio>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf("%d", res);
return 0;
}
输入:15
输出:_________
答:4
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
if (n == 0) return m;
if (m == 0) return n % 3;
return findans(n - 1, m) - findans(n, m - 1) + findans(n -
1, m - 1);
}
int main(){
cin >> n >> m;
cout << findans(n, m) << endl;
return 0;
}
输入:5 6
输出:_________
答:8
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", d + i);
v[i] = false;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!v[i]) {
for (int j = i; !v[j]; j = d[j]) {
v[j] = true;
}
++cnt;
}
}
printf("%d\n", cnt);
return 0;
}
输入:10 7 1 4 3 2 5 9 8 0 6
输出:_________
答:6
(最大公约数之和)下列程序想要求解整数n的所有约数两两之间最大公约数的和对10007求余后的值,试补全程序。(第一空 2 分,其余 3 分)
举例来说,4的所有约数是1,2,4。1和2的最大公约数为1;2和4的最大公约数为2;1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。
要求 getDivisor 函数的复杂度为0
函数的复杂度为0(log max(a, b))。
#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {
len = 0;
for (int i = 1; (1) <= n; ++i)
if (n % i == 0) {
a[++len] = i;
if ( (2) != i) a[++len] = n / i;
}
}
int gcd(int a, int b) {
if (b == 0) {
(3) ;
}
return gcd(b, (4) );
}
int main() {
cin >> n;
getDivisor();
ans = 0;
for (int i = 1; i <= len; ++i) {
for (int j = i + 1; j <= len; ++j) {
ans = ( (5) ) % P;
}
}
cout << ans << endl;
return 0;
}
(1)i * i
(2) n / i
(3)return a
(4)a % b
(5)ans + gcd(a[i], a[j])
对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令qi为第i个位置之后第一个比pi值更大的位置,如果不存在这样的位置,则qi = n +1。
举例来说,如果n = 5且p为1 5 4 2 3,则q为2 6 6 5 6。
下列程序读入了排列p,使用双向链表求解了答案。试补全程序。(第二空2 分,其余 3 分)
数据范围 1 ≤ n ≤ 10^5。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
(1) ;
}
for (int i = 1; i <= n; ++i) {
R[i] = (2) ;
L[i] = i - 1;
}
for (int i = 1; i <= n; ++i) {
L[ (3) ] = L[a[i]];
R[L[a[i]]] = R[ (4) ];
}
for (int i = 1; i <= n; ++i) {
cout << (5) << " ";
}
cout << endl;
return 0;
}
(1)a[x] = i
(2)i + 1
(3)R[a[i]]
(4)a[i]
(5)R[i]
标题统计
【问题描述】
凯凯刚写了一篇美妙的作文,请问这篇作文的标题中有多少个字符?
注意:标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字
符数时,空格和换行符不计算在内。
【输入格式】
输入文件名为 title.in。
输入文件只有一行,一个字符串 s。
【输出格式】
输出文件名为 title.out。
输出文件只有一行,包含一个整数,即作文标题的字符数(不含空格和换行符)。
【输入输出样例 1】

【输入输出样例 1 说明】
标题中共有 3 个字符,这 3 个字符都是数字字符。
【输入输出样例 2】

【输入输出样例 2 说明】
标题中共有 5 个字符,包括 1 个大写英文字母,1 个小写英文字母和 2 个数字字符,
还有 1 个空格。由于空格不计入结果中,故标题的有效字符数为 4 个。
【数据规模与约定】
规定 |s| 表示字符串 s 的长度(即字符串中的字符和空格数)。
对于 40% 的数据,1 ≤ |s| ≤ 5,保证输入为数字字符及行末换行符。
对于 80% 的数据,1 ≤ |s| ≤ 5,输入只可能包含大、小写英文字母、数字字符及
行末换行符。
对于 100% 的数据,1 ≤ |s| ≤ 5,输入可能包含大、小写英文字母、数字字符、空
格和行末换行符。
import java.util.Scanner;
public class P5015 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i)==' '){
count++;
}
}
System.out.print(s.length()-count);
}
}
龙虎斗
【问题描述】
轩轩和凯凯正在玩一款叫《龙虎斗》的游戏,游戏的棋盘是一条线段,线段上有 n个兵营(自左至右编号 1 ~ n),相邻编号的兵营之间相隔 1 厘米,即棋盘为长度为n − 1 厘米的线段。i 号兵营里有 ci 位工兵。
下面图 1 为 n = 6 的示例:

轩轩在左侧,代表“龙”;凯凯在右侧,代表“虎”。 他们以 m 号兵营作为分界,靠左的工兵属于龙势力,靠右的工兵属于虎势力,而第 m 号兵营中的工兵很纠结,他们不属于任何一方。
一个兵营的气势为:该兵营中的工兵数 × 该兵营到 m 号兵营的距离;参与游戏一方的势力定义为:属于这一方所有兵营的气势之和。
下面图 2 为 n = 6, m = 4 的示例,其中红色为龙方,黄色为虎方:

游戏过程中,某一刻天降神兵,共有 s1 位工兵突然出现在了 p1 号兵营。作为轩轩和凯凯的朋友,你知道如果龙虎双方气势差距太悬殊,轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续,你需要选择一个兵营 p2,并将你手里的 s2 位工兵全部派往兵营 p2,使得双方气势差距尽可能小。
注意:你手中的工兵落在哪个兵营,就和该兵营中其他工兵有相同的势力归属(如果落在 m 号兵营,则不属于任何势力)。
【输入格式】
输入文件名为 fight.in。
输入文件的第一行包含一个正整数 n,代表兵营的数量。
接下来的一行包含 n 个正整数,相邻两数之间以一个空格分隔,第 i 个正整数代表编号为 i 的兵营中起始时的工兵数量 ci。
接下来的一行包含四个正整数,相邻两数间以一个空格分隔,分别代表 m, p1, s1, s2。
【输出格式】
输出文件名为 fight.out。
输出文件有一行,包含一个正整数,即 p2,表示你选择的兵营编号。如果存在多个编号同时满足最优,取最小的编号。
【输入输出样例 1】

【输入输出样例 1 说明】
见问题描述中的图 2。
双方以 m = 4 号兵营分界,有 s1 = 5 位工兵突然出现在 p1 = 6 号兵营。
龙方的气势为:
2 × (4 − 1) + 3 × (4 − 2) + 2 × (4 − 3) = 14
虎方的气势为:
2 × (5 − 4) + (3 + 5) × (6 − 4) = 18
当你将手中的 s
2 = 2 位工兵派往 p2 = 2 号兵营时,龙方的气势变为:
14 + 2 × (4 − 2) = 18
此时双方气势相等。
【输入输出样例 2】

【输入输出样例 2 说明】
双方以 m = 5 号兵营分界,有 s1 = 1 位工兵突然出现在 p1 = 4 号兵营。
龙方的气势为:
1 × (5 − 1) + 1 × (5 − 2) + 1 × (5 − 3) + (1 + 1) × (5 − 4) = 11
虎方的气势为:
16 × (6 − 5) = 16
当你将手中的 s2 = 1 位工兵派往 p2 = 1 号兵营时,龙方的气势变为:
11 + 1 × (5 − 1) = 15
此时可以使双方气势的差距最小。
【数据规模与约定】
1 < m < n, 1 ≤ p1 ≤ n。
对于 20% 的数据,n = 3, m = 2, ci = 1, s1, s2 ≤ 100。
另有 20% 的数据,n ≤ 10, p1 = m, ci = 1, s1, s2 ≤ 100。
对于 60% 的数据,n ≤ 100, ci = 1, s1, s2 ≤ 100。
对于 80% 的数据,n ≤ 100, ci, s1, s2 ≤ 100。
对于 100% 的数据,n ≤ 105, ci, s1, s2 ≤ 10^9。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, p1, p2;
long long a[maxn], s1, s2, sum;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
cin >> m >> p1 >> s1 >> s2;
a[p1] += s1;
p2 = 1;
for (int i = 1; i <= n; i ++)
sum += ( (long long) (i - m) ) * a[i];
for (int i = 1; i <= n; i ++)
if ( abs(sum + (i-m) * s2) < abs(sum + (p2-m) * s2) ) p2 = i;
cout << p2 << endl;
return 0;
}
摆渡车
【问题描述】
有 n 名同学要乘坐摆渡车从人大附中前往人民大学,第 i 位同学在第 ti 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 m 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。
凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?
注意:摆渡车回到人大附中后可以即刻出发。
【输入格式】
输入文件名为 bus.in。
第一行包含两个正整数 n,m,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。
第二行包含 n 个正整数,相邻两数之间以一个空格分隔,第 i 个非负整数 ti 代表第 i 个同学到达车站的时刻。
【输出格式】
输出文件名为 bus.out。
输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。
【输入输出样例 1】

【输入输出样例 1 说明】
同学 1 和同学 4 在第 3 分钟开始等车,等待 0 分钟,在第 3 分钟乘坐摆渡车出发。摆渡车在第 4 分钟回到人大附中。
同学 2 和同学 3 在第 4 分钟开始等车,等待 0 分钟,在第 4 分钟乘坐摆渡车出发。摆渡车在第 5 分钟回到人大附中。
同学 5 在第 5 分钟开始等车,等待 0 分钟,在第 5 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 0。
【输入输出样例 2】

【输入输出样例 2 说明】
同学 3 在第 1 分钟开始等车,等待 0 分钟,在第 1 分钟乘坐摆渡车出发。摆渡车在第 6 分钟回到人大附中。
同学 4 和同学 5 在第 5 分钟开始等车,等待 1 分钟,在第 6 分钟乘坐摆渡车出发。摆渡车在第 11 分钟回到人大附中。
同学 1 在第 11 分钟开始等车,等待 2 分钟;同学 2 在第 13 分钟开始等车,等待 0 分钟。他/她们在第 13 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。
总等待时间为 4。可以证明,没有总等待时间小于 4 的方案。
【数据规模与约定】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000400;
int n, m, t, maxt;
long long f[maxn], cnt[maxn];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i ++) {
cin >> t;
cnt[t] ++;
if (t > maxt) maxt = t;
}
for (int i = 0; i <= maxt + m; i ++) {
long long tmp = 0;
for (int j = 0; j < m && i-j >=0; j ++) {
tmp += cnt[i-j] * ( (long long) j );
}
f[i] = tmp;
if (i >= m) f[i] += f[i-m];
for (int j = m+1; j <= 2*m && i - j >= 0; j ++) {
tmp += cnt[i-j+1] * ( (long long) (j-1) );
if (f[i-j] + tmp <= f[i]) f[i] = f[i-j] + tmp;
}
}
long long ans = f[maxt];
for (int i = 1; i <= m; i ++) {
ans = min(ans, f[maxt+i]);
}
cout << ans << endl;
return 0;
}
对称二叉树
【问题描述】
一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:
1. 二叉树;
2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。
下图中节点内的数字为权值,节点外的 id表示节点编号。

现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数最多。请输出这棵子树的节点数。
注意:只有树根的树也是对称二叉树。本题中约定,以节点 T 为子树根的一棵“子树”指的是:节点 T 和它的全部后代节点构成的二叉树。
【输入格式】
输入文件名为 tree.in。
第一行一个正整数 n,表示给定的树的节点的数目,规定节点编号 1~n,其中节点1 是树根。
第二行 n 个正整数,用一个空格分隔,第 i 个正整数 vi 代表节点 i 的权值。接下来 n 行,每行两个正整数 li, ri,分别表示节点 i 的左右孩子的编号。如果不存在左 / 右孩子,则以 −1 表示。两个数之间用一个空格隔开。
【输出格式】
输出文件名为 tree.out。
输出文件共一行,包含一个整数,表示给定的树的最大对称二叉子树的节点数。
【输入输出样例 1】

【输入输出样例 1 说明】

最大的对称二叉子树为以节点 2 为树根的子树,节点数为 1。
【输入输出样例 2】

【输入输出样例 2 说明】

最大的对称二叉子树为以节点 7 为树根的子树,节点数为 3。
【数据规模与约定】
共 25 个测试点。
vi ≤ 1000。
测试点 1~3,n ≤ 10,保证根结点的左子树的所有节点都没有右孩子,根结点的右子树的所有节点都没有左孩子。
测试点 4~8,n ≤ 10。
测试点 9~12,n ≤ 10^5,保证输入是一棵“满二叉树”。
测试点 13~16,n ≤ 10^5,保证输入是一棵“完全二叉树”。
测试点 17~20,n ≤ 10^5,保证输入的树的点权均为 1。
测试点 21~25,n ≤ 10^6。
本题约定:
层次:节点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一节点的层次等于其父亲节点的层次加 1。
树的深度:树中节点的最大层次称为树的深度。
满二叉树:设二叉树的深度为 h,且二叉树有 2^h − 1 个节点,这就是满二叉树。

完全二叉树:设二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n;
struct node
{
int v;
int l,r;
}tree[maxn];
int sum[maxn]={0};
int count1=0;
int check(int l,int r)//判断二叉树是否对称
{
if(l==r) return 1;
if(tree[l].v==tree[r].v)
{
if(check(tree[l].l,tree[r].r)&&check(tree[l].r,tree[r].l))
return 1;
}
return 0;
}
void yu(int i)//统计结点数量
{
int l=tree[i].l;
int r=tree[i].r;
if(i==-1) return ;
sum[i]=1;
yu(l);yu(r);
sum[i]+=sum[l]+sum[r];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tree[i].v;
}
for(int i=1;i<=n;i++)
{
cin>>tree[i].l>>tree[i].r;
}
yu(1);
int ans=0;
for(int i=1;i<=n;i++)
{
if(check(tree[i].l,tree[i].r)) ans=max(ans,sum[i]);
}
cout<<ans<<endl;
return 0;
}
成绩
【问题描述】
牛牛最近学习了 C++入门课程,这门课程的总成绩计算方法是:
总成绩 = 作业成绩 × 20% + 小测成绩 × 30% + 期末考试成绩 × 50%
牛牛想知道,这门课程自己最终能得到多少分。
【输入格式】
输入文件名为 score.in。
输入文件只有 1 行,包含三个非负整数A、B、C,分别表示牛牛的作业成绩、小测
成绩和期末考试成绩。相邻两个数之间用一个空格隔开,三项成绩满分都是 100 分。
【输出格式】
输出文件名为 score.out。
输出文件只有 1 行,包含一个整数,即牛牛这门课程的总成绩,满分也是 100 分。
【输入输出样例 1】

【输入输出样例 1 说明】
牛牛的作业成绩是 100 分,小测成绩是 100 分,期末考试成绩是 80 分,总成
绩是 100 × 20% + 100 × 30% + 80 × 50% = 20 + 30 + 40 = 90。
【输入输出样例 2】

【输入输出样例 2 说明】
牛牛的作业成绩是 60 分,小测成绩是 90 分,期末考试成绩是 80 分,总成绩是
60 × 20% + 90 × 30% + 80 × 50% = 12 + 27 + 40 = 79。
【数据说明】
对于 30% 的数据,A = B = 0。
对于另外 30% 的数据,A = B = 100。
对于 100% 的数据, 0 ≤ A、B、C ≤ 100 且 A、B、C 都是 10 的整数倍。
#include<iostream>
using namespace std;
int main()
{
int A, B, C;
cin >> A >> B >> C;
cout << A * 0.2 + B * 0.3 + C * 0.5;
return 0;
}
图书管理员
【问题描述】
图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个
正整数。
每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图
书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写
一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他
需要的书,请输出-1。
【输入格式】
输入文件名为 librarian.in。
输入文件的第一行,包含两个正整数 n 和 q,以一个空格分开,分别代表图书馆里
书的数量和读者的数量。
接下来的 n 行,每行包含一个正整数,代表图书馆里某本书的图书编码。
接下来的 q 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆
里读者的需求码的长度,第二个正整数代表读者的需求码。
【输出格式】
输出文件名为 librarian.out。
输出文件有 q 行,每行包含一个整数,如果存在第 i 个读者所需要的书,则在第 i
行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出-1。
【输入输出样例 1】

【输入输出样例 1 说明】
第一位读者需要的书有 2123、1123、23,其中 23 是最小的图书编码。第二位读者需要
的书有 2123、1123,其中 1123 是最小的图书编码。对于第三位,第四位和第五位读者,没
有书的图书编码以他们的需求码结尾,即没有他们需要的书,输出-1。
【数据规模与约定】
对于 20%的数据,1 ≤ n ≤ 2。
另有 20%的数据,q = 1。
另有 20%的数据,所有读者的需求码的长度均为 1。
另有 20%的数据,所有的图书编码按从小到大的顺序给出。
对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ q ≤ 1,000,所有的图书编码和需求码均
不超过 10,000,000。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define M 1000
int n,q;
int a[M+5],ans;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);//从小到大排序
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int f=0;
for(int j=1;j<=n;j++)
{
if(a[j]%int(pow(10,x))==y)//取末尾编码
{
f=1;
printf("%d\n",a[j]);
break;
}
}
if(f==0)printf("-1\n");
}
return 0;
}
棋盘
【问题描述】
有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在
要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、
左、右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你
不需要花费金币;如果不同,则你需要花费 1 个金币。
另外,你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个
魔法不能连续使用,而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走
到了这个暂时有颜色的格子上,你就不能继续使用魔法;只有当你离开这个位置,走到一个
本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔
法使得变为有颜色的格子)时,这个格子恢复为无色。
现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?
【输入格式】
输入文件名为 chess.in。
数据的第一行包含两个正整数 m,n,以一个空格分开,分别代表棋盘的大小,棋盘上
有颜色的格子的数量。
接下来的 n 行,每行三个正整数 x,y,c,分别表示坐标为(x,y)的格子有颜色 c。
其中 c=1 代表黄色,c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标
为(1, 1),右下角的坐标为(m, m)。
棋盘上其余的格子都是无色。保证棋盘的左上角,也就是(1,1)一定是有颜色的。
【输出格式】
输出文件名为 chess.out。
输出一行,一个整数,表示花费的金币的最小值,如果无法到达,输出-1。
【输入输出样例 1】

【输入输出样例 1 说明】

从(1,1)开始,走到(1,2)不花费金币
从(1,2)向下走到(2,2)花费 1 枚金币
从(2,2)施展魔法,将(2,3)变为黄色,花费 2 枚金币
从(2,2)走到(2,3)不花费金币
从(2,3)走到(3,3)不花费金币
从(3,3)走到(3,4)花费 1 枚金币
从(3,4)走到(4,4)花费 1 枚金币
从(4,4)施展魔法,将(4,5)变为黄色,花费 2 枚金币,
从(4,4)走到(4,5)不花费金币
从(4,5)走到(5,5)花费 1 枚金币
共花费 8 枚金币。
【输入输出样例 2】

【输入输出样例 2 说明】

从(1,1)走到(1,2),不花费金币
从(1,2)走到(2,2),花费 1 金币
施展魔法将(2,3)变为黄色,并从(2,2)走到(2,3)花费 2 金币
从(2,3)走到(3,3)不花费金币
从(3,3)只能施展魔法到达(3,2),(2,3),(3,4),(4,3)
而从以上四点均无法到达(5,5),故无法到达终点,输出-1
【数据规模与约定】
对于 30%的数据,1 ≤ m ≤ 5, 1 ≤ n ≤ 10。
对于 60%的数据,1 ≤ m ≤ 20, 1 ≤ n ≤ 200。
对于 100%的数据,1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000。
#include <iostream>
#include <bits/stdc++.h>
#include<set>
#include<string.h>
#include<algorithm>
using namespace std;
// 1 黄 0 红
int dis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int n,m;
const int maxn=105;
struct node
{
int x,y,c,v;
};
queue<node>q;
int yy[maxn][maxn],val[maxn][maxn];
int ans=0x7f7f7f7f;
void Init()
{
memset(yy,-1,sizeof(yy));
memset(val,0x7f,sizeof(val));
}
void dfs(int x,int y)
{
node pq;
pq.x=x,pq.y=y,pq.c=yy[x][y],pq.v=0;
val[x][y]=0;
q.push(pq);
while(!q.empty())
{
node now=q.front();
if(now.v>ans)
{
q.pop();
continue;
}
if(now.x==m&&now.y==m)
{
ans=min(ans,now.v);
q.pop();
continue;
}
for(int i=0;i<4;i++)
{
int dx=now.x+dis[i][0],dy=now.y+dis[i][1];
if(dx>0&&dy>0&&dx<=m&&dy<=m)
{
int bc=yy[now.x][now.y],dc=yy[dx][dy],mv=val[dx][dy],dv;
if(bc>=0&&dc>=0)
{
dv=now.v+(bc==dc?0:1);
if(mv>dv)
{
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}
else if(dc<0&&bc>=0)
{
dv=now.v+2;
if(mv>dv)
{
q.push((node){dx,dy,bc,dv});
val[dx][dy]=dv;
}
}
else if(bc<0&&dc>=0)
{
dv=now.v+(now.c==dc? 0:1);
if(mv>dv)
{
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}
}
}
q.pop();
}
}
int main()
{
cin>>m>>n;
Init();
int x,y,c;
for(int i=1;i<=n;i++)
{
cin>>x>>y>>c;
yy[x][y]=c;
}
dfs(1,1);
if(ans==0x7f7f7f7f)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
跳房子
【问题描述】
跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下:
在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人,如果他花 g 个金币改进他的机器人,那么他的机器人灵活性就能增加 g,但是需要注意的是,每次弹跳的距离至少为 1。具体而言,当g < d时,他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1, d-g+2,…,d+g-2,d+g-1,d+g;否则(当g ≥ d时),他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g-2,d+g-1,d+g。
现在小 R 希望获得至少 k 分,请问他至少要花多少金币来改造他的机器人。
【输入格式】
输入文件名为 jump.in。
第一行三个正整数 n,d,k,分别表示格子的数目,改进前机器人弹跳的固定距离,以及希望至少获得的分数。相邻两个数之间用一个空格隔开。
接下来 n 行,每行两个正整数xi, si,分别表示起点到第i个格子的距离以及第i个格子的分数。两个数之间用一个空格隔开。保证xi按递增顺序输入。
【输出格式】
输出文件名为 jump.out。
共一行,一个整数,表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分,输出-1。
【输入输出样例 1】

【输入输出样例 1 说明】
花费 2 个金币改进后,小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,3,先后到达的位置分别为 2,5,10,13,17,20,对应 1, 2, 3, 5, 6, 7 这 6 个格子。这些格子中的数字之和 15 即为小 R 获得的分数。
【输入输出样例 2】

【输入输出样例 2 说明】
由于样例中 7 个格子组合的最大可能数字之和只有 18 ,无论如何都无法获得 20 分。
【数据规模与约定】
本题共 10 组测试数据,每组数据 10 分。对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤2000, 1 ≤ xi, k ≤ 10^9, |si| < 10^5。
对于第 1,2 组测试数据,n ≤ 10;
对于第 3,4,5 组测试数据,n ≤ 500
对于第 6,7,8 组测试数据,d = 1
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
typedef long long ll;
struct node{
ll pos=0,value=0;
}a[500005];
ll n,d,k;
ll dp[500005];
bool check(ll minn,ll maxx){
for(int i=1;i<=n;i++) dp[i]=-INF;
dp[0]=0LL;
deque<int> q;
int now=0;
for(ll i=1;i<=n;i++){
while(a[i].pos-a[now].pos>maxx&&now<i) now++;
while(a[i].pos-a[now].pos<=maxx&&a[i].pos-a[now].pos>=minn&&now<i){
while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();
q.push_back(now);
now++;
}
while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();
if(!q.empty()) dp[i]=dp[q.front()]+a[i].value;
if(dp[i]>=k) return true;
}
return false;
}
int main()
{
cin>>n>>d>>k;
for(ll i=1;i<=n;i++) cin>>a[i].pos>>a[i].value;
ll l=1,r=a[n].pos;
while(l<r){
ll mid=(l+r)>>1;
if(check(max((long long)1,d-mid),d+mid)) r=mid;
else l=mid+1;
}
cout<<(r==INF?-1:r);
return 0;
}
01 #include <iostream>
02 using namespace std;
03
04 int n;
05 int a[1000];
06
07 int f(int x)
08 {
09 int ret = 0;
10 for (; x; x &= x - 1) ret++;
11 return ret;
12 }
13
14 int g(int x)
15 {
16 return x & -x;
17 }
18
19 int main()
20 {
21 cin >> n;
22 for (int i = 0; i < n; i++) cin >> a[i];
23 for (int i = 0; i < n; i++)
24 cout << f(a[i]) + g(a[i]) << ' ';
25 cout << endl;
26 return 0;
27 }
01 #include <iostream>
02 #include <string>
03 using namespace std;
04
05 char base[64];
06 char table[256];
07
08 void init()
09 {
10 for (int i = 0; i < 26; i++) base[i] = 'A' + i;
11 for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
12 for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
13 base[62] = '+', base[63] = '/';
14
15 for (int i = 0; i < 256; i++) table[i] = 0xff;
16 for (int i = 0; i < 64; i++) table[base[i]] = i;
17 table['='] = 0;
18 }
19
20 string decode(string str)
21 {
22 string ret;
23 int i;
24 for (i = 0; i < str.size(); i += 4) {
25 ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
26 if (str[i + 2] != '=')
27 ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i +
2]] >> 2;
28 if (str[i + 3] != '=')
29 ret += table[str[i + 2]] << 6 | table[str[i + 3]];
30 }
31 return ret;
32 }
33
34 int main()
35 {
36 init();
37 cout << int(table[0]) << endl;
38
39 string str;
40 cin >> str;
41 cout << decode(str) << endl;
42 return 0;
43 }
(Josephus 问题)有 n个人围成一个圈,依次标号 0 至n-1。从 0 号开始,依次 0, 1, 0, 1, … 交替报数,报到 1 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。
试补全模拟程序。
01 #include <iostream>
02
03 using namespace std;
04
05 const int MAXN = 1000000;
06 int F[MAXN];
07
08 int main() {
09 int n;
10 cin >> n;
11 int i = 0, p = 0, c = 0;
12 while (①) {
13 if (F[i] == 0) {
14 if (②) {
15 F[i] = 1;
16 ③;
17 }
18 ④;
19 }
20 ⑤;
21 }
22 int ans = -1;
23 for (i = 0; i < n; i++)
24 if (F[i] == 0)
25 ans = i;
26 cout << ans << endl;
27 return 0;
28 }
(矩形计数)平面上有 n 个关键点,求有多少个四条边都和 x 轴或者 y 轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。
试补全枚举算法。
01 #include <iostream>
02
03 using namespace std;
04
05 struct point {
06 int x, y, id;
07 };
08
09 bool equals(point a, point b) {
10 return a.x == b.x && a.y == b.y;
11 }
12
13 bool cmp(point a, point b) {
14 return ①;
15 }
16
17 void sort(point A[], int n) {
18 for (int i = 0; i < n; i++)
19 for (int j = 1; j < n; j++)
20 if (cmp(A[j], A[j - 1])) {
21 point t = A[j];
22 A[j] = A[j - 1];
23 A[j - 1] = t;
24 }
25 }
26
28 int t = 0;
29 for (int i = 0; i < n; i++)
30 if (②)
31 A[t++] = A[i];
32 return t;
33 }
34
35 bool binary_search(point A[], int n, int x, int y) {
36 point p;
37 p.x = x;
38 p.y = y;
39 p.id = n;
40 int a = 0, b = n - 1;
41 while (a < b) {
42 int mid = ③;
43 if (④)
44 a = mid + 1;
45 else
46 b = mid;
47 }
48 return equals(A[a], p);
49 }
50
51 const int MAXN = 1000;
52 point A[MAXN];
53
54 int main() {
55 int n;
56 cin >> n;
57 for (int i = 0; i < n; i++) {
58 cin >> A[i].x >> A[i].y;
59 A[i].id = i;
60 }
61 sort(A, n);
62 n = unique(A, n);
63 int ans = 0;
64 for (int i = 0; i < n; i++)
65 for (int j = 0; j < n; j++)
66 if (⑤ && binary_search(A, n, A[i].x, A[j].y) &&
binary_search(A, n, A[j].x, A[i].y)) {
67 ans++;
68 }
69 cout << ans << endl;
70 return 0;
71 }