首页 › 题库 › 信息学奥赛 › 信息学奥赛-入门级

信息学奥赛-入门级 题库

共 1088 道题 ,第 38 / 55 页 · 按题型筛选,点「查看答案」核对解析
741 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

如果a数组有重复的数字,则程序运行时会发生错误。()

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
742 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

如果b数组全为0,则输出为0。()

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
743 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

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;
}
题目详情
744 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

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;
}
题目详情
745 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

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;
}
题目详情
746 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

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;
}
题目详情
747 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
748 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <iostream>
#include <cstring>
using namespace std;

int a[200][200];
int an[200];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        int min_val = a[i][1];
        for (int j = 1; j <= n; j++) {
            if (a[i][j] < min_val) {
                min_val = a[i][j];
            }
        }
        an[i] = min_val;
    }
    // 后续处理逻辑...
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
749 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long  

int f[5007][5007]; 
int a[5007], b[5007];  
int n; 

int main() {
    scanf("%d", &n); 
    
    // 读取第一个序列
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]); 
    }
    
    // 读取第二个序列
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]); 
    }
    
    // 动态规划计算最长公共子序列(LCS)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 状态转移:取上方或左方的最大值
            f[i][j] = std::max(f[i-1][j], f[i][j-1]);
            // 若当前元素相等,则可以从左上角+1转移
            if (a[i] == b[j]) {
                f[i][j] = std::max(f[i][j], f[i-1][j-1] + 1);
            }
        }
    }
    
    printf("%d\n", f[n][n]);
    return 0;
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
750 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

字符串解码

“行程长度编码”(Run-Length Encoding)是一种无损压缩算法,常用于压缩重复字符较多的数据,以减少存储空间。假设原始字符串不包含数字字符,压缩规则如下:

①如果原始字符串中一个字符连续出现N次(N≥2),在压缩字符串中表示为“字符+数字N”。例如,编码“A12”代表12个连续的字符A。

②如果原始字符串中一个字符只出现1次,在压缩字符串中表示为该字符本身。例如,编码“B”代表1个字符B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式,试补全程序。

#include <cctype>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string z;
    cin >> z;  // 修正语法错误:将cin:>>改为cin >>
    string s = "";

    for (int i = 0; i < z.length(); ) {
        char ch = z[i];

        if (___①_____ && isdigit(z[i+1])) {
            i++;
            int count = 0;
            while (i < z.length() && isdigit(z[i])) {
                count = ____②___;
                i++;
            }
            for (int j = 0; j < __③__; ++j) {
                s += ch;
            }
        } else {
            s += __④__;
            _⑤___;
        }
    }

    cout << s << endl;
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
751 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

精明与糊涂

有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 <vector>
using namespace std;

int N;
bool query(int i, int j);  // 函数声明,参数间添加空格

int main() {
    cin >> N;

    int candidate = 0;
    int count = _①___;  // 保留留空

    for (int i = 1; i < N; ++i) {
        if (___②___) {  // 修正语法错误:将《改为{
            candidate = i;
            count = 1;
        } else {
            if (___③___) {
                ____④_____;  // 保留留空
            } else {
                count++;
            }
        }
    }  // 补充循环体闭合括号(原代码缺失)

    cout << __⑤__ << endl;  // 修正语法错误:补充<<和空格
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
752 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.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则计数变量加一,最后输出计算变量的值。 

题目详情
753 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

公交换乘


答案与解析
参考答案
#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分钟内,有做过的地铁票,并且费用大于等于公交车的,就免费;

否则要花费。

题目详情
754 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

纪念品


答案与解析
参考答案
#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。

每天买哪些纪念品呢?根据测试样例分析,纪念品任意多,没有个数限制。根据金币的上限,可以推到出这个就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包处理,当天不想卖出金币,相当于卖出金币再买入金币。

题目详情
755 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

加工零件


答案与解析
参考答案
#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的奇偶性一致。

题目详情
756 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

乘方(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;
}


题目详情
757 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

解密(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;
}


题目详情
758 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

逻辑表达式(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;
}

题目详情
759 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

上升点列(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;
}


题目详情
760 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

分糖果


答案与解析
参考答案
//参考代码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;
}

题目详情