优化
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
// freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
// freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
图
最小环路径
ll n , m , g[110][110] , dis[110][110] , z[110][110] ;
ll ans = INF ;
vector<int> v ;
void floyd()
{
for(int k = 1 ;k <= n ;k ++){
for(int i = 1 ;i < k ;i ++ ){
for(int j = i + 1; j < k ;j ++){
ll temp = g[i][k] + g[k][j] + dis[i][j] ;
if(temp < ans){
ans = temp ，v.clear() ;
int p = j ;
while(p != i){
v.push_back(p) ;
p = z[i][p] ;
}
v.push_back(i)，v.push_back(k) ;
}
}
}
for(int i = 1; i <= n ;i ++)
for(int j = 1; j <= n ;j ++){
ll temp = dis[i][k] + dis[k][j] ;
if(dis[i][j] > temp)
dis[i][j] = temp , z[i][j] = z[k][j] ;
}
}
}
int main()
{
n = in() , m = in() ;
for(int i = 0 ;i < 102 ;i ++)
for(int j = 0 ; j < 102 ;j ++)
g[i][j] = INF , dis[i][j] = INF , z[i][j] = i ;
for(int i = 1; i <= m ;i ++)
{
ll u = in() , v = in() , w = in() ;
g[u][v] = g[v][u] = dis[u][v] = dis[v][u] = min(dis[u][v] , w) ;
}
floyd() ;
if(ans == INF) puts("No solution.") ;
else
{
for(auto x : v)
cout << x << " " ;
}
return 0 ;
}
二分匹配
匈牙利匹配
int find(int u){
for(auto x : v[u]){
if(!st[x]){
st[x] = 1 ;
if(match[x] == 0 || find(match[x])){
match[x] = u ;
return true ;
}
}
}
return false ;
}
int main()
{
cin >> n >> m ;
int a , b ;
while(cin >> a >> b)
v[a].push_back(b) ;
int res = 0 ;
for(int i = 1 ;i <= n - m ;i ++){
memset(st , 0 , sizeof st) ;
if(find(i))
res ++ ;
}
cout << res << endl ;
}
HK二分匹配
int dx[N] , dy[N] , n , m ;
vector<int> v[N] ;
int vis[N] , match[N] , usedx[N] , usedy[N] , depth;
bool find(int u) {
for(auto x : v[u]) {
if(!vis[x] && dx[u] == dy[x] - 1) {
vis[x] = 1 ;
if(!usedy[x] || find(usedy[x])) {
usedx[u] = x ;
usedy[x] = u ;
return true ;
}
}
}
return false ;
}
bool bfs() {
queue<int> q ;
depth = INF ;
memset(dx , -1 , sizeof dx) ;
memset(dy , -1 , sizeof dy) ;
for(int i = 1; i <= n ;i ++ )
if(!usedx[i]) dx[i] = 0 , q.push(i) ;
while(q.size()) {
int u = q.front() ;q.pop() ;
if(depth < dx[u]) break ;
for(auto x : v[u]) {
if(dy[x] == -1) {
dy[x] = dx[u] + 1 ;
if(!usedy[x]) depth = dy[x] ;
else dx[usedy[x]] = dy[x] + 1 , q.push(usedy[x]) ;
}
}
}
return depth != INF ;
}
int work()
{
memset(usedx , 0 , sizeof usedx) ;
memset(usedy , 0 , sizeof usedy) ;
while(bfs()) {
memset(vis , 0 , sizeof vis) ;
for(int i = 1 ;i <= n ;i ++ )
if(!usedx[i] && find(i))
ans ++ ;
}
cout << ans << endl ;
return 0 ;
}
KM带权二分匹配
int love[N][N] , ex_girl[N] , ex_boy[N] , vis_girl[N] , vis_boy[N];
int match[N] , slack[N] , n ;
bool dfs(int girl){
vis_girl[girl] = true ;
for(int boy = 0 ;boy < n ;boy ++){
if(vis_boy[boy]) continue ;
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy] ;
if(gap == 0){
vis_boy[boy] = true ;
if(match[boy] == -1 || dfs(match[boy])) {
match[boy] = girl ;
return true ;
}
}
else slack[boy] = min(slack[boy] , gap) ;
}
return false ;
}
int KM(){
memset(match , -1 , sizeof match) ;
memset(ex_boy , 0 , sizeof ex_boy) ;
for(int i = 0 ;i < n ;i ++)
for(int j = 0 ;j < n ;j ++)
ex_girl[i] = max(ex_girl[i] , love[i][j]) ;
for(int i = 0 ;i < n ;i ++) {
memset(slack , INF , sizeof slack) ;
while(1) {
memset(vis_girl , 0 , sizeof vis_girl) ;
memset(vis_boy , 0 , sizeof vis_boy) ;
if(dfs(i)) break ;
int d = INF ;
for(int j = 0 ;j < n ;j ++)
if(!vis_boy[j])
d = min(d , slack[j]) ;
for(int j = 0 ;j < n ;j ++){
if(vis_girl[j]) ex_girl[j] -= d ;
if(vis_boy[j]) ex_boy[j] += d ;
else slack[j] -= d ;
}
}
}
int res = 0 ;
for(int i = 0 ;i < n ;i ++)
res += love[match[i]][i] ;
return res ;
}
int main(){
while(~scanf("%d" , &n)){
for(int i = 0 ;i < n ;i ++)
for(int j = 0 ;j < n ;j ++)
scanf("%d" , &love[i][j]) ;
printf("%d
" , KM()) ;
}
return 0 ;
}
//O^3
void bfs( ll k ){
ll x , y = 0 , yy = 0 , delta;
memset( pre , 0 , sizeof(pre) );
for( ll i = 1 ; i <= n ; i++ ) slack[i] = INF;
linker[y] = k;
while(1){
x = linker[y]; delta = INF; visy[y] = true;
for( ll i = 1 ; i <= n ;i++ ){
if( !visy[i] ){
if( slack[i] > lx[x] + ly[i] - w[x][i] ){
slack[i] = lx[x] + ly[i] - w[x][i];
pre[i] = y;
}
if( slack[i] < delta ) delta = slack[i] , yy = i ;
}
}
for( ll i = 0 ; i <= n ; i++ ){
if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
else slack[i] -= delta;
}
y = yy ;
if( linker[y] == -1 ) break;
}
while( y ) linker[y] = linker[pre[y]] , y = pre[y];
}
ll KM(){
memset( lx , 0 ,sizeof(lx) );
memset( ly , 0 ,sizeof(ly) );
memset( linker , -1, sizeof(linker) );
for( ll i = 1 ; i <= n ; i++ ){
memset( visy , false , sizeof(visy) );
bfs(i);
}
ll res = 0 ;
for( ll i = 1 ; i <= n ; i++ ){
if( linker[i] != -1 ){
res += w[linker[i]][i] ;
}
}
return res;
}
int main(){
w[i][j]=s;
printf("%lld
",KM());
}
带花树求一般图最大匹配
int findp(int x){return x==par[x]?x:par[x]=findp(par[x]);}
int Ti=0,times[maxn]={};
int lca(int x,int y){
for(Ti++;times[x]!=Ti;x^=y^=x^=y)
if(x) times[x]=Ti,x=findp(pre[link[x]]);
return x;
}
void blossom(int x,int y,int p){
while(findp(x)!=p){
pre[x]=y;
y=link[x];
par[x]=par[y]=p;
if(ty[y]==1) ty[y]=2,q.push_back(y);
x=pre[y];
}
}
bool Match(int x){
for(int i=0;i<=n;i++) ty[i]=0,par[i]=i;
q.clear();
ty[x]=2,q.push_back(x);
while(q.size()){
x=q.front(),q.pop_front();
for(int u:g[x])
if(ty[u]==0){
ty[u]=1;
pre[u]=x;
if(link[u]) q.push_back(link[u]),ty[link[u]]=2;
else {
for(;x;u=x){
x=link[pre[u]];
link[u]=pre[u];
link[link[u]]=u;
}
return 1;
}
}
else if(ty[u]==2&&findp(u)!=findp(x)){
int p=lca(x,u);
blossom(x,u,p),blossom(u,x,p);
}
}
return 0;
}
int main(){
mem(link,0);mem(pre,0);
ans=0;
scanf("%d",&n);
for(int f,t;~scanf("%d%d",&f,&t);){
g[f].push_back(t);
g[t].push_back(f);
}
for(int i=1;i<=n;i++)
if(!link[i]&&Match(i)) ans++;
printf("%d
",ans*2);
for(int i=1;i<=n;i++)
if(i<link[i])
printf("%d %d
",i,link[i]);
return 0 ;
}
二分匹配单侧多重匹配
int g[1010][1010] , vis[1010] , match[1010] , a[1010][1010] ;
bool find(int u , int mid) {
for(int i = 1; i <= m ;i ++ ) {
if(g[u][i] && !vis[i]) {
vis[i] = 1 ;
if(a[i][0] < mid) {
a[i][++ a[i][0]] = u ;
match[u] = i ;
return true ;
}
else if(a[i][0] == mid) {
for(int j = 1 ;j <= mid ;j ++ ) {
if(find(a[i][j] , mid)){
a[i][j] = u ;
match[a[i][j]] = i ;
return true ;
}
}
}
}
}
return false ;
}
// 左边n ， 右边m ， 右边点可用多条边
bool check(int mid) {
memset(match , 0 , sizeof match) ;
memset(a , 0 , sizeof a) ;
for(int i = 1; i <= n ;i ++ ) {
memset(vis , 0 , sizeof vis) ;
if(!find(i , mid)) return false ;
}
return true ;
}
int work(){
while(cin >> n >> m) {
if(n == 0 && m == 0) break ;
memset(match , 0 , sizeof match) ;
memset(g , 0 , sizeof g) ;
for(int i = 1; i <= n ;i ++ ) {
string s ;
cin >> s ;
int x ;
char c ;
while(scanf("%d%c" , &x , &c)) {
g[i][x + 1] = 1 ;
if(c == '
') break ;
}
}
int l = 0 , r = n , ans = 0;
while(l <= r) {
int mid = l + r >> 1 ;
if(check(mid)) r = mid - 1 , ans = mid ;
else l = mid + 1 ;
}
cout << ans << endl ;
}
return 0 ;
}
一般图的最大匹配(每个点都有d[i]条边相连)
void Push(int u){
que[tail]=u;
tail++;
inque[u]=1;
}
int Pop(){
int res=que[head];
head++;
return res;
}
int lca(int u,int v)//寻找公共花祖先{
memset(inpath,0,sizeof(inpath));
while(1){
u=base[u];
inpath[u]=1;
if(u==st) break;
u=pre[match[u]];
}
while(1){
v=base[v];
if(inpath[v]) break;
v=pre[match[v]];
}
return v;
}
void reset(int u)//缩环{
int v;
while(base[u]!=newbase){
v=match[u];
inhua[base[u]]=inhua[base[v]]=1;
u=pre[v];
if(base[u]!=newbase) pre[u]=v;
}
}
void contract(int u,int v)//{
newbase=lca(u,v);
memset(inhua,0,sizeof(inhua));
reset(u);
reset(v);
if(base[u]!=newbase) pre[u]=v;
if(base[v]!=newbase) pre[v]=u;
for(int i=1;i<=n;i++){
if(inhua[base[i]]){
base[i]=newbase;
if(!inque[i])
Push(i);
}
}
}
void findaug(){
memset(inque,0,sizeof(inque));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)//并查集 base[i]=i;
head=tail=1;
Push(st);
ed=0;
while(head<tail){
int u=Pop();
for(int v=1;v<=n;v++){
if(g[u][v]&&(base[u]!=base[v])&&match[u]!=v){
if(v==st||(match[v]>0)&&pre[match[v]]>0)//成环
contract(u,v);
else if(pre[v]==0){
pre[v]=u;
if(match[v]>0) Push(match[v]);
else//找到增广路ed=v,return ;
}
}
}
}
}
void aug(){
int u,v,w;
u=ed;
while(u>0){
v=pre[u];
w=match[v];
match[v]=u;
match[u]=v;
u=w;
}
}
void edmonds()//匹配{
memset(match,0,sizeof(match));
for(int u=1;u<=n;u++){
if(match[u]==0){
st=u;
findaug();//以st开始寻找增广路
if(ed>0) aug();//找到增广路 重新染色，反向
}
}
}
//以上是带花树求最大匹配算法 不用看
void create()//建图{
n=0;
memset(g,0,sizeof(g));
for(int i=1;i<=np;i++)
for(int j=1;j<=f[i];j++)
mp[i][j]=++n;//拆点，给每个度的点编号
for(int i=0;i<ne;i++)
{//此时n+1代表x,n+2代表y
for(int j=1;j<=f[x[i]];j++)
g[mp[x[i]][j]][n+1]=g[n+1][mp[x[i]][j]]=1;//每个度的点与对应的x,y相连
for(int j=1;j<=f[y[i]];j++)
g[mp[y[i]][j]][n+2]=g[n+2][mp[y[i]][j]]=1;
g[n+1][n+2]=g[n+2][n+1]=1;//x与y相连
n+=2;
}
}
void print(){
ans=0;
for(int i=1;i<=n;i++)
if(match[i]!=0){
ans++;
// if(match[i]>i)
// cout<<"_____"<<i<<' '<<match[i]<<endl;
}
//cout<<"******"<<ans<<' '<<n<<endl;
if(ans==n) printf("Yes
");
else printf("No
");
}
int main(){
while(~scanf("%d%d",&np,&ne)){
for(int i=1;i<=np;i++)
scanf("%d",&f[i]);
for(int i=0;i<ne;i++)
scanf("%d%d",&x[i],&y[i]);
create();
edmonds();
print();
}
return 0;
}
tarjan
void tarjan(int u){
// dfn 节点的时间戳 ， low 当前强联通分量根节点的时间戳 ， ssc[i] ， 当前是第i个强连通分量
// sc 强连通分量的个数 ， sz[i] 强连通分量的大小
low[u] = dfn[u] = ++dfncnt, s[++tp] = u;
for (auto x : v[u] {
if (!dfn[x])
tarjan(x), low[u] = min(low[u], low[x]);
else if (!scc[x])
low[u] = min(low[u], dfn[x]);
}
if (dfn[u] == low[u]) {
++sc;
while (s[tp] != u) scc[s[tp]] = sc, sz[sc]++, --tp;
scc[s[tp]] = sc, sz[sc]++, --tp;
}
}
tarjan 点双连通分量
int dfn[N] , low[N] , ans[N] , cnt = 0 ;
vector<int> v[N] ;
// ans[] 点所在几个点双连通分量
void tarjan(int u , int f) {
low[u] = dfn[u] = ++ cnt ;
ans[u] = 0 ;
if(f) ans[u] ++ ;
for(auto x : v[u]) {
if(x == f) continue ;
if(!dfn[x]) {
tarjan(x , u) ;
low[u] = min(low[u] , low[x]) ;
if(low[x] < dfn[u]) ans[u] -- ;
ans[u] ++ ;
}else low[u] = min(low[u] , dfn[x]) ;
}
}
int work(){
for(int i = 1; i <= n ;i ++ ) if(!dfn[i]) tarjan(i , 0) , res ++ ;
}
tarjan边双连通分量
const int N = 5010;//点数
const int M = 20010;//边数，因为是无向图，所以这个值要 *2
struct Edge{
int to,nxt;
bool cut;//是否是桥标记
} edge[M];
int head[N],tot , low[N],dfn[N],sta[N],belong[N];//Belong 数组的值是1~block
int id,top , block;//边双连通块数
bool insta[N];
int bridge;//桥的数目
void add(int u,int v){
edge[tot].to = v;
edge[tot].nxt = head[u];
edge[tot].cut=false;
head[u] = tot++;
}
void Tarjan(int u,int pre){
int v;
low[u] = dfn[u] = ++id;
sta[top++] = u;
insta[u] = true;
int pre_cnt = 0;
for(int i = head[u]; i != -1; i = edge[i].nxt){
v = edge[i].to;
if(v == pre && pre_cnt == 0){
pre_cnt++;
continue;
}
if(!dfn[v]){
Tarjan(v,u);
if(low[u]>low[v]) low[u] = low[v];
if(low[v]>dfn[u]) {
bridge++;
edge[i].cut = true;
edge[i^1].cut = true;
}
}
else if( insta[v] && low[u] > dfn[v] ) low[u] = dfn[v];
}
if(low[u] == dfn[u]){
block++;
do{
v = sta[--top];
insta[v] = false;
belong[v] = block;
}while( v!=u );
}
}
void init(){
tot = 0;
memset(head,-1,sizeof(head));
}
int du[N];//缩点后形成树，每个点的度数
void solve(int n){
memset(dfn,0,sizeof(dfn));
memset(insta,false,sizeof(insta));
id = top = block = 0;
Tarjan(1,0);
int ans = 0;
memset(du,0,sizeof(du));
for(int i = 1; i <= n; i++) for(int j = head[i]; j != -1; j = edge[j].nxt) if(edge[j].cut) du[belong[i]]++;
for(int i = 1; i <= block; i++) if(du[i]==1) ans++; //找叶子结点的个数 ans, 构造边双连通图需要加边(ans+1)/2
printf("%d
",(ans+1)/2);
}
int main(){
int n,m;
int u,v;
while(scanf("%d%d",&n,&m)==2){
init();
while(m--){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
solve(n);
}
return 0;
}
割点与桥
void Tarjan(int i,int Father){
father[i]=Father;/*记录每一个点的父亲*/
dfn[i]=low[i]=tim++;
for(int j=0;j<G[i].size();++j) {
int k=G[i][j];
if(dfn[k]==-1){
Tarjan(k,i);
low[i]=min(low[i],low[k]);
}
else if(Father!=k)/*假如k是i的父亲的话，那么这就是无向边中的重边，有重边那么一定不是桥*/
low[i]=min(low[i],dfn[k]);//dfn[k]可能！=low[k]，所以不能用low[k]代替dfn[k],否则会上翻过头了。
}
}
void count(){
int rootson=0;
Tarjan(1,0);
for(int i=2;i<=n;++i){
int v=father[i];
if(v==1)
rootson++;/*统计根节点子树的个数，根节点的子树个数>=2,就是割点*/
else{
if(low[i]>=dfn[v])/*割点的条件*/
is_cut[v]=true;
}
}
if(rootson>1) is_cut[1]=true;
for(int i=1;i<=n;++i)
if(is_cut[i]) printf("%d
",i);
for(int i=1;i<=n;++i){
int v =father[i];
if(v>0&&low[i]>dfn[v])/*桥的条件*/
printf("%d,%d
",v,i);
}
}
int main(){
input();
memset(dfn,-1,sizeof(dfn));
memset(father,0,sizeof(father));
memset(low,-1,sizeof(low));
memset(is_cut,false,sizeof(is_cut));
count();
return 0;
}
网络流
最大流最小费用
int n,m;
int get(int x,int y)
{
return x*m+y;
}
const int maxn=100100;
bool vis[maxn];
int s,t,dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
struct Edge{
int to,next,flow,dis;//flow流量 dis花费
}edge[maxn];
int head[maxn],get_edge;
queue <int> q;
void add(int from,int to,int flow,int dis){
edge[++get_edge].next=head[from];
edge[get_edge].to=to;
edge[get_edge].flow=flow;
edge[get_edge].dis=dis;
head[from]=get_edge;
}
void add_edge(int from , int to , int flow , int dis) {
add(from , to , flow , dis) ;
add(from , to , 0 , -dis) ;
}
bool spfa(int s,int t){
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s);vis[s]=1;dis[s]=0; pre[t]=-1;
while (!q.empty()) {
int now=q.front();
q.pop();
vis[now]=0;
for (int i=head[now]; i!=-1; i=edge[i].next){
if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边{
dis[edge[i].to]=dis[now]+edge[i].dis;
pre[edge[i].to]=now;
last[edge[i].to]=i;
flow[edge[i].to]=min(flow[now],edge[i].flow);//
if (!vis[edge[i].to]){
vis[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
}
return pre[t]!=-1;
}
void MCMF(){
while (spfa(s,t)){
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
//cout<<maxflow<<" "<<mincost<<endl;
while (now!=s)
{//从源点一直回溯到汇点
edge[last[now]].flow-=flow[t];//flow和dis容易搞混
edge[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int main(){
memset(head,-1,sizeof head);
get_edge=-1;
t=n*m+100,s=n*m+200;
MCMF();//cout<<maxflow<<" "<<mincost<<endl;
if(maxflow!=2)printf("-1
");
else printf("%d
",mincost);
return 0;
}
Dinic最大流
struct node{
int u, v, c, next;
}Node[2*N];
void add_(int u, int v, int c){
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].c = c;
Node[cnt].next = head[u];
head[u] = cnt++;
}
void add(int u, int v, int c){
add_(u, v, c);
add_(v, u, 0);
}
bool bfs(){
queue<int> Q;
memset(d , 0 , sizeof d) ;
Q.push(s);
d[s] = 1;
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i=head[u]; i!=-1; i=Node[i].next){
node e = Node[i];
if(!d[e.v] && e.c > 0){
d[e.v] = d[e.u] + 1;
Q.push(e.v);
if(e.v == t) return 1;
}
}
}
return d[t] != 0;
}
int dfs(int u, int cap){
int ret = 0, V;
if(u == t || cap == 0)
return cap;
for(int &i=cur[u]; i!=-1; i=Node[i].next) {
node e = Node[i];
if(d[e.v] == d[u] + 1 && e.c > 0){
int V = dfs(e.v, min(cap, e.c));
Node[i].c -= V;
Node[i^1].c += V;
ret += V;
cap -= V;
if(cap == 0) break;
}
}
if(cap > 0) d[u] = -1;
return ret;
}
int dinic(int u){
int ans = 0;
while(bfs()) {
memcpy(cur, head, sizeof(head));
ans += dfs(u, INF);
}
return ans;
}
void init() {
memset(head ,-1, sizeof head) ;
cnt = 0 ;
}
固定流量的最小费用
struct edge {
int to, next, cap;
ll cos;
}e[M<<1];
struct node {
ll a, b, c;
}p[55];
vector<int> a[55], b;
int n, m, cnt, s, t, k;
void add(int u, int v, int cap, ll cos) {
e[cnt].to = v;
e[cnt].cap = cap;
e[cnt].cos = cos;
e[cnt].next = h[u];
h[u] = cnt++;
e[cnt].to = u;
e[cnt].cap = 0;
e[cnt].cos = -cos;
e[cnt].next = h[v];
h[v] = cnt++;
}
bool spfa() {
queue<int> q;
memset(pre, -1, sizeof pre);
memset(vis, 0, sizeof vis);
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
vis[s] = 1;
flow[s] = INF;
q.push(s);
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = h[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (e[i].cap && dis[v] > dis[u] + e[i].cos) {
pre[v] = u;
last[v] = i;
dis[v] = dis[u] + e[i].cos;
flow[v] = min(flow[u], e[i].cap);
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
return pre[t] != -1;
}
void MCMF() {
while (spfa()) {
ans[++k] = ans[k-1] + 1ll*flow[t] * dis[t];
int now = t;
while (now != s) {
e[last[now]].cap -= flow[t];
e[last[now] ^ 1].cap += flow[t];
now = pre[now];
}
}
}
void solve() {
scanf("%d %d", &n, &m);
memset(h, -1, sizeof h);
memset(ans, 0, sizeof ans);
cnt = 0;
k = 0;
// 起点，会点
s = 0, t = N-2;
for (int i = 1; i <= b.size(); i++) {//所有机器向汇点连边
add(i + n, t, 1, 0);
}
MCMF();
// 固定流量的最小费用
for (int i = 1; i <= k; i++) {
if (i != k) printf("%lld ", ans[i]);
else printf("%lld
", ans[i]);
}
}
字符串
后缀数组
int y[N], x[N], c[N], sa[N], rk[N], height[N] , st[30][N] ;
int get_SA() {
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
for (int i = 1; i <= m; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) ++c[x[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1;
num = 1;
for (int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if (num == n) break;
m = num;
}
return 0;
}
int get_height() {
int k = 0;
for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
for (int i = 1; i <= n; ++i) {
if (rk[i] == 1) continue;
if (k) --k;
int j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
height[rk[i]] = k;
}
return 0 ;
}
void build_st() {
for (int i = 1; i <= n; i++) st[0][i] = height[i];
for (int k = 1; k <= 19; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
return ;
}
int lcp(int x, int y) {
int l = rk[x], r = rk[y];
if (l > r) swap(l, r);
if (l == r) return n - x + 1;
int t = log2(r - l);
return min(st[t][l + 1], st[t][r - (1 << t) + 1]);
}
struct node {
int l , r , sum ;
}t[N * 4];
int tot = 0 ;
void up(int now) {
t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
void build(int &now , int l , int r) {
t[now = ++ tot].sum = 0 ;
if(l == r) return ;
int mid = l + r >> 1 ;
build(t[now].l , l , mid) ;
build(t[now].r , mid + 1 , r) ;
return ;
}
void update(int &now , int last , int l , int r , int pos) {
t[now = ++ tot] = t[last] ;
t[now].sum ++ ;
if(l == r) return ;
int mid = l + r >> 1 ;
if(pos <= mid) update(t[now].l , t[last].l , l , mid , pos) ;
else update(t[now].r , t[last].r , mid + 1 , r , pos) ;
return ;
}
int ask(int now , int last , int l , int r , int k) {
if(l == r) return l ;
int sum = t[t[now].l].sum - t[t[last].l].sum ;
int mid = l + r>> 1 ;
if(sum >= k) return ask(t[now].l , t[last].l , l , mid , k) ;
else return ask(t[now].r , t[last].r , mid + 1 , r , k - sum) ;
}
int root[N] ;
int work(){
int q ;
tot = 0 ;
scanf("%d%d" , &n , &q) ;
scanf("%s" , s + 1) ;
m = 123 ;
get_SA() ;
get_height() ;
build_st() ;
build(root[0] , 1, n ) ;
for(int i = 1; i <= n; i ++ ) update(root[i] , root[i - 1] , 1 , n , sa[i]) ;
while(q --) {
int l , r , k ;
scanf("%d%d%d" , &l , &r , &k) ;
int len = r - l + 1 ;
int left = 1 , right = rk[l] ;
int ans = rk[l] ;
while(left <= right) {
int mid = left + right >> 1 ;
if(lcp(sa[mid] , l) >= len) right = mid - 1 , ans = mid ;
else left = mid + 1 ;
}
int LL = ans ;
ans = rk[l] ;
right = n ;
left = rk[l] ;
while(left <= right) {
int mid = left + right >> 1 ;
if(lcp(sa[mid] , l) >= len) left = mid + 1 , ans = mid ;
else right = mid - 1 ;
}
int RR = ans ;
if(RR - LL + 1 < k) puts("-1") ;
else printf("%d
" , ask(root[RR] , root[LL - 1] , 1 , n , k)) ;
}
return 0 ;
}
AC自动机
struct Trie{
int t[N][26] , fail[N] , cnt[N] , in[N] , q[N] , h , tail , tot ;
void init() {
tot = 0 ;
memset(fail , 0 , sizeof fail) ;
memset(t , 0 , sizeof t) ;
memset(cnt , 0 , sizeof cnt) ;
memset(q , 0 , sizeof q) ;
}
int ins(char *x) {
int i = 0 ;
for(int j = 0 ;x[j] ;j ++ ) {
int c = x[j] - 'a' ;
if(!t[i][c]) t[i][c] = ++ tot ;
i = t[i][c] ;
}
return i ;
}
void get_fail() {
h = 1 ,tail = 0 ;
for(int i = 0 ;i < 26 ;i ++ ) if(t[0][i]) q[++ tail] = t[0][i] ;
while(h <= tail) {
int i = q[h ++] ;
for(int j = 0 ;j < 26 ;j ++ ) {
if(t[i][j]) {
fail[t[i][j]] = t[fail[i]][j] ;
q[++ tail] = t[i][j] ;
}else {
t[i][j] = t[fail[i]][j] ;
}
}
}
}
void solve() {
for(int i = tail ;i > 0 ;i --) cnt[fail[q[i]]] += cnt[q[i]] ;
}
}T;
char x[510][510] ;
char s[N] ;
int id[N] ;
int work()
{
int n , m , q ;
scanf("%d" , &n) ;
T.init() ;
for(int i = 1; i <= n; i ++ ) {
scanf("%s" , s) ;
id[i] = T.ins(s) ;
}
T.get_fail() ;
scanf("%s" , s) ;
int p = 0 ;
for(auto x : s)
p = T.t[p][x - 'a'] , T.cnt[p] ++ ;
T.solve() ;
int ans = 0 ;
for(int i = 1; i <= n ;i ++ )
ans += T.cnt[id[i]] ;
cout << ans << endl ;
return 0 ;
}
字符串最小表示法
int getmin(int *a){
static int b[12] ;
for(int i = 0 ;i < 12 ;i ++) b[i] = a[i % 6] ;
int i = 0 , j = 1 , k ;
while(i < 6 && j < 6){
for(k = 0 ;k < 6 && b[j + k] == b[i + k] ; k ++) ;
if(k == 6) break ;
if(b[i + k] > b[j + k]){
i += k + 1 ;
if(i == j) i ++ ;
}
if(b[i + k] < b[j + k]){
j += k + 1 ;
if(i == j) j ++ ;
}
}
k = min(i , j) ;
for(int i = 0 ; i < 6 ;i ++)
a[i] = b[i + k] ;
return 0 ;
}
马拉车算法
void init(int l , int r){
int k=0;
str[k++] = '$';
for(int i=l;i<=r;i++){
str[k++]='#';
str[k++]=s[i];
}
str[k++]='#';
len=k;
str[k] = ' ' ;
}
int ans = 0 , flag ;
int Manacher(){
Len[0] = 0;
int sum = 0;
mx = 0;
id = 0 ;
// cout << str << endl ;
for(int i=1;i<len;i++){
if(i < mx) Len[i] = Min(mx - i, Len[2 * id - i]);
else Len[i] = 1;
while(str[i - Len[i]]== str[i + Len[i]]) Len[i]++;
if(Len[i] + i > mx){ // 更新最长的回文串
mx = Len[i] + i; // mx是回文串右边一个位置
id = i; //id是回文串的中心
sum = Max(sum, Len[i]); // sum 是回文串的长度 + 1
}
// cout << i << " " << Len[i] << endl ;
// if(Len[i] == i) 表示前缀是回文的
// {
// if(ans < Len[i])
// ans = Len[i] - 1 , flag = 1 ;
// }
// if(Len[i] + i == len) 表示后缀是回文的
// if(ans < Len[i])
// ans = Len[i] - 1 , flag = 2 ;
}
return sum - 1 ;
}
kmp
void get_next()
{
for(int i = 2, j = 0 ;i <= n;i ++)
{
while(j && p[i] != p[j + 1]) j = nextp[j];
if(p[i] == p[j + 1]) j ++ ;
nextp[i] = j ;
}
}
int main()
{
// 在s串里面查找
cin >> s + 1 ;
m = strlen(s + 1);
cin >> p + 1 ;
n = strlen(p + 1) ;
get_next();
int x = 0 ;
for(int i = 1 , j = 0;i <= m;i ++){
while(j && s[i] != p[j + 1]) j = nextp[j] ;
if(s[i] == p[j + 1]) j ++ ;
if(j == n){
// cout << i - n << " " ;
x ++ ;
j = nextp[j] ;
}
}
cout << x << endl ;
return 0;
}
数据结构
字典树
区间内小于某个数的所有数之和
int n , m , root[N * 20] ;
ll a[N] , bin[N] ;
struct node {
ll sum , l , r ;
}t[N * 40];
void fj(ll x) {
if(x > 1000000000ll) x = 1000000001ll ;
for(int i = 0 ;i <= 30 ;i ++ )
bin[i] = (x >> i) & 1ll ;
}
int tot = 0 ;
void insert(int &now , int last , int id , ll w) {
t[now = ++ tot] = t[last] ;
if(id < 0) {
t[now].sum += w ;
return ;
}
if(!bin[id]) insert(t[now].l , t[last].l , id - 1 , w) ;
else insert(t[now].r , t[last].r , id - 1 , w) ;
t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
// 贪心的走
ll ask(int rt , int id) {
if(id < 0 || !rt) return t[rt].sum ;
ll res = 0 ;
if(!bin[id]) res = ask(t[rt].l , id - 1) ;
else res = t[t[rt].l].sum + ask(t[rt].r , id - 1) ;
return res ;
}
int work()
{
scanf("%d%d" , &n , &m) ;
for(int i = 1; i <= n ;i ++ ) {
scanf("%d" , &a[i]) ;
fj(a[i]) ;
insert(root[i] , root[i - 1] , 30 , a[i]) ;
}
for(int i = 1; i <= m ;i ++ ) {
int l , r ;
scanf("%d%d" , &l , &r) ;
ll sum = 1 , last = 0 ;
while(1) {
fj(sum) ;
ll temp = ask(root[r] , 30) - ask(root[l - 1] , 30) ;
if(temp == last) {
printf("%lld
" , sum) ;
break ;
}
last = temp , sum = temp + 1 ;
}
}
return 0 ;
}
主席树
主席树求区间小于某个数的个数
int root[N] , tot ;
struct node {
int l , r , sum ;
}t[N];
void build(int &now , int l , int r) {
t[now = ++ tot].sum = 0 ;
if(l == r) return ;
int mid = l + r >> 1 ;
build(t[now].l , l , mid) ;
build(t[now].r , mid + 1 , r) ;
return ;
}
void up(int now) {
t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
void update(int &now , int last , int l , int r , int pos) {
t[now = ++ tot] = t[last] ;
if(l == r) {
t[now].sum ++ ;
return ;
}
int mid = l + r >> 1 ;
if(pos <= mid) update(t[now].l , t[last].l , l , mid , pos) ;
else update(t[now].r , t[last].r , mid + 1 , r , pos) ;
up(now) ;
return ;
}
int ask(int now , int last , int l , int r , int k) {
if(!k) return 0 ;
if(r <= k) return t[now].sum - t[last].sum ;
int mid = l + r >> 1 ;
int ans = 0 ;
if(k <= mid) ans += ask(t[now].l , t[last].l , l , mid , k) ;
else ans += ask(t[now].l , t[last].l , l , mid , k) + ask(t[now].r , t[last].r , mid + 1 , r , k ) ;
return ans ;
}
int ca = 0 ;
int work()
{
int n , m ;
scanf("%d%d" , &n , &m) ;
for(int i = 1; i <= n ;i ++ ) scanf("%d" , &a[i]) , b[i] = a[i] ;
sort(b + 1 , b + n + 1) ;
cnt = unique(b + 1, b + n + 1) - b - 1 ;
for(int i = 1; i <= n ;i ++ ) a[i] = lower_bound(b + 1 , b + cnt + 1 , a[i]) - b ;
tot = 0 ;
build(root[0] , 1 , cnt) ;
for(int i = 1 ; i <= n ;i ++ )
update(root[i] , root[i - 1] , 1 , cnt , a[i]) ;
printf("Case #%d:
" , ++ ca) ;
for(int i = 1; i <= m ;i ++ ) {
int l , r , x , y ;
scanf("%d%d%d%d" , &l , &r , &x , &y) ;
y = upper_bound(b + 1 , b + cnt + 1 , y) - b - 1 ;
x = upper_bound(b + 1 , b + cnt + 1 , x - 1) - b - 1;
printf("%d
" , ask(root[r] , root[l - 1] , 1 , cnt , y) - ask(root[r] , root[l - 1] , 1 , cnt , x)) ;
}
return 0 ;
}
主席树求区间第k小(静态)
struct Tree {
int l, r, sum;
} T[MAXN * 40];
vector<int> v ;
int cnt, root[MAXN], a[MAXN];
void Init()
{
cnt = 0;
T[cnt].l = 0;
T[cnt].r = 0;
T[cnt].sum = 0;
root[cnt] = 0;
v.clear();
}
int getid(int x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void Update(int l, int r, int &x, int y, int pos)
{
T[++cnt] = T[y], T[cnt].sum++, x = cnt;
if (l == r) return;
int mid = (l + r) >> 1;
if (mid >= pos)
Update(l, mid, T[x].l, T[y].l, pos);
else
Update(mid + 1, r, T[x].r, T[y].r, pos);
}
int Query(int l, int r, int x, int y, int k)
{
if (l == r) return l;
int mid = (l + r) >> 1;
int sum = T[T[y].l].sum - T[T[x].l].sum;
if (sum >= k)
return Query(l, mid, T[x].l, T[y].l, k);
else
return Query(mid + 1, r, T[x].r, T[y].r, k - sum);
}
int main()
{
Init();
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]),v.push_back(a[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; i++)
Update(1, n, root[i], root[i - 1], getid(a[i]));
int l, r, k;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &l, &r, &k);
printf("%d
", v[Query(1, n, root[l - 1], root[r], k) - 1]);
}
return 0;
}
主席树求区间小于某个数所有数的和
struct node {
ll sum ;
int l , r ;
}t[N * 40];
void fj(ll x) {
if(x > 1000000000ll) x = 1000000001ll ;
for(int i = 0 ;i <= 30 ;i ++ )
bin[i] = (x >> i) & 1ll ;
}
int tot = 0 ;
void insert(int &now , int last , int id , ll w) {
t[now = ++ tot] = t[last] ;
if(id < 0) {
t[now].sum += w ;
return ;
}
if(!bin[id]) insert(t[now].l , t[last].l , id - 1 , w) ;
else insert(t[now].r , t[last].r , id - 1 , w) ;
t[now].sum = t[t[now].l].sum + t[t[now].r].sum ;
}
// 贪心的走
ll ask(int rt , int id) {
if(id < 0 || !rt) return t[rt].sum ;
ll res = 0 ;
if(!bin[id]) res = ask(t[rt].l , id - 1) ;
else res = t[t[rt].l].sum + ask(t[rt].r , id - 1) ;
return res ;
}
int work()
{
scanf("%d%d" , &n , &m) ;
for(int i = 1; i <= n ;i ++ ) {
scanf("%d" , &a[i]) ;
fj(a[i]) ;
insert(root[i] , root[i - 1] , 30 , a[i]) ;
}
for(int i = 1; i <= m ;i ++ ) {
int l , r ;
scanf("%d%d" , &l , &r) ;
ll sum = 1 , last = 0 ;
while(1) {
fj(sum) ;
ll temp = ask(root[r] , 30) - ask(root[l - 1] , 30) ;
if(temp == last) {
printf("%lld
" , sum) ;
break ;
}
last = temp , sum = temp + 1 ;
}
}
return 0 ;
}
虚树
void dfs(int u){
dfn[u] = ++idx;
deep[u] = deep[fa[u][0]] + 1;
for(int e : RG[u]){
int v = U[e] ^ V[e] ^ u;
if(v == fa[u][0]) continue;
me[v] = C[e];
if(u != 1 && me[u] < me[v]) me[v] = me[u];
fa[v][0] = u;
dfs(v);
}
}
int LCA(int u,int v){
if(deep[u] < deep[v]) swap(u,v);
int delta = deep[u] - deep[v];
for(int i = 19;i >= 0;--i){
if((delta >> i) & 1) u = fa[u][i];
}
for(int i = 19;i >= 0;--i){
if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
}
if(u == v) return u;
return fa[u][0];
}
bool comp(int a,int b){
return dfn[a] < dfn[b];
}
void insert(int u){
if(top == 1) {stk[++top] = u;return;}
int lca = LCA(u,stk[top]);
if(lca == stk[top]) {stk[++top] = u;return ;}
while(top > 1 && dfn[lca] <= dfn[stk[top-1]]){
VG[stk[top-1]].push_back(stk[top]);
--top;
}
if(lca != stk[top]) {
VG[lca].push_back(stk[top]);
stk[top] = lca;
}
stk[++top] = u;
}
int idq[maxn],mark[maxn];
ll DP(int u){
ll cost = 0;
for(int v : VG[u])
cost += min(me[v],DP(v));
VG[u].clear();
if(mark[u]) return me[u];
else return cost;
}
int main(){
init();
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1;i < n;++i){
cin >> U[i] >> V[i] >> C[i];
RG[U[i]].push_back(i);
RG[V[i]].push_back(i);
}
dfs(1);
for(int t = 1;t <= 19;++t) for(int i = 1;i <= n;++i){
fa[i][t] = fa[fa[i][t-1]][t-1];
}
cin >> m;
for(int i = 0;i < m;++i){
int sz;
cin >> sz;
for(int j = 0;j < sz;++j){
cin >> idq[j];
mark[idq[j]] = 1;
}
sort(idq,idq+sz,comp);
top = 0;
stk[++top] = 1;
for(int j = 0;j < sz;++j) insert(idq[j]);
while(top > 0) {
VG[stk[top-1]].push_back(stk[top]);
top--;
}
cout << DP(1) << endl;
for(int j = 0;j < sz;++j) VG[idq[j]].clear(),mark[idq[j]] = 0;
VG[0].clear();
}
return 0;
}
线段树
线段树板子乘加
//线段树操作 区间最大值 单点修改 单点查询
// 区间修改 区间查询 最大连续和
#include <iostream>
using namespace std;
const int N = 1e5 + 10 ;
typedef long long ll;
int a[N];
struct node{
ll muti , add , v;
}tree[4 * N];
int n , m , mod;
void pushdown(int root ,int l,int r){
int mid = l + r >> 1;
tree[root * 2].v =(tree[root * 2].v * tree[root].muti + tree[root].add * (mid - l + 1)) % mod;
tree[root * 2 + 1].v =(tree[root * 2 + 1].v * tree[root].muti + tree[root ].add * (r - mid)) % mod;
tree[root * 2].muti =(tree[root * 2].muti * tree[root].muti) % mod ;
tree[root * 2 + 1].muti =(tree[root * 2 + 1].muti * tree[root].muti) % mod ;
tree[root * 2].add =(tree[root * 2].add * tree[root].muti + tree[root].add) % mod ;
tree[root * 2 + 1].add =(tree[root * 2 + 1].add * tree[root].muti + tree[root].add) % mod ;
tree[root].muti = 1 ,tree[root].add = 0;
return ;
}
void build(int root ,int l,int r){
tree[root].add = 0,tree[root].muti = 1;
if(l == r){
tree[root].v = a[l] ; return ;
}
int mid = l + r >> 1 ;
build(root * 2 , l, mid) ,build(root * 2 + 1,mid + 1 ,r );
tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v ) % mod;
return ;
}
void change1(int root ,int treel,int treer ,int x, ll k){//单点修改 将第x 个修改为 k
tree[root].v += k;
int mid = treel + treer >> 1;
if(x > mid) change1(root * 2 + 1,mid + 1,treer , x , k);
else change1(root * 2 , treel,mid , x , k);
tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v) % mod ;
return ;
}
int query1(int root,int treel,int treer,int x){ // 单点查询 第x个点
if(treel == treer) return tree[root].v ;
int mid = treel + treer >> 1;
if(x <= mid) query1(root * 2 , treel ,mid ,x);
else query1(root * 2 + 1 ,mid + 1 ,treer ,x) ;
}
void change2(int root,int treel,int treer,int l,int r,ll k){ // 区间修改 乘法 x - y区间乘上 k
if(l >treer || r < treel) return ;
if(l <= treel && treer <= r){
tree[root].v =(tree[root].v * k) % mod ;
tree[root].muti = (tree[root].muti * k) % mod ;
tree[root].add = (tree[root].add * k) % mod ;
return ;
}
pushdown(root,treel,treer);
int mid = treel + treer >> 1 ;
change2(root * 2,treel,mid , l ,r ,k);
change2(root * 2 + 1,mid + 1,treer, l ,r ,k);
tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v) % mod ;
return ;
}
void change3(int root,int treel,int treer,int l,int r,ll k){ // 区间修改 加法 x- y区间加上k
if(l >treer || r < treel) return ;
if(l <= treel && treer <= r){
tree[root].v =(tree[root].v + k*(treer- treel + 1)) % mod ;
tree[root].add = (tree[root].add + k) % mod ;
return ;
}
pushdown(root,treel,treer);
int mid = treel + treer >> 1 ;
change3(root * 2,treel,mid , l ,r ,k);
change3(root * 2 + 1,mid + 1,treer, l ,r ,k);
tree[root].v = (tree[root * 2].v + tree[root * 2 + 1].v) % mod ;
return ;
}
ll query2(int root,int treel,int treer,int l,int r){ // 区间求和 求区间x - y 的和
if(l >treer || r <treel) return 0;
if(l <= treel &&treer <= r) return tree[root].v ;
pushdown(root,treel,treer);
int mid = treel + treer >> 1;
return (query2(root * 2 ,treel,mid , l ,r) + query2(root * 2 + 1,mid + 1,treer ,l,r))%mod ;
}
线段树区间最值
void up(int rt){
minx[rt] = max(minx[ls] , minx[rs]) ;
}
void build(int rt , int l , int r){
if(l == r) {
minx[rt] = a[l] ;
return ;
}
int mid = l + r >> 1 ;
build(ls , l , mid) ;
build(rs , mid + 1 , r) ;
up(rt) ;
return ;
}
void down(int rt , int l , int r){
if(lazy[rt]) {
lazy[ls] += lazy[rt] ;
lazy[rs] += lazy[rt] ;
minx[ls] += lazy[rt] ;
minx[rs] += lazy[rt] ;
minx[rt] = max(minx[ls] , minx[rs]) ;
lazy[rt] = 0 ;
}
return ;
}
void add(int rt , int l , int r , int ql , int qr , ll k){
if(ql <= l && r <= qr) {
minx[rt] += k ;
lazy[rt] += k ;
return ;
}
down(rt , l , r) ;
int mid = l + r >> 1 ;
if(ql <= mid) add(ls , l , mid , ql , qr , k) ;
if(qr > mid) add(rs , mid + 1 , r , ql , qr , k) ;
up(rt) ;
return ;
}
ll ask(int rt , int l , int r , int ql , int qr){
if(ql <= l && r <= qr) return minx[rt] ;
down(rt , l , r) ;
ll ans = 0 ;
int mid = l + r >> 1 ;
if(ql <= mid) ans = max(ans , ask(ls , l , mid , ql , qr)) ;
if(qr > mid) ans = max(ans , ask(rs , mid + 1 , r , ql , qr)) ;
return ans ;
}
线段树维护矩阵乘法
struct node {
ll a[2][2] ;
} ;
char a[N] ;
node muti(node a , node b){
node res ;
for(int i = 0 ;i < 2; i ++ )
for(int j = 0 ;j < 2 ;j ++ )
res.a[i][j] = 0 ;
for(int k = 0 ;k < 2; k ++ )
for(int i = 0 ;i < 2; i ++ )
for(int j = 0 ;j < 2; j ++ )
res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j] % mod ) % mod ;
return res ;
}
struct Node {
int l , r , lazy ;
node ans , rans ;
}tr[N];
void up(int rt){
tr[rt].ans = muti(tr[ls].ans , tr[rs].ans) ;
tr[rt].rans = muti(tr[ls].rans , tr[rs].rans) ;
return ;
}
void down(int rt){
if(tr[rt].lazy) {
swap(tr[ls].ans , tr[ls].rans) ;
swap(tr[rs].ans , tr[rs].rans) ;
tr[ls].lazy ^= 1 ;
tr[rs].lazy ^= 1 ;
tr[rt].lazy ^= 1 ;
}
return ;
}
void build(int rt , int l , int r){
tr[rt].l = l , tr[rt].r = r ;
tr[rt].lazy = 0 ;
if(l == r) {
if(a[l] == 'A') {
tr[rt].ans.a[0][0] = 1 , tr[rt].ans.a[0][1] = 0 ;
tr[rt].ans.a[1][0] = 1 , tr[rt].ans.a[1][1] = 1 ;
tr[rt].rans.a[0][0] = 1 , tr[rt].rans.a[0][1] = 1 ;
tr[rt].rans.a[1][0] = 0 , tr[rt].rans.a[1][1] = 1 ;
}else {
tr[rt].ans.a[0][0] = 1 , tr[rt].ans.a[0][1] = 1 ;
tr[rt].ans.a[1][0] = 0 , tr[rt].ans.a[1][1] = 1 ;
tr[rt].rans.a[0][0] = 1 , tr[rt].rans.a[0][1] = 0 ;
tr[rt].rans.a[1][0] = 1 , tr[rt].rans.a[1][1] = 1 ;
}
return ;
}
int mid = l + r >> 1 ;
build(ls , l , mid) ;
build(rs , mid + 1 , r) ;
up(rt) ;
return ;
}
void update(int rt , int l , int r){
if(l <= tr[rt].l && tr[rt].r <= r) {
tr[rt].lazy ^= 1 ;
swap(tr[rt].ans , tr[rt].rans) ;
return ;
}
down(rt) ;
int mid = tr[rt].l + tr[rt].r >> 1 ;
if(l <= mid) update(ls , l , r) ;
if(r > mid) update(rs , l , r) ;
up(rt) ;
return ;
}
node ask(int rt , int l , int r){
if(tr[rt].l >= l && tr[rt].r <= r) return tr[rt].ans ;
down(rt) ;
int mid = tr[rt].l + tr[rt].r >> 1 ;
node ans ;
ans.a[0][0] = 1 , ans.a[0][1] = 0 ;
ans.a[1][0] = 0 , ans.a[1][1] = 1 ;
if(l <= mid) ans = muti(ans , ask(ls , l , r)) ;
if(r > mid) ans = muti(ans , ask(rs , l , r)) ;
up(rt) ;
return ans ;
}
扫描线
const int MAX=20000 ;
int mark[MAX<<2];//记录某个区间的下底边个数
double sum[MAX<<2];//记录某个区间的下底边总长度
double Hash[MAX];//对x进行离散化,否则x为浮点数且很大无法进行线段树
//以横坐标作为线段(区间),对横坐标线段进行扫描
//扫描的作用是每次更新下底边总长度和下底边个数,增加新面积
struct seg{//线段
double l,r,h;
int d;
seg(){}
seg(double x1,double x2,double H,int c):l(x1),r(x2),h(H),d(c){}
bool operator<(const seg &a)const{
return h<a.h;
}
}s[MAX];
void Upfather(int n,int left,int right){
if(mark[n])sum[n]=Hash[right+1]-Hash[left];//表示该区间整个线段长度可以作为底边
else if(left == right)sum[n]=0;//叶子结点则底边长度为0(区间内线段长度为0)
else sum[n]=sum[n<<1]+sum[n<<1|1];
}
void Update(int L,int R,int d,int n,int left,int right){
if(L<=left && right<=R){//该区间是当前扫描线段的一部分,则该区间下底边总长以及上下底边个数差更新
mark[n]+=d;//更新底边相差差个数
Upfather(n,left,right);//更新底边长
return;
}
int mid=left+right>>1;
if(L<=mid)Update(L,R,d,n<<1,left,mid);
if(R>mid)Update(L,R,d,n<<1|1,mid+1,right);
Upfather(n,left,right);
}
int search(double key,double* x,int n){
int left=0,right=n-1;
while(left<=right){
int mid=left+right>>1;
if(x[mid] == key)return mid;
if(x[mid]>key)right=mid-1;
else left=mid+1;
}
return -1;
}
int main(){
int n,num=0;
double x1,x2,y1,y2;
while(cin>>n,n){
int k=0;
for(int i=0;i<n;++i){
cin>>x1>>y1>>x2>>y2;
Hash[k]=x1;
s[k++]=seg(x1,x2,y1,1);
Hash[k]=x2;
s[k++]=seg(x1,x2,y2,-1);
}
sort(Hash,Hash+k);
sort(s,s+k);
int m=1;
for(int i=1;i<k;++i)//去重复端点
if(Hash[i] != Hash[i-1])Hash[m++]=Hash[i];
double ans=0;
//memset(mark,0,sizeof mark);
//memset(sum,0,sizeof sum);如果下面是i<k-1则要初始化,因为如果对第k-1条线段扫描时会使得mark,sum为0才不用初始化的
for(int i=0;i<k;++i){//扫描线段
int L=search(s[i].l,Hash,m);
int R=search(s[i].r,Hash,m)-1;
Update(L,R,s[i].d,1,0,m-1);//扫描线段时更新底边长度和底边相差个数
ans+=sum[1]*(s[i+1].h-s[i].h);//新增加面积
}
printf("%.0lf
",ans);
}
puts("*") ;
return 0;
}
/*
这里注意下扫描线段时r-1:int R=search(s[i].l,Hash,m)-1;
计算底边长时r+1:if(mark[n])sum[n]=Hash[right+1]-Hash[left];
解释:假设现在有一个线段左端点是l=0,右端点是r=m-1
则我们去更新的时候,会算到sum[1]=Hash[mid]-Hash[left]+Hash[right]-Hash[mid+1]
这样的到的底边长sum是错误的,why?因为少算了mid~mid+1的距离,由于我们这利用了
离散化且区间表示线段,所以mid~mid+1之间是有长度的,比如Hash[3]=1.2,Hash[4]=5.6,mid=3
所以这里用r-1,r+1就很好理解了
*/
线段树维护hash
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , p = 1e9 + 7 , mod = 65536 ;
ll pw[N << 2] , hash1[N << 2] , hash2[N << 2] , sum[N << 2] , PW[N] ;
int a[N] ;
void push_up(int rt) {
sum[rt] = (sum[ls] + sum[rs]) % mod ;
hash1[rt] = (hash1[ls] * pw[rs] % p + hash1[rs]) % p ;
hash2[rt] = (hash2[rs] * pw[ls] % p + hash2[ls]) % p ;
pw[rt] = pw[ls] * pw[rs] % p ;
return ;
}
void build(int rt , int l , int r) {
if(l == r) {
pw[rt] = 19260817 ;
hash1[rt] = hash2[rt] = sum[rt] = a[l] ;
return ;
}
int mid = l + r >> 1 ;
build(ls , l , mid) ;
build(rs , mid + 1 , r) ;
push_up(rt) ;
}
void update(int rt , int l , int r , int p) {
if(l == r) {
hash1[rt] = hash2[rt] = sum[rt] = a[l] ;
return ;
}
int mid = l + r >> 1 ;
if(p <= mid) update(ls, l , mid , p) ;
else update(rs , mid + 1 , r , p) ;
push_up(rt) ;
}
ll ask1(int rt , int l , int r , int ql , int qr) {
if(ql <= l && r <= qr) return sum[rt] ;
int mid = l + r >> 1 , ans = 0 ;
if(ql <= mid) ans = (ans + ask1(ls , l , mid , ql , qr)) % mod ;
if(qr > mid) ans = (ans + ask1(rs , mid + 1 , r , ql , qr)) % mod ;
return ans ;
}
ll ask2(int rt , int l , int r , int ql , int qr) {
if(ql <= l && r <= qr)
return hash1[rt] ;
int mid = l + r >> 1 ;
ll ans = 0 ;
if(ql <= mid) ans = (ans + ask2(ls , l , mid , ql , qr) * PW[mid < min(qr , r) ? min(qr , r) - mid : 0]) % p ;
if(qr > mid) ans = (ans + ask2(rs , mid + 1 , r , ql , qr)) % p ;
return ans ;
}
ll ask3(int rt , int l , int r , int ql , int qr) {
if(ql <= l && r <= qr) return hash2[rt] ;
int mid = l + r >> 1 ;
ll ans = 0 ;
if(ql <= mid) ans = (ans + ask3(ls , l , mid , ql , qr)) % p ;
if(qr > mid) ans = (ans + ask3(rs , mid + 1 , r , ql , qr) * PW[max(l , ql) <= mid ? mid - max(l , ql) + 1 : 0]) % p ;
return ans ;
}
// 1 a[l , r] ++
// 2 [x , x + L - 1] == [y , y + L - 1]
int main()
{
int n , q ;
memset(pw , 1 , sizeof pw) ;
scanf("%d%d" , &n , &q) ;
PW[0] = 1 ;
for(int i = 1; i <= n ;i ++ )
PW[i] = PW[i - 1] * 19260817 % p ;
for(int i = 1; i <= n ;i ++ ) scanf("%d" , &a[i]) ;
for(int i = n ;i >= 2; i -- ) {
a[i] -= a[i - 1] ;
if(a[i] < 0) a[i] += mod ;
}
build(1 , 1 , n) ;
while(q --) {
int op ;
scanf("%d" , &op) ;
if(op == 1) {
int l , r ;
scanf("%d%d" , &l , &r) ;
a[l] = (a[l] + 1) % mod ;
update(1 , 1 , n , l) ;
if(r != n) {
a[r + 1] -- ;
if(a[r + 1] < 0) a[r + 1] += mod ;
update(1 , 1 , n , r + 1) ;
}
}else {
int x , y , L ;
scanf("%d%d%d" , &x , &y , &L) ;
if(x > y) swap(x , y) ;
if(x == y) puts("yes") ;
else if(ask1(1 , 1 , n , x + 1 , y) != 0) puts("no") ;
else if(ask2(1 , 1 , n , x + 1 , x + L - 1) != ask2(1 , 1 , n , y + 1 , y + L - 1))
puts("no") ;
else if(ask3(1 , 1 , n , x + 1 , x + L - 1) != ask3(1 , 1 , n , y + 1 , y + L - 1))
puts("no") ;
else puts("yes") ;
}
}
return 0 ;
}
树hash
void get(){
for(int i = 2; i < N ;i ++ ) {
if(!vis[i]) prime[++ tot] = i ;
for(int j = 1; j <= tot && i * prime[j] < N ;j ++ ) {
vis[i * prime[j]] = 1 ;
if(i % prime[j] == 0) break ;
}
}
}
ll f[N] ;
void dfs2(int u , int fa , int rt) {
sz[u] = 1 , f[u] = 1;
for(auto x : v[u]) {
if(x == fa || x == rt) continue ;
dfs2(x , u , rt) ;
sz[u] += sz[x] ;
f[u] += 1ll * prime[sz[x]] * f[x] ;
}
}
矩阵树(矩阵树定理主要用于图的生成树计数)
//f[i][i] 存i点的度数
//f[i][j] 存i点到j点的边数的相反数
//ans为图的生成树数量
void add(int u,int v){
f[u][u]++;f[v][v]++;
f[u][v]--;f[v][u]--;
}
int u[N] , v[N] , w[N];
ll gauss () {// 生成树的数量
ll ans = 1 ;
for (int i = 1; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
while (f[j][i]) {
ll t = f[i][i] / f[j][i] ;
for (int k = i; k < n; k ++)
f[i][k] = (f[i][k] - t * f[j][k] + mod) % mod ;
swap(f[i], f[j]) ;
ans = -ans ;
}
}
ans = (ans * f[i][i]) % mod ;
}
return (ans + mod) % mod ;
}
树上启发式合并
统计当前子树内最大颜色点数和
/*
1. CF600E - Lomsat gelral
题意
N个节点以点1为根的树，每一个节点有一个颜色color[i],对于一个以u为根的子树来说，
他的子树中的节点有多种颜色，现在求出出现次数最多的颜色(可能有多个颜色出现次数相同)，并将出现次数求和
输出以所有点的答案
分析
以点1为根，我们需要保存的信息为当前点子树中颜色出现次数，并且在统计答案的时候找到颜色最多的
这里我们可以用一个桶cnt[i]来记录颜色ii出现的次数，然后用mx来记录当前次数最多的颜色，sum记录次数最多的颜色的次数之和
这样当某种颜色出现次数cnt>mx的时候，我们将mx更新，
并且sum=cnt (为什么不是加上答案呢，因为我们最大值已经更新了，所以实际上是sum=0, sum = sum + cnt)
当cnt=mx的时候，mx不必更新，sum+=cnt
当cnt<mx的时候，啥都不用做
*/
void dfs(int u , int fa)//轻重链划分
{
size[u] = 1 ;
for(auto x : v[u])
{
if(x == fa) continue ;
dfs(x, u) ;
size[u] += size[x] ;
if(!son[u] || size[x] > size[son[u]])
son[u] = x ;
}
}
void upd(int u , int fa , int k) //将信息加入/撤回
{
//k = 1的时候是加上信息，k = -1的时候是撤回信息
// 记录信息
cnt[colour[u]] += k ;
if(k == 1 && cnt[colour[u]] >= mx) {
if(cnt[colour[u]] > mx) mx = cnt[colour[u]] , sum = 0 ;
sum += colour[u] ;
}
for(auto x : v[u])
if(x != fa && !vis[x]) upd(x , u , k) ;
}
void dsu(int u , int fa , int keep)//u为当前点, fa为父节点, keep为是否保留信息
{
for(auto x : v[u]) //先搜我们的轻儿子，过程中不保留信息
if(x != fa && x != son[u]) dsu(x , u , 0) ;
if(son[u]) dsu(son[u] , u , 1) , vis[son[u]] = 1 ;
upd(u , fa , 1) ;
// 统计答案
ans[u] = sum ;
if(son[u]) vis[son[u]] = 0 ;
if(!keep) upd(u , fa , -1) , mx = 0 , sum = 0; /* 如果信息不保留，那我们就撤回 */
}
统计当前字数内两点之间距离为k的点对
void dfs(int u , int f){
deep[u] = deep[f] + 1 ;
fa[u] = f ;
for(auto x : v[u]){
if(x != f) {
dfs(x , u) ;
size[u] += size[x] ;
if(!son[u] || size[x] > size[son[u]])
son[u] = x ;
}
}
}
void calc(int u , int keep){
num[deep[u]] += keep ;
sum[deep[u]] += keep * a[u] ;
for(auto x : v[u]) {
if(x == fa[u] || x == nowson) continue ;
calc(x , keep) ;
}
}
void query(int u , int lca){
int d = k + 2 * deep[lca] - deep[u] ;
if(d > 0){
ans[lca] += sum[d] ;
ans[lca] += num[d] * a[u] ;
}
for(auto x : v[u]){
if(x == fa[u]) continue ;
query(x , lca) ;
}
}
void dsu(int u , int fa , int keep){
for(auto x : v[u]){
if(x == fa || x == son[u]) continue ;
dsu(x , u , 0) ;
}
if(son[u]) dsu(son[u] , u , 1) , nowson = son[u] ;
for(auto x : v[u]){
if(x == fa || x == nowson) continue ;
query(x , u) ;
calc(x , 1) ;
}
num[deep[u]] += 1 ;
sum[deep[u]] += a[u] ;
nowson = 0 ;
if(!keep) calc(u , -1) ;
}
数论
中国剩余定理
ll exgcd(ll a , ll b , ll &x , ll &y){
if(b == 0){
x = 1 , y = 0 ;
return a ;
}
ll t = exgcd(b , a % b , y , x) ;
y -= a / b * x ;
return t ;
}
ll inv(ll a , ll b){
ll x , y ;
ll t = exgcd(a , b , x , y) ;
while(x < 0) x += b ;
return x ;
}
ll x[N] , m[N] ;
inline ll CRT(){
for(int i = 1; i <= 4 ;i ++ ) m[i] = prime[i] ;
ll M = 1, ans = 0;
for (int i = 1 ; i <= 4; i++)
M *= m[i];
for (int i = 1; i <= 4; i++)
ans = (ans + x[i] * (M / m[i]) % M * inv(M / m[i], m[i]) % M) % M;
return ans ;
}
求n以内的素数个数
#include<cmath>
#include<cstdio>
#include<iostream>
#define IL inline
#define RG register
using namespace std;
typedef long long LL;
const int N=5000005;
const int M=7;
const int PM=2*3*5*7*11*13*17;
int p[N],pi[N];
int phi[PM+1][M+1],sz[M+1];
LL n;
bool f[N];
IL void getprime(){
for(RG int i=2;i<N;i++){
if(!f[i])
p[++p[0]]=i;
pi[i]=p[0];
for(RG int j=1;p[j]*i<N;j++){
f[p[j]*i]=1;
if(i%p[j]==0)
break;
}
}
}
IL void init(){
getprime();
sz[0]=1;
for(RG int i=0;i<=PM;i++)
phi[i][0]=i;
for(RG int i=1;i<=M;i++){
sz[i]=p[i]*sz[i-1];
for(RG int j=1;j<=PM;j++)
phi[j][i]=phi[j][i-1]-phi[j/p[i]][i-1];
}
}
IL int sqrt2(LL x){
LL r=(LL)sqrt(x-0.1);
while(r*r<=x) r++;
return (int)(r-1);
}
IL int sqrt3(LL x){
LL r=(LL)cbrt(x-0.1);
while(r*r*r<=x) r++;
return (int)(r-1);
}
IL LL getphi(LL x,int s){
if(s==0) return x;
if(s<=M) return phi[x%sz[s]][s]+(x/sz[s])*phi[sz[s]][s];
if(x<=p[s]*p[s]*p[s]&&x<N){
int s2x=pi[sqrt2(x)];
LL ans=pi[x]-(s2x+s-2)*(s2x-s+1)/2;
for(RG int i=s+1;i<=s2x;i++)
ans+=pi[x/p[i]];
return ans;
}
return getphi(x,s-1)-getphi(x/p[s],s-1);
}
IL LL getpi(LL x){
if(x<N) return pi[x];
LL ans=getphi(x,pi[sqrt3(3)])+pi[sqrt3(x)]-1;
for(RG int i=pi[sqrt3(x)]+1,ed=pi[sqrt2(x)];i<=ed;i++)
ans-=getpi(x/p[i])-i+1;
return ans;
}
LL MeiLeh(LL x){
if(x<N) return pi[x];
int a=(int)MeiLeh(sqrt2(sqrt2(x)));
int b=(int)MeiLeh(sqrt2(x));
int c=(int)MeiLeh(sqrt3(x));
LL sum=getphi(x,a)+(LL)(b+a-2)*(b-a+1)/2;
for(int i=a+1;i<=b;i++){
LL w=x/p[i];
sum-=MeiLeh(w);
if(i>c) continue;
LL lim=MeiLeh(sqrt2(w));
for(int j=i;j<=lim;j++)
sum-=MeiLeh(w/p[j])-(j-1);
}
return sum;
}
Miller_Rabin
#define me(x,y) memset(x,y,sizeof x)
#define MIN(x,y) x < y ? x : y
#define MAX(x,y) x > y ? x : y
typedef long long ll;
const int maxn = 1e5+10;
const double INF = 0x3f3f3f3f;
const int MOD = 1e6;
const double eps = 1e-06;
ll Quick_Multiply(ll a,ll b,ll p){ // a*b%p
ll ans = 0;
a %= p;
b %= p;
if(b < 0) a = -a,b = -b;
while(b){
if(b&1) ans = (ans+a)%p;
b >>= 1;
a = (a+a)%p;
}
ans = (ans+p)%p;
return ans;
}
ll Quick_Pow(ll a,ll b,ll p){ //a^b%p
ll ans = 1;
while(b){
if(b&1) ans = Quick_Multiply(ans,a,p)%p;
b >>= 1;
a = Quick_Multiply(a,a,p)%p;
}
return ans;
}
bool Miller_Rabin(ll n){ //Miller_Rabin
ll i,j,a,x,y,t,u,s = 10;
if(n == 2 || n == 3) return true;
if(n < 2 || !(n&1)) return false;
for(t = 0,u = n-1;!(u&1); t++,u>>=1); //n-1 = u*2^t
for(i = 0; i < s; i++){
a = rand()%(n-1)-1;
x = Quick_Pow(a,u,n); //a^u
for(j = 0; j < t; j++){
y = Quick_Multiply(x,x,n); //x^2
if(y == 1 && x != 1 && x != n-1) return false; //����̽��
x = y;
}
if(x != 1) return false; //��������
}
return true;
}
Pollard_rho
ll factor[maxn];
int tot;
ll muti_mod(ll a,ll b,ll c){ //����(a*b) mod c,a,b,c<2^63
a%=c , b%=c;
ll ret=0;
while (b){
if (b&1){
ret+=a;
if (ret>=c) ret-=c;
}
a<<=1;
if (a>=c) a-=c;
b>>=1;
}
return ret;
}
ll pow_mod(ll x,ll n,ll mod){ //����x^n mod c ,�ǵݹ���
if (n==1) return x%mod;
int bit[64],k=0;
while (n){
bit[k++]=n&1;
n>>=1;
}
ll ret=1;
for (k=k-1;k>=0;k--){
ret=muti_mod(ret,ret,mod);
if (bit[k]==1) ret=muti_mod(ret,x,mod);
}
return ret;
}
bool check(ll a,ll n,ll x,ll t){ //��aΪ����n-1=x*2^t������n�Dz��Ǻ���
ll ret=pow_mod(a,x,n),last=ret;
for (int i=1;i<=t;i++){
ret=muti_mod(ret,ret,n);
if (ret==1 && last!=1 && last!=n-1) return 1;
last=ret;
}
if (ret!=1) return 1;
return 0;
}
bool Miller_Rabin(ll n){
ll x=n-1,t=0;
while ((x&1)==0) x>>=1,t++;
bool flag=1;
if (t>=1 && (x&1)==1){
for (int k=0;k<S;k++){
ll a=rand()%(n-1)+1;
if (check(a,n,x,t)) {flag=1;break;}
flag=0;
}
}
if (!flag || n==2) return 0;
return 1;
}
ll gcd(ll a,ll b){
if (a==0) return 1;
if (a<0) return gcd(-a,b);
while (b){
ll t=a%b; a=b; b=t;
}
return a;
}
ll Pollard_rho(ll x,ll c){
ll i=1,x0=rand()%x,y=x0,k=2;
while (1){
i++;
x0=(muti_mod(x0,x0,x)+c)%x;
ll d=gcd(y-x0,x);
if (d!=1 && d!=x){
return d;
}
if (y==x0) return x;
if (i==k){
y=x0;
k+=k;
}
}
}
void findfac(ll n){ //�ݹ������������ֽ�N
if (!Miller_Rabin(n)){
factor[tot++] = n;
return;
}
ll p=n;
while (p>=n) p=Pollard_rho(p,rand() % (n-1) +1);
findfac(p);
findfac(n/p);
}
int idx = 0 ;
struct node
{
ll val , num ;
node() {}
node(ll val , ll num) : val(val) , num(num) {}
bool operator<(const node &a) const
{
val < a.val ;
}
}fac[maxn];
void solve(ll n)
{
if (!Miller_Rabin(n)) printf("Prime
");
else{
tot = 0;
findfac(n);
sort(factor , factor + tot) ;
idx = 0 ;
for(int i = 0 ; i < tot ;i ++)
{
if(factor[i] != fac[idx].val)
fac[++ idx] = {factor[i] , 1};
else
fac[idx].num ++ ;
}
}
}
int main(){
srand(time(NULL));
int t;
scanf("%d",&t);
while (t--){
ll n;
scanf("%I64d",&n);
solve(n) ;
for(int i = 1; i <= idx ;i ++)
cout << fac[i].val << " " << fac[i].num << endl ;
}
}
min25筛
ll k;
ll check(ll v, ll n, ll ndr, ll nv) {
return v >= ndr ? (n / v - 1) : (nv - v);
}
// ll S[10000000];
// ll V[10000000];
ll primenum(ll n) // O(n^(3/4))
{
ll r = (ll)sqrt(n);
ll ndr = n / r;
assert(r*r <= n && (r+1)*(r+1) > n);
ll nv = r + ndr - 1;
std::vector<ll> S(nv+1);
std::vector<ll> V(nv+1);
for(ll i=0;i<r;i++)
V[i] = n / (i+1);
for(ll i=r;i<nv;i++)
V[i] = V[i-1] - 1;
for(ll i = 0;i<nv;i++)
S[i] = V[i] - 1; //求素数个数
for(ll p=2;p<=r;p++) {
if(S[nv-p] > S[nv-p+1]) {
ll sp = S[nv-p+1]; // sum of primes smaller than p
ll p2 = p*p;
for(ll i=0;i<nv;i++) {
if(V[i] >= p2) {
S[i] -= 1LL * (S[check(V[i] / p, n, ndr, nv)] - sp);// //求素数个数
}
else break;
}
}
}
return S[0];
}
ll primesum(ll n) // O(n^(3/4)){
ll r = (ll)sqrt(n);
ll ndr = n / r;
assert(r*r <= n && (r+1)*(r+1) > n);
ll nv = r + ndr - 1;
std::vector<ll> S(nv+1);
std::vector<ll> V(nv+1);
for(ll i=0;i<r;i++)
V[i] = n / (i+1);
for(ll i=r;i<nv;i++)
V[i] = V[i-1] - 1;
for(ll i = 0;i<nv;i++)
S[i] = V[i] * ( V[i] + 1) / 2 - 1; //求素数和
for(ll p=2;p<=r;p++) { // p is prime
if(S[nv-p] > S[nv-p+1]) {
ll sp = S[nv-p+1]; // sum of primes smaller than p
ll p2 = p*p;
for(ll i=0;i<nv;i++)
if(V[i] >= p2)
S[i] -= p* (S[check(V[i] / p, n, ndr, nv)] - sp); //求素数和
else break;
}
}
return S[0];
}
ST表
void solve(){
for (int i=1;i<=n;i++) a[i][0]=r[i];
for (int l=1;(1<<l)<=n;l++)
for (int i=1;i+(1<<l)-1<=n;i++)
a[i][l]=min(a[i][l-1],a[i+(1<<(l-1))][l-1]);
}
int get(int x , int y){
int l=(int)log2(y-x+1);
return min(a[x][l],a[y-(1<<l)+1][l]);
}
二次剩余
const int mod=998244353;
template<typename T>
inline int pow(int x,T y)
{
rg int res=1;x%=mod;
for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)res*x%mod;
return res;
}
inline int Quadratic_residue(const int a)
{
if(a==0)return 0;
int b=(rand()<<14^rand())%mod;
while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;
int s=mod-1,t=0,x,inv=pow(a,mod-2),f=1;
while(!(s&1))s>>=1,t++,f<<=1;
t--,x=pow(a,(s+1)>>1),f>>=1;
while(t)
{
f>>=1;
if(pow((int)((ll)inv*x%mod*x%mod),f)!=1)x=(ll)x*pow(b,s)%mod;
t--,s<<=1;
}
return min(x,mod-x);
}
高精度
vector<int> add(vector<int> A,vector<int> B){
vector<int> C;
int t=0;
for(int i=0;i<A.size()||i<B.size();i++) {
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t)
C.push_back(1);
return C;
}
vector<int> muti(vector<int> A,int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size()||t;i++){
if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
return C;
}
bool cmp(vector<int> A,vector<int> B){
if(A.size()!=B.size()) return A.size()>B.size();
for(int i=A.size();i>=0;i--)
if(A[i]!=B[i])
return A[i]>B[i];
return true;
}
vector<int> div(vector<int> A, int b, int &r){
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- ) {
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
vector<int> sub(vector<int> A,vector<int> B){
vector<int> C;
int t=0;
for(int i=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size()) t-=B[i];
C.push_back((t+10)%10);
if(t<0) t=1;
else t=0;
}
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
void print(vector<int> a){
for(int i = a.size() - 1; i >= 0 ;i --) cout << a[i] ;
puts("") ;
return ;
}
高精度组合数学
void get_prime(int n){
for(int i = 2;i <= n;i ++) {
if(!st[i]) prime[tot ++] = i ;
for(int j = 0; j < tot && i * prime[j] <= n ;j ++){
st[i * prime[j]] = true ;
if(i % prime[j] == 0) break ;
}
}
return ;
}
int get(int a , int p){
int sum = 0 ;
while(a){
sum += a / p ;
a /= p ;
}
return sum ;
}
vector<int> muti(vector<int> a , int b){
int t = 0 ;
vector<int> res ;
for(int i = 0;i < a.size() ;i ++){
t += a[i] * b ;
res.push_back(t % 10) ;
t /= 10 ;
}
while(t){
res.push_back(t % 10) ;
t /= 10 ;
}
return res ;
}
int main(){
int a , b ;
cin >> a >> b ;
get_prime(a);
for(int i = 0; i < tot ;i ++){
int p = prime[i] ;
sum[i] = get(a,p) - get(b,p) - get(a-b , p);
}
vector<int> res;
res.push_back(1);
for(int i = 0;i < tot ; i ++)
for(int j = 0; j < sum[i] ;j ++)
res = muti(res, prime[i]);
for(int i = res.size() - 1;i >= 0;i --)
cout << res[i] ;
cout << endl ;
return 0;
}
高斯消元
#define D double
D a[maxn][maxn];
int n;
int main(){
scanf("%d",&n);
for(re int i=1;i<=n;++i){
for(re int j=1;j<=n+1;++j){
scanf("%lf",&a[i][j]);
}
}
for(re int i=1;i<=n;++i)//枚举列（项）{
re int max=i;
for(re int j=i+1;j<=n;++j)//选出该列最大系数
if(fabs(a[j][i])>fabs(a[max][i]))
//fabs是取浮点数的绝对值的函数
max=j;
for(re int j=1;j<=n+1;++j)//交换
swap(a[i][j],a[max][j]);
if(!a[i][i])//最大值等于0则说明该列都为0，肯定无解{
puts("No Solution");
return 0;
}
for(re int j=1;j<=n;++j)//每一项都减去一个数（就是小学加减消元）{
if(j!=i){
re D temp=a[j][i]/a[i][i];
for(re int k=i+1;k<=n+1;++k){
a[j][k]-=a[i][k]*temp;
//a[j][k]-=a[j][i]*a[i][k]/a[i][i];
}
}
}
}
//上述操作结束后，矩阵会变成这样
/*
k1*a=e1
k2*b=e2
k3*c=e3
k4*d=e4
*/
//所以输出的结果要记得除以该项系数，消去常数
for(re int i=1;i<=n;++i)
{
printf("%.2lf
",a[i][n+1]/a[i][i]);
}
return 0;
}
康托展开
#include <bits/stdc++.h>
using namespace std ;
//返回数组a中当下顺序的康拖映射
typedef unsigned long long ll ;
ll b[30] ;
//对前 10 个自然数(0 ~ 9)的阶乘存入表
//以免去对其额外的计算
ll fact[22] ;
/**
* @brief 康拓展开
*
* @param[in] permutation 输入的一个全排列
* @param[out] num 输入的康拓映射，即是第几个全排列
*/
ll contor(vector<ll> permutation) {
ll num = 0;
ll len = permutation.size();
for (ll i = 0; i < len; ++i) {
ll cnt = 0; // 在 i 之后，比 i 还小的有几个
for (ll j = i + 1; j < len; ++j)
if (permutation[i] > permutation[j]) ++cnt;
num += cnt * fact[len - i - 1];
}
return num + 1;
}
//对前 10 个自然数(0 ~ 9)的阶乘存入表
//以免去对其额外的计算
/**
* @brief 逆康拓展开
*
* @param[in] bits 给定全排列的使用数字个数
* @param[in] num 给定全排列的次位
* @param[out] permutation 输出对应的全排列
*/
vector<ll> revContor(ll bits, ll num) {
num = num - 1; //有 num - 1 个排列比目标序列要小
vector<bool> vis(bits + 1, false);
vector<ll> permutation(bits, -1);
ll n, residue = num;
for (ll i = 0; i < bits; ++i) {
n = residue / (fact[bits - i - 1]);
residue = residue % (fact[bits - i - 1]);
for (ll j = 1; j <= bits; ++j) {
if (!vis[j] && !(n--)) {
vis[j] = true;
permutation[i] = j;
break;
}
}
}
return permutation;
}
int main()
{
int n , m ;
cin >> n >> m ;
fact[0] = 1;
for(ll i = 1; i <= n ;i ++)
fact[i] = fact[i - 1] * i ;
for(int i = 1; i <= m ;i ++)
{
char s[2] ;
cin >> s ;
if(s[0] == 'P') // 求第x大的字典序
{
ll x ;cin >> x ;
vector<ll> t = revContor(n , x) ;
for(auto xx : t)
cout << xx << " " ;
puts("") ;
}
else // 求字典序第几大
{
vector<ll> b ;
for(ll i = 1 , x ; i <= n ;i ++) cin >> x , b.push_back(x) ;
cout << contor(b) << endl ;
}
}
return 0 ;
}
扩展欧几里得
ll exgcd(ll a , ll b , ll &x , ll &y){
if(b == 0){
x = 1 , y = 0 ;
return a ;
}
ll d = exgcd(b , a % b , y , x ) ;
y -= (a / b) * x ;
return d ;
}
扩展欧几里得求正整数
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return a;
}
ll q=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return q;
}
ll gcd(ll a , ll b)
{
return b == 0 ? a : gcd(b , a % b) ;
}
ll tx , ty , tz ;
// 求正整数
void get(ll a , ll b , ll d)
{
ll x , y ;
int md=exgcd(a,b,x,y);
a/=md,b/=md,d/=md;
int x1=x*d;
x1=(x1%b+b)%b;
ll y1=(d-a*x1)/b;
y1=abs(y1);
ll y2=y*d;
y2=(y2%a+a)%a;
int x2=(d-b*y2)/a;
x2=abs(x2);
if(x1+y1<x2+y2) tx = x1 , ty = y1 ;
else tx = x2 , ty = y2 ;
}
三维差分
for(int i = 1; i <= m ;i ++ ) {
int a , b , c , d , e , f ;
// a <= x <= d , b <= y <= e , c <= z <= f
cin >> a >> b >> c >> d >> e >> f ;
sum[a][b][c] ++ ;
sum[a][e + 1][c] -- ;
sum[d + 1][b][c] -- ;
sum[a][b][f + 1] -- ;
sum[d + 1][b][f + 1] ++ ;
sum[a][e + 1][f + 1] ++ ;
sum[d + 1][e + 1][c] ++ ;
sum[d + 1][e + 1][f + 1] -- ;
}
for(int i = 1; i <= n ;i ++ ) {
for(int j = 1; j <= n ;j ++ ) {
for(int k = 1; k <= n ;k ++ ) {
sum[i][j][k] += sum[i - 1][j][k] + sum[i][j - 1][k] + sum[i][j][k - 1] + sum[i - 1][j - 1][k - 1] - sum[i - 1][j - 1][k] - sum[i - 1][j][k - 1] - sum[i][j - 1][k - 1] ;
}
}
}
几何
直线相交求交点
const int maxh=62;
#define rint register int
int cmp(double x){
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
double sqr(double x){
return x*x;
}
struct point {
double x,y;
point(){}
point(double a,double b):x(a),y(b){}
void input(){
cin>>x>>y;
}
friend point operator -(const point &a,const point &b){
return point (a.x-b.x,a.y-b.y);
}
friend point operator *(const point &a,const double &b){
return point (a.x*b,a.y*b);
}
friend point operator *(const double &b,const point &a){
return point (a.x*b,a.y*b);
}
friend point operator /(const point &a,const double &b){
return point (a.x/b,a.y/b);
}
};
double cross(const point &a,const point &b){
return a.x*b.y-a.y*b.x;
}
struct line {
point a,b;
line(){}
line(point x,point y):a(x),b(y){}
void input(){
a.input();
b.input();
}
}a[N];
bool parallel(line a,line b){
return !cmp(cross(a.a-a.b,b.a-b.b));
}
bool line_make_point(line a,line b,point &res){
if(parallel(a,b)) return false;
double s1=cross(a.a-b.a,b.b-b.a);
double s2=cross(a.b-b.a,b.b-b.a);
res=(s1*a.b-s2*a.a)/(s1-s2);
return true;
}
double res=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
a[i].input();
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++){
point x,y,z;
if(!line_make_point(a[i],a[j],x)) continue;
if(!line_make_point(a[i],a[k],y)) continue;
if(!line_make_point(a[j],a[k],z)) continue;
double b,c,d;
b=sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));
c=sqrt(sqr(x.x-z.x)+sqr(x.y-z.y));
d=sqrt(sqr(y.x-z.x)+sqr(y.y-z.y));
double p=(b+c+d);
res=max(res,p/*sqrt(p*(p-b)*(p-c)*(p-d))*/);
}
if(abs(res)<eps) {
cout<<"no triangle";
} else cout<<fixed<<setprecision(12)<<res;
return 0;
}
圆与正方形的关系
struct node
{
int x , y , r ;
}p[6] , z[6];
int check1(node a){
if(a.x > z[0].x && a.x < z[1].x && a.y > z[0].y && a.y < z[3].y) return 1 ;
for(int i = 0 ;i < 4 ;i ++){
if(z[i].x == z[i + 1].x)
if(a.x == z[i].x && a.y >= min(z[i].y , z[i + 1].y) && a.y <= max(z[i].y , z[i + 1].y)) return 2 ;
if(z[i].y == z[i + 1].y)
if(a.y == z[i].y && a.x >= min(z[i].x , z[i + 1].x) && a.x <= max(z[i].x , z[i + 1].x)) return 2 ;
}
return 0 ;
}
int check2(node a){
int t = (p[0].x - a.x) * (p[0].x - a.x) + (p[0].y - a.y) * (p[0].y - a.y) ;
if(t == p[0].r * p[0].r) return 2 ;
if(t < p[0].r * p[0].r) return 1 ;
return 0 ;
}
bool have(){
for(int i = 0 ;i <= 4 ;i ++)
if(check1(p[i]) == 1) return 1 ;
for(int i = 0 ;i < 4;i ++)
if(check2(z[i]) == 1) return 1 ;
return 0 ;
}
bool touch(){
for(int i = 0 ;i <= 4 ;i ++)
if(check1(p[i]) == 2) return 1 ;
for(int i = 0 ;i < 4 ;i ++)
if(check2(z[i]) == 2) return 1 ;
return 0 ;
}
int main(){
int r ;
cin >> p[0].x >> p[0].y >> p[0].r ;
p[1].x = p[0].x + p[0].r , p[1].y = p[0].y ;
p[2].x = p[0].x , p[2].y = p[0].y + p[0].r ;
p[3].x = p[0].x - p[0].r , p[3].y = p[0].y ;
p[4].x = p[0].x , p[4].y = p[0].y - p[0].r ;
cin >> z[0].x >> z[0].y >> r;
z[1].x = z[0].x + r , z[1].y = z[0].y ;
z[2].x = z[0].x + r , z[2].y = z[0].y + r ;
z[3].x = z[0].x , z[3].y = z[0].y + r ;
z[4] = z[0] ;
if(have()) puts("2") ;
else if(touch()) puts("1") ;
else puts("0") ;
return 0 ;
}
圆与矩形相交面积
struct Point{ double x, y;
Point() {}
Point(double xx, double yy)
{
x = xx;
y = yy;
}
Point operator-(Point s) { return Point(x - s.x, y - s.y); }
Point operator+(Point s) { return Point(x + s.x, y + s.y); }
double operator*(Point s) { return x * s.x + y * s.y; }
double operator^(Point s) { return x * s.y - y * s.x; }
} p[M];
double max(double a, double b) { return a > b ? a : b; }
double min(double a, double b) { return a < b ? a : b; }
double len(Point a) { return sqrt(a * a); } // ���� a �ij���
double dis(Point a, Point b) { return len(b - a); } // a �� b ֮���ľ���
double cross(Point a, Point b, Point c) // (a , b) ��(a , c){
return (b - a) ^ (c - a);
}
double dot(Point a, Point b, Point c) // (a , b) * (a , c){
return (b - a) * (c - a);
}
int judge(Point a, Point b, Point c) // �ж� ��c �Ƿ��� �߶� ab ��{
if (c.x >= min(a.x, b.x) && c.x <= max(a.x, b.x) && c.y >= min(a.y, b.y) && c.y <= max(a.y, b.y))
return 1;
return 0;
}
double area(Point b, Point c, double r) // Բ�� a �� �뾶 r �� �������� a , b , c �ཻ������{
Point a(0.0, 0.0);
if (dis(b, c) < eps)
return 0.0;
double h = fabs(cross(a, b, c)) / dis(b, c);
if (dis(a, b) > r - eps && dis(a, c) > r - eps){
double angle = acos(dot(a, b, c) / dis(a, b) / dis(a, c));
if (h > r - eps)
return 0.5 * r * r * angle;
else if (dot(b, a, c) > 0 && dot(c, a, b) > 0){
double angle1 = 2 * acos(h / r);
return 0.5 * r * r * fabs(angle - angle1) + 0.5 * r * r * sin(angle1);
}
else return 0.5 * r * r * angle;
}
else if (dis(a, b) < r + eps && dis(a, c) < r + eps) return 0.5 * fabs(cross(a, b, c));
else{
if (dis(a, b) > dis(a, c))swap(b, c);
if (fabs(dis(a, b)) < eps) return 0.0;
if (dot(b, a, c) < eps) {
double angle1 = acos(h / dis(a, b));
double angle2 = acos(h / r) - angle1;
double angle3 = acos(h / dis(a, c)) - acos(h / r);
return 0.5 * dis(a, b) * r * sin(angle2) + 0.5 * r * r * angle3;
}
else{
double angle1 = acos(h / dis(a, b));
double angle2 = acos(h / r);
double angle3 = acos(h / dis(a, c)) - angle2;
return 0.5 * r * dis(a, b) * sin(angle1 + angle2) + 0.5 * r * r * angle3;
}
}
}
int main(){
int n = 4;
double rx, ry, R;
scanf("%lf%lf%lf", &rx, &ry, &R);
scanf("%lf%lf%lf%lf", &p[1].x, &p[1].y, &p[3].x, &p[3].y);
p[2].x = p[1].x;
p[2].y = p[3].y;
p[4].x = p[3].x;
p[4].y = p[1].y;
p[5] = p[1];
Point O(rx, ry);
for (int i = 1; i <= n + 1; i++)
p[i] = p[i] - O;
O = Point(0, 0);
double sum = 0;
for (int i = 1; i <= n; i++){
int j = i + 1;
double s = area(p[i], p[j], R);
if (cross(O, p[i], p[j]) > 0) sum += s;
else sum -= s;
}
printf("%.4lf
", fabs(sum));
}
一个点是否在线段上
double direction( node p1,node p2,node p ){
return ( p1.x -p.x )*( p2.y-p.y) - ( p2.x -p.x )*( p1.y-p.y) ;
}
int on_segment( node p1,node p2 ,node p ){
double max=p1.x > p2.x ? p1.x : p2.x ;
double min =p1.x < p2.x ? p1.x : p2.x ;
double max1=p1.y > p2.y ? p1.y : p2.y ;
double min1=p1.y < p2.y ? p1.y : p2.y ;
if( p.x >=min && p.x <=max &&
p.y >=min1 && p.y <=max1 )
return 1;
else
return 0;
}
bool check1(node p1 , node p2 , node q){
if( !on_segment( p1,p2,q ) ) return 0 ;
if( direction( q,p1,p2 )==0 )return 1 ;
else return 0 ;
}
bool check(int x ,int y){
for(int i = 1; i <= n ;i ++)
if(x != i && y != i && check1(a[x] , a[y] , a[i])) return 0 ;
for(int i = 1; i <= n ;i ++)
if(check1(a[x] , a[y] , b[i]))
return 0 ;
return 1 ;
}
计算几何板子
// 直线相交求交点 ， 凸包算法， 求点是否在多边形范围内
struct point {
double x,y;
point(){}
point(double a,double b):x(a),y(b){}
void input(){
cin>>x>>y;
}
friend point operator -(const point &a,const point &b){
return point (a.x-b.x,a.y-b.y);
}
friend point operator *(const point &a,const double &b){
return point (a.x*b,a.y*b);
}
friend point operator *(const double &b,const point &a){
return point (a.x*b,a.y*b);
}
friend point operator /(const point &a,const double &b){
return point (a.x/b,a.y/b);
}
}p[N] , s[N] ;
struct line {
point a,b;
line(){}
line(point x,point y):a(x),b(y){}
void input(){
a.input();
b.input();
}
}a[N];
int cmp(double x){
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
double sqr(double x){
return x*x;
}
double cross(const point &a,const point &b){
return a.x*b.y-a.y*b.x;
}
bool parallel(line a,line b){
return !cmp(cross(a.a-a.b,b.a-b.b));
}
bool line_make_point(line a,line b,point &res){
if(parallel(a,b)) return false;
double s1=cross(a.a-b.a,b.b-b.a);
double s2=cross(a.b-b.a,b.b-b.a);
res=(s1*a.b-s2*a.a)/(s1-s2);
return true;
}
double dis(point a,point b)
{
point c=a-b;
return sqrt(c.x*c.x+c.y*c.y);
}
double cross(point &a,point &b)//叉乘{
return a.x*b.y-a.y*b.x;
}
bool cmp(point a,point b)//极角排序{
double x=cross(a-p[1],b-p[1]);//以p[1]为积点
if(x>0) return 1;//让a处于b的顺时针
if(x==0&&dis(a,p[1])<dis(b,p[1])) return 1;//角度相同按距离排序
return 0;
}
//
double mulx(point p1,point p2,point p3){
return cross(p2-p1,p3-p1);
}
double area(point *p,int n){
if(n<3) return 0;
p[n+1]=p[1];
double sum=0;
for(int i=1;i<=n;i++)
{
sum+=p[i].x*p[i+1].y-p[i].y*p[i+1].x;//不管这个多边形在哪，都以原点为分割点，就算原点在外面也可以算出，因为有正负可以抵消掉多余的
}
sum=fabs(sum/2.0);
return sum;
}
// 判断点是否在这个多边形范围内
bool intubao(point *s,int n,point a){
int f=0;
for(int i=0;i<n;i++)
{
if(cross(s[(i+1)%n]-s[i],a-s[i])>0) f++;
}
//if(cross(s[1]-s[n],a-s[n])>0) f++;
if(f==n) return 1;
return 0;
}
// 先按照x ， 然后y
bool cmp2(point a,point b){
if (a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
int n,q , m ;
void Tubao() {
sort(p,p+n,cmp2);
for(int i=0;i<n;i++){
while(m>1&&mulx(s[m-2],s[m-1],p[i])<=0) m--;
s[m++]=p[i];
}
int kk=m;
for(int i=n-2;i>=0;i--){
while(m>kk&&mulx(s[m-2],s[m-1],p[i])<=0) m--;
s[m++]=p[i];
}
if(n>1)
m--;
}
DP
求所有区间内任意个数相加和为k的总方案数
/*
题意：一个长度为n的数组，求任意[ L,R ]区间和为S的总数。
题解：01背包
dp[N]代表前i个数中和为N的数量
每次dp[0]+=1，我们01背包板子循环到第i个物品求的是前i个物品和为N的数量，并没有
[2,i]、[3，i]、[4，i]、…、[i，i]这些情况，少了i-1种情况答案肯定不对，所以我们只需要把dp[0]赋值为 1 + （i-1） 原始就为1，再加上少的i-1中情况。
*/
ll a[maxn],dp[maxn];
int main(){
ll n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
ll ans=0;
for(int i=1;i<=n;i++){
dp[0]+=1;//[2,i]、[3，i]、[4，i]、...、[i，i]
for(int j=k;j>=a[i];j--)
dp[j]=(dp[j]+dp[j-a[i]])%mod;
ans=(ans+dp[k])%mod;//前i个数的和为K的数量
}
cout<<ans<<endl;
return 0;
}
BM线性递推
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll n;
namespace linear_seq {
const int N=10010;
ll res[N],base[N],_c[N],_md[N];
vector<int> Md;
void mul(ll *a,ll *b,int k) {
rep(i,0,k+k) _c[i]=0;
rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
for (int i=k+k-1;i>=k;i--) if (_c[i])
rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,0,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
ll ans=0,pnt=0;
int k=SZ(a);
assert(SZ(a)==SZ(b));
rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
Md.clear();
rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
rep(i,0,k) res[i]=base[i]=0;
res[0]=1;
while ((1ll<<pnt)<=n) pnt++;
for (int p=pnt;p>=0;p--) {
mul(res,res,k);
if ((n>>p)&1) {
for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
if (ans<0) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(1,1),B(1,1);
int L=0,m=1,b=1;
rep(n,0,SZ(s)) {
ll d=0;
rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
if (d==0) ++m;
else if (2*L<=n) {
VI T=C;
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+1-L; B=T; b=d; m=1;
} else {
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
int gao(VI a,ll n) {
VI c=BM(a);
c.erase(c.begin());
rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};
int main() {
/*push_back 进去前 8~10 项左右、最后调用 gao 得第 n 项*/
vector<int>v;
v.push_back(3);
v.push_back(9);
v.push_back(20);
v.push_back(46);
v.push_back(106);
v.push_back(244);
v.push_back(560);
v.push_back(1286);
v.push_back(2956);
v.push_back(6794);
int nCase;
scanf("%d", &nCase);
while(nCase--){
scanf("%lld", &n);
printf("%lld
",1LL * linear_seq::gao(v,n-1) % mod);
}
}
搜索
A_star算法
第 K 短路
int h[N] , rh[N] , e[N] , ne[N] , w[N] , idx;
void add(int *h , int a , int b , int c){
e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx ++ ;
}
int S , T , K ;
int dis[N] , f[N] , n , m , st[N] ;
void dij(){
priority_queue<PII , vector<PII> , greater<PII> > q ;
memset(dis , 0x3f , sizeof dis) ;
dis[T] = 0 ;
memset(st , 0 , sizeof st) ;
q.push({0 , T}) ;
while(q.size()){
auto t = q.top() ; q.pop() ;
int u = t.second ;
if(st[u]) continue ;
st[u] = 1 ;
for(int i = rh[u] ; ~i ; i = ne[i]){
int v = e[i] ;
if(dis[v] > dis[u] + w[i])
dis[v] = dis[u] + w[i] , q.push({dis[v] , v}) ;
}
}
memcpy(f , dis , sizeof f) ;
return ;
}
int a_star(){
priority_queue<PIII , vector<PIII> , greater<PIII > > q ;
q.push({f[S] , {0 , S}}) ;
memset(st , 0 , sizeof st) ;
while(q.size()){
auto t = q.top() ; q.pop() ;
int u = t.second.second , distance = t.second.first ;
if(st[u] >= K) continue ;
st[u] ++ ;
if(u == T && st[u] == K) return distance ;
for(int i = h[u] ; ~i ; i = ne[i]){
int v = e[i] ;
if(st[v] < K)
q.push({distance + w[i] + f[v] , {distance + w[i] , v}}) ;
}
}
return -1 ;
}
int main(){
n = in() , m = in() ;
memset(h , -1 , sizeof h ) , memset(rh , -1 , sizeof rh) ;
for(int i = 1 , a , b , c ; i <= m ;i ++)
a = in() , b = in() , c = in() , add(h , a , b , c) , add(h , b , a , c) , add(rh , b , a , c) , add(rh , a , b , c) ;
S = 0 , T = n - 1 , K = 2 ;
if(S == T) K ++ ;
dij() ;
memset(st , 0 , sizeof st) ;
int t = a_star() ;
cout << t << endl ;
return 0 ;
}
/*
*/