听说这次题目很水，于是就稍微有点不垫底的信心了。。
第一题本来是满的啊。。结果打程序时手抖把“return 0”写成“return 9”了。。
第二题乱敲，过了样例，然而没有什么卵用。。
第三四五题不是暴力就是题意没看懂乱敲的。。。
第六题打了个暴力，没加优化。。
现在来梳理一下今天的题解：
T1:
十分水的模拟题，不需要考虑任何东西。。
code:
using namespace std;
int n,a[1000010];
long long cnt;
void read(int &x){
x=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();}
int main(){
freopen("book.in","r",stdin);
freopen("book.out","w",stdout);
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
//cout<<cnt<<endl;
if(a[i]==5) cnt+=5;
if(a[i]==10){
if(cnt<5){puts("NO");return 0;}
else cnt+=5;
}
if(a[i]==20){
if(cnt<15){puts("NO");return 0;}
else cnt+=15;
}
}
puts("YES");
return 0;}
T2：
这道题题意写的云里雾里，我表示没看懂啊。。
但是经过老师讲解，总算是慢慢看懂了。。。
其实就是求组合计数，但是需要用上逆元和费马小定理。。
code:
define mod 1000000007
using namespace std;
int n,k;
long long ans=1;
long long solve(long long x,long long y){
long long now=x,cnt=1;
for(;y;y>>=1,now=now*now%mod)if(y&1) cnt=cnt*now%mod;
return cnt;}
int main(){
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)ans=1ll*ans*i%mod;
for(int i=1;i<=k;i++)ans=1ll*ans*solve(i,mod-2)%mod;
for(int i=1;i<=n-k;i++)ans=1ll*ans*solve(i,mod-2)%mod;
printf("%lld",ans);
return 0;}
T3:
这道题目本来都快要做出来了，我是用set的。。
但是结果由于set太烦，迭代器不好用，所以就没写下去。。
这道题主要是一个逆向思维的贪心：
1.将两个零合并，不合并非零数（因为这样就会减得慢）
2.其他数减一
就这样过了。。
code:
using namespace std;
int n,x,ans,ma,a[1000010],cnt;
int main(){
freopen("multiset.in","r",stdin);
freopen("multiset.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
a[x]++;
ma=max(ma,x);
}
cnt=a[0];
for(int i=1;i<=ma;i++)cnt=(cnt+1)/2+a[i];
ans=ma;
while(cnt>1){cnt=(cnt+1)/2;ans++;}
printf("%d",ans);
return 0;}
T4：
这道题主要难点在于想到数位DP。。
再加上题意的确是不太明确啊。。
所以干脆就乱搞一下，结果就0分
最后听了课之后，勉强敲了下来，但是感觉没有完全消化掉。。过会再消化吧。。
code:
using namespace std;
int n,a[100010],b[100010];
long long f[100010][2];
char s[100010];
void read(int &x){
char ch=getchar();
int f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x*=f;}
int main(){
freopen("maximum.in","r",stdin);
freopen("maximum.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)read(a[i]);
scanf("%s",s+1);
assert(strlen(s+1)==n);
for(int i=1;i<=strlen(s+1);i++)b[i]=s[i]-'0';
for(int i=1;i<=n;i++)
for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++)
f[i][k<b[i]||(k==b[i]&&j)]=max(f[i-1][j]+1LL*k*a[i],f[i][k<b[i]||(k==b[i]&&j)]);
printf("%lld",f[n][1]);
return 0;}
T5：
这道题看到“最大值最小”的时候，就想到应该是用二分，但是这么强的DP着实没有想到啊。。
首先二分出答案，check一下mid，主要就是这个check函数特别难想到DP上去。。
状态转移方程：
if abs a[i]-a[j]<=mid*(i-j) f[i]=max(f[i],f[j]+1);
这里的mid*(i-j)是指区间每两个数的差值之绝对值不超过mid，那么乘以区间长度就行了
code:
using namespace std;
long long l,r,n,k,a[1010],f[1010],ans=1e9;
bool check(long long x){
long long cnt=0;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++)
if((long long)abs(a[i]-a[j])<=(long long)x*(i-j)) f[i]=max(f[i],f[j]+1);
}
for(int i=1;i<=n;i++)cnt=max(cnt,f[i]);
return n-cnt<=k;}
int main(){
freopen("minimum.in","r",stdin);
freopen("minimum.out","w",stdout);
scanf("%lld%lld",&n,&k);
int num=0;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
r=1e9+1;l=-1;
while(l+1<r){
long long mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid;
}
printf("%lld",r);
return 0;}
T6:
这题我只会30分做法，就是记录前缀和cnt[i],表示前i个字符中A的数量（或者B的数量）；
到时候只需要枚举l~r这段区间，然后记录答案就行了。。复杂度O(q*n^2);
code:
using namespace std;
int n,x,y,q,l,r,cnt[100010],cnt1[100010];
char s[100010];
void read(int &x){
x=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
read(n);read(x);read(y);
x/=__gcd(x,y);y/=__gcd(x,y);
for(int i=1;i<=n;i++){
s[i]=getchar();
cnt[i]=cnt[i-1];
cnt1[i]=cnt1[i-1];
if(s[i]=='A') cnt[i]++;
else cnt1[i]++;
//cout<<s[i]<<endl;
}
scanf("%d",&q);
while(q--){
scanf("%d%d",&l,&r);
int ans=0;
for(int i=l;i<=r;i++)
for(int j=i;j<=r;j++){
int xt=cnt[j]-cnt[i-1],yt=cnt1[j]-cnt1[i-1];
int d=__gcd(xt,yt);
xt/=__gcd(xt,yt);yt/=d;
if(xt==x&&yt==y) ans=max(ans,j-i+1);
}
printf("%d\n",ans);
}
//for(int i=1;i<=n;i++)printf("%d %d\n",cnt[i],cnt1[i]);
return 0;}
