zdw

1.4万

zdw
5天前
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 7;
int dp[2][maxn], q[maxn]; // dp 为滚动数组， q为优先队列辅助数组
#define calc(t,i) (dp[t^1][q[i]]+((k-q[i])/v)*w)
int main() {
int n, m;
cin >> n >> m;
int t = 0;
for (int i = 1; i <= n; i++) {
int v, w, s;
scanf("%d %d %d", &v, &w, &s);
t ^= 1; //数组滚动
for (int j = 0; j < v; j++) {
int l = 1, r = 0;
for (int k = j ; k <= m; k += v) {
while (l <= r && (k-q[l])/v > s) l++; // 排除太远的
if(l<=r) dp[t][k] = max(dp[t^1][k], calc(t,l));
while (l <= r && dp[t ^ 1][q[r]] - (q[r] - j) / v * w <= dp[t ^ 1][k] - (k - j) / v * w) r--;//消除距离影响
q[++r] = k;
}
}
}
cout << dp[t][m] << endl;
return 0;
}



zdw
27天前

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 5;
int f[N][3];

int main() {
int n;
cin >> n;
f[0][1] = -0x3f3f3f3f3f;
int x;
for (int i = 1; i <= n; i++) {
cin >> x;
f[i][0] = max(f[i - 1][0], f[i - 1][2]);
f[i][1] = max(f[i - 1][1], f[i - 1][0] - x);
f[i][2] = f[i - 1][1] + x;
}
cout << max(f[n][0], f[n][2]) << endl;
return 0;
}


zdw
27天前

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 5;
int f[N][107][2]; // 可以像背包一样省略一维

int main() {
int n, m;
cin >> n >> m;
memset(f, -0x3f, sizeof f);
for (int i = 0; i <= n; i++) {
f[i][0][0] = 0;
}

int x;
for (int i = 1; i <= n; i++) {
cin >> x;
for (int j = 1; j <= m; j++) {
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + x);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - x);
}
}
int res = 0;
for (int i = 1; i <= m; i++) res = max(res, f[n][i][0]);
cout << res << endl;
return 0;
}


zdw
1个月前
#include <cstring>
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int arr[N], f[N];

// 普通解法 f[i] = max(f[i], f[i - 2] + arr[i])
int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
memset(f, 0, sizeof f);
for (int i = 2; i <= n + 1; i++) {
cin >> arr[i];
f[i] = max(f[i - 1], f[i - 2] + arr[i]);
}
cout << f[n + 1] << endl;
}
return 0;
}

#include <cstring>
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int arr[N], f[N][2];

// 状态机解法 0表示不选，1表示选。
// 有0->0，0->1, 1-> 0
// f[i,0] = max(f[i-1, 0], f[i-1, 1])
// f[i, 1] = f[i - 1, 0] + arr[i]
int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
memset(f, 0, sizeof f);
for (int i = 2; i <= n + 1; i++) {
cin >> arr[i];
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + arr[i];
}
cout << max(f[n + 1][0], f[n + 1][1]) << endl;
}
return 0;
}


zdw
2个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 2.5e4 + 5;

int arr[N];
bool st[N];
int main(){
int t, n;
cin >> t;
while (t --){
memset (st, false, sizeof st);

cin >> n;
for (int i = 0; i < n; i ++) {
cin >> arr[i];
}
sort(arr, arr + n);

int res = 0;
st[0] = true;
for (int i = 0; i < n; i ++){
if (!st[arr[i]]) res ++;
for (int j = arr[i]; j <= arr[n - 1]; j ++){
st[j] |= st[j - arr[i]];
}
}

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


zdw
3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

for (int i = 2; i < N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = 0; k <= 9; k ++ )
if (abs(j - k) >= 2)
f[i][j] += f[i - 1][k];
}

int dp(int n)
{
if (!n) return 0;

vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = -2;
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
for (int j = i == nums.size() - 1; j < x; j ++ )
if (abs(j - last) >= 2)
res += f[i + 1][j];

if (abs(x - last) >= 2) last = x;
else break;

if (!i) res ++ ;
}

// 特殊处理有前导零的数
for (int i = 1; i < nums.size(); i ++ )
for (int j = 1; j <= 9; j ++ )
res += f[i][j];

return res;
}

int main() {
init();

int l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;

return 0;
}


zdw
3个月前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 12, M = 105;
int f[N][N][M];
int a, b, p;

int mod(int x, int y) {
return (x % y + y) % y;
}

void init(){
memset(f, 0, sizeof f);
for (int i = 0; i <= 9; i ++) f[1][i][i % p] ++;

for (int i = 2; i < N; i ++){
for (int j = 0; j <= 9; j ++) {
for (int k = 0; k < p; k ++){
for (int x = 0; x <= 9; x ++) {
f[i][j][k] += f[i - 1][x][mod(k - j, p)];
}
}
}
}
}

int dp(int x){
vector<int> nums;
while (x) nums.push_back(x % 10), x /= 10;

int res = 0, last = 0; // last 前面位数的和
for (int i = nums.size() - 1; i >= 0; i --) {
int x = nums[i];
for (int j = 0; j < x; j ++) {
res += f[i + 1][j][mod(-last, p)];
}
last += x;
if (!i && last % p == 0) res ++;
}
return res;
}

int main(){

while (cin >> a >> b >> p)init(),cout << dp(b) - dp(a) << endl;
return 0;
}


zdw
3个月前

1. 如果k 小于 $2^{n-1}$, 说明是第一个方式构成，直接+0
2. 否则就去找k-$2^{n-1}$大，因为倒序所以是找$2^{n-1}$ - (k - $2^{n-1}$) - 1 ==> $2^n$ - k - 1

#include <iostream>

using namespace std;
typedef unsigned long long ULL;

string f(ULL n, ULL k){
if (!n) return "";
if ( (1ull << n - 1) > k) return "0" + f(n - 1, k);
unsigned long long  t = (1ull << n) - k - 1;
if (n == 64) t = -k -1;// 移出去了，可能会出现异常是0或1不确定，特判一下
return "1" + f(n - 1, t);
}

int main(){
ULL n, k;
cin >> n >> k;
cout << f(n, k) << endl;
return 0;
}


#include <iostream>

using namespace std;

int main(){
unsigned long long n, k;
cin >> n >> k;
unsigned long long ge = k ^ (k >> 1);
while (~--n) {
cout << (ge >> n & 1 );
}
return 0;
}


zdw
3个月前

f[i][j] = f[i - 1][j] + f[i][j - 1]， 当i，j不同时为奇数时;

#include <iostream>

using namespace std;
int f[35][35];
int main(){
int n, m;
cin >> n >> m;
f[0][1] = 1;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j++){
if (j & 1 | i & 1)
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
cout << f[n][m] << endl;
return 0;
}


zdw
3个月前
#include <iostream>

using namespace std;
const int N = 1005;
int phi[N], primes[N], tot;
bool st[N];
void get_phi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[tot++] = i;
phi[i] = i - 1;
}

for (int j = 0; primes[j] * i <= n; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
}

long long phi_sum[N];
void get_phi_sum(int n) {
for (int i = 1; i <= n; i++) phi_sum[i] += phi_sum[i - 1] + phi[i];
}

int main() {
int t, n, cnt = 1;
scanf("%d", &t);
get_phi(1000), get_phi_sum(1000);
while (t--)
{
scanf("%d", &n);
printf("%d %d %lld\n", cnt++, n, phi_sum[n] * 2 + 1);
}

return 0;
}