$\text{SDUT}\&\&\text{SDSSYZX}$

8315

1小时前

## 勿膜，做过原题 QWQ

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int T, n, x, cf[N];
signed main() {
scanf("%d", &T);
while (T --) {
memset(cf, 0, sizeof cf);
scanf("%d", &n);
for (int i = 1; i <= n; i ++) {
scanf("%d", &x);
if (x) {
cf[i + 1] --, cf[max(i - x + 1, 1)] ++;
}
}
for (int i = 1; i <= n; i ++) {
cf[i] += cf[i - 1];
if (cf[i] >= 1) {
printf("1 ");
} else {
printf("0 ");
}
}
puts("");
}
}


2小时前

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int C = 30, MOD = 1e9 + 7;
int t, a[C];
ll ten[C];
struct dp {
ll cnt, sum, sq_sum;
} f[C][C][C];
void ten_mi(){
ten[1] = 1;
for (int i = 2; i <= 18; i ++)
ten[i] =  ten[i-1] * 10 % MOD;
}
dp dfs(int pos, int sum, int cur, bool limit) {
if (!pos) {
int cnt = 0;
if (cur !=  0 && sum != 0) cnt = 1;
return f[pos][sum][cur] = (dp){cnt, 0, 0};
}
if (!limit && f[pos][sum][cur].cnt != -1) return f[pos][sum][cur];
int up = limit? a[pos] : 9;
dp ans{0, 0, 0};
for (int i = 0; i <= up; i ++) {
if (i==7)  continue;
dp tmp = dfs(pos-1, (sum + i) % 7, (cur * 10 + i) % 7,  limit && (i == a[pos]));
int k = i * ten[pos] % MOD;
ans.cnt = (ans.cnt + tmp.cnt) %  MOD;
ans.sum = ((ans.sum + ((tmp.cnt * k) % MOD   +  tmp.sum) % MOD) % MOD) % MOD ;
ans.sq_sum  += tmp.cnt * k % MOD * k % MOD;
ans.sq_sum += tmp.sq_sum % MOD;
ans.sq_sum += 2 * k % MOD * (tmp.sum % MOD) % MOD ;
ans.sq_sum %= MOD;
}
return  limit ? ans : f[pos][sum][cur] = ans;
}
ll solve(ll x) {
int len = 0;
while (x) a[++len] = x % 10, x /= 10;
dp ans = dfs(len, 0, 0, true);
return ans.sq_sum % MOD;
}
int main() {
cin >> t;
ten_mi();
for (int i = 0; i < t; i ++) {
ll l, r;
cin >> l >> r;
memset(f, -1, sizeof f);
int x = solve(r);
int y = solve(l-1);
cout << (x - y + MOD) % MOD << endl;
}
}


#include <bits/stdc++.h>
using namespace std;
int T, l, r;
signed main() {
cin >> T;
while (T --) {
cin >> l >> r;
if (2 * l > r) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}


#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int T, n, x, a[N], b[N];
signed main() {
cin >> T;
while (T --) {
int flag = 0;
cin >> n >> x;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) cin >> b[i];
sort(b + 1, b + 1 + n);
reverse(b + 1, b + 1 + n);
for (int i = 1; i <= n; i ++) {
if (a[i] + b[i] > x) {
flag = 1;
break;
}
}
if (flag) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
}
}


#include <bits/stdc++.h>
using namespace std;
const int N = 30, M = 100, inf = 0x3f3f3f3f;
int T, n, h[N], ne[M], e[M], w[M], idx, dist[N], cnt[N], r[N], num[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(int c) {
memset(h, -1, sizeof h);
idx = 0;
for (int i = 1; i <= 7; i ++) add(i + 16, i, r[i] - c);
for (int i = 8; i <= 24; i ++) add(i - 8, i, r[i]);
for (int i = 1; i <= 24; i ++) {
}
memset(dist, -0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
queue<int> q;
q.push(0);
dist[0] = 0;
while (!q.empty()) {
auto t = q.front();
q.pop();
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] < dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= 25) return 0;
if (!st[j]) {
st[j] = 1;
q.push(j);
}
}
}
}
return 1;
}
signed main() {
cin >> T;
while (T --) {
memset(num, 0, sizeof num);
for (int i = 1; i <= 24; i ++) cin >> r[i];
cin >> n;
for (int i = 0; i < n; i ++) {
int t;
cin >> t;
num[t + 1] ++;
}
int flag = 0;
for (int i = 0; i <= 1000; i ++) {
if (spfa(i)) {
cout << i << endl;
flag = 1;
break;
}
}
if (!flag) cout << "No Solution" << endl;
}
}


#include <bits/stdc++.h>
using namespace std;
int T, n, u1, r1, d1, l1;
bool check(int u, int r, int d, int l) {
if (u < 0 || r < 0 || d < 0 || l < 0){
return 0;
} else if (u > n - 2 || r > n - 2 || d > n - 2 || l > n - 2) {
return 0;
} else {
return 1;
}
}
signed main() {
cin >> T;
while (T --) {
int flag = 0;
cin >> n >> u1 >> r1 >> d1 >> l1;
for (int i = 0; i <= 1 << 4; i ++) {
int u = u1, r = r1, d = d1, l = l1;
for (int j = 0; j < 4; j ++) {
if (i >> j & 1) {
if (j + 1 == 1) {
u --, l --;
} else if (j + 1 == 2) {
u --, r --;
} else if (j + 1 == 3) {
r --, d --;
} else if (j + 1 == 4) {
l --, d --;
}
}
}
if (check(u, r, d, l)) flag = 1;
}
if (flag) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}


#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e5 + 5, inf = 0x3f3f3f3f;
int n, m1, m2, u, v, c, h[N], e[M], ne[M], w[M], idx, dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(int s) {
memset(cnt, 0, sizeof cnt);
memset(dist, 0x3f, sizeof dist);
queue<int> q;
for (int i = 1; i <= s; i ++) {
q.push(i);
dist[i] = 0;
}
while(!q.empty()) {
auto t = q.front();
q.pop();
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return 1;
if (!st[j]) {
q.push(j);
st[j] = 1;
}
}
}
}
return 0;
}
signed main() {
memset(h, -1 ,sizeof h);
cin >> n >> m1 >> m2;
for (int i = 1; i < n; i ++) add(i + 1, i, 0);
while (m1 --) {
cin >> u >> v >> c;
}
while (m2 --) {
cin >> u >> v >> c;
}
if (spfa(n)) {
cout << -1 << endl;
} else {
spfa(1);
if (dist[n] == inf) {
cout << -2 <<endl;
} else {
cout << dist[n] << endl;
}
}
}


#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a, b, c, m, h[N], e[N], ne[N], w[N], idx, dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa() {
memset(dist, -0x3f, sizeof dist);
dist[0] = 0;
queue<int> q;
q.push(0);
while(!q.empty()) {
auto t = q.front();
q.pop();
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] < dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
st[j] = 1;
q.push(j);
}
}
}
}
}
signed main() {
memset(h, -1, sizeof h);
cin >> m;
for (int i = 1; i <= 5e4 + 5; i ++) {
}
while (m --) {
cin >> a >> b >> c;
a ++, b ++;
}
spfa();
cout << dist[50001] << endl;
}


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5;
int n, m, h[N], ne[N], e[N], w[N], idx, cnt[N], x, a, b;
LL dist[N], res;
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa() {
stack<int> s;
memset(dist, -0x3f, sizeof dist);
dist[0] = 0;
s.push(0);
while (!s.empty()) {
auto t = s.top();
s.pop();
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] < dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] > n) return 0;
if (!st[j]) {
st[j] = 1;
s.push(j);
}
}
}
}
return 1;
}
signed main() {
memset(h, -1, sizeof h);
cin >> n >> m;
while (m --) {
cin >> x >> a >> b;
if (x == 1) {
} else if (x == 2) {
} else if (x == 3) {
} else if (x == 4) {
} else {
}
}
for (int i = 1; i <= n; i ++) add(0, i, 1);
if (!spfa()) {
cout << -1 << endl;
} else {
for (int i = 1; i <= n; i ++) res += dist[i];
cout << res << endl;
}
}