schinapi

schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
#include<set>
using namespace std;

const int N = 1e5 + 10;
int a[N], tr[N], ans[N];
int n;

int lowbit(int x)
{
return x & -x;
}
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

int main()
{
cin >> n;
for (int i = 2; i <= n; i ++) cin >> a[i];

for (int i = 1; i <= n; i ++) tr[i] = lowbit(i);//初始化；

for (int i = n; i; i --)
{
int k = a[i] + 1;

int l = 1, r = n;
while(l < r)
{
int mid = l + r >> 1;
if (sum(mid) >= k) r = mid;
else l = mid + 1;
}
ans[i] = l;
}
for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

blablabla


### 算法2

blablabla

#### C++ 代码

#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, m;

LL a[N], tr[N], tri[N];

int lowbit(int x)
{
return x & -x;
}

{
for (int i = x; i <= n; i += lowbit(i))
{
tr[i] += c;
tri[i] += c * x;
}
}

LL sum(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i] * (x + 1) - tri[i];
return res;
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) add(i, a[i] - a[i - 1]);

while(m --)
{
char op[2];
int l, r, c;
scanf("%s%d%d", op, &l, &r);
if(*op == 'Q')
{
cout << sum(r) - sum(l - 1) << endl;
}
else
{
scanf("%d", &c);
}
}
return 0;
}



schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

//对纵坐标y用线段树

#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
const int N = 200010;
int a[N], tr[N], lower[N], bigger[N];
int n;

int lowbit(int x)
{
return x & -x;
}

{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)//查询某一段的和
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];

for (int i = 1; i <= n; i ++)
{
int y = a[i];
bigger[i] = sum(n) - sum(y);
lower[i] = sum(y - 1);
}

memset(tr, 0, sizeof tr);
LL res1 = 0, res2 = 0;//赋初值；

for (int i = n; i; i --)
{
int y = a[i];
res1 += bigger[i] * (LL)(sum(n) - sum(y));
res2 += lower[i] * (LL)sum(y - 1);
}
cout << res1 << " " << res2 << endl;
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

const int N = 2000010;

struct query{
int a, b, type;
} query[N];
int p[N];
unordered_map<int, int> h;
int cnt, n;

int find(int x)
{
if (x != p[x])  p[x] = find(p[x]);
return p[x];
}
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%d", &n);
cnt = 0;
h.clear();
for (int i = 0; i < n; i ++)
{
int a, b, e;
scanf("%d%d%d", &a, &b, &e);

if (!h.count(a)) h[a] = ++ cnt;
if (!h.count(b)) h[b] = ++ cnt;

query[i] = {h[a], h[b], e};
}

for (int i = 1; i <= cnt; i ++) p[i] = i;

for (int i = 0; i < n; i ++)
if (query[i].type == 1)
p[find(query[i].a)] = find(query[i].b);

bool flag = true;
for (int i = 0; i < n; i ++)
{
if (query[i].type == 0 && find(query[i].a) == find(query[i].b))
{
flag = false;
break;
}
}

if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
using namespace std;

const int N = 10010;

int p[N];
int cost[N], w[N];
int f[N];
int n, m, k;

int find(int a)
{
if (p[a] != a) p[a] = find(p[a]);
return p[a];
}
int main()
{
cin >> n >> m >> k;

for (int i = 1; i <= n; i ++) p[i] = i;

for (int i = 1; i <= n; i ++)
{
int a, b;
cin >> a >> b;
cost[i] = a, w[i] = b;
}
for (int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
w[b] += w[a];
cost[b] += cost[a];
}
}
int res = 0;

for (int i = 1; i <= n; i ++)
if (p[i] == i)
{
for (int j = k; j >= cost[i]; j --)
f[j] = max(f[j - cost[i]] + w[i], f[j]);
}
cout << f[k] << endl;

return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 205;
int p[N * N] ;
int n, m;

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n * n; i ++) p[i] = i;
for (int i = 1; i <= m; i ++)
{
int x, y;
char c;
cin >> x >> y >> c;
int a = (x - 1) * n + y;
int b;
if (c == 'D') b = x * n + y;
else b = (x - 1) * n + y + 1;

//cout << a << " " << b << endl;

a = find(a), b = find(b);
if (a == b)
{
cout << i;
return 0;
}
p[a] = b;
}
cout << "draw";
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

blablabla


### 算法2

blablabla

#### C++ 代码

//m^n - m * (m - 1)^(n - 1);

#include<iostream>
using namespace std;

const int mod = 100003;

int qmi(int a, long long b)
{
int res = 1;
while(b)
{
if (b & 1) res = res * 1ll * a % mod;
a = a * 1ll * a % mod;
b >>= 1;
}
return res;
}

int main()
{
int m;
long long n;
cin >> m >> n;

cout << (qmi(m, n) - m * 1ll * qmi(m - 1, n - 1) % mod + mod) % mod;
return 0;
}


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
using namespace std;

const int mod = 200907;

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

int main()
{
int T;
cin >> T;
while(T --)
{
int a1, a2, a3, k;
cin >> a1 >> a2 >> a3 >> k;
if (a2 - a1 == a3 - a2)
cout << (a1 + (a2 - a1) * 1ll * (k - 1)) % mod << endl;
else  cout << qmi(a2 / a1, k - 1) % mod * a1 % mod << endl;
}
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
using namespace std;
const int N = 1000010;

int n;
int primes[N], cnt;
bool st[N];

void init(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] * i <= n; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}

int main()
{
cin >> n;
init(n);
//枚举每一个质数；
for (int i = 0; i < cnt; i ++)
{
int p = primes[i], c = 0;
long long  base = p;
//for (int j = n; j; j /= p) c += j / p;

while(base <= n)
{
c += n / base;
base *= p;
}
cout << p << " " << c << endl;
}
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla


schinapi
3个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

blablabla

#### C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n)
{
memset(st, 0, sizeof st);
cnt = 0;
for (int i = 2; i <= n; i ++)
{
if (!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] * i <= n; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}

int main()
{
int l, r;
while(cin >> l >> r)
{
init(50000);
memset(st, 0, sizeof st);

for (int i = 0; i < cnt; i ++)
{
LL p = primes[i];
for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
st[j - l] = true;
}

cnt = 0;
for (int i = 0; i <= r - l; i ++)
{
if (!st[i] && i + l >= 2)
primes[cnt ++] = i + l;
}

if (cnt < 2) puts("There are no adjacent primes.");
else
{
int maxv = 0, minv = 0;
for (int i = 0; i + 1 < cnt; i ++)
{
int d = primes[i + 1] - primes[i];
if (d > primes[maxv + 1] - primes[maxv]) maxv = i;
if (d < primes[minv + 1] - primes[minv]) minv = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n", primes[minv], primes[minv + 1], primes[maxv], primes[maxv + 1]);
}
}
return 0;
}


### 算法2

blablabla

#### C++ 代码

blablabla