你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
如果只一个点自环,那对于“被除自己之外的”这句话就错了吧?
洛谷上相同的题
题目链接 1134. 最短路计数
else if (dist[j] == dist[t] + 1)
{
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
请问这表示的是什么情况?
#include <cstdio>
typedef long long LL;
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, p;
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", qadd(a, b, p));
return 0;
}
#include <iostream>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p) {
LL ans = 1 % p;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * (LL)a % p;
b >>= 1;
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
while (n --) {
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
printf("%lld\n", qmi(a, b, p));
}
}
/*
f[i][j] 表示以i开始的长度为2^j的区间最大值
*/
#include <bits/stdc++.h>
#define md(x, y) ((x + y) >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 10;
int f[MAXN][20], n, m, a[MAXN];
void init()
{
for(int i = 0; i < 20; i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
if(!i) f[j][i] = a[j];
else f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
}
int query(int l, int r)
{
int len = r - l + 1;
int k = log2(len);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
init();
cin >> m;
while(m--)
{
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}
/*
*/
#include <bits/stdc++.h>
#define md(x, y) ((x + y) >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 10;
ll a[MAXN], c[MAXN], n;
typedef pair<int, int> P;
P b[MAXN];
int lowbit(int x)
{
return x & (-x);
}
ll query(int x)
{
ll ret = 0;
for(int i = x; i > 0; i -= lowbit(i))
ret += c[i];
return ret;
}
void update(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i))
c[i] += k;
}
int main()
{
while(cin >> n, n)
{
for(int i = 1, x; i <= n; i++) cin >> x, b[i] = {x, i};
sort(b + 1, b + 1 + n);
memset(c, 0, sizeof c);
ll res = 0;
for(int i = n; i >= 1; i--)
{
int x = b[i].second;
res += query(x);
update(x, 1);
}
cout << res << endl;
}
return 0;
}
/*
down 存的是低部
*/
#include <bits/stdc++.h>
#define md(x, y) ((x + y) >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;
vector<int> vec;
priority_queue<int> down;
priority_queue<int, vector<int>, greater<int>> up;
void update()
{
int a = up.size(), b = down.size();
if(b > a + 1)
{
int u = down.top();
down.pop();
up.push(u);
}
else if(a > b)
{
int u = up.top();
up.pop();
down.push(u);
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
while(up.size()) up.pop();
while(down.size()) down.pop();
vec.clear();
int kase, n;
cin >> kase >> n;
for(int i = 1; i <= n; i++)
{
int u;
cin >> u;
if(i == 1)
{
vec.push_back(u);
down.push(u);
continue;
}
int x = down.top();
if(u >= x) up.push(u);
else down.push(u);
update();
if(i % 2)
vec.push_back(down.top());
}
cout << kase <<" "<< (n + 1) / 2 << endl;
for(int i = 1; i <= vec.size(); i++)
{
printf("%d ", vec[i - 1]);
if(i % 10 == 0)
printf("\n");
}
if(vec.size() % 10)
printf("\n");
}
return 0;
}