信息学奥赛-入门级 题库
字符串解码
“行程长度编码”(Run-Length Encoding)是一种无损压缩算法,常用于压缩重复字符较多的数据,以减少存储空间。假设原始字符串不包含数字字符,压缩规则如下:
①如果原始字符串中一个字符连续出现N次(N≥2),在压缩字符串中表示为“字符+数字N”。例如,编码“A12”代表12个连续的字符A。
②如果原始字符串中一个字符只出现1次,在压缩字符串中表示为该字符本身。例如,编码“B”代表1个字符B。
以下程序实现读取压缩字符串并输出其原始的、解压后的形式,试补全程序。
数字游戏

#include<iostream>
#include<cstring>
using namespace std;
int main(){
char str[10];
cin >> str;
int ans=0;
for(int i=0;i<8;i++){//题意说了,长度固定是8
if(str[i]=='1'){
ans++;
}
}
cout << ans<<endl;
return 0;
}这道题考察字符串的操作、循环结构、分支结构等知识点。输入字符串,注意看题的最后,总长度是8.遍历字符串中每一个字符,如果字符为1则计数变量加一,最后输出计算变量的值。
公交换乘


#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct tra{
int kind,value,time;
}a[100005];
//保存打折车票的位置 车票的数量
int discount[100005],number;
int main()
{
int ans=0;
int n,start=1;
cin>>n;
//每张车票都要判断
for(int i=1;i<=n;i++){
cin>>a[i].kind>>a[i].value>>a[i].time ;
if(a[i].kind==0){//地铁票,需要花费
discount[++number]=i;
ans+=a[i].value;
}
else{
int j=0;
for(j=start;j<=number;j++){//超时的优惠票,没有用,舍弃
int t=discount[j];
if(a[i].time-a[t].time >45) {
start++;
continue;
}
if(a[i].value <=a[t].value){//未超时,且票据小于等于地铁票,可以用
a[t].value=0;
break;
}
}
if(j>number) {//没有优惠券
ans+=a[i].value;
}
}
}
//输出答案
cout<<ans<<endl;
return 0;
}和2016年海港有些像,模拟题。
车票有2中,如果是地铁票,必须要花钱。如果是公交车票,就不一定了。
如果45分钟内,有做过的地铁票,并且费用大于等于公交车的,就免费;
否则要花费。
纪念品


#include<iostream>
#include<cstring>
using namespace std;
int T,N,M;
int dp[10001];
int price[101][10001];
int main(){
cin>>T>>N>>M;
for(int i=1;i<=T;i++){
for(int j=1;j<=N;j++){
cin>>price[i][j];
}
}
int maxn=0;
for(int i=2;i<=T;i++){
maxn=0;
memset(dp,0,sizeof(dp));
for(int j=1;j<=N;j++){
for(int k=price[i-1][j];k<=M;k++){
dp[k]=max(dp[k],dp[k-price[i-1][j]]+price[i][j]-price[i-1][j]);
maxn=max(maxn,dp[k]);
}
}
M+=maxn;
}
cout <<M<< endl;
return 0;
}如果只有1天的话,买了再卖,总共剩下M个金币。
T天N种纪念币,根据题目设定范围,100以内,可以用二维表格推导。
时间不可逆,只能1~N。
每天买哪些纪念品呢?根据测试样例分析,纪念品任意多,没有个数限制。根据金币的上限,可以推到出这个就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包处理,当天不想卖出金币,相当于卖出金币再买入金币。
加工零件



#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1e5+5;
const int MAXM=2e5+5;
int n,m,que;
int head[MAXN],v[MAXM],next[MAXM],cnt=0;
int dis[MAXN][2];
void add_edge(int s,int t){
v[++cnt]=t;
next[cnt]=head[s];
head[s]=cnt;
}
void spfa(){
//0表示偶数
//1表示奇数
memset(dis,0x3f,sizeof(dis));
dis[1][0]=0;//起始路径0
queue<int> q;//队列实现
q.push(1);
while(!q.empty()){
int cur=q.front();
q.pop();
for(int i=head[cur];i;i=next[i]){
int np=v[i];
if(dis[cur][0]+1<dis[np][1] || dis[cur][1]+1<dis[np][0])
q.push(np);
dis[np][1]=min(dis[np][1],dis[cur][0]+1);
dis[np][0]=min(dis[np][0],dis[cur][1]+1);
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&que);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
spfa();
while(que--){
int a,l;
scanf("%d%d",&a,&l);
if(head[1]&&dis[a][l&1]<=l)printf("Yes\n");
else printf("No\n");
}
return 0;
}这道题考察图论的知识运用,是属于最短路径的变形题目,可以利用spfa或Dijkstra来完成,难度较高。
根据性质,工人之间的关系是图。相连接,之间的路径权值是1。加工零件的过程可以相互传递,来回都是偶数次,因此在求个最短路时看奇偶步数内能否可达,要求与L的奇偶性一致。
乘方(pow)


#include <bits/stdc++.h>
using namespace std;
int main() {
long long ans, a, b;
ans = 1;
cin >> a >> b;
if (a == 1) { // 特判a=1,避免超时
cout << ans;
} else {
for (int i = 1; i <= b; ++i) {
ans *= a; // b个a相乘
if (ans > 1e9) { // 若乘积超过10^9,直接输出-1并终止程序
cout << -1;
return 0;
}
}
cout << ans; // 输出b个a相乘的结果
}
return 0;
}解密(decode)


#include<bits/stdc++.h>
using namespace std;
int k;
int main(){
scanf("%d",&k);
for(int i=1;i<=k;i++){
long long n,d,e;
scanf("%lld %lld %lld",&n,&d,&e);
long long s=n-d*e+2;
long long r=(n-d*e+2)/2,l=1;
while(l<r){
int mid=(l+r)/2;
if(mid*(s-mid)>=n){
r=mid;
}else{
l=mid+1;
}
}
if(l*(s-l)==n){
printf("%lld %lld\n",l,(s-l));
}else{
printf("NO\n");
}
}
return 0;
}逻辑表达式(expr)



//参考代码1
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
inline void fio(string name)
{
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
inline long long read()
{
long long s=0,w=1,ch=getchar();
while(ch<'0'||ch>'9') ch=='-'?w=-1,ch=getchar():ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
const int S=1000005;
int n;
char a[S];
int top,sta[S];
int rb[S],val[S];
int mlog[S],mn[S][25];
int cnt1,cnt2;
inline int que(int l,int r)
{
int k=mlog[r-l+1];
int x=mn[l][k],y=mn[r-(1<<k)+1][k];
return val[x]<val[y]?x:y;
}
int slove(int l,int r)
{
if(rb[l]==r) l++,r--;
if(l==r) return a[l]-'0';
int pos=que(l,r);
int lft=slove(l,pos-1);
if(lft==0&&a[pos]=='&')
{
cnt1++;
return 0;
}
if(lft==1&&a[pos]=='|')
{
cnt2++;
return 1;
}
int rig=slove(pos+1,r);
if(a[pos]=='&') return lft&rig;
else return lft|rig;
}
int main()
{
fio("expr");
scanf("%s",a+1);
n=strlen(a+1);
for(int i=1;i<=n;i++)
{
if(a[i]=='(') sta[++top]=i;
else if(a[i]==')') rb[sta[top--]]=i;
else if(a[i]!='0'&&a[i]!='1') val[i]=sta[top]*2+(a[i]=='&');
if(a[i]!='&'&&a[i]!='|') val[i]=1e8;
}
mlog[0]=-1;
for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1,mn[i][0]=i;
for(int j=1;j<=mlog[n];j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
{
int x=mn[i][j-1],y=mn[i+(1<<j-1)][j-1];
mn[i][j]=val[x]<val[y]?x:y;
}
}
printf("%d\n",slove(1,n));
printf("%d %d\n",cnt1,cnt2);
return 0;
}//参考代码2
#include<bits/stdc++.h>
#define N 3000005
using namespace std;
int n,m,top,ans1,ans2;
int to[N],to2[N],stk[N],cl[N],cr[N];
char str[N],s[N];
void build(int l,int r){
if(l==r) return;
if(str[l]=='('&&str[r]==')'&&to[l]==r){build(l+1,r-1);return;}
build(l,to[l]);
for(int i=to[l]+1;i<=r;i=to[i+1]+1){
build(i+1,to[i+1]);
if(str[i]=='&'){
cl[to2[i-1]]++;cr[to2[i+1]]++;
to2[to2[i+1]]=to2[i-1];
}
}
}
int solve(int l,int r){
if(l==r) return s[l]-'0';
if(s[l]=='('&&s[r]==')'&&to[l]==r) return solve(l+1,r-1);
int val=solve(l,to[l]);
for(int i=to[l]+1;i<=r;i=to[i+1]+1){
if(s[i]=='&'){
if(!val) ans1++;
else val&=solve(i+1,to[i+1]);
}else{
if(val) ans2++;
else val|=solve(i+1,to[i+1]);
}
}
return val;
}
signed main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
scanf("%s",str+1);n=strlen(str+1);
for(int i=1;i<=n;i++){
if(str[i]=='0'||str[i]=='1') to[i]=i;
if(str[i]=='(') stk[++top]=i;
if(str[i]==')') to[stk[top]]=i,to[i]=stk[top],top--;
}
memcpy(to2,to,sizeof(to));
build(1,n);
for(int i=1;i<=n;i++){
while(cl[i]--) s[++m]='(';
s[++m]=str[i];
while(cr[i]--) s[++m]=')';
}
memset(to,0,sizeof(to));
top=0;
for(int i=1;i<=m;i++){
if(s[i]=='0'||s[i]=='1') to[i]=i;
if(s[i]=='(') stk[++top]=i;
if(s[i]==')') to[stk[top]]=i,to[i]=stk[top],top--;
}
printf("%d\n",solve(1,m));
printf("%d %d\n",ans1,ans2);
return 0;
}//参考代码3
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
string s;
int sum,sun,to[N],stk[N],stkid,now;
char la;
stack<int>r[N/2];
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>s;
int n=s.size();
for(int i=n-1;i>=0;i--) s[i+1]=s[i];
for(int i=1;i<=n;i++) to[i]=i+1;
for(int i=1;i<=n;i++){
if(s[i]=='(') stk[++stkid]=i-1;
if(s[i]==')') to[stk[stkid--]]=i;
}
for(int i=1;i<=n;i++){
if(s[i]=='|'){
if(r[now].size()){
int TOP=r[now].top();
r[now].pop();
to[TOP]=i-1;
}
r[now].push(i);
}
if(s[i]=='(') now++;
if(s[i]==')'){
if(r[now].size()){
int TOP=r[now].top();
r[now].pop();
to[TOP]=i;
}
now--;
}
}
if(r[now].size()) to[r[now].top()]=n+1;
//for(int i=1;i<=n;i++) cout<<to[i]<<' ';cout<<endl;
for(int i=1;i<=n;i++){
if(s[i]=='('||s[i]==')') continue;
if(s[i]=='|'){
if(la=='1') {sun++;i=to[i];}
}
else if(s[i]=='&'){
if(la=='0') {sum++;i=to[i];}
}
else{
la=s[i];
}
}
cout<<la<<endl<<sum<<' '<<sun;
return 0;
}//参考代码4
#include<bits/stdc++.h>
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pb push_back
using namespace std;
string s;
int tp1,tp2;
int main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>s;
int cnt1=0,cnt2=0,ans=0;
REP(i,0,s.size()){
if(s[i]=='1'||s[i]=='0')ans=s[i]-'0';
else if(s[i]=='&'){
if(ans==0){
++cnt1;
int res=0;
for(int j=i+1;j<(int)(s.size());++j){
if(s[j]=='(')++res;
else if(s[j]==')')--res;
if((!res)&&s[j]!='&'&&s[j]!='|'){
i=j;
break;
}
}
}
}else if(s[i]=='|'){
if(ans==1){
++cnt2;
int res=0;
for(int j=i+1;j<(int)(s.size());++j){
if(s[j]=='(')++res;
else if(s[j]==')')--res;
if(j!=(int)(s.size()-1)&&s[j+1]=='&')continue;
if((!res)&&s[j]!='&'&&s[j]!='|'){
i=j;
break;
}
}
}
}
}
cout<<ans<<endl;
cout<<cnt1<<' '<<cnt2<<endl;
return 0;
}上升点列(point)


//参考代码1
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
//重载运算符,按x从小到大排序,x相同,则按y从小到大排序
friend bool operator<(const node &a1,const node &a2){
if(a1.x!=a2.x)return a1.x<a2.x;
return a1.y<a2.y;
}
}a[505];//记录500个点
int f[505][105],n,m,ans;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
sort(a+1,a+1+n);//排序
for(int k=0;k<=m;k++){//枚举使用0到K个点的情况
for(int i=1;i<=n;i++){//枚举每一个点
f[i][k]=k+1;//初始化第i个点用掉K个添加点后的最长距离
for(int j=1;j<i;j++){//循环这个点之前的点
if(a[j].y>a[i].y)continue;//如果之前的点Y坐标大,则忽略
int dist=a[i].x-a[j].x+a[i].y-a[j].y;//计算距离
if(dist-1>k)continue;//如果距离大,添加的点不够用,则忽略
f[i][k]=max(f[i][k],f[j][k-dist+1]+dist);//看下现在的大还是换成之前的点大
}
ans=max(ans,f[i][k]+m-k);//跟最大值比较
}
}
cout<<ans;
return 0;
}//参考代码2
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct points
{
int x,y;
} p[510];
bool cmp(const points a,const points b)
{
if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
int f[510][110];//以i点为终点,再添加上j个点的情况下最大序列长度
int main()
{
//打开输入文件,输出文件
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1; i<=n; i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
}
sort(p+1,p+1+n,cmp);
int ans=0;
for(int i=1; i<=n; i++)
{//以i为终点
for(int j=0; j<=k; j++)
{//添加j个点
f[i][j]=j+1;//以i为终点,后续添加j个点最短的长度
for(int l=1; l<i; l++)
{ //l为i的前一个点
if(p[l].x<=p[i].x&&p[l].y<=p[i].y)
{//横坐标、纵坐标值均单调不减
int t=p[i].x-p[l].x+p[i].y-p[l].y-1;//需要添加的点数量
if(j>=t) f[i][j]=max(f[i][j],f[l][j-t]+t+1);
//cout<<p[i].x<<p[l].x<<p[i].y<<p[l].y<<t<<endl;
}
//cout<<"i="<<i<<" j="<<j<<" l="<<l<<" f="<<f[i][j]<<endl;
}
ans=max(ans,f[i][j]);
}
}
printf("%d",ans);
//关闭输入文件输出文件
fclose(stdin);
fclose(stdout);
return 0;
}分糖果

//参考代码1
#include <iostream>
using namespace std;
int n, l, r;
int main() {
cin >> n >> l >> r;
if (l / n == r / n) {
cout << r % n;
} else {
cout << n - 1;
}
return 0;
}//参考代码2
#include <iostream>
using namespace std;
int main() {
long long n, L, R;
cin >> n >> L >> R;
long long target = n - 1;
// 计算t的最小值(向上取整)
long long low = (L - target + n - 1) / n;
// 计算t的最大值(向下取整)
long long high = (R - target) / n;
if (low <= high) {
cout << target << endl;
} else {
cout << R % n << endl;
}
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;
}