首页 › 题库 › 信息学奥赛 › 2.2 运算符

信息学奥赛-入门级 题库

共 639 道题 ,第 27 / 32 页 · 按题型筛选,点「查看答案」核对解析
521 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
522 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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则计数变量加一,最后输出计算变量的值。 

题目详情
523 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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分钟内,有做过的地铁票,并且费用大于等于公交车的,就免费;

否则要花费。

题目详情
524 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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。

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

题目详情
525 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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的奇偶性一致。

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


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


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

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

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

网络连接


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


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

小熊的果篮


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


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

优秀的拆分(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;
}


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

直播获奖( 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;
}


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

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


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

方格取数(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;
}


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

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张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。

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

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

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,可以使位数更少

在保证位数最少的前提下,还要尽可能把高位的数字变小(必须保证位数最小)

按照思想,可以找到这样的规律:

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

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

小苹果(apple)

【题目描述】

小Y的桌子上放着n个苹果从左到右排成一列,编号为从1到n。

小苞是小Y的好朋友,每天她都会从中拿走一些苹果。

每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道,多少天能拿完所有的苹果,而编号为n的苹果是在第几天被拿走的?

【输入格式】

从文件apple.in中读入数据。

输入的第一行包含一个正整数n,表示苹果的总数。

【输出格式】

输出到文件apple.out中。

输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为n的苹果是在第几天。


【样例1输入】

8

【样例1输出】

5 5

【样例1解释】

小苞的桌上一共放了8个苹果。

小苞第一天拿走了编号为1、4、7的苹果。

小苞第二天拿走了编号为2、6的苹果。

小苞第三天拿走了编号为3的苹果。

小苞第四天拿走了编号为5的苹果。

小苞第五天拿走了编号为8的苹果。


【样例2】

见选手目录下的apple/apple2.in与apple/apple2.ans。

答案与解析
参考答案

题目详情