前言
上橙了，可喜可贺qwq。
A - String Generation
题目大意
构造一个长度为 (n) 且只有 (a,b,c) 三种字符的字符串，使得最长回文子串长度不超过 (k)。
解题思路
显然 (abcabcabc...) 构造的字符串最长回文子串一定是 (1)。
Code
int t,n,k;
signed main()
{
t=read();
while(t--)
{
n=read();k=read();
for(int i=1;i<=n;++i)
printf("%c",i%3==1?'a':(i%3==2?'b':'c'));
printf("
");
}
return 0;
}
B - Find the Spruce
题目大意
求出矩阵中有多少个高度任意的金字塔
解题思路
(n le 500)
直接枚举矩阵位置，然后再枚举高度，前缀和判断是否合法。
注意边界的处理。
Code
const int N=505;
int t,n,m,sum[N][N],ans;
char mp[N][N];
signed main()
{
t=read();
while(t--)
{
n=read();m=read();
for(int i=1;i<=n;++i)
scanf("%s",mp[i]+1);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
sum[i][j]=sum[i][j-1]+(mp[i][j]=='*');
ans=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=1;k<=n-i+1&&j+k-1<=m&&j-k+1>=1;++k)
if(sum[i+k-1][j+k-1]-sum[i+k-1][j-k]==(k-1)*2+1)
ans++;
else break;
printf("%lld
",ans);
}
return 0;
}
C - Random Events
题目大意
给一个排列，有 (m) 种操作，第 (i) 种操作会将排列的前 (a_i) 个数排序，有 (p_i) 的概率发生，求序列最终有序的概率。
解题思路
设 (p) 为满足 (p+1 sim n) 这段有序的最小值，(x) 为排列有序的概率，(y) 为排列无序的概率。
那么显然若 (1 le a_i le p-1)，那么这个操作肯定没用。而如果 (p le a_i le n)，那么一次操作就能让这个排列有序。
所以
注意要特判下排列本身就有序的情况。
Code
const int N=1e5+5;
int t,n,m,a[N],mmax;
double ans;
signed main()
{
t=read();
while(t--)
{
n=read();m=read();
mmax=0;ans=1;
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=n;i>=1;--i)
if(a[i]!=i)
{
mmax=i;
break;
}
for(int i=1;i<=m;++i)
{
int x=read();
double y;
scanf("%lf",&y);
if(x>=mmax) ans*=(1-y);
}
if(mmax==0)
{
printf("1
");
continue;
}
printf("%.6lf
",1-ans);
}
return 0;
}
D - Divide and Summarize
题目大意
给一个序列 (a) ，设 (mid=dfrac{max{a_i} + min{a_i}}{2})，则每次可以丢掉大于 (mid) 的数或小于等于 (mid) 的数。
有 (q) 次询问，每次回答能否通过对 (a) 操作来使得 (a) 中所有数的和等于某个数。
解题思路
显然序列 (a) 种元素的顺序不会影响答案，所以可以先排序，这样不论怎么丢，剩下的数都是一个区间。
接下来直接模拟即可，处理出所有情况，查找小于或大于每个数可以用二分来实现。
Code
const int N=1e5+5;
int t,n,q,a[N],sum[N];
map<int,int> mp;
inline void binary(int l,int r);
inline int bin(int l,int r,int x);
signed main()
{
t=read();
while(t--)
{
n=read();q=read();
mp.clear();
for(int i=1;i<=n;++i)
a[i]=read();
sort(a+1,a+1+n);
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+a[i];
binary(1,n);
while(q--)
{
int x=read();
if(mp[x]) printf("Yes
");
else printf("No
");
}
}
return 0;
}
inline void binary(int l,int r)
{
if(l>r) return;
int mid=(a[l]+a[r])>>1;
mp[sum[r]-sum[l-1]]=1;
if(l==r) return;
int pos=bin(l,r,mid);
if(pos!=r) binary(l,pos);
binary(pos+1,r);
}
inline int bin(int l,int r,int x)
{
int res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[mid]<=x)
{
res=mid;
l=mid+1;
}
else r=mid-1;
}
return res;
}
E - Water Level
题目大意
有一个数 (k)，必须时刻保持这个数在 ([l,r]) 中。
现在有 (t) 天，每天 (k) 都会减少 (x)，但每天开始前可以选择将 (k) 加上 (y)。
问能否保证 (k) 始终在 ([l,r]) 中的条件下度过这 (t) 天。
(1 le l,k,r,t,y le 10^{18},1 le x le 10^6)
解题思路
观察到这几个数中唯一小到可以枚举的只有 (x) ，因此考虑把复杂度转移到 (x) 上。
我们分两种情况讨论：
如果 (y < x)，你么每天肯定都要加，而每天都加这个数每天也会减少 (x-y)，因此看看能否减少 (t) 天即可。
而如果 (y ge x)，就会有点麻烦了。
一个显然的结论是，只在 (k) 减去 (x) 后会小于 (l) 的那天加 (y) 是最优的。
因为 (y>x)，所以加完后一定可以保证减去 (x) 后的数仍大于 (l)。
因此可以求出每一个减去 (x) 后小于 (l) 要过多少天，然后加上 (y) ，不断循环。
当出现下面这种情况时，一定不能完成：
(spacespacespacespacespace1.) (k) 不能再减 (x)，但是一旦加上 (y) 就会大于 (r)
而如果出现以下两种情况，那么一定能完成：
(spacespacespacespacespace1.) 天数超过 (t)
(spacespacespacespacespace2.) 当前的这个 (k) 在之前出现过（即出现了一个循环）
因为不能在减少 (x) 的 (k) 一共只有 (x) 个，这就保证了程序一定在 (x) 次运算内结束，因此复杂度为 ( ext{O}(x))。
Code
const int N=1e6+5;
int k,l,r,t,x,y,fl=1,vis[N];
signed main()
{
k=read();l=read();r=read();t=read();x=read();y=read();
if(y<x)
{
int now=0;
while(k+y>r&&now<t) k-=x,now++;
if((k-l)/(x-y)>=t-now) printf("Yes
");
else printf("No
");
return 0;
}
int now=(k-l)/x;
k-=now*x;
while(now<t)
{
if(vis[k-l])
break;
vis[k-l]=1;
if(k+y>r)
{
printf("No
");
return 0;
}
k+=y;
int tmp=(k-l)/x;
now+=tmp;
if(now>=t) break;
k-=tmp*x;
}
printf("Yes
");
return 0;
}