xjtu_zfw

1.6万

ShawnWen
zfw

BeiHai
Bochi
ヾ凉城づ

Tranquility
ypfyyj
ncepu_GJJ
damn_it
Feelme

Q.青青

fluo

2850g

xjtu_zfw
5小时前

#include <iostream>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

PLL get(LL n, LL a)
{
if (n == 0) return {0, 0};
LL block = 1ll << 2 * n - 2, len = 1ll << n - 1;
auto p = get(n - 1, a % block);
LL x = p.x, y = p.y;
int z = a / block;

if (z == 0) return {y, x};
else if (z == 1) return {x, y + len};
else if (z == 2) return {x + len, y + len};
return {2 * len - 1 - y, len - 1 - x};
}

int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
LL n, a, b;
scanf("%lld%lld%lld", &n, &a, &b);
auto pa = get(n, a - 1);
auto pb = get(n, b - 1);
double dx = pa.x - pb.x, dy = pa.y - pb.y;
printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 10);
}

return 0;
}


### AC

#include <iostream>

using namespace std;

const int mod = 9901;

int qmi(int a, int k)   // a^k
{
int res = 1;
a %= mod;
while (k)
{
if (k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}

int sum(int p, int k)   // p^0 + p^1 + ... + p^(k-1) + p^k
{
if (k == 0) return 1;
if (k % 2 == 0) return ((1 + qmi(p, k / 2)) * sum(p, k / 2 - 1) + qmi(p, k)) % mod;
else return (qmi(p, k) + sum(p, k - 1)) % mod;
}

int main()
{
int a, b;
cin >> a >> b;

if (a == 0)
{
puts("0");
return 0;
}

int res = 1;
// 对a分解质因数
for (int i = 2; i <= a / i; i ++)
{
int s = 0;
while (a % i == 0)
{
a /= i;
s ++;
}
res = res * sum(i, s * b) % mod;
}

if (a > 1) res = res * sum(a, b) % mod;
cout << res << endl;

return 0;
}


### TLE做法

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 9901;

unordered_map<int, int> m;

int qmi(int a, int k, int p)    // a^k % p
{
int res = 1;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}

int main()
{
int a, b;
cin >> a >> b;
for (int i = 2; i <= a / i; i ++)
{
m[i] ++;
a /= i;
}
if (a > 1) m[a] ++;

int res = 1;
for (auto prime : m)
{
int p = prime.first, a = prime.second * b;  // p是底数，a是指数
int t = 1;
while (a --) t = (t * p + 1) % mod;     // 秦久韶算法
res = res * t % mod;
}
cout << res << endl;
return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 6;
char g[N][N], bg[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void turn(int x, int y) // 按一下(x, y)的开关
{
g[x][y] ^= 1;
for (int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
g[a][b] ^= 1;
}
}

int main()
{
int T;
cin >> T;
while (T --)
{
for (int i = 0; i < 5; i ++) cin >> bg[i];

int res = 10;
for (int op = 0; op < 32; op ++)
{
int cnt = 0;
memcpy(g, bg, sizeof g);
// 操作第一行的开关
for (int i = 0; i < 5; i ++)
if (op >> i & 1)
{
turn(0, i);
cnt ++;
}

// 递推出第1~4行的开关状态
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 5; j ++)
if (g[i][j] == '0')
{
turn(i + 1, j);
cnt ++;
}

// 检查最后一行灯是否全亮
bool success = true;
for (int i = 0; i < 5; i ++)
if (g[4][i] == '0')
success = false;
if (success && cnt < res) res = cnt;
}
if (res > 6) res = -1;
cout << res << endl;
}

return 0;
}


#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)    // 快速幂
{
int res = 1;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}

LL qadd(LL a, LL b, LL p)
{
LL res = 0;
while (b)
{
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}

int main()
{
LL a, b, c;
cin >> a >> b >> c;
// cout << qmi(a, b, c) << endl;
cout << qadd(a, b, c) << endl;

return 0;
}


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

vector<PII> segs;

void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;
for (auto seg: segs)
{
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
}

if (st != -2e9) res.push_back({st, ed});

segs = res;
}

int main()
{
int n;
cin >> n;
while (n -- )
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}

merge(segs);

cout << segs.size() << endl;

return 0;
}


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;       // 存储所有待离散化的值

// 二分求出值x对应的离散化的位置
int find(int x)     // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
int x, c;
cin >> x >> c;

alls.push_back(x);
}

for (int i = 0; i < m; i ++)
{
int l, r;
cin >> l >> r;
query.push_back({l, r});

alls.push_back(l);
alls.push_back(r);
}

sort(alls.begin(), alls.end());     // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 处理插入
for (auto item : add) a[find(item.first)] += item.second;

// 预处理前缀和
for (int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];

// 处理询问
for (auto item : query)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}

return 0;
}


xjtu_zfw
29天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i --)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}

reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

int main()
{
string a;
int b;
cin >> a >> b;

vector<int> A;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

int r = 0;
vector<int> C = div(A, b, r);
for (int i = C.size() - 1; i >= 0; i --) cout << C[i];
cout << endl << r << endl;

return 0;
}


xjtu_zfw
29天前
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
vector<int> res;
int t = 0;
for (int i = 0; i < A.size(); i ++)
{
t += A[i] * b;
res.push_back(t % 10);
t /= 10;
}
while (t)
{
res.push_back(t % 10);
t /= 10;
}
while (res.size() > 1 && res.back() == 0) res.pop_back();
return res;
}

int main()
{
string a;
int b;
cin >> a >> b;

vector<int> A;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

auto res = mul(A, b);
for (int i = res.size() - 1; i >= 0; i --) cout << res[i];

return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
vector<int> res;
int t = 0;
for (int i = 0; i < A.size() || t; i ++)
{
if (i < A.size()) t += A[i] * b;
res.push_back(t % 10);
t /= 10;
}

while (res.size() > 1 && res.back() == 0) res.pop_back();

return res;
}

int main()
{
string a;
int b;
cin >> a >> b;

vector<int> A;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

auto res = mul(A, b);
for (int i = res.size() - 1; i >= 0; i --) cout << res[i];

return 0;
}


xjtu_zfw
30天前
#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
if (A.size() != B.size()) return A.size() > B.size();

for (int i = A.size() - 1; i >= 0; i --)
if (A[i] != B[i])
return A[i] > B[i];

return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> res;
for (int i = 0, t = 0; i < A.size(); i ++)
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
res.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (res.size() > 1 && res.back() == 0) res.pop_back();

return res;
}

int main()
{
string a, b;
cin >> a >> b;

vector<int> A, B;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');

vector<int> res;
if (cmp(A, B)) res = sub(A, B);
else res = sub(B, A), cout << '-';

for (int i = res.size() - 1; i >= 0; i --) cout << res[i];
cout << endl;

return 0;
}


xjtu_zfw
30天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

{
vector<int> res;

int t = 0;
for (int i = 0; i < A.size() || i < B.size(); i ++)
{
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
res.push_back(t % 10);
t /= 10;
}
if (t) res.push_back(1);

return res;
}

int main()
{
string a, b;
cin >> a >> b;

vector<int> A, B;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');