首页 › 题库 › 信息学奥赛 › 信息学奥赛-提高级

信息学奥赛-提高级 题库

共 842 道题 ,第 30 / 43 页 · 按题型筛选,点「查看答案」核对解析
581 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T4、擂台游戏(arena)

答案与解析
参考答案
//参考代码1
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
	template<class T>void rd(T &x) {
		static char ch(0);
		for(x=0,ch=getc(); !isdigit(ch); ch=getc());
		for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
	}
	template<class T>void wr(T x,const char End='\n') {
		static int top(0);
		static int st[50];
		do st[++top]=x%10,x/=10;
		while(x);
		while(top)putc(st[top]^'0'),--top;
		putc(End);
	}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
	if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
	dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
	if(L>R)return;
	if(!h) {
		int x(u-(1<<k)+1);
		if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
		if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
		return;
	}
	dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
	rd(n),rd(m);
	while((1<<k)<n)++k;
	FOR(i,1,n)rd(a_[i]);
	FOR(i,1,m)rd(c[i]);
	DOR(i,k-1,0) {
		scanf("%s",s);
		DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
	}
	rd(Q);
	while(Q--) {
		static int X[4];
		rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
		FOR(i,1,n)a[i]=a_[i]^X[i&3];
		dfs0(1,k),RCL(sum+1,0,ll,n);
		FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
		FOR(i,1,n)sum[i]+=sum[i-1];
		ll ans(0);
		FOR(i,1,m)ans^=i*sum[c[i]];
		wr(ans);
	}
	return 0;
}
//参考代码2
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
	template<class T>void rd(T &x) {
		static char ch(0);
		for(x=0,ch=getc(); !isdigit(ch); ch=getc());
		for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
	}
	template<class T>void wr(T x,const char End='\n') {
		static int top(0);
		static int st[50];
		do st[++top]=x%10,x/=10;
		while(x);
		while(top)putc(st[top]^'0'),--top;
		putc(End);
	}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
	if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
	dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
	if(L>R)return;
	if(!h) {
		int x(u-(1<<k)+1);
		if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
		if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
		return;
	}
	dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
	rd(n),rd(m);
	while((1<<k)<n)++k;
	FOR(i,1,n)rd(a_[i]);
	FOR(i,1,m)rd(c[i]);
	DOR(i,k-1,0) {
		scanf("%s",s);
		DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
	}
	rd(Q);
	while(Q--) {
		static int X[4];
		rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
		FOR(i,1,n)a[i]=a_[i]^X[i&3];
		dfs0(1,k),RCL(sum+1,0,ll,n);
		FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
		FOR(i,1,n)sum[i]+=sum[i-1];
		ll ans(0);
		FOR(i,1,m)ans^=i*sum[c[i]];
		wr(ans);
	}
	return 0;
}
//参考代码3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls x<<1
#define rs x<<1|1
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define ll long long
using namespace std;
const int N = (1 << 17) + 5;
int mx[20][N << 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1;
bool vis[N];
ll ans[N], sum;
struct node {
	ll sum;
	int x;
	bool tp, d;
} t[N << 2];
inline void build(int x, int l, int r) {
	if (l == r) {
		t[x].x = l;
		return ;
	}
	int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
	build(lson);
	build(rson);
	int win = a[t[x << 1 | d].x] >= k;
	t[x].x = t[x << 1 | (d ^ !win)].x;
	if (!d && win)t[x].tp = 1, ok[r]++, ok[mid]--;
	else t[x].tp = 0;
}
inline void build2(int x, int l, int r, int *mx) {
	t[x].sum = (l + r) * (r - l + 1ll) / 2;
	if (l == r)return ;
	int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
	if (~mx[x])mx[ls] = mx[rs] = mx[x];
	else mx[x << 1 | d] = k;
	build2(lson, mx);
	build2(rson, mx);
}
inline void up(int x) {
	sum += !vis[x] * x;
	vis[x] = 1;
}
inline int rd() {
	char c;
	int f = 1;
	while (!isdigit(c = getchar()))if (c == '-')f = -1;
	int x = c - '0';
	while (isdigit(c = getchar()))x = x * 10 + (c ^ 48);
	return x * f;
}
inline char gc() {
	char c;
	while ((c = getchar()) <= ' ');
	return c;
}
int main() {
	// freopen("arena.in","r",stdin);
	// freopen("arena.out","w",stdout);
	n = rd();
	m = rd();
	for (int i = 1; i <= n; i++)aa[i] = rd();
	for (int i = 1; i <= m; i++)c[i] = rd();
	while (nn < n)nn <<= 1;
	for (int i = 2; i <= nn; i++)lg[i] = lg[i >> 1] + 1;
	for (int i = nn / 2; i; i >>= 1)
		for (int j = i; j < i * 2; j++)
			t[j].d = gc() - '0';
	memset(mx, -1, sizeof mx);
	for (int s = 0; (1 << s) <= nn; s++)
		build2(1 << s, 1, nn>>s, mx[s]);
	for (int T = rd(); T--;) {
		int yh[4] = {rd(), rd(), rd(), rd()};
		for (int i = 1; i <= n; i++)a[i] = aa[i] ^ yh[i & 3];
		memset(ok, 0, sizeof ok);
		build(1, 1, nn);
		for (int i = nn, rt = 1, s = 0; i; i--) {
			if ((1 << lg[i]) == i) {
				if (i != nn)rt <<= 1, s++;
				for (int j = 1; j <= i; j++)vis[j] = 0;
				sum = 0;
				up(t[rt].x);
			}
			ans[i] = sum;
			if (ok[i] += ok[i + 1])continue;
			up(i);
			int x = i + nn - 1;
			while (x != rt) {
				int d = x & 1;
				x >>= 1;
				if (!d)
					if (t[x].tp)sum += t[rs].sum;
					else break;
				else if (a[t[ls].x] >= mx[s][ls])up(t[ls].x);
			}
		}
		ll num = 0;
		for (int i = 1; i <= m; i++)num ^= i * ans[c[i]];
		printf("%lld\n", num);
	}
	return 0;
}
题目详情
582 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

阅读程序

#include <iostream>
using namespace std;

const int N = 1000;
int c[N];

int logic(int x, int y) {
    return (x & y) ^ ((x ^ y) | (~x & y));
}

void generate(int a, int b, int *c) {
    for (int i = 0; i < b; i++) {
        c[i] = logic(a, i) % (b + 1);
    }
}

void recursion(int depth, int *arr, int size) {
    if (depth <= 0 || size <= 1) return;
    int pivot = arr[0];
    int i = 0, j = size - 1;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    recursion(depth - 1, arr, j + 1);
    recursion(depth - 1, arr + i, size - i);
}

int main() {
    int a, b, d;
    cin >> a >> b >> d;
    generate(a, b, c);
    recursion(d, c, b);
    for (int i = 0; i < b; i++) cout << c[i] << " ";
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
583 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <string>
using namespace std;

const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];

int solve() {
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {
            int k = (j << 1) | (s[i] - '0');
            if (j != 0 || s[i] == '1')
                dp[k] = (dp[k] + dp[j]) % P;
        }
    }
    int ans = 0;
    for (int i = 0; i < (1 << m); i++) {
        ans = (ans + 1ll * i * dp[i]) % P;
    }
    return ans;
}

int solve2() {
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        int cnt = 0;
        int num = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                num = num * 2 + (s[j] - '0');
                cnt++;
            }
        }
        if (cnt <= m) (ans += num) %= P;
    }
    return ans;
}

int main() {
    cin >> n >> m;
    cin >> s;
    if (n <= 20) {
        cout << solve2() << endl;
    }
    cout << solve() << endl;
    return 0;
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
584 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;

typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];

struct H {
    int h1, h2, l;
    H(bool b = false) {
        h1 = b + K1;
        h2 = b + K2;
        l = 1;
    }
    H operator + (const H &h)const {
        H hh;
        hh.l = l + h.l;
        hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
        hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
        return hh;
    }
    bool operator == (const H &h)const {
        return l == h.l && h1 == h.h1 && h2 == h.h2;
    }
    bool operator < (const H &h)const {
        if (l != h.l) return l < h.l;
        else if (h1 != h.h1) return h1 < h.h1;
        else return h2 < h.h2;
    }
} h[maxn];

void init() {
    memset(p, 1, sizeof(p));
    p[0] = p[1] = false;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i++) {
        p1[i] = (1ll * B1 * p1[i - 1]) % P1;
        p2[i] = (1ll * B2 * p2[i - 1]) % P2;
        if (!p[i]) continue;
        for (int j = 2 * i; j <= n; j += i) {
            p[j] = false;
        }
    }
}

int solve() {
    for (int i = n; i; i--) {
        h[i] = H(p[i]);
        if (2 * i + 1 <= n) {
            h[i] = h[2 * i] + h[i] + h[2 * i + 1];
        } 
        else if (2 * i <= n) {
            h[i] = h[2 * i] + h[i];
        }
    }
    cout << h[1].h1 << endl;
    sort(h + 1, h + n + 1);
    int m = unique(h + 1, h + n + 1) - (h + 1);
    return m;
}

int main() {
    cin >> n;
    init();
    cout << solve() << endl;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
585 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

合并序列。有两个长度为N的单调不降序列A和B,序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和,求其中第k小的和。上述参数满足N≤105和1≤K≤N2。

#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int *upper_bound(int *a, int *an, int ai) {
    int l = 0, r = ( ① );
    while (l < r) {
        int mid = (l + r) >> 1;
        if (②) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ( ③ );
}

long long get_rank(int sum) {
    long long rank = 0;
    for (int i = 0; i < n; i++) {
        rank += upper_bound(b, b + n, sum - a[i]) - b;
    }
    return rank;
}

int solve() {
    int l = 0, r =( ④ );
    while (l < r) {
        int mid = ((long long)l + r) >> 1;
        if  ( ⑤ ) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    return l;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    cout << solve() << endl;
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
586 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

次短路。已知有一个n个点m条边的有向图G,并且给定图中的两个点s和t,求次短路(长度严格大于最短路的最短路径)。如果不存在,输出一行“-1”。如果存在,输出两行,第一行表示此段路经的长度,第二行表示此段路的一个方案。

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279;

int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn << 1], *dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];

void add(int a, int b, int c) {
    ++tot;
    nxt[tot] = head[a];
    to[tot] = b;
    w[tot] = c;
    head[a] = tot;
}

bool upd(int a, int b, int d, priority_queue<pair<int, int> > &q) {
    if (d >= dis[b])return false;
    if (b < n)  ( ① );
    q.push( ② );
    dis[b] = d;
    pre[b] = a;
    return true;
}

void solve() {
    priority_queue<pair<int, int> >q;
    q.push(make_pair(0, s));
    memset(dis,  ( ③ ), sizeof(dis));
    memset(pre, -1, sizeof(pre));
    dis2 = dis + n;
    pre2 = pre + n;
    dis[s] = 0;

    while (!q.empty()) {
        int aa = q.top().second;q.pop();
        if (vis[aa])continue;
        vis[aa] = true;
        int a = aa % n;
        for (int e = head[a]; e; e = nxt[e]) {
            int b = to[e], c = w[e];
            if (aa < n) {
                if (!upd(a, b, dis[a] + c, q))
                   ( ④ );
            }
            else {
                upd(n + a, n + b, dis2[a] + c, q);
            }
        }
    }
}

void out(int a) {
    if (a != s) {
        if (a < n)
            out(pre[a]);
        else
            out( ⑤ );
    }
    printf("%d%c", a % n + 1, " \n"[a == n + t]);
}

int main() {
    scanf("%d%d%d%d", &n, &m,&s,&t);
    s--, t--;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a - 1, b - 1, c);
    }
    solve();
    if (dis2[t] == inf)
        puts("-1");
    else {
        printf("%d\n", dis2[t]);
        out(n + t);
    }
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
587 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

密码锁(lock)

【题目描述】

小Y有一把五个拨圈的密码锁。如图所示,每个拨圈上是从0到9的数字。每个拨圈都是从0到9的循环,即9拨动一个位置后可以变成0或8,

图1:密码锁

因为校园里比较安全,小Y采用的锁车方式是:从正确密码开始,随机转动密码锁仅一次;每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。当小Y选择同时转动两个相邻拨圈时,两个拨圈转动的幅度相同,即小Y可以将密码锁从00115转成11115,但不会转成12115。

时间久了,小Y也担心这么锁车的安全性,所以小Y记下了自己锁车后密码锁的n个状态,注意这n个状态都不是正确密码。

为了检验这么锁车的安全性,小Y有多少种可能的正确密码,使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部n个状态。

【输入格式】

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

输入的第一行包含一个正整数n,表示锁车后密码锁的状态数。

接下来n行每行包含五个整数,表示一个密码锁的状态。

【输出格式】

输出到文件lock.out中。

输出一行包含一个整数,表示密码锁的这n个状态按照给定的锁车方式能对应多少种正确密码。


【样例1输入】

1
0 0 1 1 5

【样例1输出】

81

【样例1解释】

一共有81种可能的方案。

其中转动一个拨圈的方案有45种,转动两个拨圈的方案有36种。


【样例2】

见选手目录下的lock/lock2.in与lock/lock2.ans。

答案与解析
参考答案

题目详情
588 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

消消乐(game)

【题目描述】

小L现在在玩一个低配版本的消消乐,该版本的游戏是一维的,一次也只能消除两个相邻的元素。

现在,他有一个长度为n且仅由小写字母构成的字符串。我们称一个字符串是可消除的,当且仅当可以对这个字符串进行若干次操作,使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符,操作后剩余字符串会拼接在一起。

小L想知道,这个字符串的所有非空连续子串中,有多少个是可消除的。

【输入格式】

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

输入的第一行包含一个正整数n,表示字符串的长度。

输入的第二行包含一个长度为n且仅由小写字母构成的的字符串,表示题目中询问的字符串。

【输出格式】

输出到文件game.out中。

输出一行包含一个整数,表示题目询问的答案。


【样例1输入】

8
accabccb

【样例1输出】

5

【样例1解释】

一共有5个可消除的连续子串,分别是cc、acca、cc、bccb、accabccb。


【样例2】

见选手目录下的game/game2.in与game/game2.ans。

【样例3】

见选手目录下的game/game3.in与game/game3.ans。

【样例4】

见选手目录下的game/game4.in与game/game4.ans。

答案与解析
参考答案

题解1:


题解2:


题解3:

题目详情
589 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

结构体(struct)

【题目背景】

在C++等高级语言中,除了int和float等基本类型外,通常还可以自定义结构体类型。在本题当中,你需要模拟一种类似C++的高级语言的结构体定义方式,并计算出相应的内存占用等信息。

【题目描述】

在这种语言中,基本类型共有4种:byte,short,int,long,分别占据1,2,4,8字节的空间。

定义一个结构体类型时,需要给出类型名和成员,其中每个成员需要按顺序给出类.型和名称。类型可以为基本类型,也可以为先.定义过的结构体类型。注意,定义结构体类型时不会定义具体元素,即不占用内存。

定义一个元素时,需要给出元素的类型和名称。元素将按照以下规则占据内存:

• 元素内的所有成员将按照定义时给出的顺序在内存中排布,对于类型为结构体的成员同理。

• 为了保证内存访问的效率,元素的地址占用需要满足对齐规则,即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。具体而言:

–对于基本类型:对齐要求等于其占据空间大小,如int类型需要对齐到4字节,其余同理。

–对于结构体类型:对齐要求等于其成员的对齐要求的最大值,如一个含有int和short的结构体类型需要对齐到4字节。

以下是一个例子(以C++语言的格式书写):

struct d {
    short a;
    int b;
    short c;
};
d e;

该代码定义了结构体类型d与元素e。元素e包含三个成员e.a,e.b,e.c,分别占据第0∼1,4∼7,8∼9字节的地址。由于类型d需要对齐到4字节,因此e占据了第0∼11字节的地址,大小为12字节。

你需要处理n次操作,每次操作为以下四种之一:

1.定义一个结构体类型。具体而言,给定正整数k与字符串s,t1,n1,...,tk,nk,其中k表示该类型的成员数量,s表示该类型的类型名,t1,t2,...,tk按顺序分别表示每个成员的类型,n1,n2,...,nk按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求,用一个空格分隔。

2.定义一个元素,具体而言,给定字符串t,n分别表示该元素的类型与名称。所有被定义的元素将按顺序,从内存地址为0开始依次排开,并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。

3.访问某个元素。具体而言,给定字符串s,表示所访问的元素。与C++等语言相同,采用.来访问结构体类型的成员。如a.b.c,表示a是一个已定义的元素,它是一个结构体类型,有一个名称为b的成员,它也是一个结构体类型,有一个名称为c的成员。你需要输出如上被访问的最内层元素的起始地址。

4.访问某个内存地址。具体而言,给定非负整数addr,表示所访问的地址,你需要判断是否存在一个基本类型的元素占据了该地址。若是,则按操作3中的访问元素格式输出该元素;否则输出ERR。

【输入格式】

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

第1行:一个正整数n,表示操作的数量。

接下来若干行,依次描述每个操作,每行第一个正整数op表示操作类型:

•若op=1,首先输入一个字符串s与一个正整数k,表示类型名与成员数量,接下来k行每行输入两个字符串ti,ni,依次表示每个成员的类型与名称。

•若op=2,输入两个字符串t,n,表示该元素的类型与名称。

•若op=3,输入一个字符串s,表示所访问的元素。

•若op=4,输入一个非负整数addr,表示所访问的地址。

【输出格式】

输出到文件struct.out中。

输出n行,依次表示每个操作的输出结果,输出要求如题目描述中所述。


【样例1输入】

5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10

【样例1输出】

8 4
16 8
0
4
x.bb

【样例1解释】

结构体类型a中,int类型的成员aa占据第0∼3字节地址,short类型的成员ab占据第4∼5字节地址。又由于其对齐要求为4字节,可得其大小为8字节。由此可同理计算出结构体类型b的大小为16字节,对齐要求为8字节。

【样例2】

见选手目录下的struct/struct2.in与struct/struct2.ans。

【样例2解释】

第二个操作4中,访问的内存地址恰好在为了地址对齐而留下的“洞”里,因此没有基本类型元素占据它。

【样例3】

见选手目录下的struct/struct3.in与struct/struct3.ans。

【数据范围】

对于全部数据,满足1≤n≤100,1≤k≤100,0≤addr≤1018。

所有定义的结构体类型名、成员名称和定义的元素名称均由不超过10个字符的小

写字母组成,且都不是byte,short,int,long(即不与基本类型重名)。

所有定义的结构体类型名和元素名称互不相同,同一结构体内成员名称互不相同。

但不同的结构体可能有相同的成员名称,某结构体内的成员名称也可能与定义的结构体或元素名称相同。

保证所有操作均符合题目所述的规范和要求,即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。

保证任意结构体大小及定义的元素占据的最高内存地址均不超过1018。

特殊性质A:没有操作1;

特殊性质B:只有一个操作1;

特殊性质C:所有操作1中给出的成员类型均为基本类型;

特殊性质D:基本类型只有long。

【提示】

对于结构体类型的对齐要求和大小,形式化的定义方式如下:

•设该结构体内有k个成员,其大小分别为s1,...,sk,对齐要求分别为a1,...,ak;

•则该结构体的对齐要求为a=max{a1,...,ak};

•再设这些成员排布时的地址偏移量分别为o1,...,ok,则:

–o1=0;

–对于i=2,...,k,oi为满足oi−1+si−1≤oi且ai整除oi的最小值;

–则该结构体的大小s为满足ok+sk≤s且a整除s的最小值;

对于定义元素时的内存排布,形式化的定义方式如下:

•设第i个被定义的元素大小为si,对齐要求为ai,起始地址为bi;

•则b1=0,对于2≤i,bi为满足bi−1+si−1≤bi且ai整除bi的最小值。

答案与解析
参考答案

题解1:


题解2:

题目详情
590 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

种树(tree)

【题目描述】

你是一个森林养护员,有一天,你接到了一个任务:在一片森林内的地块上种树,并养护至树木长到指定的高度。

森林的地图有n片地块,其中1号地块连接森林的入口。共有n−1条道路连接这些地块,使得每片地块都能通过道路互相到达。最开始,每片地块上都没有树木。

你的目标是:在每片地块上均种植一棵树木,并使得i号地块上的树的高度生长到不低于ai米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接(即通过单条道路相.连)的地块,种一棵高度为0米的树。如果所有地块均已种过树,则你当天不进行任何操作。特别地,第1天你只能在1号空地种树。

对每个地块而言,从该地块被种下树的当天开始,该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同,在第x天,i号地块上的树会长高max(bi+x∗ci,1)

米。注意这里的x是从整个任务的第一天,而非种下这棵树的第一天开始计算。

你想知道:最少需要多少天能够完成你的任务?

【输入格式】

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

输入的第一行包含一个正整数n,表示森林的地块数量。

接下来n行:每行包含三个整数ai,bi,ci,分别描述一片地块,含义如题目描述中所述。

接下来n−1行:每行包含两个正整数ui,vi,表示一条连接地块ui和vi的道路。

【输出格式】

输出到文件tree.out中。

输出一行仅包含一个正整数,表示完成任务所需的最少天数。


【样例1输入】

4
12 1 1
2 4 ‐1
10 3 0
7 10 ‐2
1 2
1 3
3 4

【样例1输出】

1 5

【样例1解释】

第1天:在地块1种树,地块1的树木长高至2米。

第2天:在地块3种树,地块1,3的树木分别长高至5,3米。

第3天:在地块4种树,地块1,3,4的树木分别长高至9,6,4米。

第4天:在地块2种树,地块1,2,3,4的树木分别长高至14,1,9,6米。

第5天:地块1,2,3,4的树木分别长高至20,2,12,7米。

【样例2】

见选手目录下的tree/tree2.in与tree/tree2.ans。

【样例3】

见选手目录下的tree/tree3.in与tree/tree3.ans。

【样例4】

见选手目录下的tree/tree4.in与tree/tree4.ans。


【数据范围】

对于所有测试数据有:1≤n≤105,1≤ai≤1018,1≤bi≤109,0≤|ci|≤109,1≤ui,vi≤n。保证存在方案能在109天内完成任务

特殊性质A:对于所有1≤i≤n,均有ci=0;

特殊性质B:对于所有1≤i<n,均有ui=i,vi=i+1;

特殊性质C:与任何地块直接相连的道路均不超过2条;

特殊性质D:对于所有1≤i<n,均有ui=1。

答案与解析
参考答案

题解1:

题解2:

题目详情
591 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假设输入的x是不超过65535的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
592 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

阅读程序

假设输入的n是不超过1000000的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
593 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

阅读程序

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
594 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(第k小路径)给定一张n个点m条边的有向无环图,顶点编号从0到n-1对于一条路径,我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n,m≤105和1≤k≤1018。

在程序中,我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。

试补全程序。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
595 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

(最大值之和)给定整数序列a0,… an-1,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤105和1≤a;≤108。

一个序列的非空连续子序列可以用两个下标l和r(其中0≤l≤r<n)表示,对应的序列为alal+1… ar。两个非空连续子序列不同,当且仅当下标不同。

例如,当原序列为[1,2,1,2]时,要计算子序列[1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2]的最大值之和,答案为18。注意[1,1]和[22]虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。解决该问题有许多算法,以下程序使用分治算法,时间复杂度0(nlogn)。

试补全程序。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
596 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
#include <string> 
#include <vector> 
 
using namespace std; 

int f(const string &s, const string &t) 
{ 
    int n = s.length(), m = t.length(); 

    vector<int> shift(128, m + 1);

    int i, j;
 
    for (j = 0; j < m; j++) 
        shift[t[j]] = m - j; 

    for (i = 0; i <= n - m; i += shift[s[i + m]]) {
        j = 0; 
        while (j < m && s[i + j] == t[j]) j++; 
        if (j == m) return i;
    }
  
    return -1; 
} 
 
int main() 
{ 
    string a, b;
    cin >> a >> b;
    cout << f(a, b) << endl;
    return 0;
}

假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
597 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 

using namespace std; 

const int MAXN = 105; 

int n, m, k, val[MAXN]; 
int temp[MAXN], cnt[MAXN]; 

void init() 
{ 
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> val[i]; 
    int maximum = val[0];
    for (int i = 1; i < n; i++) 
        if (val[i] > maximum) maximum = val[i];
    m = 1;
    while (maximum >= k) { 
        maximum /= k;
        m++;
    }
} 

void solve() 
{ 
    int base = 1;
    for (int i = 0; i < m; i++) { 
        for (int j = 0; j < k; j++) cnt[j] = 0; 
        for (int j = 0; j < n; j++) cnt[val[j] / base % k]++; 30         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1]; 
        for (int j = n - 1; j >= 0; j--) { 
            temp[cnt[val[j] / base % k] - 1] = val[j]; 
            cnt[val[j] / base % k]--; 
        }
        for (int j = 0; j < n; j++) val[j] = temp[j]; 
        base *= k;
    }
} 

int main() 
{ 
    init();
    solve();
    for (int i = 0; i < n; i++) cout << val[i] << ' '; 
    cout << endl;
    return 0;
}

假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在int 表示范围内,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
598 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
#include <algorithm> 

using namespace std; 

const int MAXL = 1000; 

int n, k, ans[MAXL]; 

int main(void) 
{ 
    cin >> n >> k;
    if (!n) cout << 0 << endl; 
    else
    {
        int m = 0;
        while (n)
        {
            ans[m++] = (n % (-k) + k) % k; 20             n = (ans[m - 1] - n) / k; 
        }
        for (int i = m - 1; i >= 0; i--) 
            cout << char(ans[i] >= 10 ?
                ans[i] + 'A' - 10 : 
                ans[i] + '0');
        cout << endl;
    }
    return 0;
}


假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
599 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严格单调递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里第 k 小的数值。

试补全程序。

#include <bits/stdc++.h> 

using namespace std; 


int solve(int *a1, int *a2, int n, int k) { 

  int left1 = 0, right1 = n - 1; 

  int left2 = 0, right2 = n - 1; 

  while (left1 <= right1 && left2 <= right2) { 

    int m1 = (left1 + right1) >> 1; 

    int m2 = (left2 + right2) >> 1; 

    int cnt =     ①     ; 

    if (     ②     ) { 

      if (cnt < k) left1 = m1 + 1; 

      else right2 = m2 - 1; 

    } else {

      if (cnt < k) left2 = m2 + 1; 

      else right1 = m1 - 1; 

    }

  }

  if (     ③     ) { 

    if (left1 == 0) {

      return a2[k - 1]; 

    } else {

      int x = a1[left1 - 1],      ④     ; 

      return std::max(x, y);

    }

  } else {

    if (left2 == 0) {

      return a1[k - 1]; 

    } else {

      int x = a2[left2 - 1],      ⑤     ; 

      return std::max(x, y);

    }

  }

} 

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
600 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(容器分水)有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允许下列的三种操作,分别为:

1)FILL(i):用水龙头将容器 i(i∈{1,2})灌满水;

2)DROP(i):将容器 i 的水倒进下水道;

3)POUR(i,j):将容器 i 的水倒进容器 j(完成此操作后,要么容器 j 被灌满,要么容器 i 被清空)。

求只使用上述的两个容器和三种操作,获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数,且 c≤max{a,b}。

试补全程序。


#include <bits/stdc++.h> 

using namespace std; 

const int N = 110; 

 

int f[N][N]; 

int ans; 

int a, b, c; 

int init; 


int dfs(int x, int y) { 

  if (f[x][y] != init)

    return f[x][y];

  if (x == c || y == c) 

    return f[x][y] = 0;

  f[x][y] = init - 1; 

  f[x][y] = min(f[x][y], dfs(a, y) + 1); 

  f[x][y] = min(f[x][y], dfs(x, b) + 1); 

  f[x][y] = min(f[x][y], dfs(0, y) + 1); 

  f[x][y] = min(f[x][y], dfs(x, 0) + 1); 

  int t = min(a - x, y); 

  f[x][y] = min(f[x][y],      ①     ); 

  t = min(x, b - y); 

  f[x][y] = min(f[x][y],      ②     ); 

  return f[x][y];

} 


void go(int x, int y) { 

  if (     ③     ) 

    return;

  if (f[x][y] == dfs(a, y) + 1) { 

    cout << "FILL(1)" << endl;

    go(a, y);

  } else if (f[x][y] == dfs(x, b) + 1) { 

    cout << "FILL(2)" << endl;

    go(x, b);

  } else if (f[x][y] == dfs(0, y) + 1) { 

    cout << "DROP(1)" << endl;

    go(0, y);

  } else if (f[x][y] == dfs(x, 0) + 1) { 

    cout << "DROP(2)" << endl;

    go(x, 0);

  } else { 

    int t = min(a - x, y); 

    if (f[x][y] ==      ④     ) { 

      cout << "POUR(2,1)" << endl;

      go(x + t, y - t); 

    } else {

      t = min(x, b - y); 

      if (f[x][y] ==      ⑤     ) { 

        cout << "POUR(1,2)" << endl;

        go(x - t, y + t); 

      } else

        assert(0);

    }

  }

} 


int main() { 

  cin >> a >> b >> c; 

  ans = 1 << 30; 

  memset(f, 127, sizeof f);

  init = **f;

  if ((ans = dfs(0, 0)) == init - 1) 

    cout << "impossible";

  else {

    cout << ans << endl;

    go(0, 0);

  }

} 

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情