后面的题目补不懂了
暴力 1001 Clarke and chemistry
这题也把我搞死了。。枚举系数判断就行了
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map> int cnt[3][30]; bool error(void) {
for (int i=0; i<2; ++i) {
for (int j=0; j<26; ++j) {
if (cnt[i][j] != -1 && cnt[2][j] == -1) {
return true;
}
}
}
return false;
} int main(void) {
int T; scanf ("%d", &T);
while (T--) {
int A, B, C; scanf ("%d%d%d", &A, &B, &C);
memset (cnt, -1, sizeof (cnt));
char c[2]; int t;
for (int i=0; i<A; ++i) {
scanf ("%s %d", &c, &t);
cnt[0][c[0]-'A'] = t;
}
for (int i=0; i<B; ++i) {
scanf ("%s %d", &c, &t);
cnt[1][c[0]-'A'] = t;
}
for (int i=0; i<C; ++i) {
scanf ("%s %d", &c, &t);
cnt[2][c[0]-'A'] = t;
}
bool flag = true;
int ans1 = 1000000, ans2 = 1000000;
for (int i=1; i<=2000&&flag; ++i) {
for (int j=1; j<=2000&&flag; ++j) {
bool ok = true;
for (int k=0; k<26; ++k) {
if (cnt[2][k] == -1) continue;
if (cnt[0][k] == -1 && cnt[1][k] == -1) {
flag = false; break;
}
int x = 0;
if (cnt[0][k] != -1) x = cnt[0][k] * i;
if (cnt[1][k] != -1) x += cnt[1][k] * j;
if (x != cnt[2][k]) {
ok = false; break;
}
}
if (ok) {
if (i < ans1 || (i == ans1 && j < ans2)) ans1 = i, ans2 = j;
}
}
}
if (error ()) flag = false;
if (flag && ans1 < 1000000) printf ("%d %d\n", ans1, ans2);
else puts ("NO");
} return 0;
}
数学 1002 Clarke and points
题意： 求|XA - XB| + |YA - YB| 最大
分析：去掉绝对值，就知道只要得到最大最小的(XA + XB) 和 (XA - XB)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std; long long seed;
inline long long rand(long long l, long long r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
} const int N = 1e6 + 5;
pair<long long, long long> p[N];
long long mx[2], mn[2]; int main(void) {
int T; cin >> T;
while (T--) {
int n;
cin >> n >> seed;
mx[0] = mx[1] = -(1ll << 60);
mn[0] = mn[1] = (1ll << 60);
for (int i = 0; i < n; i++) {
p[i].first = rand (-1000000000, 1000000000);
p[i].second = rand (-1000000000, 1000000000);
mx[0] = max (mx[0], p[i].first + p[i].second);
mx[1] = max (mx[1], p[i].first - p[i].second);
mn[0] = min (mn[0], p[i].first + p[i].second);
mn[1] = min (mn[1], p[i].first - p[i].second);
}
cout << max (abs (mx[0] - mn[0]), abs (mx[1] - mn[1])) << '\n';
}
return 0;
}
贪心 + BFS Clarke and MST
题意：求位运算and的最大生成树
分析：枚举数字每一位是否有可能为1，即(now & w == now)，用BFS遍历所有生成树
#include <cstdio>
#include <cstring>
#include <queue> const int N = 3e5 + 5;
struct Edge {
int v, w;
};
std::vector<Edge> G[N]; int n, m;
bool vis[N]; bool BFS(int now) {
std::queue<int> que;
memset (vis, false, sizeof (vis));
que.push (1); vis[1] = true;
while (!que.empty ()) {
int u = que.front (); que.pop ();
for (int i=0; i<G[u].size (); ++i) {
int v = G[u][i].v;
int w = G[u][i].w;
if (!vis[v] && (w & now) == now) {
vis[v] = true;
que.push (v);
}
}
}
for (int i=1; i<=n; ++i) if (!vis[i]) return false;
return true;
} int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &m);
for (int i=0; i<=n; ++i) G[i].clear ();
for (int u, v, w, i=0; i<m; ++i) {
scanf ("%d%d%d", &u, &v, &w);
G[u].push_back ((Edge) {v, w});
G[v].push_back ((Edge) {v, w});
}
int ans = 0;
for (int i=30; i>=0; --i) {
int now = ((1 << i) | ans);
if (BFS (now)) ans = now;
}
printf ("%d\n", ans);
} return 0;
}