asp.net mvc网站开发,有网站地图的网站,百度视频推广怎么收费,南宁网站制作多少钱A-Entertainment in MAC
题意
可以对一个字符串进行两种操作#xff1a;
将字符串反转将该字符串反转后接在原串的后面。
可以进行任意次上述操作#xff0c;获得字典序最小的字符串。
数据范围 t ( 1 ≤ t ≤ 500 ) t(1≤t≤500) t(1≤t≤500) n ( 2 ≤ n ≤ 1 0 9 ) n…A-Entertainment in MAC
题意
可以对一个字符串进行两种操作
将字符串反转将该字符串反转后接在原串的后面。
可以进行任意次上述操作获得字典序最小的字符串。
数据范围 t ( 1 ≤ t ≤ 500 ) t(1≤t≤500) t(1≤t≤500) n ( 2 ≤ n ≤ 1 0 9 ) n(2≤n≤10^9) n(2≤n≤109) s ( 1 ≤ ∣ s ∣ ≤ 100 ) s(1\le |s|\le 100) s(1≤∣s∣≤100)
思路
对比反转前后的字符串字典序大小再决定是操作1还是操作2
参考代码
void solve() {ll n;cin n;string s;cin s;string t s;reverse(t.begin(), t.end());if (s t) {cout t s endl;}else {cout s endl;}
}B-Informatics in MAC
题意 M E X MEX MEX不属于该数组的最小非负整数。
对一个数组分成 k k k个子段要求每段的 M E X MEX MEX都等于相同的数。
找到这样的子段分法或者报告不存在合法的分法。
数据范围 t ( 1 ≤ t ≤ 1 0 4 ) t(1≤t≤10^4) t(1≤t≤104) n ( 2 ≤ n ≤ 1 0 5 ) n(2≤n≤10^5) n(2≤n≤105) a i ( 0 ≤ a i n ) a_i(0\le a_i\lt n) ai(0≤ain)
思路
假设 M E X 2 MEX2 MEX2则分成 k k k段的方式为前 k − 1 k-1 k−1段只要都出现过 0 , 1 0,1 0,1就进行分段最后一段保证含 0 , 1 0,1 0,1和达到第 n n n个数。
确定 M E X MEX MEX遍历数组 a a a找到最小的没有出现过的数该数不大于 n n n该数即为 M E X MEX MEX。
参考代码
// MEX:不属于该数组的最小非负整数void solve() {ll n;cin n;vectorlla(n 1);vectorboolck(n 1, false);for (int i 1;i n;i) {ll x;cin x;a[i] x;ck[x] true;}bool f false;int y -1;for (int i 0;i n;i) {if (ck[i] false) {y i;f true;break;}}if (!f) {cout -1 endl;return;}// MEXy// cout y endl;if (y 0) {cout n endl;for (int i 1;i n;i) {cout i i endl;}return;}int p 1;int cnt 0;vectorpairint, intans;vectorboolhs(y, false);vectorboolhsf(y, false);for (int i 1;i n;i) {if (a[i] y !hs[a[i]]) {hs[a[i]] true;cnt;}if (cnt y) {ans.push_back({ p, i });p i 1;cnt 0;// 会不会Tlehs hsf;}}if (ans.size() 1) {cout -1 endl;return;}cout ans.size() endl;for (int i 0;i ans.size();i) {if (i ! ans.size() - 1)cout ans[i].first ans[i].second endl;else {cout ans[i].first n endl;}}}D-Exam in MAC
题意
有一个集合 s s s。
找到满足 0 ≤ x ≤ y ≤ c 0\le x\le y\le c 0≤x≤y≤c且 x y xy xy和 y − x y-x y−x均不包含在集合 s s s中的整数对 ( x , y ) (x,y) (x,y)的个数。
数据范围 t ( 1 ≤ t ≤ 2 × 1 0 4 ) t(1≤t≤2\times 10^4) t(1≤t≤2×104) n ( 1 ≤ n ≤ 3 × 1 0 5 ) n(1≤n≤3\times 10^5) n(1≤n≤3×105) c ( 1 ≤ c ≤ 1 0 9 ) c(1\le c\le 10^9) c(1≤c≤109)
思路
容斥。
合格的整数对满足 x y ∈ s xy\in s xy∈s满足 y − x ∈ s y-x\in s y−x∈s-既满足 x y ∈ s xy\in s xy∈s又满足 y − x ∈ s y-x\in s y−x∈s。
参考代码
void solve() {ll n, c;cin n c;ll tot (c 1) * (c 2) / 2;ll cnt0 0, cnt1 0;for (ll i 0;i n;i) {ll x;cin x;tot - x / 2 1;tot - c 1 - x;if (x 1)cnt1;else cnt0;}tot (cnt0 1) * cnt0 / 2 cnt1 * (cnt1 1) / 2;cout tot endl;
}
