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

（2）参考代码

 #include 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 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 
#include 
#include 
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 4.序列α单调不降，序列b单调不升。

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

格式

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

样例1

输入: 2 2
.
输出: 5

备注：

其中: 1

（2）参考代码

#include using namespace std;#define debug(x) cerr << #x << " is " << x << endltypedef long long ll;typedef pair 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
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

（2）参考代码

#include
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 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;lineint* arr = M[line];for(int ii=0;iiif(ii==0){for(int jj=0;jj<=(n>>1);jj++){for(int mod=0;modif(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]);elsedp[ii][jj][mod]=0;}else{if(arr[0]%k == mod)dp[ii][jj][mod] = arr[0];elsedp[ii][jj][mod] = -0x3fffffff;}}}}continue;}for(int jj=0;jj<=(n>>1);jj++){for(int mod=0;modif(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;modmx[line][mod] = dp[n-1][n>>1][mod];}}
}ull D[80][80];int main( )
{
#ifdef TESTfreopen("/Users/grh/Programming/ClionProjects/AlgoCoding/input.txt","r",stdin);
#endifscanf("%d %d %d",&m,&n,&k);for(int i=0;ifor(int j=0;jif(ii==0){for(int mod=0;modD[ii][mod] = mx[ii][mod];}continue;}for(int mod=0;modD[ii][mod] = D[ii-1][mod];for(int v=0;vint 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）参考代码

#includeusing namespace std;void solve_maze(){int m, n;cin>>m>>n;char** maze=new char*[m];//有可能溢出，需要使用Longlong** dp=new long*[m];for(int i=0;imaze[i]=new char[n];dp[i]=new long[n];for(int j=0;jcin>>maze[i][j];}
}//初始化dp数组,首先是下边界,如果遇到障碍，那么右侧无法通行,全为0dp[m-1][0]=1;bool flag= false;for(int i=1;iif(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数组,首先是作边界,如果遇到障碍，那么上侧无法通行,全为0flag= 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;jif (maze[i][j] == '1') continue;dp[i][j] = dp[i + 1][j] + dp[i][j - 1];}}cout<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）参考代码

#includeusing namespace std;int c[105];int main(){int n,x,s=0;cin>>n>>x;for(int i=0;icin>>c[i];c[i]=c[i]*(n-i);}sort(c,c+n);if(c[0]<=x)for(int i=0;iif(x-c[i]<0)break;x-=c[i];s++;}cout<

 #include 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< 0 && j > 0){if(path[i][j] == 1){res[k]=i;k++;j -= a[i];}i--;}for(i=k-1;i>=0;i--){cout<

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 9if ii == n-1:tot = 0for v in range(bound+1):tot += vreturn tot, bound+1tot, cnt = 0, 0for v in range(bound+1):t, c = dp(ii+1, all_max and v == bound)cnt += ctot += v*c + treturn tot, cntprint(dp(0, True)[0])
if __name__ == '__main__':main();

#include
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<

#include 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;}

#include using namespace std;
unsigned int ans,a,n;int main( )
{char a[10000] = {};cin>>a;int x;cin>>x;for(int i=x;i

def main():#code heren = int(input())s = str(input())s_start = 0result = 0for 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_maxbreakif result != 0:print(len(s)-result+1)breakif result==0:print(len(s))if __name__ == '__main__':main();

def main():#code heren = 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();

#includeusing 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(slentlen)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<