品牌网站建设 蝌4蚪小,东莞seo建站广告,温州网站搭建公司,wordpress 加速A. Flip Flop Sum给出一个只有1和-1的数组#xff0c;修改一对相邻的数#xff0c;将它们变为对应的相反数#xff0c;修改完后数组的和最大是多少。思路#xff1a;最优的情况是修改一对-1#xff0c;其次是一个1一个-1#xff0c;否则修改两个1。AC Code#xff1a;#i…A. Flip Flop Sum给出一个只有1和-1的数组修改一对相邻的数将它们变为对应的相反数修改完后数组的和最大是多少。思路最优的情况是修改一对-1其次是一个1一个-1否则修改两个1。AC Code#include bits/stdc.htypedef long long ll;
const int N 1e5 5;
int t, n;
int a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n;for(int i 1; i n; i ) {std::cin a[i];}bool flag false;int ans 0;for(int i 1; i n; i ) {if(a[i] -1 a[i 1] -1) {a[i] 1, a[i 1] 1;flag true;break;}}if(flag) {for(int i 1; i n; i ) {ans a[i];}std::cout ans \n;continue;}for(int i 1; i n; i ) {if(a[i] a[i 1] 0) {flag true;break;}}if(flag) {for(int i 1; i n; i ) {ans a[i];}std::cout ans \n;continue;}a[1] -a[1], a[2] -a[2];for(int i 1; i n; i ) {ans a[i];}std::cout ans \n;}return 0;
}B. The Forbidden Permutation给出一个permutation p给出一个数组a和一个数字d定义pos(a[i]) x (a[i] - p[x])定义一个not good数组满足pos(a[i]) pos(a[i 1]) pos(a[i]) d每次修改可以选择p内两个相邻的数交换两数位置。求想要达到一个good数组最少需要修改几次。 思路贪心求解即可。对于满足条件的相邻两数不需要操作对于不满足条件的两个数可以有两种修改操作1两数位置交换2移动两数使得距离大于等于d每次在满足条件的情况下采用最小值即可。AC Code#include bits/stdc.htypedef long long ll;
const int N 1e5 5;
int t, n, m, d;
int a[N], p[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n m d;d ;std::mapint, int mp;for(int i 1; i n; i ) {std::cin p[i];mp[p[i]] i;}for(int i 1; i m; i ) {std::cin a[i];}int ans n;for(int i 2; i m; i ) {int fir mp[a[i - 1]];int sec mp[a[i]];if(fir sec) ans std::min(0, ans);else {int cnt std::max(0, (d - (sec - fir)));if(fir - 1 n - sec cnt)ans std::min(ans, cnt);ans std::min(ans, sec - fir);}}std::cout ans \n;}return 0;
}C. Flexible String给出长度为n的两个字符串a和b对a进行修改每次可以将其中一个字符替换为任意的字符最多修改k种不同的字符问修改完后最多有多少区间[l, r]满足a[l, r] b[l, r]。思路因为a中最多有10中字符可以想到采用二进制枚举枚举修改k种字符然后对于修改的区间计算即可具体细节看代码。AC Code#include bits/stdc.htypedef long long ll;
#define int long long
const int N 1e5 5;
int t, n, k;
std::string a, b;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n k;std::cin a b;a a, b b;std::mapchar, int mp;int cnt 0;for(int i 1; i n; i ) {if(!mp[a[i]])mp[a[i]] cnt;}int ans 0;for(int o 0; o (1 cnt); o ) {int cnt1 __builtin_popcount(o);if(cnt1 k) continue;int res 0;for(int i 1; i n; i ) {int j i;while(j n (a[j] b[j] || mp[a[j]] (o (mp[a[j]] - 1) 1)))j ;res (j - i) * (j - i 1) / 2;i j;}ans std::max(res, ans);}std::cout ans \n;}return 0;
}os距离1600还差点啊这个二进制枚举没想到QAQD. Flexible String Revisit给出a和b两个01串随机修改a中的0和1为相反的数问使得a等于b的期望修改次数是多少。思路严格鸽AC Code#include bits/stdc.htypedef long long ll;
const int mod 998244353;
const int N 1e6 5;
int t, n;
std::string a, b;struct ModInt {int MD mod;int x;ModInt(ll x 0) : x(x % MD) {}int get() { return x; }ModInt operator (const ModInt that) const { int x0 x that.x; return ModInt(x0 MD ? x0 : x0 - MD); }ModInt operator - (const ModInt that) const { int x0 x - that.x; return ModInt(x0 MD ? x0 MD : x0); }ModInt operator * (const ModInt that) const { return ModInt((long long)x * that.x % MD); }ModInt operator / (const ModInt that) const { return *this * that.inverse(); }void operator (const ModInt that) { x that.x; if (x MD) x - MD; }void operator - (const ModInt that) { x - that.x; if (x 0) x MD; }void operator * (const ModInt that) { x (long long)x * that.x % MD; }void operator / (const ModInt that) { *this *this / that; }ModInt inverse() const {int a x, b MD, u 1, v 0;while(b) {int t a / b;a - t * b; std::swap(a, b);u - t * v; std::swap(u, v);}if(u 0) u MD;return u;}
};using mint ModInt;struct node {mint a, b;
} f[N];node operator (node L, node R) {return {L.a R.a, L.b R.b};
}node operator (node L, mint R) {return {L.a, L.b R};
}node operator - (node L, node R) {return {L.a - R.a, L.b - R.b};
}node operator - (node L, mint R) {return {L.a, L.b - R};
}node operator / (node L, mint R) {return {L.a / R, L.b / R};
}node operator * (node L, mint R) {return {L.a * R, L.b * R};
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n a b;int cnt 0;for(int i 0; i n; i ) {cnt (a[i] ! b[i]);}f[0] {0, 0};f[1] {1, 0};for(int i 2; i n; i ) {f[i] (f[i - 1] - mint{1} - f[i - 2] * mint{i - 1} / n) /((mint{n} - (i - 1)) / n);}node xx f[n] - f[n - 1];mint x (mint{1} - xx.b) / xx.a;std::cout (f[cnt].a * x f[cnt].b).get() \n;}return 0;
}os第一次用这个取模板子欸
