tom233

4930

tom233
21小时前
#include<iostream>
#include<math.h>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N = 1e6 + 10;
int f[N],a[N];
int n, len;

int main(){

cin >> n;
for (int i = 1; i <= n; i ++ ){
int x;
scanf("%d", &x);
a[x] = i;
}

f[0] = -1;
for (int i = 1; i <= n; i ++ ){
int x;
scanf("%d", &x);
int k = a[x];
if (!k) continue;

int l = 0, r = len;
while (l < r){
int mid = l + r + 1 >> 1;
if (f[mid] < k) l = mid;
else r = mid - 1;
}
len = max(l + 1, len);
f[l + 1] = k;
}

cout << len << endl;
return 0;
}


tom233
1天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 11;
int f[N][N];
int l, r;

void init(){

for (int i = 0; i <= 9; i ++ )
if (i != 4)
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 (k == 2 && j == 6) continue;
else if (j == 4) continue;
else f[i][j] += f[i - 1][k];
}

int dp(int u){

if (!u) return 1;
int res = 0, last = -1;
vector<int> nums;
while(u) nums.push_back(u % 10), u /= 10;

for (int i = nums.size() - 1; i >= 0; i -- ){
for (int j = 0; j < nums[i]; j ++ )
if (last == 6 && j == 2) continue;
else if (j == 4) continue;
else
res += f[i + 1][j];

if (nums[i] == 4 || last == 6 && nums[i] == 2) break;
last = nums[i];

if (!i && !(last == 6 && nums[i] == 2)) res ++;
}

return res;
}

int main(){

init();

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

return 0;
}



tom233
1天前

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

const int N = 11, M = 110;
int f[N][N][M];
int l, r, n;

void init(){

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

int dp(int u){

if (!u) return 1;

int res = 0, last = 0;
vector<int> nums;
while(u) nums.push_back(u % 10), u /= 10;

for (int i = nums.size() - 1; i >= 0; i -- ){
for (int j = 0; j < nums[i]; j ++ )
for (int k = 0; k < M; k ++ )
if ((k + last) % n == 0)
res += f[i + 1][j][k];
last += nums[i];
if (!i && (last % n) == 0) res ++;
}

return res;
}
int main(){

init();

while(scanf("%d%d%d", &l, &r, &n) == 3)
cout << dp(r) - dp(l - 1) << endl;

return 0;
}


tom233
1天前
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

const int N = 11;
int f[N][N];
int l, r;

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 u){
if (!u) return 0;

vector<int> nums;
int res = 0, last = 22;
while(u) nums.push_back(u % 10), u /= 10;

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

if (abs(last - nums[i]) < 2) break;
last = nums[i];
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();

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

return 0;
}


tom233
1天前
#include<set>
#include<iostream>
using namespace std;

const int N = 10;
int w[N][N];
int n, m, k;
set<int> s;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
void dfs(int x, int y, int res, int cnt){
res = res * 10 + w[x][y];
if (cnt == k){
s.insert(res);
return ;
}
for (int i = 0; i < 4; i ++ ){
int xx = dx[i] + x, yy = dy[i] + y;
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m){
dfs(xx, yy, res, cnt + 1);
}
}
}

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

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> w[i][j];

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
dfs(i, j, 0, 0);

cout << s.size() << endl;
}


tom233
2天前
#include<iostream>
#include<cstring>
using namespace std;

const int N = 210;
int f[N][N], w[N][N], a[N], n, m, k;

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

for (int i = 1; i <= m; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> w[i][j];

memset(f, -0x3f, sizeof f);
f[1][0] = 0;
for (int i = 1; i <= m; i ++ )
for (int j = 0; j <= k; j ++ )
for (int t = 1; t < i; t ++ )
if (j >= i - t - 1)
f[i][j] = max(f[i][j], f[t][j - (i - t - 1)] + w[a[t]][a[i]]);

int res = 0;
for (int i = 0; i <= k; i ++ )
res = max(res, f[m][i]);

cout << res << endl;

return 0;
}


tom233
2天前
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N = 35;
int f[N][N];
int l, r;

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 = j; k <= 9; k ++ )
f[i][j] += f[i - 1][k];
}

int dp(int u){

if (!u) return 1;

vector<int> nums;
int res = 0, last = 0;

while(u)nums.push_back(u % 10), u /= 10;

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

if ( nums[i] < last) break;
last = nums[i];

if (!i) res ++;
}
return res;
}

int main(){

init();

while(scanf("%d%d", &l, &r) == 2)
cout << dp(r) - dp(l - 1) << endl;

return 0;
}


tom233
3天前
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL sum[N], state[N], real[N], w[N];
int n, k;

int main(){

cin >> n >> k;
for (int i = 1; i <= n; i ++ ){
cin >> w[i];
sum[i] += sum[i - 1] + w[i];
}
for (int i = 1; i <= n; i ++ ){
cin >> state[i];
if (state[i]){
real[i] = real[i - 1] + w[i];
}else real[i] = real[i - 1];
}

LL res = 0;
for (int i = 1; i + k - 1 <= n; i ++ ){
res = max(res, (sum[i + k - 1] - sum[i - 1] + real[i - 1] + real[n] - real[i + k - 1]));
}

cout << res << endl;

return 0;
}


tom233
4天前

#include<iostream>
using namespace std;

const int N = 1e5 * 31 + 10, M = 1e5 + 10;
int son[N][2], idx, cnt[N], sum[M];
int n, m;

void insert(int x, int op){
int p = 0;
for (int i = 30; i >= 0; i -- ){
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
cnt[p] += op;
}
}

int query(int x){
int res = 0, p = 0;
for (int i = 30; i >= 0; i -- ){
int u = x >> i & 1;
if (cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;
else p = son[p][u], res = res * 2;
}
return res;
}

int main(){

cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
cin >> sum[i];
sum[i] ^= sum[i - 1];
}

insert(sum[0], 1);
int res = -1;
for (int i = 1; i <= n; i ++ ){
if (i > m) insert(sum[i - m - 1], -1);
res = max(res, query(sum[i]));
insert(sum[i], 1);
}

cout << res << endl;

return 0;
}


tom233
4天前
#include<iostream>
using namespace std;

const int N = 1e5 * 31 + 10, M = 1e5 + 10;
int son[N][2], cnt[N], sum[M], idx;
int n, m;

void insert(int x, int op){
int p = 0;
for (int i = 30; i >= 0; i -- ){
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
cnt[p] += op;
}
}

int search(int x){
int p = 0, res = 0;
for (int i = 30; i >= 0; i -- ){
int u = x >> i & 1;
if (cnt[son[p][!u]])p = son[p][!u], res = res * 2 + 1;
else p = son[p][u], res = res * 2;
}
return res;
}

int main(){

cin >> n >> m;

for(int i = 1; i <= n; i ++ ){
cin >> sum[i];
sum[i] ^= sum[i - 1];
}

int res = -1;
insert(sum[0], 1);

for (int i = 1; i <= n; i ++ ){
if (i > m) insert(sum[i - m - 1], -1);
res = max(res, search(sum[i]));
insert(sum[i], 1);
}

cout << res << endl;

return 0;
}