Contest Link Official Editorial
构造一个只包含 a ，b ，c 的长度为 \(n\) 的字符串，使得最长回文子串长度不超过 \(k\) .
赛时看错了，以为是最长回文子串长度为 \(k\) ，还恰好构造了一个（虽然这样也能过）……后来发现是不超过，那没事了。
//Author: RingweEH
int main()
{
int T=read();
while ( T-- )
{
int n=read(),k=read();
for ( int i=1; i<=k; i++ )
printf( "a" );
char ch=‘b‘;
for ( int i=1; i<=(n-k); i++ )
{
printf( "%c",ch ); ch=ch+1;
if ( ch==‘d‘ ) ch=‘a‘;
}
printf( "\n" );
}
}
给定一个只包含 * 和 . 的矩阵，求其中有多少 * 组成的 spruce. \(n,m\leq 500\) .
标准长这样（反正就是每一层都比上一层两边多一个，至于多少层并不关心，也就是一个 \(k\) 层能被算 \(k\) 次）：
预处理出 \(sum[i][j]\) 表示从第 \(i\) 行第 \(j\) 个格子开始，能往右拓展多少个为 * 的格子。
直接暴力枚举最上面一个，然后暴力往下拓展，\(\mathcal{O}(1)\) 算这一行往右的格子够不够（然后判掉越界的）。
复杂度讲道理应该是 \(\mathcal{O}(n^2m)\) 的，但是跑不满。（注意预处理 \(sum\) 的写法并不是 \(\mathcal{O}(nm^2)\) 的，后面的循环也显然不可能到这个上界）
//Author: RingweEH
const int N=510;
int n,m,sum[N][N],a[N][N];
char s[N][N];
int main()
{
int T=read();
while ( T-- )
{
n=read(); m=read();
for ( int i=1; i<=n; i++ )
{
scanf( "%s",s[i] );
for ( int j=1; j<=m; j++ )
a[i][j]=(s[i][j-1]==‘*‘);
sum[i][0]=0;
for ( int j=1; j<=m; j++ )
{
if ( sum[i][j-1]>0 ) { sum[i][j]=sum[i][j-1]-1; continue; }
sum[i][j]=0;
for ( int k=j; k<=m; k++ )
if ( a[i][k] ) sum[i][j]++;
else break;
}
}
ll ans=0;
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=m; j++ )
{
int cnt=1,now=1;
while ( 1 )
{
int l=j-now/2,r=j+now/2;
//printf( "i=%d j=%d l=%d r=%d sum=%d\n",i,j,l,r,sum[i][l] );
if ( l<=0 || r>m || (i+cnt-1)>n ) break;
if ( sum[i+cnt-1][l]<now ) break;
cnt++; now+=2;
}
cnt--; ans+=cnt;
}
printf( "%lld\n",ans );
}
return 0;
}
给定一个长度为 \(n\) 的排列 \(a\) ，给出 \(m\) 次操作，每次操作如下：
求做完之后序列升序的概率。
思路其实很简单。但是有个地方让我一直 Wa on test2 ……就离谱。
设最开始 \([las,n]\) 的数字都是已经就位的。那么只要任意一个 \(r_i\ge las-1\) 的操作被执行了，最后就一定是有序的，反之则一定不行。直接计算出这样的 \((1-r_i)\) 的乘积，最后用 1 减去即可，特判一开始就有序的情况。
但是……这道题是多测！我当时在读入了 \(a\) 数组之后就直接特判 并且 continue 了，完全没想到后面没读入完会造成下一个 Case 原地爆炸，而题面样例中升序的又恰好是最后一个 Case ……我当场暴毙。
//Author: RingweEH
const int N=1e5+10;
struct node
{
int pos; double pro;
}b[N];
int n,m,a[N];
int main()
{
int T=read();
while ( T-- )
{
n=read(); m=read();
for ( int i=1; i<=n; i++ )
a[i]=read();
for ( int i=1; i<=m; i++ )
b[i].pos=read(),scanf( "%lf",&b[i].pro );
int las=0;
for ( int i=n; i>=1; i-- )
if ( a[i]!=i ) { las=i+1; break; }
double ans=1.0;
for ( int i=1; i<=m; i++ )
if ( b[i].pos>=(las-1) ) ans=ans*(1.0-b[i].pro);
if ( las==0 ) { printf( "1.000000\n" ); continue; }
printf( "%.6lf\n",1.0-ans );
}
}
给定一个长为 \(n\) 的序列 \(a\) 和 \(m\) 个询问 \(s_i\) .你可以进行若干次操作，每次如下：
每次询问，问经过若干次操作，是否能使序列和为 \(s_i\) .
显然序列的顺序没有任何关系，所以可以在开始的时候先排序。然后预处理出前缀和 \(sum\) 和 \(pos[i]\) ，表示 \(\leq i\) 的数列的 \(endpos\) .
然后就可以直接模拟了。每次类似分治地递归 \(mid\) 两边即可，由于顺序不会改变，所以复杂度是 \(\mathcal{O}(\log n)\) 的。将过程中产生的所有结果放到一个 unordered_set 里面，对于每个询问直接 count 即可。
我还是第一次知道 Codeforces 交文件居然不能带中文注释的……
//Author: RingweEH
const int N=1e6+10;
int n,m,a[N],pos[N];
ll sum[N];
unordered_set<ll> s;
void solve( int l,int r )
{
s.insert( sum[r]-sum[l-1] );
if ( l>=r ) return;
int mid=(a[l]+a[r])>>1;
if ( pos[mid]+1>r ) return;
solve( l,pos[mid] ); solve( pos[mid]+1,r );
}
int main()
{
int T=read();
while ( T-- )
{
n=read(); m=read();
for ( int i=1; i<=n; i++ )
a[i]=read();
sort( a+1,a+1+n ); sum[0]=0;
for ( int i=1; i<=n; i++ )
sum[i]=sum[i-1]+a[i];
s.clear();
for ( int i=a[1]; i<=a[n]; i++ )
pos[i]=0;
for ( int i=1; i<=n; i++ )
pos[a[i]]=i;
for ( int i=a[1]; i<=a[n]; i++ )
if ( !pos[i] ) pos[i]=pos[i-1];
solve( 1,n );
while ( m-- )
puts( s.count(read()) ? "Yes" : "No" );
}
}
有一个水池，初始有 \(k\) 的水位，现在希望将每天的水位控制在 \([l,r]\) 之间。每一天：
问能否在 \(t(t\leq 1e18)\) 天内保持这个水位。
如果有 \(y\leq x\) ，那么显然水会不断减少，只需要计算原水位是否合法，以及是否够 \(t\) 天消耗即可。
现在来考虑不满足的情况。
显然，每一次会尽可能让水减到最少，然后再增加 \(y\) .但是如果直接模拟的话，这个数据范围显然会炸。那就找循环节。如果某一次被减少到了 \(k\bmod x\) ，那么后面的东西都进入了循环，这个过程一定可以重复下去。
看上去很简单的思路对吧。但是实现上细节很多：
long long .//Author: RingweEH
ll k,l,r,t,x,y;
bool vis[1000010];
int main()
{
k=read(); l=read(); r=read(); t=read(); x=read(); y=read();
if ( k<l || k>r ) { printf( "No\n" ); return 0; }
if ( x>=y )
{
if ( k+y>r ) k-=x,t--;
else k+=y;
if ( k<l ) { printf( "No\n" ); return 0; }
if ( !t ) { printf( "Yes\n" ); return 0; }
if ( (x-y)<=(k-l)/t ) printf( "Yes\n" );
else printf( "No\n" );
return 0;
}
k-=l; r-=l; ll sum=0;
if ( k+y<=r ) k+=y;
while ( 1 )
{
if ( vis[k%x] ) { printf( "Yes\n" ); return 0; }
vis[k%x]=1; ll cnt=k/x; sum+=cnt; k-=cnt*x;
if ( sum>=t ) { printf( "Yes\n" ); return 0; }
cnt=(r-k)/y;
if ( cnt==0 ) { printf( "No\n" ); return 0; }
k+=cnt*y;
}
return 0;
}
给定 \(n-1\) 个数和若干允许使用的运算符（保证只有 +-* ），在其中插入 \(n-1\) 个使得最后的结果最大。
我先胡一个大型分讨（
+* ，0/1 两边是 + ，其余是 *+- ，全 +-* ，如果有 0 的话找到第一个 0 ，在其前面是 - ，其他全部是 * ；如果没有，那么全 *+ ，其余都是 *不知道对不对……
好极了，被 Hack 了。数据如下（ WA on test 9 ）
Input
10
2 1 1 2 1 2 1 2 1 2
+*
Answer
2*1*1*2*1*2*1*2*1*2
其实就是，在 +* 和 +-* 的地方出了点问题，改成 DP 就好了。
//Author: RingweEH
const int N=1e5+10;
const ll inf=1e10;
int n,a[N],num[N],tot,pre[N];
ll sum[N],f[N];
bool opt[N],add,del,tim;
char s[5];
ll minn( ll x )
{
return min( x,inf );
}
ll calc( int i,int j )
{
return sum[num[j]]/sum[num[i]]+f[i]+num[i+1]-num[i]-1;
}
void solve( int l,int r )
{
if ( l>r ) return;
sum[l-1]=1;
for ( int i=l; i<=r; i++ )
sum[i]=minn( a[i]*sum[i-1] );
if ( sum[r]>=inf )
{
for ( int i=l; i<=r && a[i]==1; i++ )
opt[i+1]=1;
for ( int i=r; i>=l && a[i]==1; i-- )
opt[i]=1;
return;
}
tot=0;
for ( int i=l; i<=r; i++ )
if ( a[i]>1 ) num[++tot]=i;
for ( int i=l; i<=r; i++ )
opt[i]=1;
num[0]=l-1; f[0]=0;
for ( int i=1; i<=tot; i++ )
{
int mi=0;
for ( int j=1; j<i; j++ )
if ( calc( mi,i )<calc( j,i ) ) mi=j;
f[i]=calc( mi,i ); pre[i]=mi;
}
for ( int i=tot; i; i=pre[i] )
for ( int j=num[i]; j>num[pre[i]+1]; j-- )
opt[j]=0;
}
int main()
{
n=read();
for ( int i=1; i<=n; i++ )
a[i]=read();
scanf( "%s",s );
int len=strlen( s );
if ( len==1 )
{
printf( "%d",a[1] );
for ( int i=2; i<=n; i++ )
printf( "%c%d",s[0],a[i] );
return 0;
}
for ( int i=0; i<len; i++ )
if ( s[i]==‘+‘ ) add=1;
else if ( s[i]==‘-‘ ) del=1;
else tim=1;
if ( !add )
{
printf( "%d",a[1] );
for ( int i=2; i<=n; i++ )
printf( "%c%d",(a[i]==0 ? ‘-‘ : ‘*‘),a[i] );
return 0;
}
if ( !tim )
{
printf( "%d",a[1] );
for ( int i=2; i<=n; i++ )
printf( "%c%d",‘+‘,a[i] );
return 0;
}
//-----------------------
opt[1]=1;
for ( int i=1,las=0; i<=n+1; i++ )
if ( a[i]==0 )
{
opt[i]=opt[i+1]=1;
solve( las+1,i-1 ); las=i;
}
//---------------------
printf( "%d",a[1] );
for ( int i=2; i<=n; i++ )
printf( "%c%d",(opt[i]==0 ? ‘*‘ : ‘+‘),a[i] );
}
原文：https://www.cnblogs.com/UntitledCpp/p/14128888.html