## Problem A
题意：
分析可得bi=ai+ai+1
题解：
分析可得bi=ai+ai+1
C++版本一
#include<bits/stdc++.h>
using namespace std; const int maxn = 1e5 + ;
int a[maxn]; int main(int argc, char const *argv[])
{
int n;
cin >> n ;
for(int i = ;i <= n;i ++) cin >> a[i];
for(int i = ;i < n ;i ++) cout << a[i] + a[i + ] << " ";
cout << a[n] << endl;
return ;
}
## Problem B
题意：
一个人站在坐标原点处,他可以往上(U), 下(D), 左(L), 右(R), 四个方向移动,现给你一个移动序列,为了使他最后仍然能回到原点,你需要对这个序列做一些改变,每次可以改变其中一个字母,问最少的改变次数.
题解：
如果这个序列的长度是奇数,那么肯定不可能回到原点,则直接输出“-1”, 否则可以这么想, 如果 “U” 与 “ D” 和 “L” 与 “R” 能成对出现(和出现次序无关), 那么肯定可以回到原点,所以这里需要做的就是分别统计这四个操作出现的次数, 水平方向相减, 竖直方向相减, 意味着去掉成对出现的对数. 如果结果不为 0 ，那么就需要做出改变,可以想到, 对相减后的差值除 2 就可以得到最少的改变次数.
C++版本一
#include<bits/stdc++.h>
using namespace std; const int maxn = 1e5 + ;
int a[maxn]; int main(int argc, char const *argv[])
{
string str;
cin >> str;
int l , r , u , d;
l = r = u = d = ; for(int i = ;i < str.size();i ++){
if(str[i] =='L') l ++;
if(str[i] =='R') r ++;
if(str[i] =='U') u ++;
if(str[i] =='D') d ++; }
int ans = abs(l - r) + abs(u - d);
if(str.size() % == ) cout << ans / << endl;
//if(str[i] =='L') l ++;
else cout << - << endl;
return ;
}
## Problem C
题意：
题目大意：给你一个长度为x的等边三角形，每一秒你能修改一条边的长度，要你修改到长度为y的等边三角形，要求修改过程中保证它是一个三角形。
题解：
解题思路：从y开始倒着往x推。
C++版本一
#include<bits/stdc++.h>
using namespace std; const int maxn = 1e5 + ;
int a[maxn];
priority_queue<int>q;
int main(int argc, char const *argv[])
{
int n , m ;
cin >> n >> m ;
// q.push(m);
// q.push(m);
// q.push(m);
// //q.push(1); // while(q.top() != n ){
// int t = q.top();
// q.pop();
// if(t)
// }
std::vector<int > v;
v.push_back(m);
v.push_back(m);
v.push_back(m);
int i = ;
int ans = ;
while(v[] < n){
ans ++;
//for(int i = 0;i < 3;i ++){
v[] = v[] + v[] - ; //if(v[i] >= n) v[i] = n;
//}
sort(v.begin(), v.end());
// for(int i = 0;i < 3 ;i ++){
// cout << v[i] << endl;
// }
// cout << "-----------" << endl;
}
cout << ans << endl;
return ;
}
## Problem D
题意：
AB两人玩一个游戏，两人玩 t 轮
每人每次随机且等概率从 [−k,k] 中取一个数字加到总得分中 得分高者赢
已知A,B初始分别有 a,b 分，问A取得胜利的方案数是多少
答案 mod1000000007
a,b,t⩽100,k⩽1000
题解：
因为每轮Memory和Lexa能取的都在[-k,k]，也就是说每轮两人分数的变化量在[-2k,2k]；
故可以定义状态：dp[times][diff]为第times次Memory和Lexa的分数差为diff的方案数.
而dp[times][diff]可以从dp[times-1][diff-2k]到dp[times-1][diff+2k]转移而来；
又因为变化量为-2k时的方案数为1（-k，k），
变化量为-2k+1时的方案数为2（-k，k-1；-k+1，k），
变化量为-2k+2时的方案数为3（-k，k-2；-k+1，k-1；-k+2，k），
...，
变化量为-2k+m时的方案数为m+1，
...，
变化量为0时的方案数为2k+1，
...，
变化量为2k-m时的方案数为m+1，
...，
变化量为2k-1时的方案数为2，
变化量为2k时的方案数为1.
所以状态转移方程为：dp[times][diff]=dp[times-1][diff-2k]+2*dp[times-1][diff-2k+1]+3*dp[times-1][diff-2k+2]+...+(m+1)*dp[times-1][diff-2k+m]+...+2*dp[times-1][diff+2k-1]+dp[times-1][diff+2k];
dp[times][diff]是在dp[times][diff-1]的基础上前半段各个项减一，后半段各个项加一得到的，所以可以维护一个前缀和数组pre[i]，那么
dp[times][diff]=dp[times][diff-1]+(pre[diff+2k]-pre[diff-1])-(pre[diff-1]-pre[(diff-1)-2k-1])
可以在O（1）的时间内完成，优化后的代码时间复杂度为O（kt），代码如下：
C++版本一
#include<iostream>
#include<cmath>
#define M 1000000007LL
#define TIME 105
#define DIFF 500000
#define BASE 250000
using namespace std;
typedef long long LL;
LL a,b,k,t,ans;
LL dp[TIME][DIFF];
LL pre[DIFF];
int main(void){
cin>>a>>b>>k>>t;
dp[][a-b+BASE]=;
LL upper=a-b+BASE+*k*t;
LL lower=a-b+BASE-*k*t;
for(LL times=;times<=t;++times){
for(LL diff=lower;diff<=upper;diff++)
pre[diff]=pre[diff-]+dp[times-][diff],pre[diff]%=M;
for(LL m=;m<=*k;m++){
LL add=-*k+m;
if(add)dp[times][lower]
+=(dp[times-][lower+add]+dp[times-][lower-add])*(m+);
else dp[times][lower]+=dp[times-][lower]*(m+);
dp[times][lower]%=M;
}
for(LL diff=lower+;diff<=upper;diff++){
dp[times][diff]=dp[times][diff-]
+(pre[min(upper,diff+*k)]-pre[diff-])
-(pre[diff-]-pre[max(lower,diff--*k)-]);
dp[times][diff]=(dp[times][diff]+M)%M;
//记得+M，减法模运算可能会出现负数
}
}
for(int i=BASE+;i<=upper;++i)
ans=(ans+dp[t][i])%M;
cout<<ans<<endl;
}
C++版本二
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=,mod=1e9+;
using namespace std;
inline int Getint(){register int x=,f=;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}while(isdigit(ch)){x=x*+ch-'';ch=getchar();}return x*f;}
int f[][N*];
int main(){
int a=Getint(),b=Getint(),k=Getint(),t=Getint()<<;
int lim=a-b;
f[][k*t]=;
for(int i=;i<=t;i++){
int l=k*t-k*i,r=l,ret=;
for(int j=l,lim=k*t+k*i;j<=lim;j++){
while(r<=j+k&&r<=lim)ret=(ret+f[i-][r])%mod,r++;
while(l<j-k)ret=(ret-f[i-][l]+mod)%mod,l++;
f[i][j]=ret;
}
}
int ans=;
for(int i=k*t-lim+;i<=k*t*;i++)ans=(ans+f[t][i])%mod;
cout<<ans;
return ;
}
C++版本三
https://www.cnblogs.com/emiya-wjk/p/10057389.html
o（kt）
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=,T=,mod=1e9+;
using namespace std;
inline int Getint(){register int x=,f=;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}while(isdigit(ch)){x=x*+ch-'';ch=getchar();}return x*f;}
int ksm(int x,int k){
int ret=;
while(k){
if(k&)ret=(LL)ret*x%mod;
x=(LL)x*x%mod,k>>=;
}
return ret;
}
int fac[N],inv[N];
int C(int n,int m){if(n<m)return ;return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;}
int sum[N];
int main(){
int a=Getint(),b=Getint(),k=Getint(),t=Getint()<<;
int lim=k*t-a+b+;
fac[]=;
for(int i=;i<=;i++)fac[i]=(LL)fac[i-]*i%mod;
inv[]=ksm(fac[],mod-);
for(int i=-;~i;i--)inv[i]=(LL)inv[i+]*(i+)%mod; sum[]=;for(int i=;i<=*k*t;i++)sum[i]=(sum[i-]+C(t+i-,t-))%mod;
int ans=;
for(int i=;i<=t;i++){
int nw=(*k+)*(t-i),l=max(lim-nw,),r=*k*t-nw;
if(l>r||r<)continue;
if(l>r)swap(l,r);
ans=(ans+(LL)C(t,i)*((i&)?-:)*((sum[r]-(l?sum[l-]:)+mod)%mod)%mod+mod)%mod;
}
cout<<ans;
return ;
}
## Problem E
题意：
一个multiset，有t个操作，其中+ a表示multiset中加入一个数a，-a表示从multiset取出a，?表示每次询问一个01串s，如果s的一位是0，那么所匹配的数的该位应该是偶数，反之如果是1所匹配的改位应该是奇数。如果匹配时产生数位不够的问题的话添加前导0。每次询问有多少个数和s串能够匹配。
题解：
不是题目中有multiset，就一定要用multiset，这题其实就是题目难读，仔细思考一下用map操作一下就好了
+a时将 a变成一个对应询问的01串即可。举例说明：
361==101
241==001==1
然后对应保存这个得到的01串（要用long long ）为tmp，然后map[tmp]++；
同理-a 对应着map[tmp]--；
那么在询问的时候，直接输出当前01串映射的值即可。
C++版本一
#include<bits/stdc++.h>
using namespace std; const int maxn = 1e5 + ;
int a[maxn];
std::map<long long , int> mp;
char s[];
long long x;
string str;
long long solve(string x){
long long tmp = ;
for(int i = ;i < x.size(); i ++){
tmp = tmp * + ((x[i] - '') % ) ;
}
return tmp;
} int main(int argc, char const *argv[])
{
int n;
cin >> n ;
for(int i = ;i <= n ; i ++){
cin >> s ;
if(s[] == '+')
{cin >> str;
long long a = solve(str);
// string a;
// for(int i = 0;i < str.size(); i++){
// if((str[i] - '0') % 2 == 0) a.push_back('0');
// else a.push_back('1');
// }
//cout << a << endl;
mp[a] ++;
}
if(s[] == '-'){
cin >> str;
// string a;
// for(int i = 0;i < str.size(); i++){
// if(str[i] - '0' % 2 == 0) a.push_back('0');
// else a.push_back('1');
// }
long long a = solve(str);
mp[a] --;
}
if(s[] == '?'){
cin >> x;
cout << mp[x] << endl; }
} return ;
}
## Problem F
F - Sonya and Problem Wihtout a Legend
题意：
https://blog.csdn.net/lycheng1215/article/details/80089004
题解：
https://blog.csdn.net/lycheng1215/article/details/80089004
C++版本一
#include<bits/stdc++.h>
using namespace std; const int maxn = 2e5 + ;
int a[maxn]; priority_queue<int>s; int main(int argc, char const *argv[])
{
int n;
cin >> n;
long long ans = ;
for(int i = ;i <= n ; i ++) {
cin >> a[i];
a[i] -= i;
s.push(a[i]);
if(s.top() > a[i]){
ans += s.top() - a[i];
s.pop();
s.push(a[i]);
}
}
cout << ans << endl;
return ;
}
C++版本二
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=3e3+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
int n,m,k,t,a[maxn],b[maxn];
ll dp[maxn][maxn];
int main()
{
int i,j;
scanf("%d",&n);
rep(i,,n)scanf("%d",&a[i]),a[i]-=i,b[i]=a[i];
sort(b+,b+n+);
rep(i,,n)
{
ll p=1e18;
rep(j,,n)
{
p=min(p,dp[i-][j]);
dp[i][j]=p+abs(a[i]-b[j]);
}
}
ll ans=1e18;
rep(i,,n)ans=min(ans,dp[n][i]);
printf("%lld\n",ans);
//system("Pause");
return ;
}