4_3

1284

zzzgw
tianming
shy_

edgdcgxgbx
HH123_
pikachu_
Promise_You

4_3
4小时前

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

using namespace std;

const int N = 10010;

int n, tt, dd;
int t[N], d[N];

int main()
{
cin >> n;

for (int i = 0; i < n ; i ++)
{
char a;
int b;
cin >> a >> b;
if (a == 'T') t[++ tt] = b;
else d[++ dd] = b;
}
sort(t + 1, t + tt + 1);
sort(d + 1, d + dd + 1);

int x = 1, y = 1;
double s = 0, v = 1, tim = 0;
while (x <= tt && y <= dd)
{
double td = (d[y] - s) * v;
double ts = t[x] - tim;
if (td < ts)
{
s = d[y ++];
tim += td;
v ++;
}
else
{
tim = t[x ++];
s += ts / v;
v ++;
}
}
while (x <= tt)
{
s += (t[x] - tim) / v;
tim = t[x ++];
v ++;
}
while (y <= dd)
{
tim += (d[y] - s) * v;
s = d[y ++];
v ++;
}

tim += (1000 - s) * v + 0.5;
cout << int(tim) << endl;

return 0;

}


4_3
13小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m, s;
int f[N], v[N], w[N];

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

for (int i = 0; i < n; i ++)
{
cin >> v[i] >> w[i] >> s;
for (int j = m; j >= v[i]; j --)
for (int k = 0; k <= s && k * v[i] <= j; k ++)
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}

cout << f[m] << endl;

return 0;
}


4_3
13小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N], f[N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) scanf("%d%d", &v[i], &w[i]);

for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;
}


4_3
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N], v[N], w[N];

int main()
{
scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++) scanf("%d%d", &v[i], &w[i]);

for (int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
/* 保证更新等式左边第i轮f[j]时,等式右边f[j]和f[j-v[i]]是i-1轮算出的,所以j从大到小循环
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i])

j从小到大枚举，更新左边f[j]时，右边j-v[i]比j小，f[j-v[i]]先更新了
f[i][j] = max(f[i-1][j], f[i][j-v[i]]+w[i])
使k=j-v[i], k比j小，更新k时，f[k] = max(f[k], f[k-v[i]]+w[i]),v[i]可能用了两次或更多次
如果i物品价值最大，体积最小，背包里全是它了

*/
/*
f[i][j] = f[i-1][j];

去掉i维度对赋值没影响，f[j] = f[j],更新时，右边的f[j]是i-1循环算出来的

if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
max(f[i-1][j], f[i-1][j-v[i]]+w[i])
上面这个f[i][j]其实也是f[i-1][j],上面那行赋值的

去掉i维度后，保证更新第i轮循环的f[j]时f[j-v[i]]在i轮循环没更新就能保证，f[j-v[i]]就是i-1维度的算出的
j从大到小枚举，更新第i轮的f[j]时，f[j - v[i]]是上一轮i-1循环求出的，也就是f[j-v[i]]==f[i-1][j-v[i]]
*/

printf("%d", f[m]);

return 0;
}



4_3
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 12;

int n, m;       // n行m列   我们铺一个砖头，左边在哪列，哪列的相应行的状态记1
LL f[N][M];     // f[i][j] 表示前i列的所有铺法中，i列摆放j状态的合法铺法有多少种
bool st[M];     // st[j] 表示状态j是否合法，即是否有奇数个连续的0
vector<int> state[M];   // state[j]里存放能和j状态合法插入的所有状态(即互相交叉着插入且没空奇数个空)
// 用vector的妙处,用二维数组存的话state[i][j]还需要记每个i中用到的j有多少个

int main()
{
while (cin >> n >> m, n || m)
{
if (n & m & 1)      // 特判 奇数个格子，蒙德里安的梦想幻灭，从头来过吧
{
puts("0");
continue;
}

// 填充st数组，找出不合法的状态
for (int i = 0; i < 1 << n; i ++)
{
int cnt = 0;    // 表示连续的0的个数
bool is_valid = true;   // 标记状态是否合法
for (int j = 0; j < n; j ++)    // 循环每一行
if (i >> j & 1)         // i >> j & 1,先执行>>再执行&，判断第j行是否是1(即是否有块儿)
{
if (cnt & 1)        // 如果当前行有块儿，同时此行之前有奇数个块儿
{                   // 当前状态不合法，break，
is_valid = false;
break;
}
cnt = 0;            // 当前行有块且之前行有偶数个0，计数归0重新开始记
}
else cnt ++;            // 当前行没块，计数加一
if (cnt & 1) is_valid = false;  // 所有行循环完，判断是否有奇数个尾0躲过判决(之前只是遇到块之后才判决他之前的零)
st[i] = is_valid;           // 终审
}

// 优化的步骤，先计算了与状态i插入并且合法的状态j，放入state[i]中
for (int i = 0; i < 1 << n; i ++)   // 枚举所有状态i
{
state[i].clear();       // 多组数据，先清除state[i]
for (int j = 0; j < 1 << n; j ++)   // 枚举所有状态j
if ((i & j) == 0 && st[i | j])  // (i & j) == 0 如果i和j完美插入(即i的1和j的1分别对应对方的0)
//  st[i | j] 并且插入后的状态合法
state[i].push_back(j);      // 放到state[i]中
}

memset(f, 0, sizeof f);         // 多组数据，初始化数组
f[0][0] = 1;                    // 我们要填满第1列到第m列，第0列不铺
// 第0列只有一种情况f[0][0]，即第0列没有块为状态0

for (int i = 1; i <= m; i ++)   // 循环1到m列
for (int j = 0; j < 1 << n; j ++)   // 循环i列的所有状态
for (auto k: state[j])          // 循环能和i列的状态j合法插入的所有状态k
f[i][j] += f[i - 1][k];
/*
前i-1列合法铺完的所有铺法中，找到能和i列j铺法相适应的铺法(即f[i-1][k])
加到f[i][j]中，表示前i列合法铺完，且第i列用j铺法的所有合法铺法总数
*/
cout << f[m][0] << endl;    // f[m][0] 表示前m列都铺完，且m列不铺的所有合法铺法，即我们要的结果
// 我们铺一个砖头，左边在哪列，哪列的相应行的状态记1，如果m列铺了，砖头必然伸出到m+1列
}

return 0;
}


4_3
2天前

upper_bound: 返回第一个大于等于目标值的下标，不存在返回end
lower_bound: 犯规第一个大于目标值的下标， 不存在返回end

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

using namespace std;

const int N = 1010;

int q[N], n, cnt;

int b_search(int a, int b, int ll, int rr)
{
int l = ll, r = rr;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (b >= q[mid]) l = mid;
else r = mid - 1;
}
b = l;

l = ll, r = rr;
while (l < r)
{
int mid = l + r >> 1;
if (a <= q[mid]) r = mid;
else l = mid + 1;
}
a = l;

return b - a + 1;
}

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

for (int i = 0; i < n; i ++)
scanf("%d", &q[i]);

sort(q, q + n);

for (int i = 1; i < n - 1; i ++)
{
for (int j = 0; j < i; j ++)
{
int c = q[i] - q[j];
if (q[i + 1] - q[i] > c * 2) break;
else if (q[n - 1] - q[i] < c) continue;
else cnt += b_search(q[i] + c, q[i] + 2 * c, 0, n - 1);
//   else cnt += upper_bound(q + i, q + n, q[i] + 2 * c) - lower_bound(q + i, q + n, q[i] + c);
}
}

printf("%d", cnt);

return 0;
}


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

using namespace std;

const int N = 1010;

int a[N], n, cnt;

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

for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);

sort(a, a + n);

for (int i = 1; i < n - 1; i ++)
{
for (int j = 0; j < i; j ++)
{
for (int k = i + 1; k < n; k ++)
{
if (a[k] - a[i] > 2 * (a[i] - a[j])) break;
else if (a[k] - a[i] < a[i] - a[j]) continue;
else cnt ++;
}
}
}

printf("%d", cnt);

return 0;
}


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

using namespace std;

const int N = 1010;

int a[N], n, cnt;

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

for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);

sort(a, a + n);

for (int i = 1; i < n - 1; i ++)
{
for (int j = 0; j < i; j ++)
{
for (int k = i + 1; k < n; k ++)
{
if (a[k] - a[i] > 2 * (a[i] - a[j]) || a[k] - a[i] < a[i] - a[j]) continue;
cnt ++;
}
}
}

printf("%d", cnt);

return 0;
}


4_3
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 40010;

PII ps[N];
int n, X, Y, Z, ans;

int main()
{
scanf("%d%d%d%d", &n, &X, &Y, &Z);

for (int i = 1; i < n * 2; i += 2)
{
int a, b;
scanf("%d%d", &a, &b);
ps[i] = {a, Y - X};
ps[i + 1] = {b + 1, Z - Y};
}

sort(ps + 1, ps + n * 2 + 1);

int res = n * X;
for (int i = 1; i <= n * 2; i ++)
{
res += ps[i].y;
ans = max(ans, res);
}

printf("%d", ans);

return 0;
}


4_3
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 70000;

int n, state, step;
int a[N], g[N];
LL b;

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

for (int i = n - 1; ~i; i --)
{
int x;
cin >> x;
if (x) state += (1 << i);
}

for (int i = 0; i < N; i ++)
{
if (a[state])
{
step = a[state] - 1;
b = (b - step) % (i - step);
break;
}

a[state] = i + 1;
g[i] = state;

state ^= ((state >> 1) | (state & 1) << (n - 1));

}

state = g[step + b];

for (int i = n - 1; ~i; i --)
cout << ((state >> i ) & 1) << endl;

return 0;
}


4_3
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10;
const int M = 1e6 + 10;

int n, k, pre[M];
int id = -1;

int main()
{
scanf("%d%d", &n, &k);

for (int i = 1; i <= n; i ++)
{
int x;
scanf("%d", &x);
if (pre[x] && pre[x] + k >= i)
id = max(id, x);
pre[x] = i;
}

printf("%d", id);

return 0;
}


4_3
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

PII pa[N];
int pe[N], ps[N];
int n, ans;

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
pa[i] = {a, b};
}
sort(pa, pa + n);

ps[0] = pa[0].y;
for (int i = 1; i < n; i ++)
ps[i] = max(ps[i - 1], pa[i].y);

pe[n - 1] = pa[n - 1].y;
for (int i = n - 2; i >= 0; i --)
pe[i] = min(pe[i + 1], pa[i].y);

for (int i = 0; i < n; i ++)
if (ps[i] == pe[i])
ans ++;

printf("%d", ans);

return 0;
}