营销型网站管理方案,扬州西区网站建设,有限公司与有限责任公司的区别,wordpress标题优化A. Was there an Array?
翻译#xff1a; 对于整数数组 #xff0c;我们将其相等特征定义为数组 #xff0c;其中#xff0c;如果数组 a 的第 i 个元素等于其两个相邻元素#xff0c;则 #xff1b;如果数组 a 的第 i 个元素不等于其至少一个相邻元素#xff0c;则 … A. Was there an Array?
翻译 对于整数数组 我们将其相等特征定义为数组 其中如果数组 a 的第 i 个元素等于其两个相邻元素则 如果数组 a 的第 i 个元素不等于其至少一个相邻元素则 。 例如对于数组 [1,2,2,2,3,3,4,4,4]相等特征为 [0,1,0,0,0,0,1,1]。 给你数组 。你的任务是确定是否存在这样一个数组 a具有相同特征。 思路 如果b存在101则错误。 实现 #includebits/stdc.h
using namespace std;
using ll long long;void solve(){int n; cinn;vectorintb(n-2);for (int i0;in-2;i) cinb[i];if (n4){coutYESendl;}else{for (int i0;in-4;i){if (b[i]1 b[i1]0 b[i2]1){coutNOendl;return;}}coutYESendl;}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// coutfixed;// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();
} B. Set of Strangers 翻译 给你一张 n 行 m 列的表格。最初第 i 行第 j 列的单元格的颜色为 。 如果两个单元格不共用一条边那么这两个单元格就是陌生人。陌生人可以用角接触。 如果单元格集合中的所有单元格对都是陌生人我们就说这个单元格集合是陌生人集合。根据定义不超过一个单元格的集合就是陌生人集合。 在一个步骤中你可以选择任意一个陌生人集合使其中的所有单元格都具有相同的颜色然后给所有单元格涂上其他颜色。你可以选择得到的颜色。 要使整个表格的颜色相同最少需要多少步 思路 对于所有相同颜色的块如果存在相邻的块则要2次操作使所有块变为同一颜色否则只用1次操作。 得到所有颜色的变换操作数再减去所有颜色转换操作数中的最大值。 实现 #includebits/stdc.h
using namespace std;
using ll long long;
vectorvectorint direct {{0,1},{0,-1},{1,0},{-1,0}};
void solve(){int n,m; cinnm;vectorint cnts(n*m1,0);vectorvectorint graph(n2,vectorint(m2,0));for (int i1;in;i){for (int j1;jm;j){cingraph[i][j];}}int mx 0,summ 0;for (int i1;in;i){for (int j1;jm;j){int f 0;for (auto d:direct){if (graph[i][j]graph[id[0]][jd[1]]){f 1;break;}}cnts[graph[i][j]] max(1f,cnts[graph[i][j]]);}}for (int i1;in*m;i){summcnts[i];mx max(mx,cnts[i]);}coutsumm-mxendl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// coutfixed;// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();
} C. Beautiful Sequence 翻译 如果下列条件成立我们就称一个整数序列为优美序列 它的长度至少为 3除第一个元素外每个元素的左边都有一个比它小的元素除最后一个元素外每个元素的右边都有一个比它大的元素 例如[1,4,2,4,7] 和 [1,2,4,8] 很美但 [1,2]、[2,2,4] 和 [1,3,5,3] 却不美。 回想一下子序列是指在不改变其余元素顺序的情况下通过删除某些元素可以从另一个序列得到的序列。 给你一个大小为 n 的整数数组 a其中每个元素都是从 1 到 3。你的任务是计算数组 a 的优美子序列的个数。 思路 按照条件优美序列为122...23。求满足条件的序列数量。使用dp状态机。 dfs( i , k ) 为[ : i ]中以k为结尾的序列数量。 递推公式 dfs( i , k) dfs( i-1 , k); 当k3时如果a[i]3则当前3与前面的2结尾数字匹配 dfs(i , k)dfs(i-1 , 2) 当k2时如果a[i]2则当前2与前面的1或2结尾数字匹配 dfs(i , k) dfs(i-1 , 1) 当k1时如果a[i]11开头的数量1 dfs( i , k ) 边界条件 if (i0) return 0; 实现 #includebits/stdc.h
using namespace std;
using ll long long;
const ll mod 998244353;
void solve(){ll n; cinn;vectorll a(n);for (ll i0;in;i) cina[i];vectorvectorll memo(n,vectorll(4,-1));// dp状态机[:i] 中以 k 结尾的 子串数量auto dfs [](auto dfs,ll i,ll k)-ll{if (i0) return 0;ll res memo[i][k];if (res!-1) return res;res dfs(dfs,i-1,k);if (k3 a[i]3){res (resdfs(dfs,i-1,2))%mod;}else if (k2 a[i]2){res (resdfs(dfs,i-1,2)dfs(dfs,i-1,1))%mod;}else if (k1 a[i]1){res 1;}return res;};coutdfs(dfs,n-1,3)endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// coutfixed;// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();
} D. Palindrome Shuffle 翻译 给你一个由小写拉丁字母组成的字符串 s。 您可以对字符串 s 执行以下操作选择 s 的一个连续子串可能为空然后将其洗码按您的意愿重新排列子串中的字符。 回顾一下回文字符串是指从第一个字符到最后一个字符以及从最后一个字符到第一个字符的读法相同的字符串。例如字符串 a、bab、acca、bcabcbacb 是回文字符串但字符串 ab、abbbaa、ccbb 不是回文字符串。 您的任务是确定子串的最小可能长度必须在该子串上执行上述操作才能将给定的字符串 s 转换成一个回文字符串。 思路 向左右指针去除左右边界相同的字符剩余的部分 s 为由左端点开始重排或从右端点开始重排。对 s 进行中心扩展得到其最大的回文如果回文的左剩余与右剩余部分进行重排后相同则则对这些剩余部分进行重排即可。否则要重拍的部分必定在一半s以上记录 s 的每种字符的位置比较每种字符要重排的最大位置。 实现 #include bits/stdc.h
using namespace std;int main () {ios_base::sync_with_stdio(0); cin.tie(0);int T;cin T;while (T--) {string s;cin s;int n s.size();int l 0, r n-1;while (l r s[l] s[r]) {l;r--;}if (l r) {cout 0\n;continue;}s s.substr(l, r-l1);n s.size();l n/2-1, r n/2;while (l 0 s[l] s[r]) {l--;r;}string L s.substr(0, l1);string R s.substr(r);sort(L.begin(), L.end());sort(R.begin(), R.end());if (L R) {cout l1 \n;continue;}int ans n;for (int _ 0; _ 2; _) {vectorvectorint pos(26);int res 0;for (int i 0; i n; i) {pos[s[i]-a].push_back(i);}for (vectorint v: pos) {if (v.empty()) continue;res max(res, v[(int)v.size()/2-1]1);}ans min(ans, res);reverse(s.begin(), s.end());}cout ans \n;}
}有建议可以评论我会积极改进qwq。
