zcmimi's blog

categories/刷题记录/共652篇文章

avatar
zcmimi
2020-06-09 16:22:00

DZY Loves Math

题意:

对于正整数n,定义f(n)n所含质因子的最大幂指数

例如f(1960)=f(2^3\cdot 5^1\cdot 7^2)=3,f(10007)=1,f(1)=0

给定正整数a,b,求$\sum\limits_{i=1}^a\s

avatar
zcmimi
2020-05-25 19:22:00

SPOJ的GSS系列是关于区间统计技巧的集合

非常适合锻炼码力

LG GSS1 | SPOJ GSS1

[LG GSS2](

avatar
zcmimi
2019-03-06 00:03:14

题目地址:

网络流24题真的好有质量~\ (\ge \le ) /~!

进度: $\frac

avatar
zc
2020-10-22 10:06:14

查看原题

点击跳转

根据平方和公式可以发现分越多段越好

而进一步又可以发现最后一段的总和越小越好

以下是88分代码(高精什么的懒得写了):

avatar
zc
2020-10-21 21:57:52

查看原题

点击跳转

在dfs的过程中维护一个栈st

假设当前遍历节点为x,栈顶st[tp]

x与栈顶形成一个括号对,那么弹出栈顶,将新的栈顶权值+1

栈顶权值表示:

如果有新的右括号入栈,以这个右括号结尾,能形成多少合法括号串

avatar
zc
2020-10-21 18:55:41

查看原题

点击跳转

95分(未特判2^64)

#include<iostream>
int n;unsigned long long k;
int main(){
    std::cin>>n>>k;
    k^=k>>1;
    while(~--n)std::cout<<(k>>n&1);
}

100分简洁代码:

avatar
zc
2020-10-21 16:41:02

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

avatar
zc
2020-10-21 10:05:27

查看原题

点击跳转

这题考场上可能打表稳一点

n/m 1 2 3 4 5 6 7 8
1 2 4 8 16 32 64 128 256
2 4 12 36 108 324 972 2916 8748
3 8 36 112 336 1008 3024 9072 27216
4 16 108 336 912 2688 8064 24192 72576
5 32 324 1008 2688 7136 21312 63936 191808
6 64 972 3024 8064 21312 56768 170112 510336
7 128 2916 9072 24192 63936 170112 453504 1360128
8 256 8748 27216 72576 191808 510336 1360128 3626752

不妨设n<m(不难发现表格是对称的)

不难发现:

  1. n=1时,ans(n,m)=2^m
  2. n>1,m>n+1时,ans(n,m)=ans(n,m-1)\times 3

打表+快速幂就完事了

avatar
zc
2020-10-20 16:36:54

查看原题

点击跳转

建图比较麻烦的最短路问题

将每个城市考虑为4个机场

每个机场两两之间互相连边,若同一个城市,走高速,否则走航线

需要注意的是找出根据三个机场找出第四个机场时的分类讨论

avatar
zc
2020-10-19 21:49:55

查看原题

点击跳转

f[sta]为死了的猪状态为sta时最少需要多少鸟

f[sta|line(i,j)]=\min(f[sta]+1)(line(i,j)表示经过i,j的抛物线能杀死的🐖的集合)

f[sta|(1<<i)]=\min(f[sta]+1)

优化:

若令x为满足sta\&(1<<(x-1))=0的最小正整数,则由sta扩展的转移的所有线都要经过x

1/66
Search
search