首页 › 题库 › 信息学奥赛 › 1 数据结构进阶

信息学奥赛-提高级 题库

共 682 道题 ,第 24 / 35 页 · 按题型筛选,点「查看答案」核对解析
章节 1 数据结构进阶 清除
461 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

 (2分)当t是s的子序列时,输出一定不为0。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
462 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

 (2分)程序运行到第23行时,“j-i-1”一定不小于0。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
463 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

 (2分)当t是s的子序列时,pre数组和suf数组满足:对任意0≤i<slen,pre[i]>suf[i+1]+1。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
464 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

将第 21 行中 t 的类型声明从 int 改为 double,不会影响程序运行的结果。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
465 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

将第 26、27 行中的“/ sqrt(t) / 2”替换为“/ 2 / sqrt(t)”,不会影响程序运行的结果。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
466 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

将第 28 行中的“x * x”改成“sq(x)”、“y * y”改成“sq(y)” ,不会影响程序运行的结果。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
467 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(2 分)当输入为“0 0 0 1 1 0 0 1”时,输出为“1.3090”。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
468 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

程序总是会正常执行并输出两行两个相等的数。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
469 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

第 28 行与第 38 行分别有可能执行两次及以上。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
470 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

当输入为“5 -10 11 -9 5 -7”时,输出的第二行为“7”。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
471 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

程序总是先输出一行一个整数,再输出一行一个字符串。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
472 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

对于任意不含空白字符的字符串 str1,先执行程序输入“0 str1”,得到输出的第

二行记为 str2;再执行程序输入“1 str2”,输出的第二行必为 str1。( )


A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
473 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

当输入为“1 SGVsbG93b3JsZA==”时,输出的第二行为“HelloWorld”。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
474 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T1社团招新

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

vector<int> a, b, c;
int main() {
    int t;
    cin >> t;
    while(t--) {
        //清空vector
        a.clear();b.clear();c.clear();
        int n, ans = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            if (x >= y && x >= z) {
                ans += x;
                a.push_back(x - max(y, z));
            } else if (y >= x && y >= z) {
                ans += y;
                b.push_back(y - max(x, z));
            } else {
                ans += z;
                c.push_back(z - max(x, y));
            }
        }
        //判断
        n /= 2;
        if (a.size() <= n && b.size() <= n && c.size() <= n) {
            cout << ans << endl;
        } else {
            if (a.size() > n) {
                sort(a.begin(), a.end());
                for (int i = 0; i < a.size()-n; i++) {
                    ans -= a[i];
                }
            } else if (b.size() > n) {
                sort(b.begin(), b.end());
                for (int i = 0; i < b.size()-n; i++) {
                    ans -= b[i];
                }
            } else {
                sort(c.begin(), c.end());
                for (int i = 0; i < c.size()-n; i++) {
                    ans -= c[i];
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}
题目详情
475 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T2道路修复

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5;
const int MAXM = 1e6 + 5;
//快速读入 
inline int read() {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
//边结构体
struct edge{
    int u, v;
    int w;  //边权
};
int n, m, k;
vector<edge> OG;  //原图
vector<edge> NG;  //新图
int c[11];        //乡镇改造费用
int fa[MAXN+10];  //并查集
bool z[11];       //标记乡镇是否被选中
//按边权排序
bool cmp(edge x, edge y) { return x.w < y.w; }
// 标准并查集操作
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); }
void merge(int x, int y) {
    x = findroot(x);
    y = findroot(y);
    fa[x] = y;
}
//第一次kruskal,用于求出s=0的答案,并删去m条边中后续不可能被选中的边
long long kruskal_first() {
    for (int i = 1; i <= n; i++) fa[i] = i;  //并查集初始化
    long long res = 0;
    int cnt = n - 1;  //需要选取n-1条
    for (edge i : OG) {
        if (!cnt) return res;  //选完就退出
        int x = findroot(i.u), y = findroot(i.v);
        if (x != y) {
            merge(x, y);  //合并
            cnt--;
            res += i.w;
            NG.push_back(i);  //将第一次MST选中的边加入新图
        }
    }
    return res;
}
//加入乡镇后的MST
long long kruskal(int s) {
    for (int i = 1; i <= n+k; i++) fa[i] = i;  //并查集初始化
    memset(z, 0, sizeof z);  //标记数组初始化
    long long res = 0;
    int cnt = n - 1;
    for (int i = 0, j = 1; i < k; i++, j <<= 1) {
        if (s & j) {  //按二进制拆分状态
            z[i] = 1;
            res += c[i];
            cnt++;
        }
    }
    for (edge i : NG) {
        if (!cnt) return res;
        //如果边的连接点有乡镇,需要判断边是否存在
        if ((i.u > n && !z[i.u-n-1]) || (i.v > n && !z[i.v-n-1])) continue;
        int x = findroot(i.u), y = findroot(i.v);
        if (x != y) {
            merge(x, y);
            cnt--;
            res += i.w;
        }
    }
    return res;
}
int main() {
    int u, v, w;
    n = read();
    m = read();
    k = read();
    for (int i = 0; i < m; i++) {
        u = read();
        v = read();
        w = read();
        OG.push_back({u, v, w});
    }
    //排序原图并进行第一次kruskal
    sort(OG.begin(), OG.end(), cmp);
    long long ans = kruskal_first();
    //cout << ans << endl;
    for (int j = 0; j < k; j++) {
        c[j] = read();
        for (int i = 1; i <= n; i++) {
            w = read();
            NG.push_back({n+j+1, i, w});
        }
    }
    sort(NG.begin(), NG.end(), cmp);
    int MAXK = 1 << k;
    //对于乡镇的所有选取状态进行kruskal
    for (int s = 1; s < MAXK; s++) ans = min(ans, kruskal(s));
    printf("%lld", ans);
    return 0;
}
题目详情
476 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T3谐音替换

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int P = 1e9+7, Q=1e9+9, B=457, C=997;
ll next_hash (ll prev, int chr)
{
    ll a = prev >> 32, b = prev & -1u; chr ++;
    a = (a * B + chr) % P;
    b = (b * C + chr) % Q;
    return (a << 32) | b;
}
const int maxl = 5002424;
const int maxn = 200083;
struct node
{ int pt, nxt [27]; }
trie [maxl*2+maxn];
struct pn
{
    int rt;
    unordered_map <ll, int> mp;
} pns [maxn];
int ctc, ptc;
char s [maxl], t [maxl];
void q_diff (int len, int& dnq, int& dxq)
{
    int nq = len+1, xq=-1;
    int i;
    for (i=0; i<len; i++)
    if (s [i] != t [i])
    nq = min (nq, i), xq = max (xq, i);
    dnq = nq; dxq = xq;
}
#define jnode(var,chr) if(trie[var].nxt[chr])var=trie[var].nxt[chr];else var=trie[var].nxt[chr]=++ctc
#define ord(ch) (ch=='#'?26:ch-'a')
void add_s (int idx)
{
    scanf ("%s%s", s, t);
    int len = strlen (s);
    if (strcmp (s, t) == 0) return;
    int nq, xq; q_diff (len, nq, xq);
    int i, cur = 0;
    for (i=nq; i<=xq; i++)
    {
        jnode (cur, ord (s [i]));
        jnode (cur, ord (t [i]));
    }
    jnode (cur, 26);
    for (; i<len; i++)
    jnode (cur, ord (s [i]));
    int pt = trie [cur] .pt;
    if (pt == 0) pt = trie [cur] .pt = ++ptc;
    cur = pns [pt] .rt;
    if (cur == 0) cur = pns [pt] .rt = ++ctc;
    for (i=nq-1; i>=0; i--)
    jnode (cur, ord (s [i]));
    trie [cur] .pt ++;
}
void dfs_pn (int rt, int cur, ll ch, int cn)
{
    pns [rt] .mp [ch] = cn = trie [cur] .pt += cn;
    int i, m;
    for (i=0; i<27; i++)
    if (m = trie [cur] .nxt [i])
    dfs_pn (rt, m, next_hash (ch, i), cn);
}
ll hashes [maxl];
int query (void)
{
    scanf ("%s%s", s, t);
    int len = strlen (s);
    if (strlen (t) != len) return 0;
    int nq, xq; q_diff (len, nq, xq);
    int i, cur = 0;
    for (i=1; i<=nq; i++) hashes [i] = next_hash (hashes [i-1], ord (s [nq-i]));
    for (i=nq; i<=xq; i++)
    {
        if (0 == (cur = trie [cur] .nxt [ord (s [i])])) return 0;
        if (0 == (cur = trie [cur] .nxt [ord (t [i])])) return 0;
    }
    if (0 == (cur = trie [cur] .nxt [26])) return 0;
    int ans = 0;
    for (i=xq; i<len; i++)
    {
        if (trie [cur] .pt != 0)
        {
            int l = 0, r = nq;
            pn& cpn = pns [trie [cur] .pt];
            while (l < r)
            {
                int m = l+r+1 >> 1;
                if (cpn.mp.count (hashes [m])) l = m;
                else r = m-1;
            }
            ans += cpn.mp [hashes [l]];
        }
        if (i != len-1)
        if (0 == (cur = trie [cur] .nxt [ord (t [i+1])]))
        break;
    }
    return ans;
}
int main (void)
{
    int n, q; scanf ("%d%d", &n, &q);
    int i; for (i=1; i<=n; i++) add_s (i);
    for (i=1; i<=ptc; i++) dfs_pn (i, pns [i] .rt, 0, 0);
    for (i=1; i<=q; i++) printf ("%d\n", query ());
}
题目详情
477 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T4员工招聘

答案与解析
参考答案
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=507,P=998244353;
ll fac[N];
ll n,m,c[N],sum[N],k,w[N],ans; int dp[N][N][N];
char s[N];
void mian() {
	fac[0]=1; for (ll i=1;i<N;i++) fac[i]=fac[i-1]*i%P;
scanf("%lld%lld%s",&n,&m,s+1);
for (ll i=1;i<=n;i++) if (s[i]-'0'==1) k++,w[k]=i-k;
if (!k) return cout<<"0",void();
for (ll i=1;i<=n;i++) scanf("%lld",&c[i]),sum[c[i]]++;
for (ll i=1;i<=n;i++) sum[i]+=sum[i-1];
	dp[0][0][0]=1;
for (ll i=1,o=1;i<=k;i++) for (ll x=0;x<i;x++) for (ll y=0;x+y<i;y++) {
		(dp[i][x+1][y]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定第 i 个人走 
		(dp[i][x][y+1]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定他没走,容斥它 
		(dp[i][x][y]+=dp[i-1][x][y])%=P; // 指定他没走,不容斥它 
	}
for (ll x=0;x<=k-m;x++) for (ll y=0;x+y<=k;y++)
		(ans+=(y&1?P-1:1)*dp[k][x][y]%P*fac[n-x-y])%=P;
	cout<<ans;
}
bool ORY; int main() {
//	while (1)
//	int t; for (scanf("%d",&t);t--;)
mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
return 0;
}
题目详情
478 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
include <algorithm>
include <cstdio>
include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
479 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
include <algorithm>
include <cstdio>
include <cstring>
define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using %d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 1;
    while (w * (w + 1) / 2 < n) {
        ++w;
    }
    int ti = w;
    int nh = 0;
    while (true) {
        nh += ti;
        if (nh > n) {
            nh = n;
        }
        if (check(nh)) {
            for (int j = nh ti + 1; j < nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
        --ti;
        if (ti == 0) {
            assert_ans(n);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d", &t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
480 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
include <algorithm>
include <cstdio>
include <cstring>
include <vector>
define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k = k >> 1, x = x * x) {
        if (k & 1) {
            ans = ans * x;
        }
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int> &ans, int &cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1 = 1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 1]) {
            ++cntans1[newcnt1 1];
        } else {
            ans1[newcnt1++] = ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 1; i >= 0; --i) {
        while (las < cnt1 && ans1[las] + ans2[i] < 0) {
            ++las;
        }
        if (las < cnt1 && ans1[las] + ans2[i] == 0) {
            ans += cntans1[las];
        }
    }
    printf("%lld\n", ans);
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情