今天是第二天了，测评姬出了些毛病，今天的rating不算，有喜有悲吧
明天加油！
Codeforces Round #498 (Div. 3)
A：Adjacent Replacements
题解：奇数位置上的数不变，偶数位置上的数-1；
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000 + 6];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
if (a[0] % 2 == 0)printf("%d", a[0] - 1);
else printf("%d", a[0]);
for (int i = 1; i < n; i++) {
if (a[i] % 2 == 0)printf(" %d", a[i] - 1);
else printf(" %d", a[i]);
}
return 0;
}B：Polycarp’s Practice
题意：将一个序列分成n份，要求这n份中最大数的和最大
解法：由于分法不限制，所以我们将每个最大的数放到区间的右边，如果最右边的最大数不在序列最右边，就把它移过去
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
vector<int>vi;
int vis[10005], n, k, tmp, ans = 0;
vector<pii>vp;
priority_queue <int, vector<int>, less<int>> q;
bool cmp(pii a, pii b) { return a.second < b.second; }
int find(int tmp) {
for (int i = 0; i < n; i++)
if (vi[i] == tmp&&vis[i] == 0) {
vis[i] = 1; return i;
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &tmp);
vi.push_back(tmp);
q.push(tmp);
}
for (int i = 0; i < k; i++) {
tmp = q.top(); q.pop();
int len = find(tmp);
vp.push_back(make_pair(tmp, len));
ans += tmp;
}
sort(vp.begin(), vp.end(), cmp);
if (vp[vp.size() - 1].second != n - 1)vp[vp.size() - 1].second = n - 1;
printf("%d
%d", ans, vp[0].second + 1);
for (int i = 1; i < vp.size(); i++) {
printf(" %d", vp[i].second - vp[i - 1].second);
}
return 0;
}C：Three Parts of the Array
题意：将一个序列分成三份，每份序列可以为空，要求最左边的序列的和等于最右边的序列的和，问最大的和为多少？
解法：meet—in—middle，从两边同时开始搜索，循环条件是两个指针的差>1，注意当序列长度小于2的时候（即只为1）的时候和是0
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll d[200000 + 5];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &d[i]);
}
int i = 0, j = n - 1;
ll sum1 = d[0], sum3 = d[n - 1], fsum = 0;
while (j - i > 1) {
if (sum1 > sum3) { j--; sum3 += d[j]; }
else if (sum1 < sum3) { i++; sum1 += d[i]; }
else {
fsum = sum1;
if (j - i == 1)break;
else { i++; sum1 += d[i]; }
}
}
if (sum1 == sum3)fsum = sum1;
if (n < 2)fsum = 0;
printf("%I64d", fsum);
return 0;
}D：Two Strings Swaps
题意：两个字符串，三种交换方式：
1：交换a[i]和b[i]，2：交换a[i]和a[n-i+1]，3：交换b[i]和b[n-i+1]
在交换前可以将a中的任意一个字母替换成另外一个任意字母，之后可以随意使用上述变换，最终结果要求两个字符串相等，求最小替换次数（上述所有操作只针对第一串）
解法：
首先，如果位置为i的字符不用替换，那么两种串的分布有三种情况；在这种情况下，如果6个条件满足任意一个，就只能是一个字母需要替换，否则就得替换两个字母，非常好的题！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s1, s2;
int main() {
int n, ans = 0;
scanf("%d", &n);
cin >> s1 >> s2;
for (int l = 0; l < n/2; l++) {
int r = n - l - 1;
if ((s1[l] == s2[l] && s1[r] == s2[r]) || (s1[l] == s1[r] && s2[l] == s2[r]) || (s1[l] == s2[r] && s1[r] == s2[l]))
ans += 0;
else if ((s1[l] == s2[l] || s1[r] == s2[r]) || (s1[l] == s2[r] || s2[l] == s2[r]) || (s1[l] == s2[r] || s1[r] == s2[l]))
ans += 1;
else ans += 2;
}
if (n % 2 == 1 && s1[n / 2] != s2[n / 2])ans++;
cout << ans;
return 0;
}Uva11314Fabled Rooks
题意：一个棋盘，横纵分成不同的几个区间，要求每个区间必须有一个棋子，不同棋子不能重叠，横纵坐标不能相同，输出每个棋子的坐标
解法：首先横坐标和纵坐标其实没关系，直接分开看；接下来以横坐标为例，将所有的区间先按右边界从小到大排序，相等的话就按左边界从大到小排序，之后从每个区间最左边搜，如果最后大于等于右边界就无解，输出IMPOSSIBLE
贪心的思路，直接dfs搜不过去
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int vis[100000 + 5], n;
const int maxn = 1e5 + 5;
struct node {
int l, r, num;
bool operator < (const node &rhs){
//区间右端点越小，优先级越高；同等情况下，左端点越大优先级越高
//这种情况下，如果我们先取最右边的，则小区间必定满足，此时大区间被满足的几率也较大，因此不可以，所以我们从左边往右边取
return r < rhs.r || (r == rhs.r&&l > rhs.l);
}
}x[maxn], y[maxn];
int slove(int *a,node* q) {
memset(a, 0, sizeof(a));
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) {
for (int j = q[i].l; j <= q[i].r; j++) {
if (!vis[j]) {
a[q[i].num] = j; vis[j] = 1;
break;
}
if (j >= q[i].r)return 0;
}
}
return 1;
}
int main() {
int a[maxn], b[maxn];
while (cin >> n && n)
{
for (int i = 0; i < n; ++i)
{
scanf("%d%d%d%d", &x[i].l, &y[i].l, &x[i].r, &y[i].r);
x[i].num = y[i].num = i;
}
sort(x, x + n); sort(y, y + n);
if (slove(a, x) && slove(b, y))
{
for (int i = 0; i < n; ++i)
printf("%d %d
", a[i], b[i]);
}
else
{
printf("IMPOSSIBLE
");
}
}
return 0;
}