信息学奥赛-提高级 题库
共 842 道题
,第 28 / 43 页
· 按题型筛选,点「查看答案」核对解析
544
判断题
偏易
(2分)当t是s的子序列时,pre数组和suf数组满足:对任意0≤i<slen,pre[i]>suf[i+1]+1。( )
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
546
判断题
偏易
将第 26、27 行中的“/ sqrt(t) / 2”替换为“/ 2 / sqrt(t)”,不会影响程序运行的结果。( )
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
547
判断题
偏易
将第 28 行中的“x * x”改成“sq(x)”、“y * y”改成“sq(y)” ,不会影响程序运行的结果。( )
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
553
判断题
偏易
对于任意不含空白字符的字符串 str1,先执行程序输入“0 str1”,得到输出的第
二行记为 str2;再执行程序输入“1 str2”,输出的第二行必为 str1。( )
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
555
简答题
偏难
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;
}
556
简答题
偏难
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;
}
557
简答题
偏难
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 ());
}
558
简答题
偏难
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;
}