信息学奥赛-入门级 题库
插入排序

#include <bits/stdc++.h>
using namespace std;
int n, q, a[8005], b[8005], num, x, v, ans;
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// 计算每个数在数组中的排位
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (i == j || a[j] < a[i] || a[j] == a[i]) {
b[i]++;
} else {
b[j]++;
}
}
}
for (int i = 0; i < q; i++) {
scanf("%d", &num);
if (num == 1) {
scanf("%d%d", &x, &v);
for (int i = 1; i <= n; i++) {
if (i == x) {
continue;
}
// 根据条件更新排位
if ((a[i] < a[x] || (a[i] == a[x] && i < x)) &&
(a[i] > v || (a[i] == v && i > x))) {
b[i]++;
b[x]--;
} else if ((a[i] > a[x] || (a[i] == a[x] && i > x)) &&
(a[i] < v || (a[i] == v && i < x))) {
b[i]--;
b[x]++;
}
}
a[x] = v;
}
if (num == 2) {
scanf("%d", &x);
printf("%d\n", b[x]);
}
}
return 0;
}网络连接

#include <bits/stdc++.h>
using namespace std;
map<string, int> vis;
int n;
bool check(char s[]) {
int a = -1, b = -1, c = -1, d = -1, e = -1;
// 尝试读入,保存至变量中
int t = sscanf(s, "%d.%d.%d.%d:%d", &a, &b, &c, &d, &e);
// 必须读入5个部分才可能合法
if (t != 5) return 0;
// 检查各部分数值范围
if (a < 0 || a > 255) return 0;
if (b < 0 || b > 255) return 0;
if (c < 0 || c > 255) return 0;
if (d < 0 || d > 255) return 0;
if (e < 0 || e > 65535) return 0;
// 格式化后与原字符串对比,确保无冗余格式
char s2[35];
sprintf(s2, "%d.%d.%d.%d:%d", a, b, c, d, e);
int lens = strlen(s);
for (int i = 0; i < lens; i++) {
if (s[i] != s2[i]) {
return 0;
}
}
return 1;
}
int main() {
// freopen("network.in","r",stdin);
// freopen("network.out","w",stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
char op[1005], ad[1005];
cin >> op >> ad;
string t(ad);
if (op[0] == 'S') { // 服务机操作
if (!check(ad)) {
cout << "ERR" << endl; // 地址不合法
} else if (vis.count(t) != 0) {
cout << "FAIL" << endl; // 已存在该服务机
} else {
cout << "OK" << endl; // 注册成功
vis[t] = i; // 记录编号
}
} else { // 客户机操作
if (!check(ad)) {
cout << "ERR" << endl; // 地址不合法
} else if (vis.count(t) == 0) {
cout << "FAIL" << endl; // 找不到对应服务机
} else {
cout << vis[ad] << endl; // 输出对应服务机编号
}
}
}
return 0;
}小熊的果篮

#include <bits/stdc++.h>
#define INF 200010
using namespace std;
int n;
set<int> s1, s2; // 存储两种下标的集合
int main() {
scanf("%d", &n);
s1.clear();
s2.clear();
int q;
for (int i = 1; i <= n; ++i) {
scanf("%d", &q);
if (q) {
s1.insert(i); // q为1时插入s1
} else {
s2.insert(i); // q为0时插入s2
}
}
// 插入INF防止set为空时操作出错
s1.insert(INF);
s2.insert(INF);
int nw = 0;
// p表示当前要操作的集合:0为s1,1为s2(选择最小下标的集合)
bool p = (*s1.begin() < *s2.begin()) ? 0 : 1;
// 循环处理,直到当前操作的集合只剩下INF(size > 1表示还有有效元素)
while ((!p && s1.size() > 1) || (p && s2.size() > 1)) {
if (!p) { // 处理s1
nw = *s1.upper_bound(nw); // 找nw之后的下一个元素
if (nw == INF) { // 已遍历完当前轮次,从头开始
nw = 0;
// 重新选择下一轮的起始集合
p = (*s1.begin() < *s2.begin()) ? 0 : 1;
puts("");
continue;
}
printf("%d ", nw); // 输出并从集合中删除
s1.erase(nw);
p = !p; // 切换到另一个集合
} else { // 处理s2(逻辑同上)
nw = *s2.upper_bound(nw);
if (nw == INF) {
nw = 0;
p = (*s1.begin() < *s2.begin()) ? 0 : 1;
puts("");
continue;
}
printf("%d ", nw);
s2.erase(nw);
p = !p;
}
}
puts(""); // 处理最后一个果篮的换行
// 输出剩余集合中的元素(每行一个)
while (s1.size() > 1) {
printf("%d\n", *s1.begin());
s1.erase(*s1.begin());
}
while (s2.size() > 1) {
printf("%d\n", *s2.begin());
s2.erase(*s2.begin());
}
return 0;
}优秀的拆分(power)

#include <bits/stdc++.h>
using namespace std;
/*
定义:分解为了若干个不同的 2 的正整数次幂
性质:是偶数,奇数不存在优秀的拆分
思路:
如果n是偶数,将n进行进制转换
10 -> 1010
*/
int a[110],n,k = 0;//k表示a数组的下标
int main(){
cin>>n;
//特判奇数的情况
if(n % 2 != 0){
cout<<-1;
return 0;
}
//进制转换
int t = 1;//表示2的次方
while(n != 0){
if(n % 2 != 0){
k++;
a[k] = t;
}
t = t * 2;
n = n / 2;
}
//逆序输出结果
for(int i = k;i >= 1;i--){
cout<<a[i]<<" ";
}
return 0;
}直播获奖( live)

#include <bits/stdc++.h>
using namespace std;
/*
1.获奖人数为k = max(1, int(p × w%))
2.选手的成绩均为不超过 600 的非负整数
思路:使用数组统计每个分值得分的人数
从大到小统计出k个人,最后一次循环对应的分值就是要求的获奖分数
*/
int a[610];
int n,w,x;
int main(){
scanf("%d%d",&n,&w);
int k;//获奖人数
int ans;//统计人数
//读入n个人的分数,读一个算一个
for(int i = 1;i <= n;i++){
scanf("%d",&x);
a[x]++;//统计每个分值对应的人数
//计算获奖人数
k = max(1,int(i * w / 100.0));
ans = 0;
//从最高分的人数向下统计出>=k个人
for(int j = 600;j >= 0;j--){
if(ans + a[j] < k) ans += a[j];//+=
else{
printf("%d ",j);
break;
}
}
}
return 0;
}表达式(expr)

#include <bits/stdc++.h>
using namespace std;
/*
取反某一个操作数的值时,原表达式的值为多少
思路:
1.读入表达式,将表达式建成二叉树
2.计算出表达式的值
3.深搜,求出哪些结点的值修改后对结果有影响
*/
const int N = 1e6 + 10;
struct node{
int to,next;
}a[N];//邻接表
int pre[N],k;//存储以每个点为起点的最后一条边的编号
int num[N];//存储二叉树每个结点的值
char c[N];//存储操作符
int m;//表示c数组的下标
bool f[N];//标记哪些点的值修改后对结果有影响
int n;
string s,w;//w用来存储每个操作数的下标
stack<int> st;//用于计算后缀表达式
//建边
void add(int u,int v){
k++;
a[k].to = v;
a[k].next = pre[u];
pre[u] = k;
}
//深搜求哪些结点的值修改后对结果有影响
void dfs(int x){
f[x] = true;
if(x <= n) return;//如果是叶子结点
if(c[x] == '!') dfs(a[pre[x]].to);
else{
int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;
if(c[x] == '&'){
if(num[n1] == 1) dfs(n2);
if(num[n2] == 1) dfs(n1);
}else if(c[x] == '|'){
if(num[n1] == 0) dfs(n2);
if(num[n2] == 0) dfs(n1);
}
}
}
int main()
{
getline(cin,s);
cin>>n;
for(int i = 1;i <= n;i++){
scanf("%d",&num[i]);
}
//分析表达式,建树
int x,y;
m = n;
for(int i = 0;i < s.size();i++){
if(isdigit(s[i])){
w = w + s[i];
//如果连续数字结束
if(i==s.size()-1||!isdigit(s[i+1])){
st.push(atoi(w.c_str()));//将操作数的下标入栈
w = "";
}
}else if(s[i] == '!'){
//如果是取反操作符
m++;
c[m] = s[i];//操作符的编号是m
x = st.top();//取栈顶元素来运算
st.pop(); //出栈
//建边
add(m,x);
num[m] = !num[x];
st.push(m);
}else if(s[i] == '&' || s[i] == '|'){
//如果是& |操作符
m++;
c[m] = s[i];
//取2个操作数
x = st.top();
st.pop();
y = st.top();
st.pop();
//建边
add(m,x);
add(m,y);
//计算结点的值
if(s[i] == '&') num[m] = num[x] & num[y];
else if(s[i] == '|') num[m] = num[x] | num[y];
st.push(m);
}
}
int ans = num[st.top()];
//cout<<ans;
//深搜求哪些结点的值修改后对结果有影响
dfs(st.top());//从根开始深搜
//q次询问
int q;
cin>>q;
while(q--){
scanf("%d",&x);
if(f[x]==true) printf("%d\n",!ans);
else printf("%d\n",ans);
}
return 0;
}方格取数(number)

#include <bits/stdc++.h>
using namespace std;
/*
左上角走到右下角
每一步只能向上、向下或向右走一格
不能重复经过已经走过的方格
计算的结果,要用long long
*/
const int N = 1010;
int a[N][N];//读入的每个点的值
typedef long long LL;
LL f[N][N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
scanf("%d",&a[i][j]);
}
}
/*
DP求出走到每个点经过的数字和的最大值
一列一列求,对于每一列而言,要求从上向下走到每个点经过的数字和的最大值
也要求从下向上走到每个点经过的数字和的最大值
*/
memset(f,-0x7f,sizeof(f));
LL ma;//走到每个格子经过的数字和最大
f[1][0] = 0;
for(int j = 1;j <= m;j++){
//从上向下求
ma = -1e18;
for(int i = 1;i <= n;i++){
ma = max(ma,f[i][j-1]) + a[i][j];
f[i][j] = max(f[i][j],ma);
}
//从下向上求
ma = -1e18;
for(int i = n;i >= 1;i--){
ma = max(ma,f[i][j-1]) + a[i][j];
f[i][j] = max(f[i][j],ma);
}
}
cout<<f[n][m];
return 0;
}T1 扑克牌

#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<string> st;
while (n--) {
string s;
cin >> s;
st.insert(s);
}
cout << 52 - st.size() << endl;
return 0;
}题目给出已有的牌,要求计算最少需要补充多少张牌才能凑齐一副完整的扑克牌(52张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。
T2 地图探险

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 5;
int n, m, k, x, y, d, dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
char mp[N][N];
bool vis[N][N];
int main() {
int t;
cin >> t;
while (t--) {
memset(vis, false, sizeof (vis));
cin >> n >> m >> k >> x >> y >> d;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> mp[i][j];
vis[x][y] = true;
while (k--) {
int nx = x + dir[d][0], ny = y + dir[d][1];
if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) {
d = (d + 1) % 4;
continue;
}
x = nx, y = ny;
vis[nx][ny] = true;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vis[i][j] == true)
ans++;
}
}
cout << ans << endl;
}
return 0;
}需要的变量 / 数组
描述机器人状态需要的3个变量:
x:位置。
y:位置。
d:朝向(0~3)。
vis数组:
当机器人走过[x, y],vis[x][y] = true。
dir数组:
dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}。
[x + dir[d][0], y + dir[d][1]]表示当机器人朝向为d时往前走一步之后的位置。
d = 0: 右 (0, 1)。
d = 1: 下 (1, 0)。
d = 2: 左 (0, -1)。
d = 3: 上 (-1, 0)。
核心思想
vis[x][y] = true;
while (k--) {
int nx = x + dir[d][0], ny = y + dir[d][1]; // 计算下一步的位置
if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) { // 是否能走
d = (d + 1) % 4; // 若不能走 右转
continue;
}
x = nx, y = ny; // 若能走 更新
vis[nx][ny] = true;
}T3 小木棍

#include <iostream>
using namespace std;
string Solve(int n) {
if (n == 1)
return "-1";
if (n % 7 == 0)
return string(n / 7, '8');
if (n % 7 == 1)
return "10" + string((n - 8) / 7, '8');
if (n % 7 == 2)
return "1" + string((n - 2) / 7, '8');
if (n % 7 == 3)
return n == 3 ? "7" : n == 10 ? "22" : "200" + string((n - 17) / 7, '8');
if (n % 7 == 4)
return n == 4 ? "4" : "20" + string((n - 11) / 7, '8');
if (n % 7 == 5)
return "2" + string((n - 5) / 7, '8');
if (n % 7 == 6)
return "6" + string((n - 6) / 7, '8');
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << Solve(n) << endl;
}
return 0;
}拼出0~9分别需要的木棍数量:

求解思想:
因为拼出8所需的木棍最多(7根),所以用8,可以使位数更少
在保证位数最少的前提下,还要尽可能把高位的数字变小(必须保证位数最小)
按照思想,可以找到这样的规律:

T4 接龙

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5, R = 105;
vector<int> s[N];
int n, k, q;
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}
int main() {
int t;
cin >> t;
while (t--) {
int mx = -1;
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int l;
cin >> l;
s[i].clear();
s[i].resize(l);
for (int j = 0; j < l; j++) {
cin >> s[i][j];
mx = max(mx, s[i][j]);
}
}
vector<vector<int> > dp = Solve(mx);
while (q--) {
int r, c;
cin >> r >> c;
cout << (dp[r][c] != -1 ? 1 : 0) << endl;
}
}
return 0;
}解题思路
本文的解题思想为dp。
dp[r][x]:接龙 r 轮、以 x 结尾的状态:
dp[r][x] = -1:不可实现。
dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。
dp[r][x] = -2:可以通过多个词库实现。
代码解析
完整的求解部分:
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}逐行分析
mx:所有词库中的最大值,用于构建dp的第二个维度。
dp的大小为R(最大轮数) * mx(所有词库中的最大值)。
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。
dp[0][1] = -2;
r:轮数。
i:尝试让第 i 个人接龙。
j:第 i 个人词库中第 j 个词语。
lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
}
}
}获取当前人员 i 的词库中第 j 个词语。
如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:
那么选择子序列[lst, j]开始接龙。
更新当前状态。
如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i; // 首次发现路径则记录序列i
else if (dp[r][tmp] != i)
dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;完善程序(1)
(判断平方数) 问题:给定一个正整数 n,判断这个数 是不是完全平方数,即存在一个正整数 x 使得 x 的平方等于 n。试补全程序。
完善程序(2)
(汉诺塔问题)给定三根柱子,分别标记为 A、B 和 C。初始状态下,柱子A上有若干个圆盘,这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子c上,且必须保持原有顺序不变。在移动过程中,需要遵守以不规则:
1.只能从一根柱子的顶部取出圆盘,并将其放入另一根柱子的顶部。
2.每次只能移动一个圆盘
3.小圆盘必须始终在大圆盘之上。
试补全程序
小苹果(apple)
【题目描述】
小Y的桌子上放着n个苹果从左到右排成一列,编号为从1到n。
小苞是小Y的好朋友,每天她都会从中拿走一些苹果。
每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为n的苹果是在第几天被拿走的?
【输入格式】
从文件apple.in中读入数据。
输入的第一行包含一个正整数n,表示苹果的总数。
【输出格式】
输出到文件apple.out中。
输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为n的苹果是在第几天。
【样例1输入】
【样例1输出】
【样例1解释】
小苞的桌上一共放了8个苹果。
小苞第一天拿走了编号为1、4、7的苹果。
小苞第二天拿走了编号为2、6的苹果。
小苞第三天拿走了编号为3的苹果。
小苞第四天拿走了编号为5的苹果。
小苞第五天拿走了编号为8的苹果。
【样例2】
见选手目录下的apple/apple2.in与apple/apple2.ans。


公路(road)
【题目描述】
小苞准备开着车沿着公路自驾。
公路上一共有n个站点,编号为从1到n。其中站点i与站点i+1的距离为vi公里。
公路上每个站点都可以加油,编号为i的站点一升油的价格为ai元,且每个站点只出售整数升的油。
小苞想从站点1开车到站点n,一开始小苞在站点1且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进d公里。问小苞从站点1开到站点n,至少要花多少钱加油?
【输入格式】
从文件road.in中读入数据。
输入的第一行包含两个正整数n和d,分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含n−1个正整数v1,v2...vn−1,分别表示站点间的距离。
输入的第二行包含n个正整数a1,a2...an,分别表示在不同站点加油的价格。
【输出格式】
输出到文件road.out中。
输出一行,仅包含一个正整数,表示从站点1开到站点n,小苞至少要花多少钱加油。
【样例1输入】
【样例1输出】
【样例1解释】
最优方案下:小苞在站点1买了3升油,在站点2购买了5升油,在站点4购买了2升油。
【样例2】
见选手目录下的road/road2.in与road/road2.ans。
。

旅游巴士(bus)
【题目描述】
小Z打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。
旅游景点的地图共有n处地点,在这些地点之间连有m条道路。其中1号地点为景区入口,n号地点为景区出口。我们把一天当中景区开门营业的时间记为0时刻,则从0时刻起,每间隔k单位时间便有一辆旅游巴士到达景区入口,同时有一辆旅游巴士从景区出口驶离景区。
所有道路均只能单向通行。对于每条道路,游客步行通过的用时均为恰好1单位时间。
小Z希望乘坐旅游巴士到达景区入口,并沿着自己选择的任意路径走到景区出口,再乘坐旅游巴士离开,这意味着他到达和离开景区的时间都必须是k的非负整数倍。由于节假日客流众多,小Z在坐旅游巴士离开景区前只想一直沿着景区道路移动,而不.想在任何地点(包括景区入口和出口)或者道路上逗留。
出发前,小Z忽然得知:景区采取了限制客流的方法,对于每条道路均设置了一个“开放时间”ai,游客只有不早于ai时刻才能通过这条道路。
请你帮助小Z设计一个旅游方案,使得他乘坐旅游巴士离开景区的时间尽量地早。
【输入格式】
从文件bus.in中读入数据。
输入的第一行包含3个正整数n,m,k,表示旅游景点的地点数、道路数,以及旅游巴士的发车间隔。
输入的接下来m行,每行包含3个非负整数ui,vi,ai,表示第i条道路从地点ui出发,到达地点vi,道路的“开放时间”为ai。
【输出格式】
输出到文件bus.out中。
输出一行,仅包含一个整数,表示小Z最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案,输出‐1。
【样例1输入】
【样例1输出】
【样例1解释】
图1:

样例1示例
小Z可以在3时刻到达景区入口,沿1→3→4→5的顺序走到景区出口,并在6时刻离开。
【样例2】
见选手目录下的bus/bus2.in与bus/bus2.ans。
【数据范围】
对于所有测试数据有:2≤n≤104,1≤m≤2×104,1≤k≤100,1≤ui,vi≤n,0≤ai≤106。

参考程序1:

参考程序2:




