Yipxx

183

Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 2e9;

int n;
int p[N];

int main()
{
cin >> n;
p[0] = -INF, p[n + 1] = INF;
for (int i = 1; i <= n; i ++ ) cin >> p[i];
sort(p + 1, p + n + 1);

int res = 0;
for (int i = 1; i <= n; i ++ )
{
int l = 1, r = 1, a = i, b = i;
while (p[a] - p[a - 1] <= l)
{
int k = a - 1;
while (p[a] - p[k - 1] <= l) k -- ;
a = k;
l ++ ;
}
while (p[b + 1] - p[b] <= r)
{
int k = b + 1;
while (p[k + 1] - p[b] <= r) k ++ ;
b = k;
r ++ ;
}

res = max(res, b - a + 1);
}

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


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

unordered_map<char, int> cnt[2];
while (n -- )
{
char c;
int x;
cin >> c >> x;
cnt[abs(x) % 2][c] ++ ;
}

char str[] = "BESIGOM";

int res = 0;
unordered_map<char, int> v;
for (int i = 0; i < 1 << 7; i ++ )
{
for (int j = 0; j < 7; j ++ )
v[str[j]] = i >> j & 1;

if ((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M'] % 2 == 0)
{
int sum = 1;
for (int j = 0; j < 7; j ++ )
sum *= cnt[i >> j & 1][str[j]];
res += sum;
}
}

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


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
string s;

int main()
{
cin >> n >> s;

LL a = 0, b = 0, c = 0;
for (auto ch: s)
{
if (ch == 'C')
a ++ ;
else if (ch == 'O')
b += a;
else
c += b;
}
cout << c << endl;

return 0;
}


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 2e9;

int n;
int v[N];

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
scanf("%*d%d", &v[i]);    //%*d：跳过一个数

int res = 0, vmin = INF;
for (int i = n - 1; i >= 0; i -- )
{
if (v[i] <= vmin)
res ++ ;
vmin = min(vmin, v[i]);
}
cout << res << endl;

return 0;
}


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;

int n;
PII q[N];

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
int x;
char c;
cin >> x >> c;
if (c == 'G')
q[i] = {x, 1};
else
q[i] = {x, -1};
}
sort(q, q + n);

unordered_map<int, int> hash;

int res = 0, sum = 0, last;
for (int i = 0; i < n; i ++ )
{
if (!hash.count(sum)) hash[sum] = q[i].x;
sum += q[i].y;
if (hash.count(sum)) res = max(res, q[i].x - hash[sum]);

if (i == 1 || q[i].y != q[i - 1].y) last = q[i].x;
res = max(res, q[i].x - last);
}

printf("%d\n", res);
return 0;
}


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y, int d)
{
if (x < 0 || x >= n || y < 0 || y >= m)
return 0;

if (g[x][y] == '/')
d ^= 1;
else
d ^= 3;

return dfs(x + dx[d], y + dy[d], d) + 1;
}

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
cin >> g[i];

int res = 0;
for (int i = 0; i < n; i ++ )
{
res = max(res, dfs(i, 0, 1));
res = max(res, dfs(i, m - 1, 3));
}

for (int i = 0; i < m; i ++ )
{
res = max(res, dfs(0, i, 2));
res = max(res, dfs(n - 1, i, 0));
}

cout << res << endl;

return 0;
}


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010;

int n;
vector<int> a, b;

int main()
{
cin >> n;

char c;
int x;
while (n -- )
{
cin >> c >> x;
if (c == 'T')
a.push_back(x);
else
b.push_back(x);
}

b.push_back(1000);
sort(a.begin(), a.end());
sort(b.begin(), b.end());

double t = 0, s = 0, v = 1;    //v是速度的倒数
int i = 0, j = 0;
while (i < a.size() || j < b.size())
{
if (j == b.size() || i < a.size() && a[i] - t < (b[j] - s) * v)
{
s += (a[i] - t) / v;
t = a[i];
v ++ ;
i ++ ;
}
else
{
t += (b[j] - s) * v;
s = b[j];
v ++ ;
j ++ ;
}
}
printf("%.0lf\n", t);

return 0;
}


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, k;
PII q[N];

int main()
{
cin >> n >> k;
for (int i = 0; i < n; i ++ )
cin >> q[i].y >> q[i].x;

sort(q, q + n);

int res = 0, sum = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
sum += q[i].y;
while (q[i].x - q[j].x > 2 * k)
sum -= q[j ++ ].y;
res = max(res, sum);
}
cout << res << endl;

return 0;
}


Yipxx
6个月前

#### 写法1：map

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

using namespace std;

const int INF = 2e9;

int n, x, y, z;

int main()
{
map<int, int> b;
cin >> n >> x >> y >> z;
for (int i = 0; i < n; i ++ )
{
int l, r;
cin >> l >> r;
b[-INF] += x;
b[l] += y - x;
b[r + 1] += z - y;
b[INF] -= z;
}
int res = 0, sum = 0;
for (auto [x, y]: b)
{
sum += y;
res = max(res, sum);
}
cout << res << endl;

return 0;
}


#### 手写离散化

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

using namespace std;

const int N = 20010, INF = 2e9;

int n, x, y, z;
vector<int> xs;
int l[N], r[N], b[N * 2];

int find(int v)
{
int l = 0, r = xs.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (xs[mid] >= v) r = mid;
else l = mid + 1;
}
return r;
}

int main()
{
scanf("%d%d%d%d", &n, &x, &y, &z);

xs.push_back(-INF), xs.push_back(INF);
for (int i = 0; i < n; i ++ )
{
scanf("%d%d", &l[i], &r[i]);
xs.push_back(l[i]);
xs.push_back(r[i] + 1);
}

sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

for (int i = 0; i < n; i ++ )
{
int L = find(l[i]), R = find(r[i] + 1);
b[0] += x;
b[L] += y - x;
b[R] += z - y;
b[xs.size() - 1] -= z;
}

int res = 0, sum = 0;
for (int i = 0; i < xs.size(); i ++ )
{
sum += b[i];
res = max(res, sum);
}

printf("%d\n", res);
return 0;
}


Yipxx
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1 << 16;

int n;
LL m;
int p[N];    //记录每个状态是第几步走到的

int update(int state)
{
int res = 0;
for (int i = 0; i < n; i ++ )
{
int j = (i - 1 + n) % n;    //找到上一位
int x = state >> i & 1, y = state >> j & 1;
res |= (x ^ y) << i;
}
return res;
}

void print(int state)
{
for (int i = 0; i < n; i ++ )
cout << (state >> i & 1) << endl;
}

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

int state = 0;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
state |= x << i;
}

memset(p, -1, sizeof p);
p[state] = 0;

for (int i = 1; ; i ++ )
{
state = update(state);
if (i == m)
{
print(state);
break;
}
else if (p[state] == -1)
p[state] = i;
else
{
int len = i - p[state];
int r = (m - i) % len;
while (r -- )
state = update(state);
print(state);
break;
}
}
return 0;
}