信息学奥赛-入门级 题库
直播获奖( 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。试补全程序。
小苹果(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:

甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定 去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不 去。如果周末丙去了,则甲 (去了/没去) (1 分),乙 (去 了/没去) (1 分),丁 (去了/没去) (1 分),周末 (下雨/ 没下雨) (2 分)。
去了
没去
没去
没下雨



