A - Broken Keyboard
题意：键盘一些键坏了，按一下出俩字，给一个串，判断哪些键没坏。
题解：那肯定是至少有一段连续相同字母区间内的个数为奇数的没坏。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[505];
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t;
scanf("%d", &t);
while(t--) {
scanf("%s", s + 1);
int n = strlen(s + 1);
vector<char> ans;
for(int i = 1; i <= n; ++i) {
int j = i;
while(j + 1 <= n && s[j + 1] == s[i])
++j;
if((j - i + 1) & 1)
ans.push_back(s[i]);
i = j;
}
sort(ans.begin(), ans.end());
ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
for(auto c : ans)
printf("%c", c);
printf("
");
}
}
B - Binary Palindromes
题意：给n个01串，可以在串之间任意交换字符，操作次数不限。求能构造的最多有几个回文串。
题解：一个直观的猜测是答案是n或者n-1（把一个串作为垃圾桶存放多出来的（奇数个的）那个位）。假如是全0或者全1就肯定都是回文串，否则，假如是其中的偶数个发生的翻转，全部丢在一个串的两侧翻转即可。假如是奇数个发生翻转，可以把奇数的那次放在某个奇数长度串的中间。
具体来说，设有a个0，b个1，假设a,b都是偶数，那么全部乱丢一通就可以了。假设a,b一奇一偶，那么把奇的那次丢给一定会出现至少一个的奇数串就可以了。假如a,b两个奇数，那么就判断有多少个奇数串，有两个以上奇数串就n，否则n-1（没有奇数串，必须破坏一个偶数串）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[55];
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
int a = 0, b = 0, c = 0;
for(int j = 1; j <= n; ++j) {
scanf("%s", s + 1);
int l = strlen(s + 1);
c += l & 1;
for(int i = 1; i <= l; ++i) {
if(s[i] == '0')
++a;
else
++b;
}
}
printf("%d
", n - ((a & 1) && (b & 1) && (c == 0)));
}
}
C - Minimize The Integer
题意：给一个数字串，假如两个相邻位置的奇偶不同就可以交换位置，求最小的串，可以有前导零。
题解：看起来就是奇数的顺序保持不变，偶数的顺序保持不变，这两个东西可以互相渗透。看起来像归并排序。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[300005];
queue<char> odd, even;
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t;
scanf("%d", &t);
while(t--) {
scanf("%s", s + 1);
int n = strlen(s + 1);
for(int i = 1; i <= n; ++i) {
if((s[i] - '0') & 1)
odd.push(s[i]);
else
even.push(s[i]);
}
string ans;
while(odd.size() && even.size()) {
if(odd.front() < even.front()) {
ans += odd.front();
odd.pop();
} else {
ans += even.front();
even.pop();
}
}
while(odd.size()) {
ans += odd.front();
odd.pop();
}
while(even.size()) {
ans += even.front();
even.pop();
}
cout << ans << endl;
}
}
D - Salary Changing
题意：给s块钱，n（n是奇数）个人，每个人有个工资区间[l,r]，发不超过s的工资使得中位数最大。
题解：一个简单的思路就是二分中位数m，然后验证填充这个中位数要不要s块钱，l>=m的肯定发l，假设发了a个，那么看看剩下的人有没有办法使得中位数为m，假如可以，则包含中位数m的区间就发m直到使得m为中位数，剩下的发l（所以这一步要按l从大到小贪心）。做法是扫一遍取出包含中位数m的人（按l排序，但可以先验证可行再排），右侧于中位数的人全部发l并统计数量，左侧于中位数的人全部发l，包含中位数的全部发m到中位数恰为m剩下的发l，复杂度两个log。睡醒后发现其实要找的是前k个，直接用nth_element()更快，复杂度一个log（但是实测反而更慢，估计是两个log的算法没有被故意卡或者说经过验证是不能卡的）。
注意：nth_element()的使用，是把nth迭代器传第二个参数，而且类比第1个元素是+1可以知道，第n个容器应该是+n（从1开始计数）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll s;
int l[200005], r[200005];
int cl[200005], cr[200005];
int tmp[200005], top;
bool check(int M) {
int cntL = 0, cntR = 0;
top = 0;
ll sum = 0;
for(int i = 1; i <= n; ++i) {
if(r[i] < M) {
++cntL;
sum += l[i];
} else if(l[i] > M) {
++cntR;
sum += l[i];
} else
tmp[++top] = l[i];
}
if(cntL >= (n + 1) / 2 || cntR >= (n + 1) / 2)
exit(-1);
int k = n / 2 - cntL;
nth_element(tmp + 1, tmp + k, tmp + 1 + top);
for(int i = 1; i <= k; ++i)
sum += tmp[i];
sum += 1ll * (top - k) * M;
return sum <= s;
}
int bs(int L, int R) {
while(1) {
int M = L + R >> 1;
if(L == M) {
if(check(R))
return R;
return L;
}
if(check(M))
L = M;
else
R = M - 1;
}
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%lld", &n, &s);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &l[i], &r[i]);
cl[i] = l[i], cr[i] = r[i];
}
nth_element(cl + 1, cl + ((n + 1) / 2), cl + 1 + n);
nth_element(cr + 1, cr + ((n + 1) / 2), cr + 1 + n);
int L = cl[(n + 1) / 2], R = cr[(n + 1) / 2];
printf("%d
", bs(L, R));
}
}
补题题解：在二分前对所有(l,r)对进行l排序，然后对夹有M的提取出来之后就不用排序了。不过渐进复杂度是一样的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll s;
pair<int, int> p[200005];
int tmp[200005], top;
bool check(int M) {
int cnt = 0;
top = 0;
ll sum = 0;
for(int i = 1; i <= n; ++i) {
if(p[i].second < M) {
++cnt;
sum += p[i].first;
} else if(p[i].first > M)
sum += p[i].first;
else
tmp[++top] = p[i].first;
}
int k = n / 2 - cnt;
for(int i = 1; i <= k; ++i)
sum += tmp[i];
sum += 1ll * (top - k) * M;
return sum <= s;
}
int bs(int L, int R) {
while(1) {
int M = L + R >> 1;
if(L == M) {
if(check(R))
return R;
return L;
}
if(check(M))
L = M;
else
R = M - 1;
}
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%lld", &n, &s);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &p[i].first, &p[i].second);
tmp[i] = p[i].second;
}
sort(p + 1, p + 1 + n);
sort(tmp + 1, tmp + 1 + n);
printf("%d
", bs(p[(n + 1) >> 1].first, tmp[(n + 1) >> 1]));
}
}
注：话说官方题解里好像有点问题的，need过多的话是M取得太小，而sum>s是M取得太大，两种怎么都返回false呢？感觉正确的做法是先找出不会使得need过多的合法的M。直接给l,r分别排序，取中位数的l必是下界，取中位数的r必是上界，满足M在这俩之间的至少能构造出一组解（全部给l，最省钱），而突破r的中位数显然不可能。这样就满足了单调性。
E1 - Voting (Easy Version)
见下题
E2 - Voting (Hard Version)
题意：有n（5000）个人，每个人有pi和mi，笼hui络lu他要pi块钱，或者当其他人支持数达到mi时他会免费从众，问花费最少的钱笼络所有人。
补题题解：看了一下好像是要从从众难度最高的人开始判断是否要收买，理由是很明显的，无后效性。好像越想越显然的样子，要找出那些必须要用钱才能收买的人。
按mi分层，倒着枚举。当前枚举到x层，假设<x的层已经全部收买完了（记为pre[x]），若pre[x]>=x，那么这一层不需要进行任何收买，否则一直收买>=x的层最便宜的人叠到pre[x]上。
为什么要倒着枚举呢，因为高层的会先面临不得不收买的问题（高层的从众难度更大）？先看对最高层的解释，最高层的人要么直接花费pi收买，要么由于收买前面的人已经够了而免费。假如存在免费的可能，先把这个最高层的放进优先队列里面待定，否则直接出手收买，然后考虑次高的那个……由数学归纳法，贪心成立？（每个购买决策都是万不得已的选择，就是假设前面的全部都笼络完了，后面的该买的买了，但是还是不能免费，所以现在一定要买，这个时候必须从后面这堆里面从最小的开始买，这个贪心很显然。）好像和CCPC网络赛的钓鱼那题一样。
干脆起个名字叫做“用堆暂时延迟决策的贪心”好了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> l[200005];
int pre[200005];
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
l[i].clear();
while(pq.size())
pq.pop();
for(int i = 1; i <= n; ++i) {
int mi, pi;
scanf("%d%d", &mi, &pi);
l[mi].push_back(pi);
}
pre[0] = 0;
for(int i = 1; i < n; ++i)
pre[i] = pre[i - 1] + l[i - 1].size();
int cnt = 0;
ll sum = 0;
for(int i = n - 1; i >= 0; --i) {
if(!l[i].size())
continue;
for(auto j : l[i])
pq.push(j);
while(pre[i] + cnt < i) {
++cnt;
sum += pq.top();
pq.pop();
}
}
printf("%lld
", sum);
}
}