信息学奥赛-入门级 题库
T1拼数


#include <bits/stdc++.h>
using namespace std;
//循环字符串,将所有数字插入vector
//将vector排序
//倒序输出
string s;
vector<char> v;
int main() {
cin >> s;
for (char i : s) {
if (i >= '0' && i <= '9') {
v.push_back(i);
}
}
sort(v.begin(), v.end(), greater<int>());
for (char i : v) {
cout << i;
}
return 0;
}T2座位



#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, a, a1, k = 1;
cin >> n >> m >> a1;
for (int i = 1; i < n*m; i++) {
cin >> a;
if (a > a1) k++;
}
int lie = ceil(1.0 * k / n);
int g = k % n;
if (g == 0) g = n; //特殊情况
int hang;
if (lie % 2 == 0) { //偶数列:从下往上排
hang = n - g + 1;
} else { //奇数列:从上往下排
hang = g;
}
cout << lie << " " << hang;
return 0;
}T3异或和



#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
int n, k, a;
int dp[MAXN];
//存储每种异或和最后一次出现的下标
map<int, int> m;
int main() {
cin >> n >> k;
int qzh = 0;
m[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a;
qzh ^= a;
dp[i] = dp[i-1];
if (m.find(k ^ qzh) != m.end()) dp[i] = max(dp[i], dp[m[k ^ qzh]] + 1);
m[qzh] = i;
}
cout << dp[n];
return 0;
}T4多边形



#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int MAXN = 5005;
int a[MAXN];
int cnt[MAXN][MAXN];
int dp[MAXN];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
cnt[1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 5001; j++) {
cnt[i+1][j] = (cnt[i+1][j] + cnt[i][j]) % mod;
cnt[i+1][min(j+a[i],5001)] = (cnt[i+1][min(j+a[i],5001)] + cnt[i][j]) % mod;
}
}
//求dp
for (int i = 1; i <= n; i++) {
dp[i] = dp[i-1];
for (int j = a[i]+1; j <= 5001; j++) dp[i] = (dp[i] + cnt[i][j]) % mod;
}
cout << dp[n];
return 0;
}字符串解码
“行程长度编码”(Run-Length Encoding)是一种无损压缩算法,常用于压缩重复字符较多的数据,以减少存储空间。假设原始字符串不包含数字字符,压缩规则如下:
①如果原始字符串中一个字符连续出现N次(N≥2),在压缩字符串中表示为“字符+数字N”。例如,编码“A12”代表12个连续的字符A。
②如果原始字符串中一个字符只出现1次,在压缩字符串中表示为该字符本身。例如,编码“B”代表1个字符B。
以下程序实现读取压缩字符串并输出其原始的、解压后的形式,试补全程序。
精明与糊涂
有N个人,分为两类:①精明人:永远能正确判断其他人是精明还是糊涂;②糊涂人:判断不可靠,会给出随机的判断。已知精明人严格占据多数,即如果精明人有k个,则满足k>N/2
你只能通过函数query(;j)让第i个人判断第j个人:返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人”。目标是通过互相判断,找出至少一个百分之百能确定的精明人(无需关心query(i,j)的内部实现)。
以下程序利用“精明人占多数”的优势,通过“消除”过程让人们互相判断并抵消.经过若干轮抵消后,最终留下的候选者必然属于多数派,即精明人。
例如,假设有三个人0、1、2。如果0说1是糊涂人,而1也说0是糊涂人,则O和1至少有一个是糊涂人。程序将同时淘汰0和1。由千三人里至少有两个精明人,我们确定2是精明人。试补全程序。
数字游戏

#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;
}