|
题意：选择一个黑色格子，将其同一行或者同一列染成黑色，最后询问一个坐标是否可以被染成黑色，需要几次操作。
题解：首先，如果当前格子为黑色，则0次，如果不是黑色，且没有黑色格子，则输出-1，若当前格子的同一行或者同一列有黑色格子，则为1，其他情况为2。
const int N = 110;
char a[N][N];
int n, m;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cin.tie(0);
int t;
cin >> t;
while (t--)
{
memset(a, 0, sizeof a);
int x, y;
cin >> n >> m >> x >> y;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
bool flag = false, f = false, ff = false;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 'B')
{
flag = true;
}
if (a[i][j] == 'B' && i == x)
{
f = true;
}
if (a[i][j] == 'B' && j == y)
{
f = true;
}
if (a[i][j] == 'B' && j == y && i == x)
{
ff = true;
}
}
}
if (f && flag && ff) cout << 0 << endl;
else if (f && flag && !ff) cout << 1 << endl;
else if (!f && flag && !ff) cout << 2 << endl;
else cout << -1 << endl;
}
return 0;
}
题意：两个人，a同学想尽量靠近b同学，b同学想尽量远离a同学，且b同学可以将座位染色，使得a同学不能选此座位而b却可以选。两者采取最优方案。
题解：首先，a想靠近b，那么他一定会选最中间位置，b想远离，那么他一定会选角落，所以直接计算每个位置到四个角落距离取最大值即可。
const int N = 1e5 + 10;
int g[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cin.tie(0);
int t;
cin >> t;
while (t--)
{
memset(g , 0, sizeof g);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
g[(i - 1) * m + j] = max(abs(i - 1) + abs(j - 1), g[(i - 1) * m + j]);
g[(i - 1) * m + j] = max(abs(i - n) + abs(j - m), g[(i - 1) * m + j]);
g[(i - 1) * m + j] = max(abs(i - 1) + abs(j - m), g[(i - 1) * m + j]);
g[(i - 1) * m + j] = max(abs(i - n) + abs(j - 1), g[(i - 1) * m + j]);
}
}
sort(g + 1, g + 1 + m * n);
for (int i = 1; i < 1 + m * n; i++) cout << g[i] << ' ';
cout << endl;
}
return 0;
}
题意：求质数树，即相邻两条边均为质数且相加为质数
题解：若有某节点为三叉即以上，则不可能组成质数树，因为质数相加中只有2和其他质数相加才为质数。所以，我们可以利用出度入度来做。
typedef pair<int, int>PII;
map<PII, int>mp;
const int N = 1e5 + 10, M = 2e5 + 10;
int rd[N], cd[N];
int e[M], ne[M], h[N], idx;
int n,dist[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool st[N];
void spfa()
{
queue<PII>q;
memset(st, 0, sizeof st);
memset(dist, 0, sizeof dist);
for (int i = 1; i <= n; i++)
{
if (rd[i] == 1)
{
q.push({ i, 2 });
break;
}
}
while (!q.empty())
{
auto t = q.front();
st[t.first] = true;
q.pop();
for (int i = h[t.first]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
dist[mp[{t.first, j}]] = t.second;
q.push({ j, 5 - t.second });
}
}
}
for (int i = 1; i < n; i++)
{
cout << dist[i] << ' ';
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cin.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n;
memset(rd, 0, sizeof rd);
memset(cd, 0, sizeof cd);
memset(h, -1, sizeof h);
idx = 0;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
rd[b]++;
rd[a]++;
cd[a]++;
cd[b]++;
mp[{a, b}] = mp[{b, a}] = i;
add(a, b), add(b, a);
}
int f = 1;
for (int i = 1; i <= n; i++)
{
if (rd[i] + cd[i] >= 6)
{
cout << -1 << endl;
f = 0;
break;
}
}
if (!f) continue;
else
{
spfa();
}
}
return 0;
}
题意：给定一个数组，求任意两个数的gcd，若数组不存在改值，则将该值加入，问最多能加入几个数。
题解：a = gcd(b, c) ，我们可以知道b和c一定为a的倍数，所以我们直接枚举1到1e6的每个数（该数不在数组中），观察数组是否存在两个该数的倍数，如果存在，则ans++
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
a[x]++;
}
int ans = 0;
for (int i = N; i >= 1; i--)
{
if (a[i]) continue;
int t = 0;
for (int j = i; j <= N; j += i)
{
if (a[j]) t = gcd(t, j);
}
if (t == i) ans++;
}
cout << ans << endl;
return 0;
}
|