信息学奥赛-提高级 题库
如右图所示,共有13个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0,或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要 次操作。

3
如下图所示,A到B是连通的。假设删除一条细的边的代价是1,删除一条粗的边的代价是2,要让A、B不连通,最小代价是_____(2分),最小代价的不同方案数是_______(3分)。(只要有一条删除的边不同,就是不同的方案)

4
9
(最长路径)给定一个有向无环图,每条边长度为1,求图中的最长路径长度。(第五空2分,其余3分)
输入:第一行是结点数n(不超过100)和边数m,接下来m行,每行两个整数a,b,表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。
输出:最长路径长度。
提示:先进行拓扑排序,然后按照拓扑序计算最长路径。
#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100]; // 记录每个结点的入度
int len[100]; // 记录以各结点为终点的最长路径长度
int queue[100]; // 存放拓扑排序结果
int main() {
cin >> n >> m;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
graph[i][j] = 0;
for (i = 0; i < n; i++)
degree[i] = 0;
for (i = 0; i < m; i++) {
cin >> a >> b;
graph[a][b] = 1;
(1) ;
}
tail = 0;
for (i = 0; i < n; i++)
if ( (2) ) {
queue[tail] = i;
tail++;
}
head = 0;
while (tail < n - 1) {
for (i = 0; i < n; i++)
if (graph[queue[head] ][i] == 1) {
(3) ;
if (degree[i] == 0) {
queue[tail] = i;
tail++;
}
}
(4) ;
}
ans = 0;
for (i = 0; i < n; i++) {
a = queue[i];
len[a] = 1;
for (j = 0; j < n; j++)
if (graph[j][a] == 1 && len[j] + 1 > len[a])
len[a] = len[j] + 1;
if ( (5) )
ans = len[a];
}
cout << ans << endl;
return 0;
}
(1)degree[b]=degree[b]+1 或 degree[b]++ 或 ++degree[b]
(2)degree[i]==0 或 !degree[i]
(3)degree[i]=degree[i]-1 或 degree[i]-- 或 --degree[i]
(4)head=head+1 或 head++ 或 ++head
(5)ans<len[a] 或 len[a]>ans
一个 1×8 的方格图形(不可旋转)用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色,且不允许两个黑格相邻,共有_________种填 涂方案。
55
双子序列最大和)给定一个长度为n(3≤n≤1000)的整数序列,要求从中选出两个连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为1,且两个连续子序列之间至少间隔1个数。(第五空4分,其余 2.5分)
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN];
// lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中,最大的序列和
int rmax[MAXN];
// rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中,最大的序列和
int main() {
cin >> n;
for (i = 0; i < n; i++)
cin >> x[i];
lmax[0] = x[0];
for (i = 1; i < n; i++)
if (lmax[i - 1] <= 0)
lmax[i] = x[i];
else
lmax[i] = lmax[i - 1] + x[i];
for (i = 1; i < n; i++)
if (lmax[i] < lmax[i - 1])
lmax[i] = lmax[i - 1];
(1) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i + 1] <= 0)
(2) ;
else
(3) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i] < rmax[i + 1])
(4) ;
ans = x[0] + x[2];
for (i = 1; i < n - 1; i++) {
sum = (5) ;
if (sum > ans)
ans = sum;
}
cout << ans << endl;
return 0;
}
(1)rmax[n-1]=x[n-1]
(2)rmax[i]=x[i]
(3)rmax[i]=rmax[i+1]+x[i]
(4)rmax[i]=rmax[i+1]
(5) lmax[i-1]+rmax[i+1]
(双栈模拟数组)只使用两个栈结构stack1和stack2,模拟对数组的随机读取。作为栈结构,stack1和stack2只能访问栈顶(最后一个有效元素)。栈顶指针top1和top2均指向栈顶元素的下一个位置。
输入第一行包含两个整数,分别是数组长度n和访问次数m,中间用单个空格隔开。
第二行包含n个整数,依次给出数组各项(数组下标从0到n-1)。第三行包含m个整数,需要访问的数组下标。对于每次访问,输出对应的数组元素。(前两空每空2.5分,其余每空3分,共14分)
#include <iostream>
using namespace std;
const int SIZE = 100;
int stack1[SIZE], stack2[SIZE];
int top1, top2;
int n, m, i, j;
void clearStack() {
int i;
for (i = top1; i < SIZE; i++)
stack1[i] = 0;
for (i = top2; i < SIZE; i++)
stack2[i] = 0;
}
int main() {
cin >> n >> m;
for (i = 0; i < n; i++)
cin >> stack1[i];
top1 = (1) ;
top2 = (2) ;
for (j = 0; j < m; j++) {
cin >> i;
while (i < top1 - 1) {
top1--;
(3) ;
top2++;
}
while (i > top1 - 1) {
top2--;
(4) ;
top1++;
}
clearStack();
cout << stack1[ (5) ] << endl;
}
return 0;
}
(1)n
(2)0
(3)stack2[top2]=stack1[top1]
(4)stack1[top1]=stack2[top2]
(5)top1-1
(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长,输出任意一个即可。例如,序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中,有两段满足条件的最长子序列,长度均为7,分别用下划线和上划线标出。
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 100;
int n, i, j, a[SIZE], cur1, cur2, count1, count2,
ans_length, ans_start, ans_end;
//cur1, cur2 分别表示当前子序列中的两个不同整数
//count1, count2 分别表示 cur1, cur2 在当前子序列中出现的次数
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i];
i = 1;
j = 1;
//i, j 分别表示当前子序列的首尾,并保证其中至多有两个不同整数
while ((j <= n) && (a[j] == a[i]))
j++;
cur1 = a[i];
cur2 = a[j];
count1 = (1) //(3 分)
count2 = 1;
ans_length = j - i + 1;
while (j < n) {
j++;
if (a[j] == cur1)
count1++;
else if (a[j] == cur2)
count2++;
else {
if (a[j - 1] == (2) ) { //(3 分)
while (count2 > 0) {
if (a[i] == cur1)
count1--;
else
ount2--;
i++;
}
cur2 = a[j];
count2 = 1;
}
else {
while (count1 > 0) {
if (a[i] == cur1)
(3) //(2 分)
else
(4) //(2 分)
i++;
}
(5) //(3 分)
count1 = 1;
}
}
if (ans_length < j - i + 1) {
ans_length = j - i + 1;
ans_start = i;
ans_end = j;
}
}
for (i = ans_start; i <= ans_end; i++)
cout<<a[i]<<' ';
return 0;
}
(1)j - 1
(2)cur1
(3)count1--(或 count1 = count1 – 1,或--count1)
(4)count2--(或 count2 = count2 – 1,或--count2)
(5)cur1 = a[j]
如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a, b, c(如右图所示),另有元素 d 已经出栈,则可能的入栈顺序有( )。

(新壳栈)小 Z 设计了一种新的数据结构“新壳栈”。首先,它和传统的栈一样支持压入、弹出操作。此外,其栈顶的前 c 个元素是它的壳,支持翻转操作。其中,c > 2 是一个固定的正整数,表示壳的厚度。小 Z 还希望,每次操作,无论是压入、弹出还是翻转,都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗?
程序期望的实现效果如以下两表所示。其中,输入的第一行是正整数 c,之后每行输入都是一条指令。另外,如遇弹出操作时栈为空,或翻转操作时栈中元素不足 c 个,应当输出相应的错误信息。


#include <iostream>
using namespace std;
const int
NSIZE = 100000,
CSIZE = 1000;
int n, c, r, tail, head, s[NSIZE], q[CSIZE];
//数组 s 模拟一个栈,n 为栈的元素个数
//数组 q 模拟一个循环队列,tail 为队尾的下标,head 为队头的下标
bool direction, empty;
int previous(int k)
{
if (direction)
return ((k + c - 2) % c) + 1;
else
return (k % c) + 1;
}
int next(int k)
{
if (direction)
① ;
else
return ((k + c - 2) % c) + 1;
}
void push()
{
int element;
cin>>element;
if (next(head) == tail) {
n++;
② ;
tail = next(tail);
}
if (empty)
empty = false;
else
head = next(head);
③ = element;
}
void pop()
{
if (empty) {
cout<<"Error: the stack is empty!"<<endl;
return;
}
cout<< ④ <<endl;
if (tail == head)
empty = true;
else {
head = previous(head);
if (n > 0) {
tail = previous(tail);
⑤ = s[n];
n--;
}
}
}
void reverse()
{
int temp;
if ( ⑥ == tail) {
direction = !direction;
temp = head;
head = tail;
tail = temp;
}
else
cout<<"Error: less than "<<c<<" elements in the stack!"<<endl;
}
int main()
{
cin>>c;
n = 0;
tail = 1;
head = 1;
empty = true;
direction = true;
do {
cin>>r;
switch (r) {
case 1: push(); break;
case 2: pop(); break;
case 3: reverse(); break;
}
} while (r != 0);
return 0;
}
①return (k % c) + 1
②s[n] = q[tail]
③q[head]
④q[head]
⑤q[tail]
⑥next(head)
(最优子序列)取m=6,给出长度为n的整数序列a1,a2,……an(0 ≤ ai<2m)。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1,b2,…,bk,定 义其子序列分值S为w(b1㊉b2)+w(b2㊉b3)+w(b3㊉b4)+……+w(bk-1㊉bk)。其中㊉表示按位异或。对于空子序列,规定其子序列分值为0。求一个子序列使得其子序列分值最大,输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1,a2,……,an。
提示:考虑优化朴素的动态规划算法,将前
位和后
位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。

(归并第 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);
}
}
}
蚯蚓
【问题描述】
本题中,我们将用符号
表示对c向下取整,例如:
蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n 只蚯蚓(n 为正整数)。每只蚯蚓拥有长度,我们设第 i 只蚯蚓的长度为 ai(i=1,2,…,n),并保证所有的长度都是非负整数(即:可能存在长度为 0的蚯蚓)。
每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 p(是满足 0 < p < 1 的有理数)决定,设这只蚯蚓长度为 x,神刀手会将其切成两只长度分别为
的蚯蚓。特殊地,如果这两个数的其中一个等于 0则这个长度为 0 的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 q(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 m 秒才能到来……(m 为非负整数)
蛐蛐国王希望知道这 m秒内的战况。具体来说,他希望知道:
m 秒内,每一秒被切断的蚯蚓被切断前的长度(有 m 个数);
m 秒后,所有蚯蚓的长度(有 n+m 个数)。
蛐蛐国王当然知道怎么做啦!但是他想考考你……
【输入格式】
从文件earthworm.in中读入数据。
第一行包含六个整数 n , m , q , u , v , t 其中:n , m , q的意义见【问题描述】;u , v , t均为正整数;你需要自己计算 p = u / v(保证 0 < u < v)t 是输出参数,其含义将会在【输出格式】中解释。
第二行包含 n 个非负整数,为 a 1 , a 2 , … , a n即初始时 n 只蚯蚓的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。

【输出格式】
输出到文件earthworm.out中。
第一行输出
个整数,按时间顺序,依次输出第 t 秒,第 2t 秒,第 3t 秒,……被切断蚯蚓(在被切断前)的长度。
第二行输出
个整数,输出 m 秒后蚯蚓的长度;需要按从大到小的顺序,依次输出排名第 t ,第 2t,第3t,……的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要输出,你也应输出一个空行。
请阅读样例来更好地理解这个格式。
【样例1输入】
3 7 1 1 3 1
3 3 2
【样例1输出】
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
【样例1说明】
在神刀手到来前:3 只蚯蚓的长度为3,3,2。
1 秒后:一只长度为3 的蚯蚓被切成了两只长度分别为1 和2 的蚯蚓,其余蚯蚓的长度增加了1。最终4 只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。
2 秒后:一只长度为4 的蚯蚓被切成了1 和3 。5 只蚯蚓的长度分别为:2,3,(1,3),4。
3秒后:一只长度为4 的蚯蚓被切断。6 只蚯蚓的长度分别为:3,4,2,4,(1,3)。
4 秒后:一只长度为4 的蚯蚓被切断。7 只蚯蚓的长度分别为:4,(1,3),3,5,2,4。
5 秒后:一只长度为5 的蚯蚓被切断。8 只蚯蚓的长度分别为:5,2,4,4,(1,4),3,5。
6 秒后:一只长度为5 的蚯蚓被切断。9 只蚯蚓的长度分别为:(1,4),3,5,5,2,5,4,6。
7 秒后:一只长度为6 的蚯蚓被切断。10 只蚯蚓的长度分别为:2,5,4,6,6,3,6,5,(2,4)。
所以,7 秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。7 秒后,所有蚯蚓长度从大到小排序为 6,6,6,5,5,4,4,3,2,2。
【样例2输入】
3 7 1 1 3 2
3 3 2
【样例2输出】
4 4 5
6 5 4 3 2
【样例2说明】
这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。
虽然第一行最后有一个6 没有被输出,但是第二行仍然要重新从第二个数再开始输出。
【样例3输入】
3 7 1 1 3 9
3 3 2
【样例3输出】
2
【样例3说明】
这个数据中只有t=9与上个数据不同。
注意第一行没有数要输出,但也要输出一个空行。
【子任务】


#include <bits/stdc++.h>
using namespace std;
double m,Q,u,v;
int t,n;
int cnt=0,tot=0,num=1;
double p;
int dd;
int ans1[(int)7e6+5];
int a[(int)7e6+5];
queue<int>q1;
queue<int>q2;
queue<int>q3;
inline int read() {
int X = 0, F = 1;
char C = getchar();
while (C < '0' || C>'9') {
if (C == '-') {
F = -1;
}
C = getchar();
}
while (C >= '0' && C <= '9') {
X = (X << 3) + (X << 1) + C - '0';
C = getchar();
}
return X * F;
}
inline void write(int N) {
if (N < 0) {
putchar('-');
N = -N;
}
if (N >= 10) {
write(N / 10);
}
putchar(N % 10 + '0');
}
inline int Get() {
int x1=INT_MIN,x2=INT_MIN,x3=INT_MIN;
if(!q1.empty())
x1=q1.front();
if(!q2.empty())
x2=q2.front();
if(!q3.empty())
x3=q3.front();
if(x1>=x2&&x1>=x3) {
q1.pop();
return x1;
} else if(x2>=x3) {
q2.pop();
return x2;
} else {
q3.pop();
return x3;
}
}//那个公式
int main() {
n=read();
m=read();
Q=read();
u=read();
v=read();
t=read();
p=(double)u/v;
for(register int i=1; i<=n; ++i) {
ans1[i]=read();
}
sort(ans1+1,ans1+n+1, greater<int>());//排序后再压入
for(register int i=1;i<=n;i++){
q1.push(ans1[i]);
}
int tag=0;
for(register int i=1; i<=m; ++i) {
int d=Get();
d+=tag;
a[i]=d;
int tad=d*p;
q2.push(tad-tag-Q);//截断后的第一节
q3.push(d-tad-tag-Q);//第二节
tag+=Q;
}
for(register int i=t; i<=m; i+=t) {
write(a[i]);
printf(" ");
}
puts("");
while(!q1.empty()||!q2.empty()||!q3.empty()) {
int u=Get();
if(num%t==0) {
write(u+tag);//因为前面减了一个tag,现在加上
printf(" ");
}
num++;
}
return 0;
}
玩具谜题
【问题描述】
小南有一套可爱的玩具小人,它们各有不同的职业。
有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

这时singer告诉小南一个谜题:“眼镜藏在我左数第3个玩具小人的右数第1个玩 具小人的左数第2个玩具小人那里。”
小南发现,这个谜题中玩具小人的朝向非常关键,因为朝内和朝外的玩具小人的左右方向是相反的:面朝圈内的玩具小人,它的左边是顺时针方向,右边是逆时针方向;而面向圈外的玩具小人,它的左边是逆时针方向,右边是顺时针方向。
小南一边艰难地辨认着玩具小人,一边数着:
“singer朝内,左数第3个是archer。
“archer朝外,右数第1个是thinker。
“thinker朝外,左数第2个是writer。
“所以眼镜藏在writer这里!”
虽然成功找回了眼镜,但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜,或是谜题的长度更长,他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为:
有n个玩具小人围成一圈,已知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜题,其中第i条指令形如“左数/右数第Si个玩具小人”。你需要输出依次数完这些指令后,到达的玩具小人的职业。
【输入格式】
从文件toy.in中读入数据。
输入的第一行包含两个正整数n, m,表示玩具小人的个数和指令的条数。
接下来n行,每行包含一个整数和一个字符串,以 逆时针 为顺序给出每个玩具小人的朝向和职业。其中0表示朝向圈内,1表示朝向圈外。保证不会出现其他的数。字符串长度不超过10且仅由小写字母构成,字符串不为空,并且字符串两两不同。整数和字符串之间用一个空格隔开。
接下来m行,其中第i行包含两个整数ai, si,表示第i条指令。若ai=0,表示向左数Si个人;若ai=1,表示向右数si个人。保证ai不会出现其他的数,1<=Si<n。
【输出格式】
输出到文件toy.out中。
输出一个字符串,表示从第一个读入的小人开始,依次数完m条指令后到达的小人的职业。
【样例1输入】
7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2
【样例1输出】
writer
【样例1说明】
这组数据就是【问题描述】中提到的例子。
【样例2输入】
10 10
1 c
0 r
0 p
1 d
1 e
1 m
1 t
1 y
1 u
0 v
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4
【样例2输出】
y
【子任务】
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试只解决一部分测试数据。
每个测试点的数据规模及特点如下表:

其中一些简写的列意义如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,m,ans=1;
int x,y;
char job[maxn][100];//job存储职业
int out[maxn];//out存储小人朝向
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=10*x+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
freopen("input.txt","r",stdin);
}
void readdata()
{
n=read(),m=read();
for(int i=0;i<n;i++)
{
scanf("%d",&out[i]);
scanf("%s",job[i]);
}
}
void work()
{
int now=0;
for(int i=1;i<=m;i++)
{
x=read(),y=read();
if(out[now]==0 && x==0) now=(now+n-y)%n;//这儿分四种情况,out[now]为0则朝圈内,再x=0时往左数,找出现在的now,下面的亦是如此。
else if(out[now]==0 && x==1) now=(now+y)%n;
else if(out[now]==1 && x==0) now=(now+y)%n;
else if(out[now]==1 && x==1) now=(now+n-y)%n;//但注意我们存储职业时是按照逆时针的顺序存储的,所以在面向圈外并按照小人右手数时,要减y,可以动手操作下
}
printf("%s",job[now]);
}
int main()
{
// init();
readdata();
work();
return 0;
}
换教室
【问题描述】
对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中,有 2n 节课程安排在 n 个时间段上。在第 i(1≤i≤n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 ci上课,而另一节课程在教室 di 进行。
在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n 节安排好的课程。如果学生想更换第 i 节课程的教室,则需要提出申请。若申请通过,学生就可以在第 i 个时间段去教室 di上课,否则仍然在教室 ci上课。
由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 i 节课程的教室时,申请被通过的概率是一个已知的实数 ki,并且对于不同课程的申请,被通过的概率是互相独立的。
学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的 m 门课程,也可以不用完这 m 个申请的机会,甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有 v 个教室,有 e 条道路。每条道路连接两间教室,并且是可以双向通行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。
当第 i(1≤i≤n−1)节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。
【输入格式】
从文件classroom.in中读入数据。
第一行四个整数 n,m,v,e。n 表示这个学期内的时间段的数量;m 表示牛牛最多可以申请更换多少节课程的教室;v 表示牛牛学校里教室的数量;e表示牛牛的学校里道路的数量。
第二行 n 个正整数,第 i(1≤i≤n)个正整数表示 ci,即第 i 个时间段牛牛被安排上课的教室;保证 1≤ci≤v。
第三行 n 个正整数,第 i(1≤i≤n)个正整数表示 di,即第 i 个时间段另一间上同样课程的教室;保证 1≤di≤v。
第四行 n 个实数,第 i(1≤i≤n)个实数表示 ki,即牛牛申请在第 i 个时间段更换教室获得通过的概率。保证0≤ki≤1。
接下来 e 行,每行三个正整数 aj,bj,wj,表示有一条双向道路连接教室 aj,bj,通过这条道路需要耗费的体力值是 wj;保证 1≤aj,bj≤v,1≤wj≤100。
保证1≤n≤2000,0≤m≤2000,1≤v≤300,0≤e≤90000。
保证通过学校里的道路,从任何一间教室出发,都能到达其他所有的教室。
保证输入的实数最多包含 3 位小数。
【输出格式】
输出到文件classroom.out中。
输出一行,包含一个实数,四舍五入精确到小数点后恰好2位,表示答案。你的输出必须和标准输出完全一样才算正确。
测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 4×10^−3。(如果你不知道什么是浮点误差,这段话可以理解为:对于大多数的算法,你可以正常地使用浮点数类型而不用对它进行特殊的处理)
【样例1输入】
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
【样例1输出】
2.80
【样例1说明】
所有可行的申请方案和期望收益如下表:

【提示】
道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是同一间教室。
请注意区分n,m,v,e的意义,n不是教室的数量,m不是道路的数量。
【子任务】

特殊性质1:图上任意两点ai,bi,
间,存在一条耗费体力最少的路径只包含一条道路。
特殊性质2:对于所有的1≤i≤n,ki=1。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5;
const double inf = 1e17 + 5;
int n, m, v, e, c[MAXN][2], mp[305][305];
double k[MAXN], dp[MAXN][MAXN][2], ans;
inline int read() {
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) {if (ch == '-')f = -1; ch = getchar();}
while (isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();}return u * f;
}
int main(){
memset(mp, 63, sizeof(mp));
n = read(); m = read(); v = read(); e = read();
for (register int i = 1; i <= n; i++)c[i][0] = read();
for (register int i = 1; i <= n; i++)c[i][1] = read();
for (register int i = 1; i <= n; i++)scanf("%lf", &k[i]);
for (register int i = 1; i <= e; i++){
int x = read(), y = read(), w = read();
mp[x][y] = mp[y][x] = min(mp[x][y], w);
}
for (register int k = 1; k <= v; k++)
for (register int i = 1; i <= v; i++)
for (register int j = 1; j <= v; j++)
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
for (register int i = 1; i <= v; i++)mp[i][i] = mp[i][0] = mp[0][i] = 0;
for (register int i = 0; i <= n; i++)
for (register int j = 0; j <= m; j++)dp[i][j][0] = dp[i][j][1] = inf;
dp[1][0][0] = dp[1][1][1] = 0;
for (register int i = 2; i <= n; i++){
dp[i][0][0] = dp[i - 1][0][0] + mp[c[i - 1][0]][c[i][0]];
for (register int j = 1; j <= min(i, m); j++){
int C1 = c[i - 1][0], C2 = c[i - 1][1], C3 = c[i][0], C4 = c[i][1];
dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][0] + mp[C1][C3], dp[i - 1][j][1] + mp[C1][C3] * (1 - k[i - 1]) + mp[C2][C3] * k[i - 1]));
dp[i][j][1] = min(dp[i][j][1], min(dp[i - 1][j - 1][0] + mp[C1][C3] * (1 - k[i]) + mp[C1][C4] * k[i], dp[i - 1][j - 1][1] + mp[C2][C4] * k[i] * k[i - 1] + mp[C2][C3] * k[i - 1] * (1 - k[i]) + mp[C1][C4] * (1 - k[i - 1]) * k[i] + mp[C1][C3] * (1 - k[i - 1]) * (1 - k[i])));
}
}
ans = inf;
for (register int i = 0; i <= m; i++)ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
printf("%.2lf", ans);
return 0;
}
函数调用(call)
【题目描述】
函数是各种编程语言中一项重要的概念,借助函数,我们总可以将复杂的任务分解成一个个相对简单的子任务,直到细化为十分简单的基础操作,从而使代码的组织更加严密、更加有条理。然而,过多的函数调用也会导致额外的开销,影响程序的运行效率。
某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类:
1. 将数据中的指定元素加上一个值;
2. 将数据中的每一个元素乘以一个相同值;
3. 依次执行若干次函数调用,保证不会出现递归(即不会直接或间接地调用本身)。
在使用该数据库应用时,用户可一次性输入要调用的函数序列(一个函数可能被调用多次),在依次执行完序列中的函数后,系统中的数据被加以更新。某一天,小 A 在应用该数据库程序处理数据时遇到了困难:由于频繁而低效的函数调用,系统在执行操作时进入了无响应的状态,他只好强制结束了数据库程序。为了计算出正确数据,小 A 查阅了软件的文档,了解到每个函数的具体功能信息,现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。
【输入格式】
输入文件名为 call.in。
第 1 行一个正整数 n,表示数据的个数。
第 2 行 n 个整数,第 i 个整数表示下标为 i 的数据的初始值为 ai。
第 3 行一个正整数 m,表示数据库应用程序提供的函数个数。函数从 1 ∼m 编号。
接下来 m 行中,第 j(1 ≤ j ≤ m)行的第一个整数为 Tj,表示 j 号函数的类型:
1. 若 Tj = 1,接下来两个整数 Pj, Vj 分别表示要执行加法的元素的下标及其增加的值;
2. 若 Tj = 2,接下来一个整数 Vj 表示所有元素所乘的值;
3. 若 Tj = 3,接下来一个正整数 Cj 表示 j 号函数要调用的函数个数,随后 Cj个整数 g1(j), g2(j), ⋯ , gCj(j) 依次表示其所调用的函数的编号。
第 m + 4 行一个正整数 Q,表示输入的函数操作序列长度。
第 m+ 5 行 Q 个整数 fi,第 i 个整数表示第 i 个执行的函数的编号。
【输出格式】
输出文件名为 call.out。
一行 n 个用空格隔开的整数,按照下标 1 ∼ n 的顺序,分别输出在执行完输入的函数序列后,数据库中每一个元素的值。答案对 998244353 取模。
【样例 1 输入】
3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3
【样例 1 输出】
6 8 12
【样例 1 解释】
1 号函数功能为将 a1 的值加一。2 号函数功能为所有元素乘 2。3 号函数将先调用 1 号函数,再调用 2 号函数。
最终的函数序列先执行 2 号函数,所有元素的值变为 2,4,6。
再执行 3 号函数时,先调用 1 号函数,所有元素的值变为 3,4,6。再调用 2号函数,所有元素的值变为 6,8,12。
【样例 2 输入】
10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3
【样例 2 输出】
36 282 108 144 180 216 504 288 324 360
【数据范围与提示】

对于所有数据:0 ≤ ai ≤ 10^4,Tj ∈ {1,2,3},1 ≤ Pj ≤ n,0 ≤ Vj ≤ 10^4,1 ≤
≤ m,1 ≤fi ≤ m。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 998244353;
const int N = 100005;
// d[i]表示全局积 f[i] 表示后继积
int a[N], op[N], b[N], c[N];
LL d[N], f[N];
vector<pair<int, int> > G[N], H[N];
LL dfs(int u) {
if (~d[u]) return d[u];
d[u] = op[u] == 2 ? c[u] : 1;
LL s = 1;
for (int i = G[u].size() - 1; i >= 0; i--) {
int v = G[u][i].first;
G[u][i].second = s;
d[u] = d[u] * dfs(v) % mod;
s = s * d[v] % mod; // 所有右兄弟的积
}
return d[u];
}
LL dfs2(int u) {
if (~f[u]) return f[u];
f[u] = 0;
for (int i = 0; i < H[u].size(); i++) {
int v = H[u][i].first, w = H[u][i].second;
f[u] = (f[u] + w * dfs2(v)) % mod;
}
return f[u];
}
int main() {
// freopen("call.in", "r", stdin);
// freopen("call.out", "w", stdout);
int n, m, q;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &op[i]);
if (op[i] == 1) {
scanf("%d %d", &b[i], &c[i]);
} else if (op[i] == 2) {
scanf("%d", &c[i]);
} else {
int t;
scanf("%d", &t);
while (t--) {
int v;
scanf("%d", &v);
G[i].push_back({v, 0});
}
}
}
scanf("%d", &q);
while (q--) {
int v;
scanf("%d", &v);
G[0].push_back({v, 0});
}
memset(d, -1, sizeof d);
memset(f, -1, sizeof f);
dfs(0);
for (int i = 1; i <= n; i++) {
a[i] = a[i] * d[0] % mod;
}
for (int u = 0; u <= m; u++) {
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first, w = G[u][i].second;
H[v].push_back({u, w});
}
}
f[0] = 1;
for (int i = 1; i <= m; i++) {
if (op[i] == 1) {
a[b[i]] = (a[b[i]] + dfs2(i) * c[i]) % mod;
}
}
for (int i = 1; i <= n; i++) {
printf("%d%c", a[i], " \n"[i == n]);
}
return 0;
}

