滨海新区建设和交通局网站,做中医诊所网站,网站网页制作的公司,怎么做网站卖车A. New Palindrome 要求#xff1a;对于一个回文串#xff0c;判断是否可以转换为其他回文串 思路#xff1a;如果回文串的前一半存在不相同的字符#xff0c;就可以转换
#includebits/stdc.h
using namespace std;int n;
string s;void solve(){cins;boo…A. New Palindrome 要求对于一个回文串判断是否可以转换为其他回文串 思路如果回文串的前一半存在不相同的字符就可以转换
#includebits/stdc.h
using namespace std;int n;
string s;void solve(){cins;bool f0;for(int i0;is.size()/2-1;i){if(s[i]!s[i1]){coutYES\n;ftrue;break;}}if(!f)coutNO\n;
} int main()
{cinn;while(n--)solve();
}
B. Maximum Sum 要求给出一个序列通过q次操作 总和减去最小值次小值或 最大值得到最大的序列和 刚开始想要贪心如果最小值次小值最大值就减最大值否则减最小值次小值之后发现子序列
6 2
15 22 12 10 13 11
不能满足情况贪心时为tot-1011-22但实际应该为tot-22-15
所以用了两个前缀和来存储减小值的总和和减大值的总和之后遍历一下得到最大值
#includebits/stdc.h
using namespace std;int t;
long long f[200001],ff[200001],a[200001];
/*
1操作选取最小值和次小值
2操作选取最大值
f[i]选取i次1操作时的删减值
ff[i]选取i次2操作时的删减值
*/void solve(){int n,q;long long tot0;cinnq;for(int i1;in;i)cina[i],tota[i];sort(a1,a1n);//排序for(int i2;in;i2)f[i1]a[i-1]a[i]f[(i1)-1];for(int i1;in;i)ff[i]ff[i-1]a[n-i1];long long mi1e18;for(int i0;iq;i)mimin(mi,f[i]ff[q-i]);//找出最小的i次1操作和q-i次2操作的删减值couttot-mi\n;
}int main()
{cint;while(t--)solve();
}
C. Contrast Value 要求求出a最短的子序列b满足a的对比值b的对比值 分析分析一下几个情况就能理清思路 情况11 2 3 5 6
要看到 2-13-2是等于3-1的即对比值为6-1所以最短为2而如果序列为递减序列也是这种情况
情况21 1 1 1 1
很明显对比值为0所以应该最短为1
情况31 2 3 2 1
可以将这种情况看成递增递减序列的组合所以最短为3
那么思路就出来了 遍历一下看序列的变化性递增\递减若变化性变化长度1
#includebits/stdc.h
using namespace std;int T;
int n;
int a[300001];void solve() {cinn;for(int i1; in; i)cina[i];int f0;//用表示单调性-1递减1递增 0等值序列int ans1;for(int i1; in; i) {if(f0) {if(a[i]a[i1])f-1;else if(a[i]a[i1])f1;//决定初始单调性} else {if(f1) {if(a[i]a[i1]) {f-1;ans;}//转变单调性} else {if(a[i]a[i1]) {f1;ans;}//转变单调性}}}if(f)ans;//f不为0时需要在多选取序列最后一个数coutans\n;
}int main() {cinT;while(T--)solve();return 0;
}
