188

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int cows[N];
double sum[N];
int n, f;
bool check(double avg)
{
for (int i = 1; i <= n; i++ ) //初始前缀和减平均值
sum[i] = sum[i - 1] + cows[i] - avg;
double minv = 0;
for (int i = 0, j = f; j <= n; i ++ , j ++ )
{
minv = min(minv, sum[i]); //记录最小值
if (sum[j] - minv >= 0) return true;
}
return false;
}
int main()
{
cin >> n >> f;
double l = 0, r = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> cows[i];
r = max(r, (double)cows[i]); //设定二分初始右边界
}
while (r - l > 1e-6)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d\n", (int)(r * 1000));
return 0;
}

10天前
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int n, m, p, h;
int s[N];

int main()
{
cin >> n >> p >> h >> m;
set<pair<int, int>> existed;
s[1] = h;
for (int i = 1, a, b; i <= m; i ++ )
{
cin >> a >> b;
if (a > b) swap(a, b);
if (!existed.count({a, b}))
{
existed.insert({a, b});
s[a + 1] -- , s[b] ++ ;
}
}
for (int i = 1; i <= n; i ++ )
{
s[i] += s[i - 1];
cout << s[i] << endl;
}
return 0;
}

10天前
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL n, pos, neg;
LL a[N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = n; i > 0; i -- ) a[i] = a[i] - a[i - 1];
for (int i = 2; i <= n; i ++ )
if (a[i] > 0)
pos += a[i];
else if (a[i] < 0)
neg -= a[i];
cout << max(neg, pos) << endl;
cout << abs(neg - pos) + 1 << endl;
return 0;
}

11天前
#include <iostream>
using namespace std;
const int N = 5e3 + 10;
int s[N][N];
int m = 5001;

int main()
{
int cnt, r;
cin >> cnt >> r;
r = min(r, 5001);

while (cnt -- )
{
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
x ++ , y ++ ;
s[x][y] += w;
}

for (int i = 1;  i <= m; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

int res = 0;
for (int i = r; i <= m; i ++ )
for (int j = r; j <= m; j ++ )
res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);

cout << res << endl;
return 0;
}

13天前
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
int n;

PLL calc(LL n, LL m)
{
if (n == 0) return {0, 0};
LL len = 1ll << (n - 1);
LL cnt = 1ll << (2 * n - 2);
PLL pos = calc(n - 1, m % cnt);
int z = m / cnt;
LL x = pos.first, y = pos.second;
if (z == 0) return {y - len, x - len};
if (z == 1) return {x - len, y + len};
if (z == 2) return {x + len, y + len};
if (z == 3) return {-y + len, -x - len};
}

int main()
{
cin >> n;
while (n -- )
{
LL A, B, N;
cin >> N >> A >> B;
PLL da = calc(N, A - 1);
PLL db = calc(N, B - 1);
double dx = da.first - db.first, dy = da.second - db.second;
printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 5);
}
}

14天前

acwing98 分形之城
y总代码中z==3这一步 类似于z=0，1，2都是平移旋转 为何z=3时的坐标变换 多了减1。

y总的AC代码：

PLL calc(LL n, LL m)
{
if (!n) return {0, 0};
LL len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
auto pos = calc(n - 1, m % cnt);
auto x = pos.first, y = pos.second;
auto z = m / cnt;
if (z == 0) return {y, x};
if (z == 1) return {x, y + len};
if (z == 2) return {x + len, y + len};
return {len * 2 - 1 - y, len - x - 1}; //<-------------这一步
}

14天前
#include <iostream>
using namespace std;
const int mod = 9901;
int A, B;

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

int sum(int p, int k)
{
if (k == 0) return 1;
if (k % 2 == 0) return (p % mod * sum(p, k - 1) % mod + 1) % mod;
else return sum(p, k / 2) % mod * (1 + qmi(p, k / 2 + 1)) % mod;//奇数向下取整 k / 2 + 1 + k / 2 = k
}

int main()
{
cin >> A >> B;
int res = 1;
for (int i = 2; i <= A / i; i ++ )
{
int s = 0;
while (A % i == 0)
{
s ++ ;
A /= i;
}
if (s) res = res * sum(i, s * B) % mod;
}
if (!A) res = 0;
if (A > 1) res = res * sum(A, B) % mod;
cout << res << endl;
return 0;
}

16天前
#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
int main()
{
int d[N], f[N];
d[1] = 1;
memset(f, 0x3f, sizeof f);
for (int i = 2; i <= 12; i ++ )
{
d[i] = d[i - 1] * 2 + 1;
}
f[0] = 0;
for (int i = 1; i <= 12; i ++ )
{
for (int j = 0; j < i; j ++ )
f[i] = min(f[i], f[j] * 2 + d[i - j]);
cout << f[i] << endl;
}
return 0;
}

16天前
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 100000;
char g[10][10];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
void turn(int x, int y){
for (int i = 0; i < 5; i ++ ){
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 5 && b >= 0 && b < 5)
g[a][b] = '0' + !(g[a][b] - '0');
}
}
int work(){
int ans = INF;
for (int k = 0; k < 1 << 5; k ++ ){
int res = 0;
char backup[10][10];
memcpy(backup, g, sizeof g);
for (int j = 0; j < 5; j ++ ){
if (k >> j & 1) res ++ , turn(0, j);
}
for (int i = 0; i < 4; i ++ )
for (int j = 0; j < 5; j ++ )
if (g[i][j] == '0')
res ++ , turn(i + 1, j);
bool is_successful = true;
for (int j = 0; j < 5; j ++ )
if (g[4][j] == '0'){
is_successful = false;
break;
}
if (is_successful) ans = min(ans, res);
memcpy(g, backup, sizeof g);
}
if (ans > 6) return -1;
return ans;
}
int main(){
int T;  cin >> T;
while (T -- ){
for (int i = 0; i < 5; i ++ ) cin >> g[i];
cout << work() << endl;
}
return 0;
}

20天前
#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> path;

void dfs(int u, int state)
{
if (u == n)
{
for (auto x : path)
cout << x << ' ';
cout << endl;
return;
}
for (int i = 0; i < n; i ++ )
//搜索顺序区别于前两题 前两题枚举的是是否选择这个数
//本题枚举的是该位置是否有数
if (!(state >> i & 1))
{
path.push_back(i + 1);
dfs(u + 1, state | 1 << i);
path.pop_back();
}
}
int main()
{
cin >> n;
dfs(0, 0);
return 0;
}