目录
A. Deletions of Two Adjacent Letters
C. Weight of the System of Nested Segments
杂谈
Div.3的题还是做着比较顺的，D题AC之后直接睡觉去了（第二天还要早八╯︿╰）
前两题签得还是比较顺利的（没有像上一场的B分类分崩了），C题读题和样例卡了很久，在我反应过来题意和样例输出的意思的时候，它发通知解释输出的意思了......然后D题调数组下标问题的过程真的非常痛苦，好在最后调完一遍过了，提前收工睡觉。
A. Deletions of Two Adjacent Letters
题目大意：给定一个字符串s和一个字符c，每次可以删除字符串中两个相邻的字符，问能否将字符串进行如上操作使得最终仅剩一个字符c。
解题思路：要想剩下一个字符，那么剩下的这个字符的左右边必须有偶数个字符，由于题目保证字符串长度为奇数，因此只要遍历一遍字符串，存在一个字符c出现的位置是奇数位置，那么就可以满足要求，否则不行。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
string s;
cin >> s;
char c;
cin >> c;
int len = s.size();
int flag = 0;
for(int i = 0; i < len; i++){
if(s[i] == c && i % 2 == 0){
flag = 1;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}B. DIV + MOD
题目大意：定义一个函数，给定区间?
?以及?
，在区间内找到一个数?
，使得这个函数值最大，并输出最大值。
解题思路：首先可以发现整除运算要想增加1，那 x 就得增加一轮 a，要想这个函数值最大，很明显需要从区间最大值开始考虑。如果说最大值恰好比 a 小 1，那么这个点整除值最大，模除值也最大，这样函数值也一定是最大的；如果最大值不恰好比 a 小 1，那么只要??够小（小于上一个整除点），就可以找到上一个整除点 - 1 的位置，这个点的函数值一定是比当前这个右端点的函数值来得大的（因为虽然整除值比右端点少1，但是模除值一定至少比右端点多出1），反之如果?
?不够小，那么函数值还是在右端点取到最大值。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int l, r, a;
cin >> l >> r >> a;
int x = r - r % a - 1;
if(r % a != a - 1 && l <= x) cout << x / a + x % a << endl;
else cout << r / a + r % a << endl;
}
return 0;
}C. Weight of the System of Nested Segments
题目大意：给定 m 个点，每个点有对应的坐标值和权值，在这之中选出 2n 个点，使得权值总和最小。其中，这 2n 个点必须满足如下条件：每两个点坐标值配对形成一个区间，每两个区间之间要是真子集的关系。如题图所示：（蓝色代表坐标值，红色代表权值）
要求输出最小权值和，并且按照输入的点的顺序作为编号，输出两两配对的结果。
解题思路：要求最小权值和，很明显必须选择的是前 2n 个小的值。配对的时候一定是选出的这 2n 个值中最小坐标点和最大坐标点进行配对，次小坐标点和次大坐标点进行配对……那么关键就在于怎么输出了，可以建立一个结构体将坐标值，权值，编号区分开，然后先对整体按权值排序，再对前 2n 个点按坐标值排序，这样就可以直接进行配对并输出对应的点的编号了。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200005;
struct node{
int x, w, id; // x表示坐标值，w表示权值，id表示编号
}a[N];
bool cmp1(node a, node b){
return a.w < b.w;
}
bool cmp2(node a, node b){
return a.x < b.x;
}
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> a[i].x >> a[i].w;
a[i].id = i;
}
sort(a + 1, a + m + 1, cmp1);
sort(a + 1, a + 2 * n + 1, cmp2);
ll sum = 0;
for(int i = 1; i <= 2 * n; i++)
sum += a[i].w;
cout << sum << endl;
for(int i = 1; i <= n; i++){
cout << a[i].id << ' ' << a[2 * n - i + 1].id << endl;
}
cout << endl;
}
return 0;
}D. Twist the Permutation
题目大意：一个长度为 n 的序列初始状态为 1，2，3，...，n，可以进行如下操作：第 i 次操作对于序列前 i 位进行循环向右移动 x 次，假设 n = 6，i = 2，x = 1，则序列变为 2，1，3，4，5，6。总共有 i 次操作，每次可以选择向右移动的次数。给定序列的最终状态，问由初始状态最少经过几次移动能够得到这个最终状态，并且输出每次操作移动的次数。（如果达不到这个最终状态则输出-1）
解题思路：首先可以发现对于任意一个最终状态，一定都能由起始状态经过 n 次操作得到。从大到小考虑每个值偏离了初始位置多少，然后每次得到偏离值后更新序列状态，再进行下一个数的偏离值计算。每个数的偏离值就是对应在第 i 次操作进行的移动次数。按照这个思路直接模拟就好了。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 2005;
int ans[N];
struct node{
int num, id;
}a[N];
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].num;
a[i].id = i;
if(a[i].num == n) ans[0] = (a[i].id == n ? 0 : a[i].id);
// 将最大值的偏离值先处理好
}
for(int i = 1; i < n; i++){
for(int j = 1; j <= n; j++){ // 更新序列状态
int x = a[j].id - ans[i - 1];
int mn = n - (i - 1);
a[j].id = (x == 0 ? mn : (x + mn) % mn);
}
for(int j = 1; j <= n; j++){ // 寻找第 i + 1 大的数并计算偏离值
if(a[j].num == n - i){
ans[i] = (a[j].id == n - i ? 0 : a[j].id);
break;
}
}
}
for(int i = n - 1; i >= 0; i--){
cout << ans[i] << ' ';
}
cout << endl;
}
return 0;
}