第34次csp

矩阵重塑（其一）

刷新

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录（样例文件）

题目背景

矩阵（二维）的重塑（reshape）操作是指改变矩阵的行数和列数，同时保持矩阵中元素的总数不变。

题目描述

矩阵的重塑操作可以具体定义为以下步骤：

设原矩阵为 MM，其维度为 n×mn×m，即有 nn 行和 mm 列。新矩阵为 M′M′，其维度为 p×qp×q。重塑操作要满足 n×m=p×qn×m=p×q，这保证了元素的总数不变。

线性化原矩阵：按照行优先的顺序，将原矩阵 MM 的元素转换成一个长度为 n×mn×m 的一维数组 AA。这意味着你先读取 MM 的第 00 行元素，然后是第 11 行，依此类推，直到最后一行。
填充新矩阵：使用一维数组 AA 中的元素按照行优先的顺序填充新矩阵 M′M′。首先填充 M′M′ 的第 00 行，直到该行有 qq 个元素，然后继续填充第 11 行，直到所有 pp 行都被填满。

给定原矩阵中的一个元素的位置 (i,j)(i,j)（0≤i<n0≤i<n 且 0≤j<m0≤j<m），我们可以找到这个元素在被线性化后的一维数组 AA 中的位置 kk（0≤k<n×m0≤k<n×m），然后确定它在新矩阵 M′M′ 中的位置 (i′,j′)(i′,j′)（0≤i′<p0≤i′<p 且 0≤j<q0≤j<q）。它们之间满足如下数学关系：i×m+j=k=i′×q+j′i×m+j=k=i′×q+j′

给定 n×mn×m 的矩阵 MM 和目标形状 pp、qq，试将 MM 重塑为 p×qp×q 的矩阵 M′M′。

输入格式

从标准输入读入数据。

输入共 n+1n+1 行。

输入的第一行包含四个正整数 nn、mm 和 pp、qq。

接下来依次输入原矩阵 MM 的第 00 到第 n−1n−1 行，每行包含 mm 个整数，按列下标从 00 到 m−1m−1 的顺序依次给出。

输出格式

输出到标准输出。

输出共 pp 行，每行 qq 个整数，表示重塑后的矩阵 M′M′。输出格式与输入相同，即依次输出 M′M′ 的第 00 行到第 p−1p−1 行；行内按列下标从 00 到 q−1q−1 的顺序输出，且两个整数间仅用一个空格分隔。

样例1输入

2 3 3 2
1 2 3
4 5 6

样例1输出

1 2
3 4
5 6

样例2输入

2 2 1 4
6 6
6 6

样例2输出

6 6 6 6

子任务

全部的测试数据满足：

nn、mm 和 pp、qq 均为正整数且 n×m=p×q≤104n×m=p×q≤104；
输入矩阵中每个元素的绝对值不超过 10001000。

提示

评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如 numpy、pytorch 等）。

方法1
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N][N],b[N][N],k[N*N];
int main()
{int n,m,p,q;cin>>n>>m>>p>>q;int t=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];k[t++]=a[i][j];}}t=0;for(int i=0;i<p;i++){for(int j=0;j<q;j++){b[i][j]=k[t++];}}for(int i=0;i<p;i++){for(int j=0;j<q;j++){cout<<b[i][j]<<" ";}cout<<endl;}}

#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N][N],b[N][N];map<int,int>k;int main()
{int n,m,p,q;cin>>n>>m>>p>>q;int t=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>k[i*m+j];}}for(int i=0;i<p;i++){for(int j=0;j<q;j++){a[i][j]=k[i*q+j];}}for(int i=0;i<p;i++){for(int j=0;j<q;j++){cout<<a[i][j]<<" ";}cout<<endl;}}

矩阵重塑（其二）

刷新

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录（样例文件）

题目背景

矩阵转置操作是将矩阵的行和列交换的过程。在转置过程中，原矩阵 AA 的元素 aijaij 会移动到转置后的矩阵 ATAT 的 ajiaji 的位置。这意味着 AA 的第 ii 行第 jj 列的元素在 ATAT 中成为了第 jj 行第 ii 列的元素。

例如，有矩阵 AA 如下：

A=[abcdef]A=[adbecf]

它的转置矩阵 ATAT 会是：

AT=[adbecf]AT=abcdef

矩阵转置在线性代数中是一个基本操作，广泛应用于各种数学和工程领域。

题目描述

给定 n×mn×m 的矩阵 MM，试编写程序支持以下查询和操作：

重塑操作 pp、qq：将当前矩阵重塑为 p×qp×q 的形状（重塑的具体定义见上一题）；
转置操作：将当前矩阵转置；
元素查询 ii、jj：查询当前矩阵第 ii 行 jj 列的元素（0≤i<n0≤i<n 且 0≤j<m0≤j<m）。

依次给出 tt 个上述查询或操作，计算其中每个查询的结果。

输入格式

从标准输入读入数据。

输入共 n+t+1n+t+1 行。

输入的第一行包含三个正整数 nn、mm 和 tt。

接下来依次输入初始矩阵 MM 的第 00 到第 n−1n−1 行，每行包含 mm 个整数，按列下标从 00 到 m−1m−1 的顺序依次给出。

接下来输入 tt 行，每行包含形如 op a b 的三个整数，依次给出每个查询或操作。具体输入格式如下：

重塑操作：1 p q
转置操作：2 0 0
元素查询：3 i j

输出格式

输出到标准输出。

每个查询操作输出一行，仅包含一个整数表示查询结果。

样例1输入

样例1输出

2
6

样例2输入

样例2输出

3
2
5

初始矩阵： [123456]135246， (1,0)(1,0) 位置元素为 33；

转置后： [135246][123456]， (1,0)(1,0) 位置元素为 22；

重塑后： [135246]154326， (1,0)(1,0) 位置元素为 55。

子任务

8080 的测试数据满足：

t≤100t≤100；

全部的测试数据满足：

t≤105t≤105 且其中转置操作的次数不超过 100100；
nn、mm 和所有重塑操作中的 pp、qq 均为正整数且 n×m=p×q≤104n×m=p×q≤104；
输入矩阵中每个元素的绝对值不超过 10001000。

提示

对于 n×mn×m 的矩阵，虽然转置和重塑操作都可以将矩阵形态变为 m×nm×n，但这两种操作通常会导致不同的结果。
评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如 numpy、pytorch 等）。

#include <iostream>
using namespace std;
const int N=10010;
int a[N][N],b[N][N],c[N][N],k[N*N];
int main()
{int n,m,q;cin>>n>>m>>q;int t=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];k[t++]=a[i][j];}}int x1=n,y1=m;while(q--){int op,x,y;cin>>op>>x>>y;if(op==1){ t=0;x1=x,y1=y;for(int i=0;i<x1;i++){for(int j=0;j<y1;j++){a[i][j]=k[t++];}}		}else if(op==2){t=0;for(int i=0;i<x1;i++){for(int j=0;j<y1;j++){b[j][i]=a[i][j];}}for(int i=0;i<y1;i++){for(int j=0;j<x1;j++){a[i][j]=b[i][j];k[t++]=a[i][j];}}swap(x1,y1);	}else cout<<a[x][y]<<endl;   }
}

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N*N],b[N][N],c[N][N],k[N*N];
int main()
{int n,m,q;cin>>n>>m>>q;int t=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>k[t++];}}int x1=n,y1=m;while(q--){int op,x,y;cin>>op>>x>>y;if(op==1){ x1=x,y1=y;}else if(op==2){for(int i=0,cnt=0;i<t;i++,cnt++){a[(cnt%y1)*x1+(cnt/y1)]=k[cnt];}for(int i=0;i<t;i++){k[i]=a[i];}swap(x1,y1);}else cout<<k[x*y1+y]<<endl;}
}

文本分词

刷新

时间限制： 1.5 秒

空间限制： 512 MiB

相关文件： 题目目录（样例文件）

题目背景

西西艾弗岛大数据中心正在如火如荼地开展大语言模型的研究工作。众所周知，计算机在执行机器学习的任务时，更适合处理数字的数据。对于大语言文本的处理，最好的方式是将文本转化为数字，然后再进行处理。通常，对输入数据进行整理后，需要将其按照一定的规则进行编码，以便计算机能够更好地处理。

这一转换过程是通过词汇表进行的。词汇表是一个包含了所有可能出现的词的列表。对于一个给定的文本，可以按照该表格将文本转化为一个数字的序列。而词表也需要根据文本的特点进行设计，以便更好地反映文本的特点。

题目描述

词汇表包括一系列的字符串，可以用于将输入的文本转换为数字序列。这里，我们认为输入文本事先经过一定的处理，将字母统一转换为了小写字母。词汇表的生成过程是一个迭代的过程。首先将文本按照一定的规则切分为单词序列，并统计全部单词的出现频率。然后将单词拆分为单字母字符串，组成初始的词汇表。接下来根据词汇表中的词汇接连出现在单词中的频率，将词汇反复合并，组成更长的词汇加入到词汇表中。词汇表的具体生成过程如下：

首先，输入文本中所有的单词和其出现的频率。然后，统计其中所有的字符，将其按照字典序排序，并将这些字符作为单字母字符串加入到词汇表中。同时，将输入的单词相应切分为词汇序列。

例如，输入下列词组和频率：

cut 15
cute 10
but 6
execute 3

则执行完上述过程后，词汇表中包含了 b、c、e、t、u、x 这些单字母字符串，而输入的词组被切分为：

c u t 15
c u t e 10
b u t 6
e x e c u t e 3

接下来，统计词汇表中，两个词汇组成的“词汇对”相连出现的频率，并选取出现次数最多的那一组拼接为一个字符串加入词汇表中。如果存在多个这样的“词汇对”，则再按照如下优先级顺序选取：

选取拼接后的字符串长度最短的那一组；
选取“词汇对”中前一个词汇长度最短的那一组；
选取拼接后的字符串字典序最小的那一组。

同时生成对应的合并规则（即将选出的“词汇对”合并成一个词汇），并按照该规则将所有输入单词的词汇序列按从前到后的顺序依次加以合并。

例如，在上述单词列表中词汇组合 <c, u> 在单词 cut 、 cute 和 execute 中分别出现了 15、10 和 3 次。相应统计全部的“词汇对”出现次数如下：

c u 28
u t 34
t e 13
b u 6
e x 3
x e 3
e c 3

于是，将 ut 加入词汇表中，并生成合并规则 <u, t>，可得到词汇表 b、c、e、t、u、x、ut。同时，将输入的单词切分为：

c ut 15
c ut e 10
b ut 6
e x e c ut e 3

上述过程可以重复进行。例如，继续统计“词汇对”出现的频率如下：

c ut 28
ut e 13
b ut 6
e x 3
x e 3
e c 3

这时，将 cut 加入词汇表中，并生成合并规则 <c, ut>，可得到词汇表 b、c、e、t、u、x、ut、cut。同时，将输入的单词切分为：

cut 15
cut e 10
b ut 6
e x e cut e 3

词汇表的生成，需要重复进行上述过程，直到词汇表达到指定的长度，或者所有输入的单词都被合并为一个词汇。

此外需要注意，一种特殊情况是选取的“词汇对”由两个相同的词汇组成。例如按“词汇对”<a, a> 进行合并时，由于从前到后的顺序要求，序列 a a a 会被合并为 aa a，而序列 a a a a 则会被合并为 aa aa。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数，nn 和 mm，分别表示输入的单词的数量和期望的词汇表长度。

接下来的 nn 行，每行包含一个非空字符串 ss 和一个正整数 ff，表示输入的单词和其出现的频率。其中，ss 中只包含小写字母。

输出格式

输出共 mm 行，每行包含一个字符串，按照加入词汇表的顺序输出词汇表中所有词汇。

样例1输入

4 8
cut 15
cute 10
but 6
execute 3

样例1输出

b
c
e
t
u
x
ut
cut

样例1解释

该样例即为题目描述中所举的例子。

子任务

对 20% 的数据，有 n≤200n≤200，mm 恰好等于输入单词中出现的所有字母的个数。

对 40% 的数据，有 n≤200n≤200，m≤200m≤200。

对 80% 的数据，有 n≤2000n≤2000，m≤2500m≤2500。

对 100% 的数据，有 n≤10000n≤10000，m≤5000m≤5000 且大于等于输入单词中出现的所有字母的个数，ss 的长度 ∣s∣≤25∣s∣≤25，输入单词的总频率（ff 的总和）不超过 106106。文本取材于真实的英文著作。

#include <bits/stdc++.h>
using namespace std;const int N=205;
map<char,int>mp;
int main()
{int n,m;cin>>n>>m;while(n--){string s;int f;cin>>s>>f;for(int i=0;i<s.size();i++){mp[s[i]]++;}}for(auto &t:mp){cout<<t.first<<endl;}
}//能力有限，只会20分，希望有大佬可以给我看满分代码

货物调度

刷新

时间限制： 2.0 秒

空间限制： 512 MiB

相关文件： 题目目录（样例文件）

题目描述

西西艾弗岛上共有 nn 间物流仓库，小 P 目前有 mm 件货物存放其中。为了获得至少为 vv 的现金，小 PP 需要选取一些货物卖出。

已知货物信息如下，第 ii 件（0≤i<m0≤i<m）货物：

存放在第 titi 间仓库中（0≤ti<n0≤ti<n）；
价值为 aiai，即选择卖出该货物可获得 aiai 的现金。

但在调货出库时也需要支付一些费用，对于第 jj 间（0≤j<n0≤j<n）仓库：

只要调用了该仓库的货物（至少一件），就需要支付 bjbj 的基本费用；
如果调用了该仓库中共 kk 件货物，则还需要支付 k×cjk×cj 的计件费用。

小 P 的最终目标是获得至少为 vv 的现金，即要求卖出的货物总价值减去总费用的结果大于或等于 vv。在满足该目标的前提下，试为小 PP 规划一种花费最小的卖货方案。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 nn、mm 和 vv。

接下来 nn 行输入仓库信息，其中第 jj 行（0≤j<n0≤j<n）包含两个整数 bjbj 和 cjcj。

接下来 mm 行输入货物信息，其中第 ii 行（0≤i<m0≤i<m）包含两个整数 aiai 和 titi。

输出格式

输出到标准输出。

仅输出一个整数，表示完成目标前提下的最小花费。

样例1输入

样例1输出

样例1解释

最优方案：选取货物 00 和 22，二者均在 00 号仓库，总花费为 2+2×1=42+2×1=4。

选取货物 11 也刚好能满足要求（20−3−1×2≥1520−3−1×2≥15），但花费更多。

单独选取货物 00 或 22 均不能满足要求。

样例2输入

样例2输出

样例2解释

小 P 所有货物均存放在仓库 11 中，任取两件货物卖出即可满足要求（10+10−1−2×1≥1510+10−1−2×1≥15）。

子任务

30%30% 的数据满足：

m≤15m≤15

另有 40%40% 的数据满足：

ai≤20ai≤20

全部的数据满足：

0<n,m≤10000<n,m≤1000
0<bj,cj≤200<bj,cj≤20
0<ai≤10000<ai≤1000
0<v≤1060<v≤106 且保证至少存在一种可满足要求的卖货方案。

不会，希望大佬们教教

哥德尔机

刷新

关于本题测试数据的说明
由于认证现场数据强度较弱，本题在原有20组测试数据基础上提供了4组加强数据（其中第21, 22组满足第4个子任务的特殊性质；第23, 24组满足第6个子任务的性质），每组测试数据仍对应5分。通过原有的20组数据即可在本题获得100分，我们欢迎有能力的同学挑战加强数据。

时间限制： 5.0 秒

空间限制： 1024 MiB

相关文件： 题目目录（样例文件）

题目背景

ReLU 函数是机器学习中常用的一个激活函数，其定义为：ReLU(x)=max⁡(0,x)ReLU(x)=max(0,x)。

题目描述

在西西艾弗岛上有一台基于哥德尔机原理设计的通用人工智能机器，小 C 是负责维修这台机器的机器人。

有一天小 C 发现这个机器在一个算法部分上遇到了计算瓶颈，这个算法是这样的：

机器内部维护了一个神经网络，这个神经网络的权重是一个二维矩阵 VV，并且权重是一个整数。

即对于每个二维坐标 (x,y)(x,y)，矩阵在该位置的权重是 V(x,y)V(x,y)，初始权重为 00。

神经网络会进行 nn 轮学习操作，每轮学习会给出参数 x1,x2,y1,y2,vx1,x2,y1,y2,v，然后对每个满足 x1≤x≤x2;y1≤y≤y2x1≤x≤x2;y1≤y≤y2 的 (x,y)(x,y)，将该位置对应的神经网络权重 V(x,y)V(x,y) 修改为 v+ReLU(V(x,y)−v)v+ReLU(V(x,y)−v)；

在所有学习操作之后，神经网络的参数定下来不变了，紧接着有 mm 次神经网络推理操作，每次推理操作给出 x1,x2,y1,y2x1,x2,y1,y2，查询对应子矩阵范围内最大的神经网络权重，即 max⁡x1≤x≤x2y1≤y≤y2V(x,y)x1≤x≤x2y1≤y≤y2maxV(x,y)。

小 C 发现机器在枚举这个问题优秀的算法时卡住了，目前只枚举出了一个很暴力的算法，为了让机器可以快点启动，他决定自己写好这个问题的算法来降低其启动常数，你能帮帮他吗？

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 n,mn,m；

接下来 nn 行每行五个整数 x1,x2,y1,y2,vx1,x2,y1,y2,v，依次表示每次学习操作的参数；

接下来 mm 行每行四个整数 x1,x2,y1,y2x1,x2,y1,y2，依次表示每次推理操作的参数。

输出格式

输出到标准输出。

共 mm 行，依次表示每次查询操作的答案。

样例1输入

样例1输出

样例2输入

10 10
3 10 7 7 10
1 10 9 9 3
4 6 7 7 7
1 8 5 5 1
6 8 1 1 1
1 3 8 8 2
2 10 10 10 9
1 10 6 6 4
1 8 9 9 4
5 9 9 9 2
1 9 2 2
2 10 1 10
2 10 6 9
2 2 1 4
2 10 8 10
7 10 1 10
1 8 1 9
1 8 5 7
3 7 5 8
2 10 1 7

样例2输出

子任务

对于 10%10% 的数据，满足 1≤n,m≤1001≤n,m≤100。

对于另外 10%10% 的数据，满足 1≤n,m≤1031≤n,m≤103。

对于另外 20%20% 的数据，满足 1≤n,m≤1041≤n,m≤104。

对于另外 20%20% 的数据，满足 1≤n,m≤5×1041≤n,m≤5×104。

对于另外 10%10% 的数据，满足 1≤n≤1031≤n≤103。

对于 100%100% 的数据，满足 1≤n,m≤5×1051≤n,m≤5×105，对每个修改或查询操作，满足 1≤x1≤x2≤n1≤x1≤x2≤n，1≤y1≤y2≤n1≤y1≤y2≤n 对每个修改操作，满足 1≤v≤n1≤v≤n，所有数值为整数。

只会暴力

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N][N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;while(n--){int x1,x2,y1,y2,v;cin>>x1>>x2>>y1>>y2>>v;for(int i=x1;i<=x2;i++){for(int j=y1;j<=y2;j++){a[i][j]=v+max(0,a[i][j]-v);}}}while(m--){int mx=-0x3f3f3f3f;int x1,x2,y1,y2;cin>>x1>>x2>>y1>>y2;for(int i=x1;i<=x2;i++){for(int j=y1;j<=y2;j++){mx=max(mx,a[i][j]);}}cout<<mx<<endl;}
}

希望佬们教教我