首页 > 其他分享 >2022.8.22 颓废记录

2022.8.22 颓废记录

时间：2022-08-23 00:34:47浏览次数：82  
标签：std sz le 颓废 22 int maxn 2022.8 ans

Preface

没有序言

Content

[luogu P4059][Code+#1]找爸爸

题面太长难以概括，不写简要题目了QAQ。

首先发现，肯定没有两个对应位置都是空格的，否则可以去掉让答案更优。

因此，我们只需要考虑最后一位是不是空格，如果是，讨论它在小 A 还是小 B。

具体而言，令 \(dp(i,j,k)\) 表示两个字符串分别匹配 \(i,j\) 个字符的最大相似度，且：

  • \(k=0\)：最后一位都不是空格，有 \(dp(i,j,k=0)=\max\{dp(i-1,j-1,0/1/2)\}\)。

  • \(k=1\)：小 A 的最后一位是空格，则有 \(dp(i,j,k=1)=\max\{dp(i,j-1,0)-A,dp(i,j-1,1)-B,dp(i,j-1,2)-A\}\)。

  • \(k=2\)：小 B 最后一位为空格，则有 \(dp(i,j,k=2)=\max\{dp(i-1,j,0)-A,dp(i-1,j,1)-A,dp(i-1,j,2)-B\}\)。

时间复杂度 \(O(nm)\)。

Code

// Problem: P4059 [Code+#1]找爸爸
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4059
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
typedef long long ll;
int pos[200];
ll dp[maxn][maxn][3],d[5][5],A,B;
char s[maxn],t[maxn];
int main() {
    pos['A'] = 1;
    pos['T'] = 2;
    pos['G'] = 3;
    pos['C'] = 4;
    scanf("%s%s",s + 1,t + 1);
    int n = strlen(s + 1),m = strlen(t + 1);
    for(int i = 1;i <= 4;++ i) {
        for(int j = 1;j <= 4;++ j) {
            scanf("%lld",&d[i][j]);
        }
    }
    scanf("%lld %lld",&A,&B);
    for(int i = 1;i <= max(n , m);++ i) {
        dp[0][i][0] = dp[i][0][0] = dp[0][i][2] = dp[i][0][1] = -1ll << 60;
        dp[0][i][1] = dp[i][0][2] = -A - 1ll * B * (i - 1);
    }
    for(int i = 1;i <= n;++ i) {
        for(int j = 1;j <= m;++ j) {
            dp[i][j][0] = max(dp[i - 1][j - 1][0] , max(dp[i - 1][j - 1][1] , dp[i - 1][j - 1][2])) + d[pos[s[i]]][pos[t[j]]];
            dp[i][j][1] = max(dp[i][j - 1][0] - A , max(dp[i][j - 1][1] - B , dp[i][j - 1][2] - A));
            dp[i][j][2] = max(dp[i - 1][j][0] - A , max(dp[i - 1][j][1] - A , dp[i - 1][j][2] - B));
        }
    }
    printf("%lld",max(dp[n][m][0] , max(dp[n][m][1] , dp[n][m][2])));
    return 0;
}

[CF1030E]Vasya and Good Sequences

你可以进行一种操作，每次操作可以交换一个数某两个二进制位上的数值。

如果你可以通过若干次操作使得 \(b\) 序列所有数异或和为 \(0\)，那么称 \(b\) 序列是好序列。

给定 \(a_{1\sim n}\)，求有多少 \([l,r]\) 满足 \(a_{l\sim r}\) 是一个好序列。

\(1\le n\le 3\times 10^5,1\le a_i\le 10^{18}\)。

首先我们需要知道 \(a_{l\sim r}\) 是好序列的条件。

显然第一个条件是 \(a_{l\sim r}\) 中的数的二进制 \(1\) 的个数必须为偶数。

并且，\(1\) 的个数最多的那个数 \(1\) 的个数不能超过总体的个数的一半。

可以发现，只要满足这两个条件，总能构造出一个异或和为 \(0\) 的序列。

第一点很好统计，直接前缀和加上统计数组维护。

至于第二点，显然这样的 \([l,r]\) 满足 \(r-l+1\) 不超过 \(64\)，直接暴力统计即可。

时间复杂度 \(O(64n)\)。

Code

// Problem: CF1030E Vasya and Good Sequences
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1030E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
typedef long long ll;
int n;
ll sum,cnt[2],ans,a[maxn];
int popcount(ll x) {
    int ans = 0;
    for(;x;x -= x & -x)++ ans;
    return ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie();
    std::cout.tie();
    std::cin >> n;
    for(int i = 1;i <= n;++ i)std::cin >> a[i],a[i] = popcount(a[i]);
    sum = 0;
    ++ cnt[0];
    for(int i = 1;i <= n;++ i) {
        ans += cnt[(sum += a[i]) & 1] ++;
        ll res = 0,maxval = 0;
        for(int j = i;j <= std::min(n , i + 58);++ j) {
            res += a[j];
            maxval = std::max(maxval , a[j]);
            ans -= (!(res & 1)) and (maxval > res / 2);
        }
    }
    std::cout << ans << endl;
    return 0;
}

[CF852B]Neural Network country

有一幅有向图，除了源点和汇点有 \(L\) 层，每层 \(n\) 个点。 第 \(i+1\) 层的每个点到第 \(i+2\) 层的每个点都有一条边，边的权值为有向边终点的权值。求源点到汇点的路径长度能被 \(m\) 整除的个数。

\(1\le n\le 10^6,1\le L\le 10^5,1\le m\le 100\)。

\(n,L\) 范围很离谱而 \(m\) 很小，一眼矩阵快速幂优化 DP。

直接预处理矩阵跑矩乘是 \(O(nm+m^3\log L)\) 的，可以通过但不完美。

其实这里没必要用矩乘，直接用几个行向量做一个类似卷积的东西就行。

（这么说起来这玩意是不是还可以用多项式优化 QAQ）

要注意的是源点和第 \(1\) 层，第 \(L\) 层和汇点要特殊处理。

时间复杂度 \(O(n+m^2\log L)\)。

Code

// Problem: CF852B Neural Network country
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF852B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;
const int maxm = 105;
int n,k,m;
struct matrix {
    int g[maxm];
    matrix() {
        memset(g , 0 , sizeof(g));
    }
}f,A,B;
matrix operator * (const matrix& a,const matrix& b) {
    matrix c;
    for(int i = 0;i < m;++ i) {
        for(int j = 0;j < m;++ j) {
            (c.g[(i + j) % m] += 1ll * a.g[i] * b.g[j] % mod) %= mod;
        }
    }
    return c;
}
int a[maxn];
matrix power(matrix x,int y) {
    matrix ans;
    ans.g[0] = 1;
    for(;y;y >>= 1) {
        if(y & 1)ans = ans * x;
        x = x * x;
    }
    return ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> n >> k >> m;
    for(int i = 1;i <= n;++ i) {
        std::cin >> a[i];
        ++ f.g[a[i] % m];
    }
    for(int i = 1;i <= n;++ i) {
        std::cin >> a[i];
        ++ A.g[a[i] % m];
    }
    for(int i = 1;i <= n;++ i) {
        int x;
        std::cin >> x;
        ++
 B.g[(x + a[i]) % m];
    }
    f = f * power(A , k - 2) * B;//才发现这里写成 printf 了，这是怎么过的QAQ
    //printf("%d\n",f.g[0]);
    std::cout << f.g[0];
    return 0;
}

[CF771C]Bear and Tree Jumps

给定一棵 \(n\) 个结点的树和一个整数 \(k\)。

每次可以从一个节点 \(u\) 跳到树上距离 \(u\) 不超过 \(k\) 的某个节点。

定义 \(f(u,v)\) 表示从 \(u\) 跳到 \(v\) 的最小步数。

求 \(\sum\limits_{1\le s\lt t\le n}f(s,t)\)。

\(1\le n\le 2\times 10^5,1\le k\le 5\)

这个题面是不是在预示着我要 fst 了

简单的换根 DP，只不过一开始一直没有往这个方向想，一直在硬算。

设 \(f(u,i)\) 表示从 \(u\) 跳到 \(u\) 子树中与 \(u\) 的距离 \(\bmod k\) 为 \(i\) 的节点的最小步数之和，\(sz(u,i)\) 表示 \(u\) 的子树中与 \(u\) 距离 \(\bmod k\) 为 \(i\) 的节点个数。

好绕啊QAQ

显然有：

\[sz(u,(i+1)\bmod k)=\sum_{v\in son_u} sz(v,i) \\ f(u,1\bmod k)=\sum_{v\in son_u}f(v,0)+sz(v,0) \\ f(u,(i+1)\bmod k)=\sum_{v\in son_u}f(v,i)(i\neq 0) \]

换根的时候撤销 \(v\) 的贡献，把 \(u\) 贡献到 \(v\) 里，然后最后回溯一下就行。

时间复杂度 \(O(nk)\)。

当然，如果这题树边有权值，就需要淀粉质来帮忙了，具体珂以看 zzyz 神仙云浅的题解。

本来想写一下，但是太懒，咕了（逃

Code

// Problem: CF771C Bear and Tree Jumps
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF771C
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 2e5 + 5;
int n,k;
vector<int> G[maxn];
typedef long long ll;
ll f[maxn][5],sz[maxn][5],ans;
void dfs1(int u,int fa) {
    sz[u][0] = 1;
    for(auto& v : G[u]) {
        if(v == fa)continue ;
        dfs1(v , u);
        for(int i = 0;i < k;++ i) {
            sz[u][(i + 1) % k] += sz[v][i];
            f[u][(i + 1) % k] += f[v][i];
            if(!i)f[u][1 % k] += sz[v][i];
        }
    }
    return ;
}
void dfs2(int u,int fa) {
    for(int i = 0;i < k;++ i)ans += f[u][i];
    for(auto& v : G[u]) {
        if(v == fa)continue ;
        ll Fu[5],Fv[5],Sizeu[5],Sizev[5];
        for(int i = 0;i < k;++ i) {
            Fu[i] = f[u][i];
            Fv[i] = f[v][i];
            Sizeu[i] = sz[u][i];
            Sizev[i] = sz[v][i];
        }
        for(int i = 0;i < k;++ i) {
            sz[u][(i + 1) % k] -= sz[v][i];
            f[u][(i + 1) % k] -= f[v][i];
            if(!i)f[u][1 % k] -= sz[v][i];
        }
        for(int i = 0;i < k;++ i) {
            sz[v][(i + 1) % k] += sz[u][i];
            f[v][(i + 1) % k] += f[u][i];
            if(!i)f[v][1 % k] += sz[u][i];
        }
        dfs2(v , u);
        for(int i = 0;i < k;++ i) {
            f[u][i] = Fu[i];
            f[v][i] = Fv[i];
            sz[u][i] = Sizeu[i];
            sz[v][i] = Sizev[i];
        }
    }
    return ;
}
int main() {
    scanf("%d %d",&n,&k);
    for(int i = 1;i < n;++ i) {
        int u,v;
        scanf("%d %d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs1(1 , 0);
    dfs2(1 , 0);
    printf("%lld\n",ans >> 1ll);
    return 0;
}

[luogu P5906]【模板】回滚莫队&不删除莫队

没什么好说的，模板题，直接放代码。

Code

// Problem: P5906 【模板】回滚莫队&不删除莫队
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5906
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 2e5 + 5;
int FIR[maxn];
int n,m,a[maxn],c[maxn],bel[maxn],fir[maxn],lst[maxn],ans[maxn],L[maxn],R[maxn];
struct query {
	int l,r,id;
	query() {
		l = r = id = 0;
	}
}Q[maxn];
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),c[i] = a[i];
	sort(c + 1 , c + 1 + n);
	int tot = unique(c + 1 , c + 1 + n) - c - 1;
	for(int i = 1;i <= n;++ i)a[i] = lower_bound(c + 1 , c + 1 + tot , a[i]) - c;
	int t = sqrt(n);
	for(int i = 1;i <= t;++ i) {
		L[i] = R[i - 1] + 1;
		R[i] = i * t;
	}
	if(t * t < n) {
		L[t + 1] = R[t] + 1;
		R[t + 1] = n;
		++ t;
	}
	for(int i = 1;i <= t;++ i) {
		for(int j = L[i];j <= R[i];++ j) {
			bel[j] = i;
		}
	}
	scanf("%d",&m);
	for(int i = 1;i <= m;++ i) {
		scanf("%d %d",&Q[i].l,&Q[i].r);
		Q[i].id = i;
	}
	sort(Q + 1 , Q + 1 + m , [&](const query& p,const query& q) {
		return (bel[p.l] ^ bel[q.l]) ? bel[p.l] < bel[q.l] : p.r < q.r;
	});
	int del[maxn],cnt;
	for(int k = 1,i = 1;k <= t;++ k) {
		int l = R[k] + 1,r = R[k],now = 0;
		cnt = 0;
		for(;bel[Q[i].l] == k;++ i) {
			if(bel[Q[i].l] == bel[Q[i].r]) {
				int res = 0;
				for(int j = Q[i].l;j <= Q[i].r;++ j) {
					if(!FIR[a[j]])FIR[a[j]] = j;
					res = max(res , j - FIR[a[j]]);
				}
				ans[Q[i].id] = res;
				for(int j = Q[i].l;j <= Q[i].r;++ j) {
					FIR[a[j]] = 0;
				}
				continue ;
			}
			for(;r < Q[i].r;) {
				++ r;
				if(!fir[a[r]])fir[a[r]] = r,del[++ cnt] = a[r];
				lst[a[r]] = r;
				now = max(now , r - fir[a[r]]);
			}
			int tmp = now;
			for(;l > Q[i].l;) {
				-- l;
				if(!lst[a[l]])lst[a[l]] = l;
				now = max(now , lst[a[l]] - l);
			}
			ans[Q[i].id] = now;
			for(;l <= R[k];++ l) {
				if(lst[a[l]] == l)lst[a[l]] = 0;
			}
			now = tmp;
		}
		for(int j = 1;j <= cnt;++ j)fir[del[j]] = lst[del[j]] = 0;
	}
	for(int i = 1;i <= m;++ i)printf("%d\n",ans[i]);
	return 0;
}

[CF700B]Connecting Universities

\(n\) 个结点的树，有 \(2k\) 个特殊节点，把它们分成 \(k\) 对，使得每对节点间的距离之和最大。

\(2\le n\le 2\times 10^5,1\le k\le \frac{n}{2}\)。

考虑贪心。

看到求距离，使用经典的处理手法，考虑每条边的贡献。

显然，每条边的最大贡献值就是左端特殊节点个数和右端特殊节点个数的最小值。

多写几组数据发现，一定可以构造一种方案使得每条边的贡献值最大化。

所以跑一遍 DFS 就完事了。时间复杂度 \(O(n)\)。

Code

// Problem: CF700B Connecting Universities
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF700B
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int n,k,sz[maxn];
vector<int> G[maxn];
ll ans;
void dfs(int u,int fa) {
	for(auto& v : G[u]) {
		if(v == fa)continue ;
		dfs(v , u);
		sz[u] += sz[v];
		ans += min(sz[v] , 2 * k - sz[v]);
	}
	return ;
}
int main() {
	scanf("%d %d",&n,&k);
	for(int i = 1;i <= 2 * k;++ i) {
		int x;
		scanf("%d",&x);
		++ sz[x];
	}
	for(int i = 1;i < n;++ i) {
		int u,v;
		scanf("%d %d",&u,&v);
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1 , 0);
	printf("%lld\n",ans);
	return 0;
}

好困QAQ，睡了，不写了。

标签：std,sz,le,颓废,22,int,maxn,2022.8,ans
From： https://www.cnblogs.com/Royaka/p/16614738.html

相关文章

  • 2022-08-22 马特起航
    嘻嘻，马特准备在博客园更新文章啦，希望这次能够坚持下来，尽量每周能够更新一篇文章。希望自己的文章，无论是技术笔记还是生活随笔，都能够尽量真实反馈自己的状态，不求能给别人提......
  • 【2022.8.22】前端开发（1）
    学习内容概要前段简介HTTP超文本传输协议HTML简介head内常见标签body内常见标签内容详细前段简介1.前段与后端的本质前段：与用户直接打交道的操作界面都......
  • 8.22
    ABC265F题意：给定两个\(n\)维空间上的点，问有多少个点距离这两个点的曼哈顿距离不超过\(m\)？\(n\leq100\)，其他数字小于等于\(1000\)题解：感谢\(SSRS\)大神考虑一个二维......
  • 2022DASCTF MAY-MISC
    不懂PCB的厨师不是好黑客可以直接用winrar打开搜索直接查看卡比谷歌搜索出对照表对照字符为：PTRH{GWDVSWVQBFISZSZ}直接用维吉尼亚解密，key就是题目中的kirby......
  • 2022-08-22 第十小组 石晓荟
    HTMLHTML1.HTML简介HTML是用来描述网页的一种语言。HTML叫做超文本标记语言（HyperTextMarkerUpLanguage）HTML不是编程语言，而是一种标记语言......
  • 2022-08-20 数据库连接池
    数据库连接池每次去初始化一个连接池，连接池中会有很多个连接等待被使用，使用完连接之后，不需要关闭连接，只需要把连接还回到连接池，还回到连接池的操作不需要我们手动控制。......
  • 2022第六届河南省高等学校信息安全对抗大赛（ISCC2022)——一时语塞
    2.一时语塞（图片好像经过了某些处理）  看到事一张图片，先用kali中的binwalk命令查看图片信息，结果发现有压缩包   然后用kali中得foremost-T将其分离出来 ......
  • 【2022-08-22】python前端开发(一)
    python前端开发(一)前端简介前端与后端前端与用户直接交互的操作界面都可以称之为是前端后端不直接与用户交互，内部真正执行核心业务逻辑的......
  • 2022-08-22 第六小组 张宁杰 HTML&CSS回顾
    知识点什么是HTMLHTML是用来描述网页的一种语言。HTML叫做超文本标记语言（HyperTextMarkerUpLanguage）HTML不是编程语言，而是一种标记语言，标记语言就是一套标记标签，HTM......
  • 2022-08-19 PreparedStatement
    PreparedStatementPreparedStatement接口是Statement的子接口，它表示一条预编译过的SQL语句什么是SQL注入SQL注入是利用某些系统没有对用户输入的数据进行充分的检查，而......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99