算法竞赛入门【码蹄集进阶塔335题】(MT2176-2200）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法竞赛入门【码蹄集进阶塔335题】(MT2176-2200）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

前言

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

为什么突然想学算法了？

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

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

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

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

（1）题目描述
某农场有一个由按编号排列的n根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩高度成一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选取出t根木桩的方案总数c。

格式

输入格式: 文件中的第一行只有一个数m，表明随后有m 个问题的描述信息。每个问题的描述信息格式为nh1, h2, h3,. . . , hn(其中hi (i= 1,2,3,. . . ,n)表示第i根木桩的高度。)
.
输出格式: 依次输出每个问题中t和c的解。每行输出一个问题的解。
样例1

输入:
3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12
.
输出:
4 1
2 2
3 3

备注：

其中: 1≤m ≤5,1≤n≤20,1 ≤hi≤150

（2）参考代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k,n,b[2005],c[2005],a[2005],i,j;
    cin>>k;
    while(k--){
        cin>>n;
        for(i=1;i<=n;i++){
            cin>>a[i];
            b[i]=c[i]=1;
        }
        for(j=2;j<=n;j++){
            int r;
            for(r=j-1;r>=1;r--){
                if(a[j]>=a[r]){
                    if(b[j]<b[r]+1){
                        b[j]=b[r]+1;
                        c[j]=c[r];
                    }else if(b[j]==b[r]+1){
                    c[j]+=1;
                    }   
                }
            }
        }
        int max=-1,bj=0;
        for(i=1;i<=n;i++){
            if(b[i]>max){
                max=b[i];
                bj=i;
            }
        }   
        int ans=0;
        for(i=1;i<=n;i++){
            if(b[i]==b[bj]) ans+=c[i];
        }
        cout<<b[bj]<<" "<<ans<<endl;
    }
    
    return 0;
}

2. MT2177 学习时间

（1）题目描述

小码哥是个不爱学习的学生，但由于A天后进行期末考试，他不得不在第i天学习不少于minT’ime;小时，不多于maxTime; 小时的时间。

现在小码哥知道了复习完所有的知识需要总计用时sumTime(小时) .现在他希望知道他能否制作一份时间表，包含A个数，每个数schedule表示小码哥第i天在复习考试上的用时(单位为小时)，并应满足上文提及的要求。

格式

输入格式:
第一行包含两个数:A, sumT’ime 。
1≤A≤30,0≤sumTime ≤ 240,意义如上所述。
接下来A行，每行两个数: minTime[i],maxtime[i],两个数之间有一个空格，意义如上。( 0 ≤minTime[i] ≤maaTime[i]≤8 )。
如果能够复习完，在单独一行输出”YES”(不含引号)。
如果可能复习完，在单独一行输出”MAYBE”(不含引号)。如果不能复习完，在单独一行中输出”NO! YOU AREDEAD!!!”(注意空格)。
.
输出格式:
如果能够复习完，在单独一行输出”YES”(不含引号)。如果可能复习完，在单独一行输出”MAYBE”(不含引号)。如果不能复习完，在单独一行中输出”NO! YOU AREDEAD!!!”(注意空格)。

样例1

输入:
2 5
0 1
3 5
.
输出: MAYBE

（2）参考代码

#include<bits/stdc++.h>
 //3.学习时间
 /*
 算出他最长的学习时间和最短的学习时间，进行判断即可

 */
 using namespace std;

 int main( )
{
 int a,sumTime;
 cin>>a>>sumTime;
 int mint=0;
 int maxt=0;
 for(int i=0; i<a; i++){
 int m1,m2;
 cin>>m1>>m2;
 mint+=m1;
 maxt+=m2;
 }

 if(mint>=sumTime){//最少的时间都可以完成任务，必能完成
 cout<<"YES"<<endl;
 }else if(maxt<sumTime){//最长的时间都不能完成，必不能完成
 cout<<"NO! YOU ARE DEAD!!!"<<endl;

 }else{//其他待定
 cout<<"MAYBE"<<endl;
 }
 return 0;
 }

3. MT2178 最长子段和

（1）题目描述
给出一个长度为n的序列a，选出其中连续且非空的一段使得这段和最大。

格式

输入格式:
第一行是一个整数，表示序列的长度n。
第二行有n个整数，第i个整数表示序列的第i个数字ai。
.
输出格式: 输出一行一个整数表示答案。

样例1

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

备注：

其中: 1<n ≤2e5，- 1e4 ≤ ai≤1e4

（2）参考代码

import java.util.Scanner;
import java.util.*;
class Main {
public static void main(String[] args) {
 Scanner input = new Scanner(System.in);
 int n = input.nextInt();
 int[] arr = new int[n + 1];
 int max = arr[0];
 for (int i = 1; i < arr.length; i++) {
 arr[i] = input.nextInt();
 if (arr[i-1]>0) {
 arr[i] +=arr[i-1];
 }
 max = Math.max(max,arr[i]);
 }
 System.out.println(max);
}
}

4. MT2179 写程序

（1）题目描述
有n个程序员，每个程序员都可以写任意行代码，总共要编写m 行代码，这m 行代码可以由多个程序员来编写。但是第﹔个程序员在一行代码中会出现a个bug。现在希望知道有多少种方案能使得这m 行代码中的 bug 的数量不超过b个。

两个方案不同当且仅当某个程序员编写的代码量（(行数）不同。

格式

输入格式:
第一行四个数n, m, b, mod，第二行为a[动]。
.
输出格式: 输出一行一个整数，表示m行代码 bug数量小于b的方案数对mod取模后的答案。

样例1：

输入：
3 3 3 100
1 1 1
.
输出：10

备注：

其中:1 ≤n, m ≤500,0 ≤b ≤500; 1 ≤ mod ≤109＋7;0≤a[i]≤500

（2）参考代码

 #include <stdio.h>
 #include <string>
 #include <string.h>
 #include <algorithm>
 #include <map>
 #include <vector>
 #include <algorithm>
 #include <vector>
#include <set>
 #include <queue>
 #include <string>
 #include <unordered_map>
 using namespace std;

 typedef unsigned long long ull;

 struct dp {
 int d[505][505];
 } d0, d1;

 int arr[505];

 int main() {
 //TEST;
 int n, m, b, mod; scanf("%d %d %d %d", &n, &m, &b, &mod);
 for (int i = 0; i < n; i++) scanf("%d", arr + i);

 struct dp* dp0 = &d0, *dp1 = &d1;


 for (int j = 0; j <= m; j++) {
 for (int k = 0; k <= b; k++) {
 if (arr[0] * j <= k) dp0->d[j][k] = 1;
 else dp0->d[j][k] = 0;
 }
 }

 for (int i = 1; i <= n-1; i++) {
 for (int j = 0; j <= m; j++) {
 for (int k = 0; k <= b; k++) {
 if (j == 0) {
 dp1->d[j][k] = 1;
 } else {
 int ans = dp0->d[j][k] % mod;
 if (arr[i] <= k) {
 ans += dp1->d[j - 1][k - arr[i]];
 ans %= mod;
 }
dp1->d[j][k] = ans;
 }
 }
 }

 swap(dp0, dp1);
 }

 printf("%d\n", dp0->d[m][b]);
 return 0;
 }

5. MT2180 三个一组

（1）题目描述
都知道当数字的数量到三的时候会发生奇妙的事情。

小码哥给你一个整数数组，判断数组中是否存在长度为3的递增子序列。

递增子序列的定义是，满足下标i<j<k的数组, num[i]<num[j]<num[k]

格式

输入格式: 一个整数数组
.
输出格式: 返回”true”或”false"

样例1

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

备注：

数组长度不超过5*10的5次，元素范围在―2的31次到2的31次 -1之间。

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    bool flag1=false;
    bool flag2=false;
    int a,b = 2147482647;
    while(cin>>a){
        if(a>b&&flag1){
            flag2=true;
            break;
        }
        if(a>b){
            flag1=true;
        }else{
            flag1=false;
        }
        b=a;
    }
    if(flag2)cout<<"true";
    else cout<<"false";
    return 0;
}

6. MT2181 购物

（1）题目描述
小码哥有m块钱的经费，被派去买礼物，商店里的礼物共n个，有不同的价钱ai，小码哥想尽可能多的花这笔经费，毕竟剩下的钱就落到他上司的手里了。

在m块的经费范围内，求小码哥最多可以用多少钱，输出剩余的经费。

格式

输入格式:
1个整数m，表示经费;
1个整数n，表示有n个礼物;
接下来n行，分别表示这n个礼物的各自价格。
.
输出格式: 1个整数，表示经费的剩余量。

样例1

输入:
24
6
8
3
1
7
3
7
.
输出: 1

备注：

提示:1≤m ≤10000,1 ≤n ≤300 。

（2）参考代码

 #include <iostream>
 using namespace std;
 const int MAXM = 10005;
 const int MAXN = 305;

 int dp[MAXN][MAXM], price[MAXN];
 int main()
 {
 int m, n;
 cin >> m >> n;
 for (int i = 1; i <= n; i++) {
 cin >> price[i];
 }
 for (int i = 1; i <= n; i++) {
 for (int j = 1; j <= m; j++) {
 if (j < price[i]) {
 dp[i][j] = dp[i - 1][j];
 } else {
 dp[i][j] = max(dp[i - 1][j - price[i]] + price[i], dp[i - 1][j]);
 }
 }
 }
 cout << m - dp[n][m];
 return 0;
 }

7. MT2182 旅费

（1）题目描述
提瓦特大陆上有个贫穷的占星术士小码哥，他要去从蒙德去往璃月，两个地方相隔很远，所以要搭乘车队。但是搭乘车队需要金币，而小码哥没有太多金币，幸运的是，车队在这一路上有n个停靠点，每两个停靠点之间所需要的金币数不一样，如果能选择好的话说不定能省点钱。于是小码哥找来了每个站点之间所需的路费，请你帮他找出他完成这一旅途所需要的最少的旅费。

格式

输入格式:
第一行输入一个数n，表示马车中间停靠的站点数。
接下来一个n行的半矩阵，表示从蒙德开始，每个站点到接下来每个站点所需要的金币数。
.
输出格式: 输出一行一个正整数，表示完成这一旅途所需要的最少的旅费(金币数)。

样例1

输入:
1
6 18
9
.
输出: 15

备注：

其中: 1≤n <1000
任意两站间所需旅费不超过10000
样例解释:
蒙德–-6- ->站点1，蒙德–-18–>璃月
站点1 - -9- ->璃月

（2）参考代码

#include<bits/stdc++.h> 


using namespace std;
 const int maxn=30000;
 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;
 }
 struct Edge{
 int v,w,next;
 }e[maxm*2];
 int en,front[maxn];
 int n,m,s,t;
 inline void addedge(int u,int v,int w){
 en++; e[en].v=v; e[en].w=w; e[en].next=front[u]; front[u]=en;
 }
 void SPFA(){
 int inq[maxn];
 int d[maxn];
queue<int> q;
 memset(inq,0,sizeof(inq));
 for (int i=1;i<=n+m;i++) d[i]=INF;
 d[s]=0; inq[s]=1; q.push(s);
 while (!q.empty())
 {
 int u=q.front(); q.pop(); inq[u]=0;
 for (int i=front[u];i>=0;i=e[i].next){
 int v=e[i].v,w=e[i].w;
 if(d[v]>d[u]+w){
 d[v]=d[u]+w;
 if (!inq[v]){
 inq[v]=1;q.push(v);
 }
 }
 }
 }
 if (d[t]!=INF)cout<<d[t];
 else cout<<-1;
 }
 char c;
 int main(){
 memset(front,-1,sizeof(front));
 n=read();
 n+=2;
 for (int i=1;i<=n-1;i++){
 for (int j=1;j<=n-i;j++){
 int tmp=read();
 // cout<<i<<" "<<i+j<<endl;
 addedge(i,i+j,tmp);
 }
 }
 s=1,t=n;

SPFA();
 return 0;
 }

8. MT2183 散步

（1）题目描述
小码哥今天在公园里散步，公园里有一个环型的小道，因为小码哥想要刷一下他的移动步数，所以他决定在小道上走m步。

现已知环形小道长度为n，小码哥一步走1的距离，将小道坐标化:小码哥的初始位置在1，顺时针分别是1 ~ n ，到n后继续走就回到了1。

问小码哥有多少种走路方法，使得走m步过后回到原点。(期间可以经过原点，只要移动的序列不同就可以看作两个方法)。

注:小码哥只可以顺时针或逆时针走，不可以走半步，或者是原地不动;

格式

输入格式:
共一行，有两个用空格隔开的整数n，m (3<n ≤30，1<m≤30）。摇串。
.
输出格式:
共一行，有一个整数，表示符合题意的方法数。

样例1

输入: 7 9
.
输出: 18

备注：

提示:(3≤n≤30，1≤m≤30）

（2）参考代码

 #include<bits/stdc++.h>
 using namespace std;
 //#define N 7
 int main()
 {
 int N,n;
 cin>>N>>n;
 vector<vector<int>> dp(n+1,vector<int>(N,0));
 dp[0][0]=1;
 for(int i=1;i<=n;i++) //步数
 {
 for(int j=0;j<N;j++)
 {
 dp[i][j]=dp[i-1][(j-1+N)%N]+dp[i-1][(j+1)%N];
 }
 }
 cout<<dp[n][0]<<endl;
 return 0;
 }

9. MT2184 抽奖

（1）题目描述
小码哥在集市上逛街，遇见了抽奖活动，抽一次2元，但是可能会抽出1，2，3，4四种情况，他们是等概率的。

小码哥计划抽n次，问亏本的概率是多少(即得到的奖金小于本金)，小码哥赚了超过一半本金的概率是多少（赚到的钱是奖金-本金后的部分)

格式

输入格式: 输入n表示小码哥连抽的次数
.
输出格式:
第一行输出亏的概率
第二行输出赚超过一半本金的概率
概率用最简分数表示，具体看样例

样例1

输入: 2
.
输出:
3/16
3/16

备注：

其中:1≤n ≤30

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

 long long a[50][200];
 long long gcd(long long x, long long y){
 if(x<y){
 long long t=x;
 x=y;
 y=t;
 }

if(x%y==0)
 return y;
 return gcd(y,x%y);
 }
 int main( )
{
 int n;
 cin>>n;
a[1][1]=1;
a[1][2]=1;
a[1][3]=1;
a[1][4]=1;
 for (int i=1; i<=n; i++){
 for(int j=1; j<200; j++){
 for(int k=1; k<=4; k++){
 if(j>k){
 a[i][j]+=a[i-1][j-k];
 }
 }

 }
}
 long long x=0,y=0;
 for(int i=n; i<200; i++){
 if(i<2*n)
 x+=a[n][i];
 if(i-2*n>n)
 y+=a[n][i];
 }

 long long Max=1;
 for(int i=1; i<=n; i++){
 Max*=4;
 }
 int x_gcd = gcd(x,Max);
 int y_gcd = gcd(y,Max);
 cout<<x/x_gcd<<"/"<<Max/x_gcd<<endl;
 cout<<y/y_gcd<<"/"<<Max/y_gcd<<endl;
 return 0;
 }

10. MT2185 异或和

（1）题目描述
给一个长度为n的序列 a1, a2,. . . , an，寻找在α的所有递增子序列(可以为空)的异或和中出现的数。

格式

输入格式:
第一行一个正整数n表示序列长度。
第二行n个整数表示序列a。
.
输出格式:
第一行输出满足要求的数的个数。
第二行从小到大输出在a的所有递增子序列(可以为空)的异或和中出现的数。

样例1

输入:
4
4 2 2 4
.
输出:
4
0 2 4 6

样例2

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

样例3

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

备注：

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

（2）参考代码

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 550;
 const int inf = 0x3f3f3f3f;
 int f[N];

signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

 memset(f, 0x3f, sizeof f);
 f[0] = 0;

 int n;
 cin >> n;
 for (int i = 1, x; i <= n; ++i) {
 cin >> x;
 for (int j = 0; j < N; ++j) {
 if (f[j] < x)
 f[j ^ x] = min(f[j ^ x], x);
 }
 }

 vector<int> res;
 for (int i = 0; i < N; ++i)
 if (f[i] != inf) res.push_back(i);

 cout << res.size() << endl;
 for (auto x: res) cout << x << " ";
 }

11. MT2186 海龟

（1）题目描述
很多人把LOGO编程语言和海龟图形联系起来。在这种情况下，海龟沿着直线移动，接受命令“T”(“转向180度”）和“F”(“向前移动1单元”)。

你会收到一份给海龟的命令清单。你必须从列表中精确地改变Ⅳ个命令（一个命令可以被改变多次）。要求出海龟在遵循修改后的所有命令后，会从起点最远可以移到多远?

格式

输入格式: 第一行为命令清单，第二行为需要改变的命令数
.
输出格式: 一行即为答案

样例1

输入:
FFFTFFF
2
.
输出: 6

备注：

字符串非空且长度不大于100，1≤n ≤50。

（2）参考代码

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dp[101][51][2];
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
char order[105];
int n;
scanf("%s", order);
scanf("%d", &n);
int len = strlen(order);
for(int i = len - 1; i >= 0; i--)
order[i + 1] = order[i];
order[0] = ' ';
for(int i = 0; i <= len; i++)
for(int j = 0; j <= n; j++)
dp[i][j][0] = dp[i][j][1] = -1000000000;
dp[0][0][0] = 0;
dp[0][0][1] = 0;
for(int i = 1; i <= len; i++)
for(int j = 0; j <= n; j++)
for(int k = 0; k <= j; k++)
if(order[i] == 'F')
if(k % 2 == 1)
{
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - k][0]);
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k][0]);
}
else
{
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - k][0] + 1);
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k][1] - 1);
}
else
if(k % 2 == 1)
{
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - k][0] + 1);
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k][1] - 1);
}
else
{
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - k][1]);
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k][0]);
}
printf("%d\n", max(dp[len][n][0], dp[len][n][1]));
return 0;
}

12. MT2187 两数列

（1）题目描述
输入两整数n、m，求有多少对正整数序列ai、b，满足:
1.a 、 b的长度为m;
2.a;、b。中所有元素的值小于等于n;
3.对于所有1<ism , ai≤ bi ;
4.序列α单调不降，序列b单调不升。

答案对10的9次＋7取模。

格式

输入格式: 第一行为n, m
.
输出格式: 输出一个整数为答案

样例1

输入: 2 2
.
输出: 5

备注：

其中: 1<n ≤1000,1 ≤m ≤ 10

（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, N = 1015;
 const int MOD = 1e9 + 7;
 int fac[N];
 int n, m;

 int qpow(int x, int y) {
 int res = 1;
 for (; y; y >>= 1, x = 1ll * x * x % MOD)
 if (y & 1) res = 1ll * res * x % MOD;
 return res;
 }

 int C(int x, int y) {
 if (x < y) return 0;
 return 1ll * fac[x] * qpow(fac[y], MOD - 2) % MOD * qpow(fac[x-y],MOD - 2) % MOD;
 }

 int main()
 {
 ios::sync_with_stdio(false);
 cin.tie(0);
 cin >> n >> m;
 fac[0] = 1;
 for (int i = 1; i <= n + m; ++i) fac[i] = 1ll * fac[i-1] * i % MOD;
 ll ans = 0;
 for (int i = 1; i <= n; ++i) {
 ans += 1ll * C(i + m - 2, m - 1) * C(n + m - i, m) % MOD;
 ans %= MOD;
 }
 cout << ans << "\n";
 return 0;
 }

13. MT2188 数的计算

（1）题目描述
我们要求找出具有下列性质数的个数(包含输入的正整数n )。

先输入一个正整数n ,然后对此正整数按照如下方法进行处理:
1.不作任何处理;
2.在它的左边加上一个正整数,但该正整数不能超过原数的一半;
3.加上数后;继续按此规则进行处理,直到不能再加正整数为止。

格式

输入格式: 一个正整数n
.
输出格式: 一个数表示答案

样例1

输入: 6
.
输出: 6

备注：

其中: n≤1000
对于样例来说，有以下几种:
6，16，26，36，126，136

（2）参考代码

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=1005;
int f[maxn];
int n;
 
int main() {
	f[0]=f[1]=1;
	scanf("%d",&n);
	for(int i=2; i<=n; i++) {
		if(i%2==0) f[i]=f[i-1]+f[i/2];
		else f[i]=f[i-1];
	}
	printf("%d\n",f[n]);
	return 0;
}

14. MT2189 四柱河内塔

（1）题目描述
河内塔问题:

有三个柱子，编号为1，2，3;在编号为1的柱子上有n个大小不同圆盘，圆盘从小到大，从上到下堆叠，你只可以移动一个柱子上最上面的圆盘。

现在你需要将编号为1的柱子上的圆盘移到3柱子上，顺序不变;
注意:你在移动过程中，不可以将大的圆盘放在小圆盘上，你一次只可以移动一个盘子;

现在有一个4个柱子的河内塔，在规则不变的情况下，问最少需要移动多少次才能把盘子从1号柱子移到4号柱子上。

格式

输入格式: 一个整数f，表示n取(1,f)的f种情况。
.
输出格式: 输出f行，表示当n分别取(1,f)的情况下，需要的最少移动次数。

样例1

输入: 12
.
输出:
1
3
5
9
13
17
25
33
41
49
65
81

备注：

提示:1<n ≤50

（2）参考代码

#include<bits/stdc++.h>
using namespace std;

using namespace std;
#define ll long long 
#define N 10000
const ll inf = 0x3f3f3f3f;
ll d[6000], f[6000];
int main()
{
    ll n;
    cin >> n ;
    for (ll i = 1; i <= n; ++i)
        d[i] = 2 * d[i - 1] + 1;
    memset(f, inf, sizeof f);
    f[0] = 0;
    for (ll i = 1; i <= n; ++i)
        for (ll j = 0; j <= i; ++j)
            f[i] = min(f[i], 2 * f[j] + d[i - j]);
    for (ll i = 1; i <= n; ++i)
        cout << f[i] << endl;
    return 0;
}

15. MT2190 矩阵取数

（1）题目描述

给定n* m的矩阵A，和一个整数k，要求每行只能选取不超过一半的元素，且总的选择元素的和要是k的倍数，求满足条件的和的最大值。

格式

输入格式:
第一行为n，m，k
后n行为所述的矩阵
.
输出格式: 输出仅一行，为所求答案

样例1

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

备注：

所有数据均在70以内，且大于0

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
typedef long long ull;
typedef long long LL;

const int MAX_N = 80;

int m,n,k;
int M[80][80];
ull mx[80][80];
ull dp[80][80][80];

void pre_process(){
    for(int line = 0;line<m;line++){
        int* arr = M[line];
        for(int ii=0;ii<n;ii++){
            if(ii==0){
                for(int jj=0;jj<=(n>>1);jj++){
                    for(int mod=0;mod<k;mod++){
                        if(jj==0){
                            if(mod==0) dp[ii][jj][mod]=0;
                            else dp[ii][jj][mod] = -0x3fffffff;
                        }else{
                            if(mod==0){
                                if(arr[0]%k==0)
                                    dp[ii][jj][mod] = max(0,arr[0]);
                                else
                                    dp[ii][jj][mod]=0;
                            }else{
                                if(arr[0]%k == mod)
                                    dp[ii][jj][mod] = arr[0];
                                else
                                    dp[ii][jj][mod] = -0x3fffffff;
                            }
                        }
                    }
                }
                continue;
            }

            for(int jj=0;jj<=(n>>1);jj++){
                for(int mod=0;mod<k;mod++){
                    if(jj==0){
                        if(mod==0) dp[ii][jj][mod] = 0;
                        else dp[ii][jj][mod] = -0x3fffffff;
                    }else{
                        dp[ii][jj][mod] = dp[ii-1][jj][mod];
                        int new_mod = (((mod-arr[ii])%k)+k)%k;
                        dp[ii][jj][mod] = max(dp[ii][jj][mod],arr[ii]+dp[ii-1][jj-1][new_mod]);
                    }
                }
            }
        }
        for(int mod=0;mod<k;mod++){
            mx[line][mod] = dp[n-1][n>>1][mod];
        }
    }
}

ull D[80][80];

int main( )
{
#ifdef TEST
    freopen("/Users/grh/Programming/ClionProjects/AlgoCoding/input.txt","r",stdin);
#endif

    scanf("%d %d %d",&m,&n,&k);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++) scanf("%d",&(M[i][j]));
    }
    pre_process();

    for(int ii=0;ii<m;ii++){
        if(ii==0){
            for(int mod=0;mod<k;mod++){
                D[ii][mod] = mx[ii][mod];
            }
            continue;
        }

        for(int mod=0;mod<k;mod++){
            D[ii][mod] = D[ii-1][mod];
            for(int v=0;v<k;v++){
                int new_mod = (((mod-v)%k)+k)%k;
                D[ii][mod] = max(D[ii][mod],mx[ii][v]+D[ii-1][new_mod]);
            }
        }
    }

    printf("%lld",D[m-1][0]);
    return 0;
}

16. MT2191 迷宫

（1）题目描述
小码哥和他的手下在维多利亚的迷宫玩耍，小码哥并不喜欢这个项目，于是他决定以最快的速度结束这个项目，这个迷宫可以看作是一个直角坐标系，小码哥在左下，终点在右上点。

小码哥只从a, y轴的正方向走，因为这样是理论最快的解，问小码哥有多少种行走方法来最快到达终点。

格式

输入格式: 第一行两个整数m,n表示迷宫是m行n列接下来m行，每行n个数，描述了地图
0-空地
1-墙（无法通过)
.
输出格式: 一个整数表示答案( mod2333）

样例1

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

备注：

是示: n, m ≤3,000

（2）参考代码

#include<bits/stdc++.h>

 using namespace std;
 void solve_maze(){
 int m, n;
 cin>>m>>n;
 char** maze=new char*[m];
 //有可能溢出，需要使用Long
 long** dp=new long*[m];
 for(int i=0;i<m;i++){
 maze[i]=new char[n];
 dp[i]=new long[n];
 for(int j=0;j<n;j++){
 cin>>maze[i][j];
 }
}
 //初始化dp数组,首先是下边界,如果遇到障碍，那么右侧无法通行,全为0
 dp[m-1][0]=1;

 bool flag= false;
 for(int i=1;i<n;i++){
 if(maze[m-1][i]=='1'){
 dp[m-1][i]=0;
 flag=true;
 continue;
 }
 if(flag){
 dp[m-1][i]=0;
 }
 else{
 dp[m-1][i]=1;
 }

}
 //初始化dp数组,首先是作边界,如果遇到障碍，那么上侧无法通行,全为0
 flag= false;
 for(int i=m-2;i>=0;i--){
 if(maze[i][0]=='1'){
 dp[i][0]=0;
 flag=true;
 continue;
 }
 if(flag){
 dp[i][0]=0;
 }
 else{
 dp[i][0]=1;
 }

 }
 // 从下至上，从左到右更新dp数组
 for(int i=m-2;i>=0;i--){
 for(int j=1;j<n;j++){
 if (maze[i][j] == '1') continue;
 dp[i][j] = dp[i + 1][j] + dp[i][j - 1];
 }
 }

 cout<<dp[0][n-1]%2333;
 }
 int main( )
 {
 solve_maze();
 return 0;
}

17. MT2192 动物们

（1）题目描述
有某类动物，可以在农场中待n天，每天最多增加一只动物，第i天到来的动物每天要吃的粮食为c[i]，现在初始粮草是X，问你在每天动物尽可能多的情况下最多容纳几只动物?

有某类动物，可以在农场中待n天，每天最多增加一只动物，第i天到来的动物每天要吃的粮食为c[i]，现在初始粮草是X，问你在每天动物尽可能多的情况下最多容纳几只动物?

格式

输入格式: 第一行为n和X，第二行为上述c[i]
.
输出格式: 输出一个整数，表示最多可以容纳的动物数量

样例1

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

备注：

其中:1≤n ≤100,1≤X ≤10000，c[i]≤300

（2）参考代码


 #include<bits/stdc++.h>
 using namespace std;
 int c[105];
 int main(){
 int n,x,s=0;
 cin>>n>>x;
 for(int i=0;i<n;i++){
 cin>>c[i];
 c[i]=c[i]*(n-i);
 }
 sort(c,c+n);
 if(c[0]<=x)
 for(int i=0;i<n;i++){
 if(x-c[i]<0)
 break;
 x-=c[i];
 s++;
 }
 cout<<s;
 return 0;
 }

18. MT2193 赶deadline

（1）题目描述
小码哥有严重的拖延症，因此他经常赶deadline(即忙于要完成的任务)。有一天小码哥向你求助，因为要做的事太多了，只能舍弃一些相对不重要的。小码哥共有n项任务，每个任务有重要度Ⅰ和需要消耗的时间t。小码哥现在还有时间T,他希望你帮他写一个程序判断应该选择完成哪些任务使得完成的任务重要度之和最大。

格式

输入格式:
第一行两个整数n(0 <n <104)，T(T <2000)
第2至n＋1行输入第i项任务的重要度Ⅰ和完成需要的时间(0 <I,ti<1000)
.
输出格式:
第一行一个整数，完成任务的重要度之和的最大值
第二行若干个由空格隔开的整数，从小到大输出最优选择的任务的序号(从1开始)

样例1

输入:
4 1000
50 500
75 400
60 300
22 200
.
输出:
157
2 3 4

备注：

当做不完所有任务，但有多个重要度与消耗时间都一样的任务，可以选取其中一部分时，选取编号较小的，例如输入为:
4 1000
50 500
50 500
80 300
22 200
对应输出:
152
134

（2）参考代码

 #include <bits/stdc++.h>
 using namespace std;
 int a[10005],b[10005],t=0,k=0,n,m,dp[10005]={ },w,v,s,path[10005]
[10005]={0},res[10005];
int main()
 {
 cin>>n>>m;
 while(n--)
 {
 cin>>w>>v;
 a[++t]=v;
 b[t]=w;
 }
 for(int i=1;i<=t;i++)
 {
 for(int j=m;j>=a[i];j--)
 {
 if(dp[j-a[i]]+b[i] > dp[j])
 {
 dp[j] = dp[j-a[i]]+b[i];
 path[i][j] = 1;
 }
 }
 }
 cout<<dp[m]<<endl;
 int i = t, j = m;
 while(i > 0 && j > 0)
 {
 if(path[i][j] == 1)
 {
 res[k]=i;
 k++;
 j -= a[i];
 }
 i--;
 }
 for(i=k-1;i>=0;i--)
 {
 cout<<res[i]<<' ';
 }
 return 0;
 }

19. MT2194 page

（1）题目描述
一本书的页码是从1~n编号的连续整数:1,2,3;…,n。请你求出全部页码中所有单个数字的和。例如第123页，它的和就是1+2+3=6。当n = 15，全部页码单个数字的和=1+2+3+4+5+6+7+8+9+(1+O)+(1+1)+(1+2)+(1+3)+(1+4)+(1+5)。

格式

输入格式: 一行一个整数n。
.
输出格式: 一行，代表所有单个数字的和。

样例1

输入: 3456789
.
输出: 96342015

备注：

其中:1<n ≤1e9

（2）参考代码

from functools import lru_cache
def main():
    s = str(int(input()))
    arr = []
    for ch in s:
        arr.append(ord(ch) - ord('0'))
    n = len(arr)
    # 返回(数位和，可能的数字个数)
    @lru_cache(typed=False, maxsize=128000000)
    def dp(ii, all_max):
        bound = arr[ii] if all_max else 9
        if ii == n-1:
            tot = 0
            for v in range(bound+1):
                tot += v
            return tot, bound+1
        tot, cnt = 0, 0
        for v in range(bound+1):
            t, c = dp(ii+1, all_max and v == bound)
            cnt += c
            tot += v*c + t
        return tot, cnt
    print(dp(0, True)[0])
if __name__ == '__main__':
    main();

20. MT2195 连锁反应

（1）题目描述
小码哥在玩一个5x5的棋盘游戏，棋盘上有25个棋子，棋子有黑白两面，初始棋子无规则的正反放置在棋盘上，白用1表示，黑用0表示;

每一次玩家可以改变一个棋子的正反，但是由于有连锁反应，这个棋子的上下左右4个棋子会跟着转变其正反，即0变1，1变0;

小码哥想要知道需要多少步才能使棋盘上的棋子全部变为1;

但是如果需要的步数超过6步（小码哥没有那么多耐心等你算出来)，或者，没有办法使棋子全部变为1，你需要告诉小码哥。

格式

输入格式:
第一行有一个正整数n，代表数据中共有n个棋盘游戏的初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个数字0/1。每组数据描述了一个棋盘的初始状态。各组数据间用一个空行分隔。
.
输出格式:
输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的棋盘状态最少需要几步才能使所有棋子白色的面朝上。
对于某一个棋盘初始状态，若6步以内无法使所有棋子白色的面朝上，请输出“-1”。

样例1

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

备注：

其中: n≤500

（2）参考代码

#include<iostream>
using namespace std;
bool s[7][7]={};
int l[10000]={};
void turn(int a,int b)
{
	s[a][b]=!s[a][b];
	s[a][b+1]=!s[a][b+1];
	s[a][b-1]=!s[a][b-1];
	s[a-1][b]=!s[a-1][b];
	s[a+1][b]=!s[a+1][b];
}
int judge(int f)
{
	for(int i=2;i<=5;i++)
	for(int j=1;j<=5;j++)
	{
		if(s[i-1][j]) {
			f++;
			turn(i,j);
		}
	}
	for(int i=1;i<=5;i++)
	if(s[5][i]) return 10000;
	return f;
}
int main()
{
	int n;
	cin>>n;
	for(int p=1;p<=n;p++)
	{
		int ans=1000000,d[7][7];
		char s1[7][7];
		for(int j=1;j<=5;j++)
		for(int k=1;k<=5;k++)
		{cin>>s1[j][k];
		d[j][k]=!(bool)(s1[j][k]-'0');
		}
		for(int i=0;i<1<<5;i++)
		{
			for(int j=1;j<=5;j++)
			for(int k=1;k<=5;k++)
				s[j][k]=d[j][k];
			int f=0;
			for(int j=0;j<5;j++)
			if(i>>j&1) {
				turn(1,j+1);
				f++;
				}
			ans=min(ans,judge(f));
		}
		if(ans<=6) l[p]=ans;
		else l[p]=-1;
	}
	for(int i=1;i<=n;i++)
	cout<<l[i]<<endl;
	return 0;
}

21. MT2196 字符串构造2

（1）题目描述
用a，b，c三种元素构造一个长度为n的字符串，要求:这个字符串中不能有三个相邻的元素，元素值相同，即aaa，这种数列不可以出现;

问可以构造出多少种符合条件的字符串?

格式

输入格式:
输入一个数f ,表示f组数据
每组数据输入一个n，占一行
.
输出格式: 输出一个数，表示符合条件的字符串的数量（结果取余1e9 ＋7)

样例1

输入:
2
30
5000
.
输出:
350832575
568440090

备注：

其中: n ≤100000

（2）参考代码

#include <iostream>
 using namespace std;
 const int mod=1000000007;
 long long getAns(int n){
 long long repeat = 0;
 long long norepeat = 3;
 long long flag;
 for (int i = 2; i <= n; i++) {
 flag = norepeat;
 norepeat = 2*(norepeat + repeat);
 repeat = flag;
 norepeat %= mod;
 repeat %= mod;
 }
 long long ans=(repeat + norepeat)%mod;
 return ans;
 }

 int main(){
 int f, n;
 cin >> f;
 while (f--){
 cin >> n;
long long ans = getAns(n);
 cout << ans << endl;
 }
 return 0;
 }

22. MT2197 字符串旋转

（1）题目描述
实现一个函数，可以左旋字符串中的k个字符。

尽量使用指针。

格式

输入格式:
第一行输入一个非空字符串(只包含小写字母)，长度不大于1000
第二行输入一个非负整数(小于字符串的长度)，表示旋转几个字符。
.
输出格式: 一个旋转后的字符串。

样例1

输入:
abcd
1
.
输出: bcda

样例2

输入:
abcd
2
.
输出: cdab

（2）参考代码


#include<bits/stdc++.h> 

using namespace std;
unsigned int ans,a,n;

int main( )
{
    char a[10000] = {};
    cin>>a;
    int x;
    cin>>x;
    for(int i=x;i<strlen(a);i++) cout<<a[i];
    for(int i=0;i<x;i++) cout<<a[i];
    return 0;
}

23. MT2198 打字

（1）题目描述
输入n及一串长度为n的目标字符串，有两种操作得到目标字符串:
1.—个一个添加字符，直到添加完为止。
⒉.复制前面已经添加的字符，把复制的添加到后面(仅能执行一次)，然后继续添加字符，直到添加完。
问最少需要多少步骤，把字符添加完。

格式

输入格式: 第一行为一个正整数n，第二行为字符串(仅包含小写字母)
.
输出格式: 一个整数即答案

样例1

输入:
7
abcabca
.
输出: 5

备注：

其中:n≤100

（2）参考代码


def main():
    #code here
    n = int(input())
    s = str(input())
    s_start = 0
    result = 0
    for s_max in reversed(range(2,n//2+1)):
        for i in range(0,(n-2*s_max+1)):
            tmp = s[s_start+i:s_max+i]
            if s.count(tmp,s_start+i,s_start+i+s_max*2)==2:
                result = s_max
                break
        if result != 0:
            print(len(s)-result+1)
            break
    if result==0:
        print(len(s))


if __name__ == '__main__':
    main();

24. MT2199 拼写检测

（1）题目描述
小码哥输入单词时经常打错，所以他想让你写一个程序来帮助他检测单词的拼写。

你的程序首先需要接收一个含有若干单词的字典，然后输入一个单词。如果字典上存在完全匹配的单词，输出0;如果删去一个字母后可以变为字典上的单词，先输出可能变成的单词数量，再按字典序依次输出这些单词;其余情况输出-1 。

格式

输入格式:
第一行一个正整数n≤1 x105，表示字典中的单词数量。接下来n 行每行一个字符串s 表示字典中的单词，保证1<|s≤30且单词按字典序排列。
再下一行输入一个字符串t表示待检测的单词，保证1≤lt≤30。
.
输出格式: 详见题面

样例1

输入:
5
aobyhef
fdsgreed
obyhefv
pobhefv
subvxdy
aobyhefv
.
输出:
2
aobyhef
obyhefv

（2）参考代码


def main():
    #code here
    n = int(input().strip())
    vocab = set()
    for i in range(n):
        vocab.add(input().strip())

    t=input().strip()

    if t in vocab:
        print(0)
    else:
        ans=[]
        for i in range(len(t)):
            s = t[:i]+t[i+1:]
            if s in vocab and s not in ans:
                ans.append(s)
        
        if len(ans)==0:
            print(-1)
            exit(0)
        print(len(ans))
        ans = sorted(ans)
        for i in ans:
            print(i)


if __name__ == '__main__':
    main();

25. MT2200 默契的配合

（1）题目描述
小码哥和小码妹是好朋友，他们有时会用一种方式检测双方的默契程度:两人分别给出一个字符串s 和t，并进行若干次操作使s串变得和t串一样。操作分为两种:
1.删除s 串的第一个字符;
⒉将一个新字符插在s 串的第一个字符之前。

如果可以用正好n 次操作使s串变为t串，就意味着他们两人很有默契，输出YEs，否则输出No。

格式

输入格式:
输入共三行。第一行一个整数n 满足0≤n ≤2×106。第二行一个字符串s，第三行一个字符串t，保证1≤|[s ,lt≤2×105且包含的字符均为小写字母。
.
输出格式: 输出一行， YEs或No 。

样例1

输入:
16
aeomopil
scomlpab
.
输出: YES

备注：

对于样例的情况，可以先进行8 次删除操作，再进行8次插入操作。

（2）参考代码

#include<bits/stdc++.h>
 using namespace std;
 int main(){
 	int n,slen,tlen,least=0;
 	string s,t;
 	cin>>n;
 	cin>>s>>t;
 	slen=s.length();
 	tlen=t.length();
 	least=abs(slen-tlen);
 	if(slen<tlen)t.erase(0,least);
 	else if(slen>tlen)s.erase(0,least);
 		assert(s.length()==t.length());
 	int i=s.length()-1;
 	while(i>=0&&s[i]==t[i])i--;
 	least=least+(i+1)*2;
 //cout<<least<<endl;
 	if((least%2==n%2)&&(least<=n))
 		puts("YES");
 	else puts("NO");
 	return 0;
 }