146

fml4d1

19小时前
#include <iostream>
using namespace std;
const int N = 100005;
int n, m;
int a[N], d[N];

void insert(int l, int r, int c) {
d[l] += c;
d[r + 1] -= c;
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = a[i] - a[i - 1];
}
for (int i = 0; i < m; i++) {
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + d[i];
cout << a[i] << ' ';
}
cout << endl;
return 0;
}


20小时前
#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> PII;
char A[1005][1005];
int B[1005][1005];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

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

queue<PII> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i][j] == '1') {
q.push({i, j});
}
}
}

while (!q.empty()) {
auto cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x_ = cur.first + dx[i], y_ = cur.second + dy[i];
if (x_ >= 0 && x_ < n && y_ >= 0 && y_ < m && B[x_][y_] == 0 && A[x_][y_] == '0') {
B[x_][y_] = B[cur.first][cur.second] + 1;
q.push({x_, y_});
}
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << B[i][j] << ' ';
}
cout << endl;
}
return 0;
}


22小时前

f(n, k): 人数为 n，间隔为 k 时死掉的人的序号

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

int a[1005];

int main(){
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n, m;
cin >> n >> m;
for (int j = 0; j < m; j++) {
cin >> a[j];
}

int f = 0;
for (int u = 2; u <= n; u++) {
int k = (n - u) % m;
f = (f + a[k]) % u;
}
cout << f << endl;
}
return 0;
}


#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 100005, M = 18;
PII vals[N];
string num;
int k, n;

int w[N];
int f[N][M];

void init() {
for (int j = 0; j < M; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = w[i];
else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}

int query(int l, int r) {
int len = r - l + 1;
int k = log(len) / log(2);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}

int bsearch(PII q[], int k, int p) {
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (q[mid].first >= k) {
r = mid;
} else {
l = mid + 1;
}
}
int st = l;
r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (q[mid].first < k + 1) {
l = mid;
} else {
r = mid - 1;
}
}
int ed = l;
while (st < ed) {
int mid = st + ed >> 1;
if (q[mid].second >= p) {
ed = mid;
} else {
st = mid + 1;
}
}
return q[st].second;
}

int main() {
cin >> num;
cin >> k;
n = num.length();
int remain = n - k;
int p = 1, q = n - remain + 1;

for (int i = 1; i <= n; i++) {
vals[i] = {num[i - 1] - '0', i};
w[i] = num[i - 1] - '0';
}

sort(vals + 1, vals + n + 1);

init();

string res;
for(int i = 1; i <= remain; i++) {
int minval = query(p, q);
p = bsearch(vals, minval, p) + 1;
if (res.length() != 0 || minval != 0) {
res += minval + '0';
}
q ++;
}
if (res.length() == 0) {
res = "0";
}
cout << res << endl;

return 0;
}


#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 100005, M = 18;
PII vals[N];
string num;
int k, n;

int w[N];
int f[N][M];

void init() {
for (int j = 0; j < M; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = w[i];
else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}

int query(int l, int r) {
int len = r - l + 1;
int k = log(len) / log(2);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}

int bsearch(PII q[], int k, int p) {
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (q[mid].first >= k) {
r = mid;
} else {
l = mid + 1;
}
}
int st = l;
r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (q[mid].first < k + 1) {
l = mid;
} else {
r = mid - 1;
}
}
int ed = l;
while (st < ed) {
int mid = st + ed >> 1;
if (q[mid].second >= p) {
ed = mid;
} else {
st = mid + 1;
}
}
return q[st].second;
}

int main() {
cin >> num;
cin >> k;
n = num.length();
int remain = n - k;
int p = 1, q = n - remain + 1;

for (int i = 1; i <= n; i++) {
vals[i] = {num[i - 1] - '0', i};
w[i] = num[i - 1] - '0';
}

sort(vals + 1, vals + n + 1);

init();

string res;
for(int i = 1; i <= remain; i++) {
int minval = query(p, q);
p = bsearch(vals, minval, p) + 1;
if (res.length() != 0 || minval != 0) {
res += minval + '0';
}
q ++;
}
if (res.length() == 0) {
res = "0";
}
cout << res << endl;

return 0;
}


3个月前
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int N, W;
int C[20];
int w[20];
int ans = INT_MAX;

bool cmp (int& a, int& b) {
return a > b;
}

void dfs(int cid, int num) {
if (num >= ans) {
return;
}
if (cid > N) {
ans = min(num, ans);
return;
}

for(int i = 0; i < num; i++) {
if (w[i] + C[cid] > W) {
continue;
}
w[i] += C[cid];
dfs(cid + 1, num);
w[i] -= C[cid];
}

w[num] += C[cid];
dfs(cid + 1, num + 1);
w[num] -= C[cid];

}

int main() {
cin >> N >> W;
for(int i = 0; i < N; i++) {
cin >> C[i];
}

sort(C, C + N, cmp);

dfs(0, 0);

cout << ans << endl;

return 0;
}


3个月前
#include <iostream>
#include <queue>
#include <bitset>
using namespace std;

int N, M;
int tot;
int A[30005];
int deg[30005];
bitset<30005> f[300005];

void add(int x, int y) {
ver[++tot] = y;
}

void topo() {
int id = 0;
queue<int> Q;

for(int i = 1; i <= N; i++) {
if (deg[i] == 0) {
Q.push(i);
}
}

while(!Q.empty()) {
int t = Q.front();
Q.pop();
A[++id] = t;
for(int i = head[t]; i; i = ne[i]) {
int v = ver[i];
if (--deg[v] == 0) {
Q.push(v);
}
}
}
}

int main() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
deg[y] ++;
}

topo();

for (int i = N; i >= 1; i--) {
int u = A[i];
f[u][u] = 1;
for (int j = head[u]; j; j = ne[j]) {
f[u] |= f[ver[j]];
}
}

for (int i = 1; i <= N; i++) {
cout << f[i].count() << endl;
}

return 0;
}


4个月前
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct U {
public:
int i1, i2, v1, v2;
U(int i1, int i2, int v1, int v2):i1(i1), i2(i2), v1(v1), v2(v2){}

};

bool operator<(const U& a, const U& b) {
return a.v1 + a.v2 > b.v1 + b.v2;
}

void compute(vector<int>& a, vector<int>& b) {
sort(a.begin(), a.end());
priority_queue<U> q;

int n = a.size();

vector<int> c;

for(int i = 0; i < n; i++) {
q.push(U(0, i, a[0], b[i]));
}

for(int i = 0; i < n; i++) {
auto u = q.top();
c.push_back(u.v1 + u.v2);
q.pop();
if (i != n - 1) {
q.push(U(u.i1 + 1, u.i2, a[u.i1 + 1], b[u.i2]));
}
}

b.swap(c);
}

int main() {
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++) {
int m, n;
scanf("%d %d", &m, &n);
vector<vector<int>> a;
for(int j = 0; j < m; j++) {
a.push_back(vector<int>());
for(int k = 0; k < n; k++) {
int num;
scanf("%d", &num);
a[j].push_back(num);
}
}

if (m > 1) {
for(int j = 0; j < m - 1; j++) {
compute(a[j], a[j + 1]);
}
}
else {
sort(a[0].begin(), a[0].end());
}

for(int j = 0; j < n; j++) {
printf("%d ", a[m - 1][j]);
}
printf("\n");

}
return 0;
}


4个月前
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

struct cmp {
public:
bool operator()(const PII& a, const PII& b) {
return a.second > b.second;
}
};

bool cmp2(const PII& a, const PII& b) {
if (a.first != b.first) {
return a.first < b.first;
} else {
return a.second > b.second;
}
}

int main() {
int n;
while (scanf("%d", &n) != -1) {
priority_queue<PII, vector<PII>, cmp> q;
vector<PII> a;
for (int i = 0; i < n; i++) {
int p, d;
scanf("%d %d", &p, &d);
a.push_back(PII(d, p));
}
sort(a.begin(), a.end(), cmp2);

for(int i = 0; i < n; i++) {
if(a[i].first > q.size()) {
q.push(a[i]);
} else if(a[i].second > q.top().second){
q.pop();
q.push(a[i]);
}
}
int ans = 0;
while(!q.empty()) {
ans += q.top().second;
q.pop();
}
printf("%d\n", ans);
}
return 0;
}


4个月前
#include <cstdio>
#include <deque>
#include <algorithm>
#include <limits.h>
using namespace std;

int m, n;
int s[300005];
deque<int> q;

int main() {

scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
int tmp = 0;
scanf("%d", &tmp);
s[i] = s[i - 1] + tmp;
}

int i = 1, j = 1, ans = INT_MIN;

while (j <= m) {
while(!q.empty() && q.back() < s[j]) {
q.pop_back();
}
q.push_back(s[j]);
ans = max(ans, q.front() - s[i - 1]);
j++;
}

while (j <= n) {
if (q.front() == s[i]) {
q.pop_front();
}
while(!q.empty() && q.back() < s[j]) {
q.pop_back();
}
q.push_back(s[j]);
i++, j++;
ans = max(ans, q.front() - s[i - 1]);
}

while (i < n) {
if (q.front() == s[i]) {
q.pop_front();
}
i++;
ans = max(ans, q.front() - s[i - 1]);
}
printf("%d\n", ans);

return 0;
}