Codeforces Global Round 15
A. Subsequence Permutation
- 签到
- 思路
字符串排个序，然后匹配就行了
code:
const int N = 200100;
int st[30];
void solve(){
int n;
string str;
cin >> n >> str;
string s = str;
int ans = 0;
sort(s.begin(), s.end());
for(int i = 0;i < n;i ++) {
if(s[i] == str[i]) ans ++;
}
cout << n - ans << endl;
}
B. Running for Gold
- 题意
n个人，每个人有5次分数，(rank_i,_j)运动员i在第j次分数的排名情况，i比j优秀： 三次或三次以上的排名大于j即可，现需找出最优秀的人。
- 思路
每次比较两个人的优秀，然后删掉另一个即可，最后在扫一遍，看最后剩的人会不会比别人小，输出-1
code:
struct node {
int a,b,c,d,e;
int id;
};
bool cmp(node a, node b) {
int cnt = 0;
if(a.a > b.a) cnt ++;
if(a.b > b.b) cnt ++;
if(a.c > b.c) cnt ++;
if(a.d > b.d) cnt ++;
if(a.e > b.e) cnt ++;
return cnt < 3;
}
vector<node> v, u;
void solve(){
int n;
cin >> n;
v.resize(n);
for(int i = 0;i < n;i ++) {
cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d >> v[i].e;
v[i].id = i + 1;
}
u = v;
while(u.size() > 1) {
if(cmp(u[0],u[1])) {
u.erase(u.begin() + 1);
}else {
u.erase(u.begin());
}
}
bool flag = 0;
for(int i = 0;i < n;i ++) {
if(cmp(v[i], u[0]) && v[i].id != u[0].id) flag = 1;
}
if(flag) cout << "-1" << endl;
else cout << u[0].id << endl;
v.clear();
}
C. Maximize the Intersections
- 题意
一共2 * n个点，并且给出了k对弦， 要求用甚于(n - k) * 2个点进行连边，并让交点最大。
- 思路
首先，两边相交，那么就是x1 < x2 < y1 < y2 || x2 < x1 < y2 < y1这两条，那么我们要让我们建的点最大化这一性质，通过不断话图形可以推出来一个规律，我们将所有剩余的点排序后分为两半，前半部分和后半部分按顺序连边即可另数量最大化，1 -> 5,2 -> 6, 3 -> 7····顺时针
code:
pii p[N];
int idx;
bool sk[N];
vector<int> v;
bool check(pii a, pii b) {
if(a.first < b.first && a.second < b.second && b.first < a.second) return 1;
if(b.first < a.first && b.second < a.second && a.first < b.second) return 1;
return 0;
}
void solve(){
int n, k;
cin >> n >> k;
idx = 0;
memset(sk,0,sizeof sk);
v.clear();
for(int i = 1;i <= k;i ++) {
int a,b;
cin >> a >> b;
if(a > b) swap(a,b);
sk[a] = sk[b] = 1;
p[++ idx] = {a,b};
}
for(int i = 1;i <= n * 2;i ++) {
if(!sk[i]) v.push_back(i);
}
int len = v.size();
for(int i = 0;i < len / 2;i ++) {
p[++ idx] = {v[i], v[i + len / 2]};
}
int ans = 0;
for(int i = 1;i < idx;i ++) {
for(int j = i + 1;j <= idx;j ++) {
// cout << p[i].first << ' ' << p[i].second << ' ' << p[j].first << ' ' << p[j].second << endl;
if(check(p[i],p[j])) ans ++;
}
}
cout << ans << endl;
}
D. Array Differentiation
- 题意
给出一个序列(a_i), 要求你是否能构造出另一个序列(b_i), 满足任意(a_i = b_j - b_k),(1 <= i <= n, 1 <= j,k <= n).
- 思路
- 首先，我们可以很简单的证明序列不能是升序或降序的。
- 其次，如果本题b的长度如果是n + 1个，那么随便填就行了，两两生成一个即可，所以我们需要思考可以怎么通过k个b[i],满足k个a[i]，然后其他n - k个随便填就行了。
- 然后，可以发现, 如满足(a_i + a_j == a_k + a_d)类似的东西，对于b的求解就多了一个等式，那么就可以通过求解来满足：
A: a b c d
B: x1 x2 x3 x4
首先，令x1 = a, x2 = -(d - a)，x4 = 0
那么, x1 - x2 = d, x1 - x4 = a,
然后令x3 = -(b + (d - a)), 那么 x2 - x3 = c;
然后a,c,d都出来了，通过等式对x1,x2,x3,x4进行运算不就出来了。
code：
const int N = 11;
set<int> t;
int a[N];
void solve(){
int n;
t.clear();
cin >> n;
for(int i = 1;i <= n;i ++) {
cin >> a[i];
}
for(int i = 0;i < (1 << n);i ++) {
int res = 0;
for(int j = n - 1;j >= 0;j --) {
if(i >> j & 1) res += a[j + 1];
}
if(t.count(res)) {
cout << "YES" << endl;
return;
}
t.insert(res);
}
cout << "NO" << endl;
}
F. Telepanting
- 题意
一只蚂蚁从位置0走到位置(x_n + 1), 途中有n个传送阵，(op_i)表示是否激活
若(op_i = 1)则激活，蚂蚁传送到(y_i)的位置上去
否则，激活这个传送
题目满足((x_i > x_j (n >= i > j >= 1)))
- 思路
dp+二分预处理即可
首先，蚂蚁在走的下标之前的传送门，一定是都激活的
f[i]记录蚂蚁当前传送阵且激活的情况需要多走的路程
- 若往回走不需要经过传送门，之间减去两端(x_i - y_i)即可
- 否则，就多加一层前缀即可
sum[i]记录f[i]前缀和
忘了mod就等着wa吧
code:
const int N = 200100;
const int mod = 998244353;
int f[N];
int u[N],v[N],op[N];
int sum[N];
void solve(){
int n;
cin >> n;
int now = 0;
for(int i = 1;i <= n;i ++) {
cin >> u[i] >> v[i] >> op[i];
int l = 1,r = i;
while(l < r) {
int mid = l + r >> 1;
if(v[i] <= u[mid]) r = mid;
else l = mid + 1;
}
if(r == i)
f[i] = (u[i] - v[i]);
else
f[i] = (u[i] - v[i]) + (sum[i - 1] - sum[r - 1] + mod * 3) % mod; // 不mod就等着wa吧
f[i] %= mod;
sum[i] = (f[i] + sum[i - 1]) % mod;
now = u[i];
}
int ans = u[n] + 1;
for(int i = 1;i <= n;i ++) {
if(op[i]) {
ans += f[i];
ans %= mod;
}
}
cout << ans % mod << endl;
}