Codeforces Round #440 (Div. 2)
codeforces 870 A. Search for Pretty Integers（水题）
题意：给两个数组，求一个最小的数包含两个数组各至少一个数。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int a[], b[];
int main() {
int i, j, x = , y = , s = ;
scanf("%d%d", &n, &m);
for(i = ; i <= n; ++i) {
scanf("%d", &a[i]); if(a[i] < x) x = a[i];
}
for(i = ; i <= m; ++i) {
scanf("%d", &b[i]); if(b[i] < y) y = b[i];
for(j = ; j <= n; ++j)
if(a[j] == b[i] && b[i] < s) s = b[i];
}
if(s < ) printf("%d\n", s);
else {
if(x > y) swap(x, y);
printf("%d%d\n", x, y);
}
return ;
}
31ms
codeforces 870 B. Maximum of Maximums of Minimums（模拟）
题意：给一排N个数，要求分割成K份，每份里面取出最小的数，再从取出的这些数中求最大的数，，求能得到的最大的数。
题解：K=1时答案即为最小的数，K≥3时，答案为这排数中最大的数，K=2时，就是两端 两个数的最大的一个。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ;
int n, m;
int a[N];
int main() {
int i, j, mi = , ma = -;
scanf("%d%d", &n, &m);
for(i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if(a[i] < mi) mi = a[i];
if(a[i] > ma) ma = a[i];
}
if(m==) printf("%d\n", mi);
else if(m==) printf("%d\n", max(a[], a[n]));
else printf("%d\n", ma);
return ;
}
31ms
codeforces 870 C. Maximum splitting（数学）
题意：一个数拆分成几个合数之和，求最多能拆分成几个数之和。
题解：合数为4,6,9最优咯。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int ans = ;
if(n & ) {
n -=; ans++;
}
if(n < && n != ) puts("-1");
else {
ans += n/;
printf("%d\n", ans);
}
}
return ;
}
61ms
codeforces 870 E. Points, Lines and Ready-made Titles（思维）
题意：对每个点，可以绘制一条垂直线，或一条水平线，或什么都不做。几条重合的直线是一条直线，求可以得到多少个不同的图片。
题解：排序，将同一行的用并查集合并，再将同一列的也合并，假设一个集合的点在原图的不重复行列数为s，如果该集合的点在原图中不能形成环，则该集合的贡献是2^s-1（少一种是环的图形）,否则贡献为2^s。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = ;
const ll mod = 1e9+;
int f[N], r1[N], r2[N];
struct node {
int x, y, id;
}p[N];
int cmp1(node a, node b) {return a.x < b.x;}
int cmp2(node a, node b) {return a.y < b.y;}
int fin(int x) {
if(f[x]!=x) f[x] = fin(f[x]);
return f[x];
}
void uni(int x, int y) {
if((x=fin(x)) == (y=fin(y))) r2[y]++;
else {
f[x] = y;
r1[y] += r1[x];
r2[y] += r2[x] + ;
}
}
int main() {
int n, i, j;
ll ans = ;
ll a[*N]; a[] = 1ll;
for(i = ; i < *N; ++i) a[i] = (a[i-] * ) % mod;
scanf("%d", &n);
memset(r2, , sizeof(r2));
for(i = ; i <= n; ++i) {
scanf("%d%d", &p[i].x, &p[i].y);
p[i].id = i;
f[i] = i;
r1[i] = ;
}
sort(p+, p++n, cmp1);
for(i = ; i <= n; ++i)
if(p[i].x == p[i-].x) uni(p[i].id, p[i-].id);
sort(p+, p++n, cmp2);
for(i = ; i <= n; ++i)
if(p[i].y == p[i-].y) uni(p[i].id, p[i-].id); for(i = ; i <= n; ++i)
if(f[i] == i) {
if(r1[i] == r2[i]+) ans = ans * (ll)(a[r1[i]+] - ) % mod;
else ans = ans * (ll)(a[*r1[i] - r2[i]]) % mod;
}
printf("%lld\n", ans);
return ;
}
93ms