算法竞赛入门【码蹄集进阶塔335题】(MT2151-2175）

文章目录

算法竞赛入门【码蹄集进阶塔335题】(MT2151-2175）
前言
- - 为什么突然想学算法了？
  - 为什么选择码蹄集作为刷题软件？
目录
- 1. MT2151 权值计算
- 2. MT2152 黑客小码哥
- 3. MT2153 来给单词分类
- 4. MT2154 构词法
- 5. MT2155 泡泡
- 6. MT2156 管理通讯簿
- 7. MT2157 一元多项式的加法
- 8. MT2158 调整队伍
- 9. MT2159 修建传送带
- 10. MT2160 合成大数字
- 11. MT2161 队列安排
- 12. MT2162 约瑟夫环
- 13. MT2163 稀疏矩阵的乘法
- 14. MT2164 供水管线
- 15. MT2165 附庸的附庸
- 16. MT2166 采蜜
- 17. MT2167 暧昧团
- 18. MT2168 快排变形
- 19. MT2169 逆序
- 20. MT2170 线段树
- 21. MT2171 最大的忠诚度
- 22. MT2172 上楼梯
- 23. MT2173 上楼梯2
- 24. MT2174 大厨小码哥
- 25. MT2175 纸带
- 结语

前言

在这里插入图片描述

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

在这里插入图片描述

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。

（1）题目描述
对于一个长度为n的数组a，我们定义它的权值wa。若α中存在数a 满足a在整个数组中出现的次数大于等于a本身，这样的α中最大的一个就是a的权值wa;若不存在这样的a，则该数组的权值为 0。现在给你一个数组，请你计算它的权值。

格式

输入格式: 输入共两行，第一行一个正整数n ∈[1,1 ×105]，第二行n个以空格隔开的整数，表示数组中的数，它们均在[0,1 x 105]内。
.
输出格式: 输出该数组的权值。

样例1

输入:
6
0 1 5 5 2 2
.
输出: 2

（2）参考代码

#include<bits/stdc++.h> using namespace std;#define debug(x) cerr<< #x << " is "<<x<<endl;
typedef long long ll;
typedef pair<int,int> p;
const int INF=0x3f3f3f3f;
const int N=1e5+5;int n;
unordered_map<int, int> cnt;int main( )
{cin>>n;int res=0,x;for(int i=1;i<=n;++i){cin>>x;cnt[x]++;if(cnt[x]>=x) res=max(res,x);}cout<<res<<"\n";return 0;
}

2. MT2152 黑客小码哥

（1）题目描述

小码哥是一名黑客，他最近刚彩票中奖，由于还没兑换，小码哥十分担心彩票被盗(小码哥过分谨慎了)，他想为自己的保险箱设新的密码，顺便他想让你测试编码。

现有两种编码方式:
1.对于已知字符串中的任意字符，用其他字符交换，如用A和B交换，原先用A的地方换成B，用B的地方换成A。
2.对于当前字符串，打乱字符顺序。

先给你一个加密后的字符串和加密前的字符串，判断加密前的字符串是否能得到加密后的字符串。字符串中字符均为大写字母。

格式

输入格式:
第一行加密后的字符串
第二行加密前的字符串
有多组数据输入
.
输出格式: 输出”YES”或”NO"

样例1

输入:
JWPUDJSTVP
VICTORIOUS
MAMA
ROME
HAHA
HEHE
AAA
AAA
NEERCISTHEBEST
SECRETMESSAGES
.
输出:
YES
NO
YES
YES
NO

备注：

所有字符串长度不超过100

（2）参考代码

#include<stdio.h>
#include <string.h>
#define min(x,y) (x)<(y)?(x):(y)
int dp[2005][2005];
int cost[30];
int main() 
{ char str[2005];int n,m,i,j;scanf("%d %d %s",&n,&m,str);char c;int add,del;for(i=0;i<n;i++){scanf(" %c %d %d",&c,&add,&del);cost[c-'a']=min(add,del);}memset(dp,0,sizeof(dp));for(j=1;j<m;j++)for(i=j-1;i>=0;i--){dp[i][j]=min(dp[i+1][j]+cost[str[i]-'a'],dp[i][j-1]+cost[str[j]-'a']);if(str[i]==str[j])dp[i][j]=min(dp[i][j],dp[i+1][j-1]);}printf("%d\n",dp[0][m-1]);return 0; 
}

3. MT2153 来给单词分类

（1）题目描述
现有如下单词分类原则:两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。

现有n个单词均由大写字母组成，每个单词长度小于等于100。求单词被分为几类。

格式

输入格式: 第一行输入单词个数n，以下n行每行一个单词
.
输出格式: 一个整数表示类数

样例1

输入:
3
AABAC
CBAAA
AAABB
.
输出: 2

备注：

对于70%的数据满足n ≤100。对于100%的数据满足n ≤10000。

（2）参考代码

import java.util.Scanner;
import java.util.*;
class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n= Integer.parseInt(input.next());Set<String> a=new HashSet<>();for (int i = 0; i < n; i++) {char[] ch=input.next().toCharArray();int[] b=new int[26];for (int j = 0; j < ch.length; j++) {b[ch[j]-'A']++;}a.add(Arrays.toString(b));}System.out.println(a.size());input.close();}
}

4. MT2154 构词法

（1）题目描述
小码哥最近在背单词，他认为自己找到了单词构造的规律，其中有一条是这样的:一个单词中不会出现三个连续的相同字母。为了炫耀他的发现，他向你展示了一个字符串，问你能否将这个字符串重新排列为一个合法的单词。请你编写一个程序来完成这个任务，如果可以排成合法单词输出「YEs，否则输出No。

格式

输入格式:
一行，一个字符串s，满足 1≤ls/ ≤1×105且所有字符均为小写字母。
.
输出格式: 输出一行，YEs或No。

样例1：

输入： deeelh
.
输出：YES

备注：

样例的一种合法的排列方式为heeled

（2）参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;int n = s.size();int m=0;vector<int> cnt(30,0);for(auto p:s) cnt[p-'a'+1]++;for(int i=1;i<=26;i++) m = max(m,cnt[i]);if(m<=2*(n-m+1)) puts("YES");else puts("NO");return 0;
}

5. MT2155 泡泡

（1）题目描述
小码哥小时候喜欢吹泡泡，有一次他吹出了n个一样小的泡泡，过了一段时间后，这些泡泡相互碰到一起，形成了各种大小的泡泡…，但小码哥不知道的是，他生活的地方是母体构筑的虚拟世界，里面的泡泡实际是一串串被拼成环状的数字。

小码哥一开始吹出的泡泡被母体记为1，2，… n ,而泡泡的碰撞融合实际是数字的拼接（有序)。母体会通过模拟得知两个泡泡环碰撞的情况（用a->y表示)。例如，有一个为1-2的泡泡环与3-4-5的泡泡环碰撞，碰撞的点为1- >4(后一个数字接在前一个数字下面)，则会形成1一4-5-3-2的泡泡环。

一开始所有泡泡环都只有一个数字，母体演算出了泡泡之后的碰撞点，现在请你输出泡泡碰撞完后的所有泡泡的情况。

格式

输入格式:
第一行两个正整数n，m，表示一开始泡泡的数量和泡泡碰撞的次数;
接下来m行，每行两个数字。，y，表示泡泡碰撞的两个点。
.
输出格式:
输出所有泡泡的情况，一行表示一个泡泡的情况;
要求按照字典序最小的方式按顺序输出。

样例1

输入:
9 6
4 1
6 1
5 1
6 8
2 4
9 7
.
输出:
1 2 4 6 8 5
3
7 9

备注：

1≤m<n ≤ 10的6次，1≤，y ≤n ,
保证c，y属于不同的泡泡环。

（2）参考代码

#include<bits/stdc++.h>using namespace std;typedef long long int LL;const int maxn = 1000005;int n, m;struct B {int before, next;}b[maxn];bool book[maxn];int main() {cin >> n >> m;for(int i = 1; i <= n; i++)b[i].before = b[i].next = i;while(m--) {int x, y;cin >> x >> y;b[b[y].before].next = b[x].next;b[b[x].next].before = b[y].before;b[x].next = y;b[y].before = x;}for(int i = 1; i <= n; i++) {if(!book[i]) {int t = i;do {printf("%d ", t);book[t] = true;t = b[t].next;}while(t != i);printf("\n");}}return 0;}

6. MT2156 管理通讯簿

（1）题目描述
已知一个通讯记录是由学号（6位整数，并且学号不重复)、姓名（长度小于10，只包含大写字母和小写字母)、性别（’F′或’M’)、出生日期（长度小于10)、邮编(6位整数)、通讯地址（长度小于30，只包含大写字母或小写字母)、QQ号(9位整数)、电话（11位整数）等数据项组成，利用单链表编写管理通讯簿(多个通讯记录)的程序，要求实现添加、删除、查找、逆序打印通讯记录功能。输入必须合理。

格式

输入格式:
第一行输入学生数量，正整数(大于2，小于10)，后续行依次输入每个学生学号、姓名、性别、生日、邮编、通讯地址、QQ号、电话，空格分隔。每个学生一行。输入数据必须合理，不考虑不合理的输入或是溢出等特殊情况。然后输入正整数N，根据N的值执行添加、删除、查找、逆序打印。
如上文所述，首先输入学生信息来建立通讯录。然后输入正整数N，如果N为1，执行添加操作，后续行依次输入每个学生学号、姓名、性别、生日、邮编、通讯地址、QQ号、电话，空格分隔。然后输出第一行”The records is:”，后续行逆序打印通讯录。
如果N为2，执行删除操作，第二行输入整型学号，删除对应节点(若找不到要删除的节点，则不进行删除操作)，然后输出第一行”The records is:"，后续行逆序打印通讯录。
如果N为3，执行查找操作，输入整型学号，如果能够查找到这一条记录则输出查到的记录，找不到则输出”not found”。
如果N为4，执行逆序打印操作，输出第一行”The recordsis:”，后续行逆序打印通讯录。
.
输出格式: 根据N的值，输出对应的操作结果，如样例所示。

样例1

输入:
4
202101 Mike F 2017513 710072 xigongda 810794716 18392561229
202102 Wendy M 2018513 710071 xigongda 123451229 18392561221
202103 Wesley M 2019513 710012 xigongda 123411189 18392561211
202106 Wink F 2017212 110072 xigongda 121116710 18392561111
4
.
输出:
The records is:
202106 Wink F 2017212 110072 xigongda 121116710 18392561111
202103 Wesley M 2019513 710012 xigongda 123411189 18392561211
202102 Wendy M 2018513 710071 xigongda 123451229 18392561221
202101 Mike F 2017513 710072 xigongda 810794716 18392561229

（2）参考代码

 #include<bits/stdc++.h>#define x first#define y second#define bug(x) cerr<<#x<<'='<<x<<' '#define debug(x) cerr<<#x<<'='<<x<<'\n'#define FOR(a,b,c) for(int a=(b),a##_end=(c);a<=a##_end;++a)#define ROF(a,b,c) for(int a=(b),a##_end=(c);a>=a##_end;--a)using namespace std;typedef long long ll;typedef pair<int,int> PII;const int INF=0x3f3f3f3f,N=1e5+10;template<class T>inline bool chkmin(T &A,const T &B){return B<A?A=B,1:0;}template<class T>inline bool chkmax(T &A,const T &B){return A<B?A=B,1:0;}string a[N][10];int tot,vis[N];void Print(){cout<<"The records is:\n";ROF(i,tot,1)if(!vis[i])FOR(j,1,8)cout<<a[i][j]<<" \n"[j==8];}int main(){int n;cin>>n;FOR(i,1,n)FOR(j,1,8)cin>>a[i][j];tot=n;// while(n--){int op;cin>>op;if(op==1){++tot;FOR(j,1,8)cin>>a[tot][j];Print();}else if(op==2){string t;cin>>t;FOR(i,1,tot)if(!vis[i]&&a[i][1]==t)vis[i]=1;Print();}else if(op==3){string t;int flag=0;cin>>t;FOR(i,1,tot)if(!vis[i]&&a[i][1]==t){FOR(j,1,8)cout<<a[i][j]<<" \n"[j==8];flag=1;break;}if(!flag)cout<<"not found"<<endl;}else{Print();}// }return 0;}

7. MT2157 一元多项式的加法

（1）题目描述
给出两个一元多项式LA和LB，请你将这两个一元多项式相加，得到新的一元多项式Lc。

如样例:
在这里插入图片描述

格式

输入格式:
第一行两个整数n和m，分别表示A和LB的项数。
接下来n行，每行输入LA的每一项的信息，两个整数分别表示该项的系数coef和次数eapn，输入保证次数递增。
接下来m行，每行输入LB的每一项的信息，两个整数分别表示该项的系数coef和次数expn，输入保证次数递增。
.
输出格式: 输出k行，k为Lc的项数，每行输出Lc的每一项的信息，两个整数分别表示该项的系数coef和次数eacpn，输出按次数递增。

样例1

输入:
4 5
1 0
-10 6
2 8
7 14
-1 4
10 6
-3 10
8 14
4 18
.
输出:
1 0
-1 4
2 8
-3 10
15 14
4 18

备注：

保证:对于100%的数据:0≤n, m ≤ 1,000,000，-1,000 ≤coef ≤1,000，- 1,000,000,000 ≤epn ≤1,000,000,000。

（2）参考代码

 #include<cstdio>#include<algorithm>using namespace std;int n,m;struct chj{int c,e;bool operator <(const chj b)const{return e<b.e;}}a[2000005];int main(){scanf("%d%d",&n,&m);n+=m;for (int i=1;i<=n;i++) scanf("%d%d",&a[i].c,&a[i].e);sort(a+1,a+n+1);int i=1;while (i<=n){int j=i+1;while (a[i].e==a[j].e){a[i].c+=a[j].c;j++;}if (a[i].c!=0) printf("%d %d\n",a[i].c,a[i].e);i=j;}return 0;}

8. MT2158 调整队伍

（1）题目描述
小码哥迎来了他大学的第一次军训，军训的第一个项目就是列队，每个同学在队伍中都有属于自己的编号。但在练习过程中，教官怎么看这支队伍怎么不顺眼，于是决定调整一下队伍的顺序。

为了顺便考验同学们的反应力，教官与学生们约定了一个口令，每当他说x y O，a号同学就要移动到y号同学的前面，每当他说x y 1，x号同学就要移动到y号同学的后面，但学生们不想一次次慢慢移动这么麻烦，想要知道队伍最后是怎么排的然后直接排好。为了解决同学们的烦恼，小码哥立刻动手原地写了一个程序算出了最终排序。

现在告诉你队伍从前到后的初始排序编号以及教官的口令，要你得出队伍从前往后的最终排序。

已知有n个学生，编号不重复且1≤编号≤n。

格式

输入格式:
第一行两个正整数n，m，表示学生的数量和教官口令的数量;
第二行n个正整数，表示学生们的初始排序;
接下来m行，每行3个整数，表示教官的口令。
.
输出格式:
n个数字，每个数字之间用空格隔开，表示队伍从前往后的最终排序。

样例1

输入:
10 5
8 4 6 7 9 3 5 10 1 2
4 9 0
10 5 1
3 9 0
1 9 1
3 6 0
.
输出: 8 3 6 7 4 9 1 5 10 2

备注：

其中: 2≤n ≤3 * 10的5次，1≤m≤3 * 10的6次，保证1≤a，y≤n，并且α不等于g 。

（2）参考代码

#include<bits/stdc++.h>using namespace std;const int N = 300010;int a[N], r[N], l[N];// 初始化哨兵节点void init() {r[0] = N - 1;l[N - 1] = 0;}// 将 x 插入 y 之前void putFront(int x, int y) {// 删除 xl[r[x]] = l[x];r[l[x]] = r[x];// 插入到 y 之前r[x] = y;l[x] = l[y];r[l[y]] = x;l[y] = x;}// 将 x 插入 y 之后void putRear(int x, int y) {// 删除 xl[r[x]] = l[x];r[l[x]] = r[x];// 插入到 y 之后l[x] = y;r[x] = r[y];l[r[y]] = x;r[y] = x;}int main( ){int n, m;cin >> n >> m;init();for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}// 初始化 r 数组int idx = 0; // idx 表示当前要处理的节点，初始从前往后处理for (int i = 0; i < n; i++) {r[idx] = a[i];idx = a[i];}r[idx] = N - 1; // 注意维持尾哨兵和最后一个元素的关系idx = N - 1; // 从后往前处理for (int i = n - 1; i >= 0; i--) {l[idx] = a[i];idx = a[i];}
l[idx] = 0; // 注意维持头哨兵和第一个元素的关系while (m--) {int x, y, op;scanf("%d%d%d", &x, &y, &op);if (op == 0) {putFront(x, y);} else {putRear(x, y);}}for (int i = r[0]; i != N - 1; i = r[i]) {printf("%d ", i);}return 0;}

9. MT2159 修建传送带

（1）题目描述
伊卡洛斯，主脑需要更多的能量…

伊卡洛斯在距离母星系11.4光年的地方发现了一颗地形为贫瘠荒漠的行星，它决定把这块适建区域100%的星球改造成一个巨大的生产基地。

伊卡洛斯首先把星球的建造区域分成了n个节点，并记为1，2，。。。，n号节点，伊卡洛斯已经在这些节点放置了工作站，剩下的就是用单向传送带把它们连接起来（伊卡洛斯的美学原则是不使用物流塔)。但随着传送带越铺越多，伊卡洛斯开始处理不来节点之间的连接关系了，为了确认接下来的铺设方案，伊卡洛斯需要知道从某一个节点放置的货物能否随着传送带被送往另一个指定的节点，但伊卡洛斯看不懂自己混乱的走线了，于是它决定求助于主脑。

伊卡洛斯的所有行动可以被概况成两条指令
1.A x y，表示修建—条从x号节点到y号节点的传送带
2.Qx y，表示询问从x号节点放下的货物能否被送往y号节点(只要经过y号节点就算被送达)

一开始所有节点互不相连
为了货物能有一个明确的流向，传送带只允许有一个出口，并只有一个方向例如:原本有2条传送带(x->y表示一个从x号节点到y号节点的传送带)1->2->3

此时修建一条2->5的传送带，则传送带变为1->2->5->6
4->5->6
5号节点就有两个传送带通往它，而原本由2->3的传送带会断开

再修建一条6->5的传送带，则传送带变为
1->2->5
4->5
6->5

原本5->6的传送带会断开

格式

输入格式:
第一行两个正整数n，m，表示节点的个数和伊卡洛斯的总指令数;
接下来m行，每行1条指令，保证两种指令都会出现， α可能等于y。
.
输出格式: 对于每条询问指令，如果能够送达，则输出Yes，否则输出No,每次输出之间换行。

样例1

输入:
6 7
A 1 2
A 2 3
A 4 5
A 5 6
A 2 5
Q 1 6
Q 1 3
.
输出:
Yes
No

备注：

其中:3≤n ≤100000，3<m ≤300000，1≤c，g ≤n。

（2）参考代码

 #include<bits/stdc++.h>using namespace std;const int maxm=1200000;const int INF=1<<30;inline int read(){register int a=0,po=1;char ch=getchar();while (!isdigit(ch)&&ch!='-') ch=getchar();if (ch=='-') po=-1,ch=getchar();while (isdigit(ch)) a=(a<<1)+(a<<3)+ch-48,ch=getchar();return a*po;}
const int maxn = 1e5 + 7;int fa[maxn];void solve(){int n, m; cin >> n >> m;while(m--) {char c; cin >> c;int x, y; cin >> x >> y;if(c == 'A') {fa[x] = y;if(fa[y] == x) fa[y] = 0;}else {int t = x;bool ok = false;set<int> s;while(t != 0) {if(t == y) {ok = true;break;}t = fa[t];if(s.find(t) != s.end()) break;s.insert(t);if(t == x) break;}cout << (ok ? "Yes" : "No") << '\n';}}}signed main() {solve();}

10. MT2160 合成大数字

（1）题目描述
小码哥最近对小游戏很感兴趣，于是他仿照着合成大西瓜小游戏做了一个简化版程序。

在这个程序中游戏的区域变为了一维(即一条直线)。游戏内有n次投放格子的村会，每次机会程序会给出一个有着随机数R的新格子供小码哥投放。

一开始游戏内是空的（无格子)，当游戏内无格子的时候，小码哥只能把新格子投放到第一个位置(最左边)﹔当游戏内有格子时，小码哥只能将新格子投放到某个已存在的格子上(称为被碰撞格子)，并且如果被碰撞格子里的数字与新格子的数字相同，那么被碰撞格子里的数字会与新格子的数字合并，被碰撞的格子的数字也变成原来的2倍，这被称为一次合并，如果被碰撞格子里的数字与新格子的数字不同，那么新格子会插入到被碰撞格子的右侧。

除了上面的方式能触发合并以外，程序在每次投放后还会从左往右进行一次结算，如果相邻的两个格子的数字相同，那么这两个格子会合并成一个并且合并得到的格子的数字为原本两个格子的数字之和，并且右边的所有格子会向左移动来补齐空位（如果连续n个相同(n>2)先结算前两个)，然后重新从左到右结算，这是合并的另一种触发方式

每当合并触发后，如果生成的格子内的数大于2048，那么这个格子会立即消失(消失优先度最高)，空位由右边的所有格子向左移动来补齐，这被称为一次完美的合并

小码哥还设计了一个得分系统:
1.每当他投放一个新数字或者触发一次合并，则得到等于新数字的得分或者等于合并生成的新数的得分，两者分开计算，即投入新数字时得到得分（(无论是否触发合并)，投入后并触发合并再追加获得合并的得分(另外，虽然完美的合并后格子会立即消失，但得分会计入)

2.程序会记录达成完美的合并的次数，初始次数为0，每当完成一次完美的合并次数+1

由于小码哥做这个程序时得分的显示区域有限，因此小码哥的得分系统里的得分显示的是总得分对10007取模得到的数字

现在给出投放机会的次数n，以及每次投放的数字R和小码哥投放的位置l，请你求出投放次数用完后游戏界面的情况（即格子的情况）以及小码哥最后的得分对10007取模得到的结果和小码哥达成完美的合并的次数

格式

输入格式:
第一行一个正整数n，表示小码哥的投放次数
接下来n行每行两个数字R，l，表示新格子的数字和小码哥投放的位置
.
输出格式:
第一行若干个正整数，表示最后游戏界面的情况，如果无输出也要换行
第二行两个整数，表示小码哥的得分对10007取模的结果和完成完美的合并的次数

样例1

输入:
5
8 1
8 1
4 1
2 1
8 3
.
输出:
16 2 4 8
46 0

（2）参考代码

 #include<iostream>#include<vector>using namespace std;vector<int>vec;
int point = 0, perfect = 0;void printVec() {//cout << ">";
for (int i = 0; i < vec.size(); i++) {cout << vec[i] << " ";}cout << endl;//cout << "point=" << point << ",perfect=" << perfect << endl;}void mergeVec() {if (vec.size() == 1 || vec.size() == 0) {return;}int flag = 0;//不用再来一次for (int i = 0; i < vec.size()-1; i++) {if (vec[i] == vec[i + 1]) {flag = 1;//再来一次vec[i] += vec[i + 1];point += vec[i]; point = point % 10007;vec.erase(vec.begin() + i + 1);//大于2048的删掉if (vec[i] > 2048) {vec.erase(vec.begin() + i);perfect++;}break;}}//printVec();if (flag == 1) {mergeVec();}}void insertVec(int num,int pos) {int flag = 0;point += num; point = point % 10007;if (vec.empty()||pos>vec.size()) {//初始化vec.push_back(num);}else {//插入vector <int>::iterator iter = vec.begin();vec.insert(iter + pos, 1, num);//合并mergeVec();}//printVec();}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {int num, pos;cin >> num >> pos;insertVec(num, pos);}printVec();cout << point << " " << perfect << endl;}

11. MT2161 队列安排

（1）题目描述
一个学校里老师要将班上N个同学排成一列，同学被编号为1～N，他采取如下的方法:

1.先将1号同学安排进队列，这时队列中只有他一个人;
2.2一N号同学依次入列，编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1～(i一1)中某位同学(即之前已经入列的同学)的左边或右边;
3.从队列中去掉 M(M <N)个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

格式

输入格式:
第1行为一个正整数N，表示了有N个同学。
第2-N行，第i行包含两个整数k, p，其中k为小于i的正整数, p为0或者1。若p为0，则表示将i号同学插入到k号同学的左边， p为1则表示插入到右边。
第N＋1行为一个正整数M，表示去掉的同学数目。
接下来M行，每行一个正整数a，表示将c号同学从队列中移去，如果α号同学已经不在队列中则忽略这一条指令。
.
输出格式: 1行，包含最多NⅣ个由空格隔开的正整数，表示了队列从左到右所有同学的编号。

样例1

输入:
4
1 0
2 1
1 0
2
3
3
.
输出: 2 4 1

（2）参考代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int mx=1e5+10;
int n,m;
struct T{int l,r;        //每个同学的“左右手” int d;          //表示同学是否输出 
}t[mx]={0};
void add(int i,int k,int f)       //新增同学 
{if(f==1)         //左 {t[k].r=t[i].r;t[k].l=i; t[i].r=k;t[t[k].r].l=k;}else             //右 {t[k].r=i;t[k].l=t[i].l;t[i].l=k;t[t[k].l].r=k;}
}
int main()
{int x,k,f;cin>>n;t[0].r=0,t[0].l=0;add(0,1,1);for (int i=2;i<=n;i++){cin>>x>>f;add(x,i,f);}cin>>m;while(m--){cin>>x;t[x].d=1;         //将该同学标记为不输出 }for (int i=t[0].r;i;i=t[i].r){if (t[i].d==0)    //输出未标记的 cout<<i<<" ";}return 0;
}

12. MT2162 约瑟夫环

（1）题目描述
讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后杀死所有人。

于是约瑟夫建议:每次由其他两人一起杀死一个人，而被杀的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在杀了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。

我们这个规则是这么定的:
在一间房间总共有n个人(编号1～n )，最后只能有一个人活下来。

按照如下规则去杀人:
所有人围成一圈
从1号开始顺时针(1- >n)报数，每次报到q的人将被杀掉被杀掉的人将从房间内被移走
然后从被杀掉的下一个人重新报数，继续报到q，再清除，直到剩余一人
你要做的是:当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来。
实现约瑟夫环首先需要判断选择的那个人是否是最后一个幸存的人，不是的话再进行约瑟夫环行动。

格式

输入格式: 第一行为n，q
.
输出格式: 输出仅一行，为剩下的人的编号

样例1

输入: 5 2
.
输出: 3

备注：

其中: 1≤n，q ≤1000 。

（2）参考代码

 #include<stdio.h>#include<stdlib.h>struct node{int no;struct node * next;};int main(){int n,k,m,sum=0;scanf("%d %d",&n,&m);k=1;
struct node *head,*p,*q;head=(struct node *)malloc(sizeof(struct node));head->no=1;head->next=head;for(int i=n;i>1;i--){p=(struct node *)malloc(sizeof(struct node));p->no=i;p->next=head->next;head->next=p;}for(int i=0;i<n-1;i++){p=p->next;}for(int i=0;i<k-1;i++){p=p->next;}int flag=0;while(n!=1){for(int i=0;i<m-1;i++){p=p->next;}if(flag==1){p=p->next;}flag=1;for(int j=0;j<n-1;j++){p=p->next;}q=p->next;p->next=q->next;free(q);n--;}printf("%d\n",p->no);}

13. MT2163 稀疏矩阵的乘法

（1）题目描述
输入两个以三元组表表示的矩阵，并输出它们相乘的结果。

注:三元组表表示法是指一个矩阵元素用三个性质（行坐标，列坐标和元素值)表示，在矩阵非零元素较少时，该表示方法更节省空间。

例如，3*3矩阵:
在这里插入图片描述
在三元组表表示法下为:

每行的第一个整数是行坐标，第二个整数是列坐标，第三个整数是元素值。

格式

输入格式:
第一行输入第一个矩阵的行数和列数，再输入该矩阵的三元组表形式，以000结束。
然后输入第二个矩阵的行数和列数，再输入该矩阵的三元组表形式，以000结束。
.
输出格式: 输出相乘后的矩阵三元组。

样例1

输入:
3 3
1 1 1
2 2 2
2 3 4
3 1 -4
0 0 0
3 3
1 3 -2
2 3 -5
3 1 8
3 2 -6
0 0 0
.
输出:
1 3 -2
2 1 32
2 2 -24
2 3 -10
3 3 8

备注：

矩阵的行列数不大于1000，非零元素个数不大于1000。元素值最终结果在int范围内。

（2）参考代码

#include<bits/stdc++.h> using namespace std;
typedef struct{int i,j;int e;
}Node;typedef struct
{
Node nodes[10005];
int rpos[10005];
int m, n, t;
} Matrix;
int main()
{
Matrix A, B;
scanf("%d%d", &A.m, &A.n);
int cnt = 1;
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
while (x != 0 && y != 0 && z != 0)
{
A.nodes[cnt].i = x;
A.nodes[cnt].j = y;
A.nodes[cnt++].e = z;
scanf("%d%d%d", &x, &y, &z);
}
A.t = cnt - 1;
map<int, int> num;
for (int col = 1; col <= A.m; col++)
{
num[col] = 0;
}
for (int i = 1; i <= A.t; i++)
{
num[A.nodes[i].i]++;
}
A.rpos[1] = 1;
for (int col = 2; col <= A.m; col++)
{
A.rpos[col] = A.rpos[col - 1] + num[col - 1];
}
scanf("%d%d", &B.m, &B.n);
cnt = 1;scanf("%d%d%d", &x, &y, &z);while (x != 0 && y != 0 && z != 0){B.nodes[cnt].i = x;B.nodes[cnt].j = y;B.nodes[cnt++].e = z;scanf("%d%d%d", &x, &y, &z);}B.t = cnt - 1;for (int col = 1; col <= B.m; col++){num[col] = 0;}for (int i = 1; i <= B.t; i++){num[B.nodes[i].i]++;}B.rpos[1] = 1;for (int col = 2; col <= B.m; col++){B.rpos[col] = B.rpos[col - 1] + num[col - 1];}Matrix Q;Q.m = A.m;Q.n = B.n;Q.t = 0;if (A.t * B.t != 0){for (int arow = 1; arow <= A.m; arow++){map<int, int> ctemp;Q.rpos[arow] = Q.t + 1;int tp;if (arow < A.m){tp = A.rpos[arow + 1];}else{tp = A.t + 1;}for (int p = A.rpos[arow]; p < tp; p++){int brow = A.nodes[p].j;int t;if (brow < B.m){t = B.rpos[brow + 1];}else{t = B.t + 1;}for (int q = B.rpos[brow]; q < t; q++){int ccol = B.nodes[q].j;ctemp[ccol] += A.nodes[p].e * B.nodes[q].e;}}for (int ccol = 1; ccol <= Q.n; ccol++){if (ctemp[ccol]){Q.t++;Q.nodes[Q.t].i = arow;Q.nodes[Q.t].j = ccol;Q.nodes[Q.t].e = ctemp[ccol];}}}}
for (int i = 1; i <= Q.t; i++){printf("%d %d %d\n", Q.nodes[i].i, Q.nodes[i].j, Q.nodes[i].e);}return 0;
}

14. MT2164 供水管线

（1）题目描述
在n (1<n <100）个城市之间原本要规划修建许多条下水管道，管理人员发现这些管道会形成一条回路，而下水道只要将城市联通即可，所以回路会加大施工的成本。所以希望你来帮忙找出多余的管道来进行优化。当然管道和管道之间是有区别的，比如用si;来表示à到j的管道管理费用， s.a越小则表示该管道管理费用越低。能否去除一些管线，使得总管理成本最低。求出最低的管理成本(不存在自身与自身成为回路的管道)。

格式

输入格式:
第一行有两个数n和k表示城市数量和管道数量。
接下来k行，每行都有三个数i，j，c表示城市i和城市j之间的管道成本为c。
.
输出格式: 一个正整数，最低管理成本。

样例1

输入:
3 3
1 2 3
1 3 5
2 3 8
.
输出: 8

（2）参考代码

#include <bits/stdc++.h>
using namespace std;
int f[10000001];
int main()
{int n;cin>>n;for(int i=1;i<=5000000;i++){for(int j=i*2;j<10000000;j+=i){int b=j-i;if((j^b)==i) f[j]++;}}for(int i=1;i<=n;i++) f[i]+=f[i-1];cout<<f[n];
}

15. MT2165 附庸的附庸

（1）题目描述

蒙德城的旧贵族们存在着附庸的关系。欧洲有一位伟人说过，我的附庸的附庸不是我的附庸。尽管如此，他们还是存在着隐性的自上而下的关系，属于同一个利益集团。所以，在蒙德城，附庸的附庸也是附庸。也就是说，如果两个附庸都能追溯到同一个贵族，他们也存在附庸关系（仅仅是蒙德人这样认为）蒙德城人口众多，骑士团的凯亚把各人的关系都梳理了出来交给了你。现在，他想让你告诉他，某两个人存不存在附庸关系(按照蒙德人的观念)。

格式

输入格式:
第一行一个整数n，表示n个关系，
接下来n行，每行两个数a,b，表示b是a的附庸，下一行一个整数q，表示询问次数，接下来q行，每行两个数a,b，询问a和b是否存在附庸关系。
.
输出格式:
q行，每行一个数，
1表示存在附庸关系，
0表示不存在。

样例1

输入:
5
1 2
2 3
1 7
4 5
5 6
2
2 7
1 4

.
输出:
1
0

备注：

其中:5≤n ≤10000,2≤q≤2000,1 ≤ a,b≤20000, a≠ b，保证涉及询问的关系中不存在环。

（2）参考代码

#include<bits/stdc++.h> using namespace std;
typedef long long ll;//整数分块
int main( )
{ll n,sum=0;cin>>n;for(int i=1,r;i<=n;i=r+1){r = n/(n/i);sum += (r-i+1)*(n/i);}cout<<sum;return 0;
}

16. MT2166 采蜜

（1）题目描述
现在有n个蜂巢，每一个蜂窝都对应了一个蜂蜜值si 。

小码哥发现:有一些蜂窝相互联结，使得他们可以共享蜂蜜值，即该蜂巢的蜂蜜值变为:它和它连接(直接连接或间接连接)的蜂巢的蜂蜜值的和。

现在小码哥想要查询一下一些蜂巢的蜂蜜值。

格式

输入格式:
第一行有两个数n(蜂巢的数量)、 m(操作的数量)
第二行有n个数字(s1,…· ,sn)︰分别表示了每一个蜂巢的蜂蜜值。
随后有m行:第一个数字如果是1，则后面还有两个数字a，b ，表示此次发现蜂巢a 和b是相连的。第一个数字如果是2，则后面只有一个数字c，表示查询所有与蜂巢c相连的蜂巢(包括自己)的总蜂蜜值。
.
输出格式: 对每一次的查询操作输出查询的蜂巢的蜂蜜值。

样例1

输入:
4 6
1 1 1 1
1 1 2
2 1
1 2 3
2 1
1 3 4
2 1
.
输出:
2
3
4

备注：

1 ≤m, n ≤100000,0≤si≤100。

（2）参考代码

 #include<cstdio>#define maxn 100005using namespace std;int n,m,a[maxn],fa[maxn];inline int get(int x){if (x==fa[x]) return x;return fa[x]=get(fa[x]);}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),fa[i]=i;while (m--){int f=0;scanf("%d",&f);if (f==1){int x,y;scanf("%d%d",&x,&y);int fx=get(x),fy=get(y);if (fx!=fy){fa[fy]=fx;a[fx]+=a[fy];}}else{int x;scanf("%d",&x);printf("%d\n",a[get(x)]);}}return 0;}

17. MT2167 暧昧团

（1）题目描述
小码哥正在整理NPU的学生信息。现在到了关键的一步:存储cp信息。

因为众所周知情网很乱，所以可能一个人和多个人暧昧，并且不分性别，而且有可能自己和自己暧昧（?自交)。
同时一对暧昧关系可能会由于大意等原因多次记录。

现在我们知道n个人，并且有m个暖昧关系。
现在我们对暧昧团进行定义:一个人所有和他有直接暧昧关系以及间接暧昧关系的集合。
比如1与2暖昧，2与3暖昧，3与4暧昧，5与3暖昧，6与2暧昧，那么{1,2,3,4,5,6},{2,3],{1,4,5,6},{空集合}就均属于暧昧团，其中，{1,2,3,4,5,6}就是极大暧昧团

现在小码哥告诉你一个人名的编号x，让你回答与x所处极大暧昧团的大小。

如果一个人和谁都不暧昧，那么答案就是1

格式

输入格式:
第一行一个整数n,m( 1 ≤n, m ≤ 1e5 )，表示人数，和暧昧关系的数量。
接下来m行，每行两个整数a,b( 1 ≤a,b ≤n )，表示a, b之间存在暧昧关系。
最后一行一个整数x，表示询问x所处极大暧昧团的大小
.
输出格式: 一行一个整数表示答案

样例1

输入:
6 8
1 2
5 2
3 6
4 5
1 4
2 2
3 6
3 6
3
.
输出: 2

（2）参考代码

 #include<bits/stdc++.h>using namespace std;int n,m,a,b,f[100005],sz[100005];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}int main( ){cin>>n>>m;for(int i=1;i<=n;i++) sz[i]=1,f[i]=i;while(m--){cin>>a>>b;int fa=find(a),fb=find(b);if(fa!=fb){f[fa]=fb;sz[fb]+=sz[fa];}}cin>>a;cout<<sz[find(a)];return 0;}

18. MT2168 快排变形

（1）题目描述
有n个数，问如果通过每次交换邻项的两个数来使数组中的元素变为升序排列。eg : 9876 5，
变为升序:
5678 9。
需要10次邻项交换。

格式

输入格式:
第一行输入一个整数n，表示序列长度。
第二行输入n个数。
.
输出格式: 输出一个整数，表示最少的交换次数。

样例1

输入:
5
9 8 7 6 5
.
输出: 10

备注：

提示:1<n ≤200000。

（2）参考代码

#include<bits/stdc++.h> using namespace std;
#define int long longint n, ans = 0;
int a[200010], temp[200010];void merge_pai(int l, int r, int mid) {int i = l, p = l, j = mid;while (i < mid && j <= r) {if (a[i] <= a[j]) temp[p++] = a[i++];else {temp[p++] = a[j++];ans += mid - i;}}while (i < mid) temp[p++] = a[i++];while (j <= r) temp[p++] = a[j++];p = i = l;while (p <= r) a[i++] = temp[p++];}void merge_sort(int l, int r) {if (l < r) {int mid = (l + r) / 2;merge_sort(l, mid);merge_sort(mid + 1, r);merge_pai(l, r, mid + 1);}}signed main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];merge_sort(1, n);cout << ans << endl;}

19. MT2169 逆序

（1）题目描述
给一个长度为n的排列p，找一个元素，使得从排列中取出这个元素以后排列的"records”最多。

一个”record”是一个元素a满足:对于每个正整数1≤j <i,ai > aj 。

格式

输入格式:
第一行为n
第二行为排列p
.
输出格式: 一个整数即答案

样例1

输入:
5
5 1 2 3 4
.
输出: 5

备注：

其中: 1≤n, a[i]≤1e5。

（2）参考代码

import time
from typing import List,Tuple
from collections import deque, Counter
from queue import PriorityQueue
import math
from functools import lru_cache
import random
import copydef main():n = int(input())arr = list(map(int,input().split()))ss = set()c = Counter()ma,mi=-1,-1for v in arr:if ma<v:ss.add(v)else:if mi<v:c[ma]+=1if v>ma:ma,mi=v,maelif v>mi:mi=vmx = -1ans = Nonefor i in range(1,n+1):val = 0if i in ss:val -= 1if i in c:val+=c[i]if val>mx:mx=valans=iprint(ans)if __name__ == '__main__':main();

20. MT2170 线段树

（1）题目描述
要求使用指针来实现该数据结构。如题，已知一个数列，你需要进行下面两种操作:将某区间每一个数加上k，求出某区间每一个数的和。

格式

输入格式: 第一行包含两个整数 n, m( 5≤n, m ≤10),分别表示该数列数字的个数和操作的总个数。
第二行包含n 个用空格分隔的整数(0-109)，其中第i个数字表示数列第i项的初始值。
接下来m行每行包含3或4个整数，表示一个操作，具体如下:1 x y k:将区间[x, y]内每个数加上k。
2 x y:输出区间[x, y]内的数的和。( 1≤a ≤y ≤n,0≤k ≤105)。
.
输出格式: 输出包含若干行整数，即为所有操作2的结果。

样例1

输入:
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
.
输出:
11
8
20

备注：

线段树模板

（2）参考代码

 #include<iostream>#include<cstdio>#include<cstdio>using namespace std;typedef long long ss;struct node{int l,r;ss data,lz;}tree[3000010];
ss a[3000010];void jian(int l,int r,int now){tree[now].l=l;tree[now].r=r;tree[now].lz=0;if(l==r){tree[now].data=a[l];return;}int mid=(l+r)>>1;jian(l,mid,now*2);jian(mid+1,r,now*2+1);tree[now].data=tree[now*2].data+tree[now*2+1].data;}void xia(int x){if(tree[x].lz){tree[x*2].lz+=tree[x].lz;tree[x*2+1].lz+=tree[x].lz;int mid=(tree[x].l+tree[x].r)/2;tree[x*2].data+=tree[x].lz*(mid-tree[x*2].l+1);tree[x*2+1].data+=tree[x].lz*(tree[x*2+1].r-mid);tree[x].lz=0;}}void update(int l,int r,int now,int k){if(tree[now].l>=l&&tree[now].r<=r){
tree[now].data+=k*(tree[now].r-tree[now].l+1);tree[now].lz+=k;return;}xia(now);if(tree[now*2].r>=l)update(l,r,now*2,k);if(tree[now*2+1].l<=r)update(l,r,now*2+1,k);tree[now].data=tree[now*2].data+tree[now*2+1].data;}ss get_sum(int l,int r,int now){if(tree[now].l>=l&&tree[now].r<=r){return tree[now].data;}xia(now);ss ans=0;if(tree[now*2].r>=l)ans=ans+get_sum(l,r,now*2);if(tree[now*2+1].l<=r)ans=ans+get_sum(l,r,now*2+1);return ans;}int main(){int n,m,x,y,k,t;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);jian(1,n,1);while(m--){scanf("%d%d%d",&t,&x,&y);if(t==1){scanf("%d",&k);update(x,y,1,k);}else{printf("%lld\n",get_sum(x,y,1));}}return 0;}

21. MT2171 最大的忠诚度

（1）题目描述
小码哥有n个手下，每一个手下对小码哥都有一个忠诚度f，他今天要向他的上司展示他的手下，最多可以带m个人，

于是他叫手下排成一排，小码哥将挑选一个不超过m的连续子序列，使得他们的忠诚度和最大。
有些是其他公司的卧底，所以可以存在负的忠诚度。

小码哥请你来找出最大的忠诚度之和。

格式

输入格式:
第一行两个正整数n, m
第二行n个整数，表示n个手下的忠诚度f
.
输出格式: 一个数，最大的忠诚度之和

样例1

输入:
6 4
1 -3 5 1 -2 3
.
输出: 7

备注：

提示:1≤n, m≤ 1e6, abs(fi)≤ 1e6

（2）参考代码

 import java.util.Scanner;class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);// code here
int n = input.nextInt();int m = input.nextInt();int[] fi = new int[n];for (int i = 0; i < fi.length; i++) {fi[i] = input.nextInt();}//max fiint max = Integer.MIN_VALUE;for (int i = 0; i < fi.length; i++) {int tempSum = 0;
for (int index = i; index <= i+m && index < fi.length;index++) {tempSum += fi[index];if (tempSum > max) {max = tempSum;}}}System.out.print(max);input.close();}}

22. MT2172 上楼梯

（1）题目描述

小码哥是个调皮的孩子，他上楼梯喜欢蹦蹦跳跳，也就是说，每次他会随机向上走1级或2级台阶。无聊的你想知道他从地面上到n层共有多少种走法。每层楼之间有m级台阶。

格式

输入格式: 输入两个正整数m、n，代表每层台阶数以及要去到的楼层。
.
输出格式: 输出一个数，代表所有可能的走法的总个数。

样例1

输入: 1 4
.
输出: 3

备注：

上楼哦! n * m≤90。

（2）参考代码

#include<bits/stdc++.h> using namespace std;
typedef long long ll;ll dp[100005]={0};int main( )
{int n,m;cin>>m>>n;dp[0] = 0;dp[1] = 1,dp[2] = 2;for(int i=3;i<=m*(n-1);i++) dp[i] = dp[i-1]+dp[i-2];cout<<dp[m*(n-1)]<<'\n';return 0;
}

23. MT2173 上楼梯2

（1）题目描述
小码哥是个调皮的孩子，他上楼梯喜欢蹦蹦跳跳，也就是说，每次他会随机向上走1级或2级台阶。他初始在第1阶台阶上。

这道题已经做过了，现在把它升级，假设这个小码哥不是个普通的小孩，他是超人宝宝，每次最多可以向上走k级台阶(超人宝宝当然不傻，最少也会向上走一个台阶)，请你求出他从底部上到第n级台阶共有多少种可能的走法。

格式

输入格式: 输入一行用空格隔开的两个正整数n和k。
.
输出格式:
输出一个数，代表所有可能的走法的总个数。
由于这个数可能很大，请你输出结果对114584取模的结果。

样例1

输入: 3 4
.
输出: 4

备注：

n≤10的5次, k ≤ 100 。

（2）参考代码


def main():#code heren,k=map(int,input().split())f = [0 for i in range(n+1)]f[0]=1f[1]=1for i in range(2,n+1):for j in range(1,min(k+1,i+1)):f[i]+=f[i-j]f[i]%=114584print(f[n])if __name__ == '__main__':main();

24. MT2174 大厨小码哥

（1）题目描述
大厨小码哥要做一道菜，这道菜需要烹饪数个小时，达到一定的火力值。可以选择小火烹饪一次加n点火力值，中火烹饪加m点火力值，大火烹饪加k点火力值，烹饪次数不限制。这道菜总共要达到a点火力值，不多不少，才能显现出大厨小码哥的实力。但大厨小码哥觉得这还是太简单了。所以他想考考你，这道菜有多少种不同的烹饪方式?(火力烹饪的顺序不同也算不同的情况，毕竟厨艺学博大精深，先小火后大火和先大火后小火烹饪的菜品会有很大不同）由于数据很大，请输出答案mod 1e9＋7之后的值。

格式

输入格式: 四个整数a, n, m, k
.
输出格式:
一个整数，表示不同的方案数
若无法烹饪则输出“impossible"

样例1

输入: 5 1 2 3
.
输出: 13

备注：

所有数据均在longlong范围内，0<a <1000,0 <n<m<k <30。

（2）参考代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;ll dp[1010] = {1, 0};
const ll mod = 1e9 + 7;int main() {int x;int val[3];cin >> x;for (int i = 0; i < 3; i++) {cin >> val[i];}for (int i = 1; i <= x; i++) {for (int j = 0; j < 3; j++) {if (i - val[j] >= 0) {dp[i] += dp[i - val[j]];dp[i] %= mod;}}}if (dp[x]) {cout << dp[x] << endl;}else {puts("impossible");}return 0;
}

25. MT2175 纸带

（1）题目描述
小码哥有一张 1xn的纸带，由n 个格子组成。初始有一个点在n号格子（即左数第n个)中。

假设现在这个点在c(a >1)号格子，每次小码哥可以对这个点进行如下操作中的一种:
减法。选择一个[1,c ―1]中的正整数y，将点移动到c -y号格子中。除法。选择一个[2, ar]中的正整数z，将点移动到L引」号格子中。当点在1号格子中时无法移动，操作结束。

求将点从n号格子移到1号格子的方案数，答案对给定的模数取模。两个方案不同当且仅当有一步选择的操作或选择的数不同。

格式

输入格式: 一行两个数，纸带长度n和模数m。
.
输出格式: 一行一个数，表示答案对m取模的结果

样例1

输入: 3 998244353
.
输出: 5

备注：

2≤n ≤4e6,1e8 <m<1e9, m是质数。

（2）参考代码

 #include <bits/stdc++.h>#define IO ios::sync_with_stdio(NULL)#define sc(z) scanf("%lld", &(z))#define _ff(i, a, b) for (int i = a; i <= b; ++i)#define _rr(i, a, b) for (int i = b; i >= a; --i)#define _f(i, a, b) for (int i = a; i < b; ++i)#define _r(i, a, b) for (int i = b - 1; i >= a; --i)
#define mkp make_pair#define endl "\n"#define pii pair<int,int>#define fi first#define se second#define lowbit(x) x&(-x)
#define pb push_backusing namespace std;typedef double db;typedef long long ll;typedef long double ld;const int N = 4e6 + 5;const ll M = 1e5 + 5;const ll mod = 998244353;const int inf = 1e9;const double eps = 1e-9;const double PI = acos(-1.0);ll f[N],g[N];void solve() {ll sum=0,sum2=0;f[1]=1;ll n,p;cin>>n>>p;_ff(i,1,n){f[i]=(f[i]+((sum+sum2)%p+g[i])%p)%p;for(int j=i;j<=n;j+=i)g[j]=(g[j]+f[i])%p;for(int j=i+1;j<=n;j+=i+1)g[j]=(g[j]-f[i]+p)%p;sum=(sum+f[i])%p;sum2=(sum2+g[i])%p;}cout<<f[n]<<endl;}int main() {solve();return 0;}