2022杭电 中超
K Random
简单的概率题，直接能推出公式为\((n - m) / 2\)
但是不能就这样简单的去算，加减乘与模运算的顺序交换不会影响结果，但是除法不行。这个题目要求对一个大质数取模，原式里面有除法，我们就需要求取除数对于取模数的逆元，然后进行转化为乘法运算。
这样我们就需要先求出\(2\)对于\({10}^9+7\)的逆元\(x^{-1}\)(费马小定理转化一下，快速幂嗯算就完了)
这样计算公式为:
点击查看代码
#include
int mod = 1e9+7;
int main()
{
int t = 1;
std::cin >> t;
int tem = 500000004;
while(t--)
{
int x,y;
std::cin >> x >> y;
std::cout << 1ll * (x-y) * tem % mod < L Alice and Bob
博弈论
点击查看代码
#include
const int N = 1e6 + 10;
using namespace std;
int a[N];
int n;
void slove()
{
cin >> n;
for(int i = 0;i <= n;i++)cin >> a[i];
for(int i = n;i > 0;i--)a[i-1] += a[i] / 2;
cout << a[0] << endl;
if(a[0])puts("Alice");
else puts("Bob");
}
int main()
{
int t;
cin >> t;
while(t--)slove();
return 0;
}
B Dragon slayer
点击查看代码
#include
#include
using namespace std;
int n, m, k;
int xs, ys, xt, yt;
int wall;
int x1[16], y1[16], x2[16], y2[16];
bool p[16], col[40][40];
const int dx[4] = {0, 2, 0, -2};
const int dy[4] = {2, 0, -2, 0};
void dfs(int x, int y)
{
col[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
int midx = x + dx[i] / 2;
int midy = y + dy[i] / 2;
if (newx >= n or newx < 0 or newy < 0 or newy >= m or col[newx][newy])continue;
bool fa = 0;
for (int j = 0; j < k; j++)
{
if (!(wall >> j & 1))continue;
if (x1[j] == x2[j])
{
if (midx == x1[j] and midy >= y1[j] and midy <= y2[j])
{
fa = 1;
break;
}
}
else
{
if (midy == y1[j] and midx >= x1[j] and midx <= x2[j])
{
fa = 1;
break;
}
}
}
if (!fa)dfs(newx, newy);
}
return;
}
int cnt(int x)
{
int ans = 0;
while (x)
{
if (x & 1)ans++;
x >>= 1;
}
return ans;
}
int fd()
{
int ans = k, tn = 1 << k;
for (int i = 0; i < tn; i++)
{
if (k - cnt(i) > ans)continue;
memset(col, 0, sizeof col);
wall = i;
dfs(xs,ys);
if (col[xt][yt])
{
if (k - cnt(i) < ans)ans = k - cnt(i);
}
}
return ans;
}
void slove()
{
cin >> n >> m >> k;
cin >> xs >> ys >> xt >> yt;
n *= 2;
m *= 2;
xs = xs * 2 + 1;
ys = ys * 2 + 1;
xt = xt * 2 + 1;
yt = yt * 2 + 1;
for (int i = 0; i < k;i++)
{
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i] *= 2;
x2[i] *= 2;
y1[i] *= 2;
y2[i] *= 2;
if (x1[i] > x2[i])swap(x1[i], x2[i]);
if (y1[i] > y2[i])swap(y1[i], y2[i]);
}
cout << fd() << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
slove();
}
return 0;
}