题意：给出两个字符串，求出一个尽量长的序列使得有不超过p%的x满足Ax!=Bx
思路：首先明确条件是
(i-j)*p>=(sum[i]-sum[j])*100 => i*p-sum[i]*100 >= j*p-sum[j]*100,
sum[i]表示前i个的不相等的个数,然后就是构造一个单调递减队列，储存结果,然后二分找出最小的j，第一个入队列的是一定是<0,否则就是整个都可以
#include#include #include #include #include using namespace std; const int MAXN = 150010; char s1[MAXN],s2[MAXN]; int sum[MAXN]; int n,p; vector q; int idx[MAXN]; int main(){ while (scanf("%d%d",&n,&p) != EOF && n+p){ scanf("%s%s",s1+1,s2+1); sum[0] = 0; q.clear(); q.push_back(0); idx[0] = 0; int ans = 0; for (int i = 1; i <= n; i++){ sum[i] = sum[i-1] + (s1[i] != s2[i]); int t = q.size() - 1; if (i*p-sum[i]*100 < q[t]){ q.push_back(i*p-sum[i]*100); idx[q.size()-1] = i; } int l = 0,r = q.size() - 1; int temp = i*p-sum[i]*100; while (l < r){ int mid = (l+r) >> 1; if (temp >= q[mid]) r = mid; else l = mid+1; } ans = max(ans,i-idx[l]); } if (ans) printf("%d\n",ans); else printf("No solution.\n"); } return 0; }