害怕,也不知道能不能,就是感觉有点累,有点空虚,赶紧学习啊!
比赛地址链接
C题:
题意:有n个人,q个询问,每次询问会给出回答的同学名字,之后会给出要求的人的回答的所有问题,1代表它回答了那个问题,0代表他没回答那个问题,问能不能唯一确定那个人,如果能的话就输出那个人的名字,不能的话就输出“去图书馆!”。
方法:
留意到最多21道题,就可以想到用一个数来储存答案,这个人每回答一道题,就把这个1左移这个题的编号位,这样每个人的回答题的情况就是一个不同的数,如果存在两个相同的数,就说明判断不了问题,直接输出“去图书馆就行了”
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
map<string, int>mp;
map<int, string>mp2;
int check(int t) {
return distance(mp2.upper_bound(t) , mp2.lower_bound(t));
}
int main() {
int T; scanf("%d", &T);
while (T--) {
mp.clear(); mp2.clear();
int n, q; scanf("%d%d", &n, &q);
int c; scanf("%d", &c);
string tmp;
for (int i = 0; i < c; i++) {
cin >> tmp;
mp[tmp] = 0;
}
for (int i = 1; i <= q; i++) {
int m; scanf("%d", &m);
for (int j = 0; j < m; j++) {
cin >> tmp;
mp[tmp] |= (1 << i);
}
}
for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) {
if (mp2.find(it->second) == mp2.end())mp2[it->second] = it->first;
else mp2[it->second] = "Let's go to the library!!";
}
map<int, string>::iterator it;
for (int i = 0; i < n; i++) {
int t = 0, a;
for (int j = 1; j <= q; j ++ ) {
scanf("%d", &a);
t += (1 << j)*a;
}
it = mp2.find(t);
if ( it != mp2.end())cout << it->second << endl;
else cout << "Let's go to the library!!" << endl;
}
}
return 0;
}
D:
题意:有两个人聊天,如果这两个人连续聊了超过m天,他们之间的友情值就会增加一点,给出他们之间所有天的聊天记录,问最后他们的亲密度是多少。
解法:
首先这个题的考点之一是子区间的求交集问题,它的左区间的位置是max(l1,l2),他的右区间的位置是min(l1,l2)。交集长度对于最后亲密度的贡献是len-m+1+1即(nr-nl-m+1+1)。
对于每个区间如果a区间的右端点要比b区间的右端点大,那么我们就换下个a区间,否则就换下一个b区间
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 500;
struct inter {
int l, r;
bool operator < (inter &rhs) {
return l < rhs.l;
}
};
inter a[maxn], b[maxn];
int main() {
int T; scanf("%d", &T);
while (T--) {
int n, m, x, y;
scanf("%d%d%d%d", &n, &m, &x, &y);
for (int i = 0; i < x; i++)scanf("%d%d", &a[i].l, &a[i].r);
for (int i = 0; i < y; i++)scanf("%d%d", &b[i].l, &b[i].r);
//sort(a, a + x); sort(b, b + y);
int ans = 0, i = 0, j = 0;
while (i < x && j < y) {
int nl = max(a[i].l, b[j].l);
int nr = min(a[i].r, b[j].r);
ans += max(0, nr -nl- m + 1 + 1);
if (a[i].r <= b[j].r)i++;
else j++;
}
printf("%d
", ans);
}
return 0;
}
Uva1611
题意:给你一个序列,每一只能选择一个偶数区间,将这个区间的前一半和后一半交换位置,要求在9的6次方次操作内将这个序列变成有序的
解法:
要注意紫书上的提示,最多只需要2n次操作。也就是说,对每个数,最多只需要两次操作即可归位。那么,一次就将某数字归位是什么情况呢?假设现在我们要将数字m归位,那么数字m的正确位置就是m,而现在m的位置为p(设p>m),那么一次归位的做法就是我们选择位置m为交换区间的左端点,2*(p-m)作为区间的长度(即位置p恰好是我们所选区间的右半部分的第一个),这样交换过去后数字m就到了位置m。当然,这个操作的前提是交换区间的右端点不大于n。
若是不满足上述条件,即交换区间右端点大于n了,这时我们可以先进行一次操作将数字m向左移动足够的距离再进行上面的操作。我们当然希望将m向左移动的越多越好,这个做法还是很好实现的,只需从p开始选一个左端点不小于m的最大偶数区间即可。这样一次移动后,便一定可以使用上述操作一将其一次归位。
//https://blog.csdn.net/interstellar_/article/details/52675958
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 1e4 + 5;
int a[maxn], p[maxn];
vector<pair<int, int>>v;
void swa(int l,int r) {
int m = (l + r) >> 1;
//[l,m][m+1,r]
for (int i = 0; l + i <= m; i++) {
int L = l + i, R = m + i + 1;
swap(a[L], a[R]);
swap(p[a[L]], p[a[R]]);
}
v.push_back(make_pair(l, r));
return;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
v.clear();
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
p[a[i]] = i;//应该移动到的位置
}
for (int i = 1; i <= n; i ++ ) {//从左到右扫,不必担心已经排序好的元素
if (a[i] == i)continue;
int pos = p[i];
while (a[i] != i) {
if (pos + pos - i - 1 <= n)//区间右边没有越界
swa(i, i + 2 * (pos - i) - 1);
else {
int len = pos - i + 1;//pos到i的距离
if (len & 1) swa(i + 1, pos);
else swa(i, pos);//把i往右移
pos -= len / 2;//将i往右移其实就是将pos往左移,但是因为不能直接变i,所以选择变pos
}
}
}
printf("%d
", v.size());
for (int i = 0; i < v.size(); i++) {
printf("%d %d
", v[i].first, v[i].second);
}
}
return 0;
}