• 13967708449
  • 1322284500@qq.com

Category Archive题解

AGC 001E BBQ Hard

题目传送门

分析:

题目的意思大概可以转化为,给你数字n,然后给你A B数组,然后询问

\sum_{i\not =j} \begin{pmatrix}
A_i +B_i+A_j+B_j \\
A_i +B_i
\end{pmatrix}

然后给出数据范围,n≤200000, A[i],B[i]≤2000
我们可以发现, A B的范围都很小,那么我们可以进行模型转化,我们把

\begin{pmatrix}
A_i +B_i+A_j+B_j \\
A_i +A_j
\end{pmatrix}

看成从(-A_i,-B_i)走到(A_j,B_j)的方案数,这个东西,我们直接直接暴力跑就好了…先把所有点向右上方位移到第一象限,假设我们直接从原点出发,那么走到(x,y)点的方案数就是(x-1,y)+(x,y-1)方案数的和…然后我们一开始就把所有的起点位置的值加1,然后跑一次,就可以求出所有起点到一个终点的方案数…最后要减去自己到自己的方案,再除以2….
(感谢Vexoben的指导)

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 4e3+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
LL n,a[200010],b[200010],ans;
LL fac[N*2],fav[N*2],inv[N*2];
void init()
{
    fac[0]=fav[0]=1;
    inv[1] = fac[1] = fav[1] = 1;
    for (int i = 2; i < N * 2; ++i) 
    {
        inv[i] = -mod / i * inv[mod % i] % mod + mod;
        fac[i] = fac[i - 1] * i % mod;
        fav[i] = fav[i - 1] * inv[i] % mod;
    }
}
inline LL C(int x, int y) 
{
    if (x < 0 || x < y) return 0;
    return fac[x] * fav[y] % mod * fav[x - y] % mod;
}
LL cost[N][N];
signed main()
{
    read(n);init();
    for(int i=1;i<=n;i++) read(a[i]),read(b[i]);
    for(int i=1;i<=n;i++) cost[-a[i]+2001][-b[i]+2001]++;
    for(int i=1;i<=4001;i++)
        for(int j=1;j<=4001;j++)
            (cost[i][j]+=(cost[i-1][j]+cost[i][j-1]))%=mod;
    //cout<<ans<<endl;
    for(int i=1;i<=n;i++) 
        ans=(ans+cost[a[i]+2001][b[i]+2001])%mod;
    //cout<<ans<<endl;
    for(int i=1;i<=n;i++)
        ans=(ans-C(a[i]*2+b[i]*2,a[i]*2)+mod)%mod;
    printf("%lld\n",(ans*(mod+1)/2%mod+mod)%mod);
    return 0;
}

2286. [Sdoi2011]消耗战

题意:

给你一棵带边权的树,然后给出m次询问,每次询问一些点,问他们和点1不连通的最小代价…..

分析:

我们知道数据范围非常大,然后复杂度要么是O(n)要么是O(nlogn),我们考虑,我们怎么求最小代价,明显是一个dp可以解决的.但是每次直接O(n)dp一遍明显不行,我们考虑,询问的点的和最多和n同级,那么我们对于每次询问建出虚树,书上的边是两个点之间链上是最小值,然后在虚树上面dp就好了….

代码:



\#pragma GCC optimize(3) #include<bits/stdc++.h> #define LL long long const LL N=5e5+10; const LL inf=0x3f3f3f3f; const LL mod=1e9+7; using namespace std; template <typename tp> inline void read(tp &x) { x=0;char c=getchar();bool f=0; for(;c<'0'||c>'9';f=(c=='-'),c=getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar()); if(f) x=-x; } int n,m; int head[N],cnt,ask[N],vis[N]; struct Edge{int next,to,cost;} edge[N*2]; void add(int from,int to,int cost) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].cost=cost; head[from]=cnt; } int dfn[N],num,fa[N][22],dep[N]; LL hua[N][22]; void dfs(int now,int fath,int cost) { dfn[now]=++num;fa[now][0]=fath; dep[now]=dep[fath]+1;hua[now][0]=cost; for(int i=1;i<=20;i++) fa[now][i]=fa[fa[now][i-1]][i-1]; for(int i=1;i<=20;i++) hua[now][i]=min(hua[fa[now][i-1]][i-1],hua[now][i-1]); for(int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if(to==fath) continue; dfs(to,now,edge[i].cost); } } bool cmp(int a,int b){return dfn[a]<dfn[b];} int lca(int a,int b) { if(dep[a]<dep[b]) swap(a,b); for(int i=20;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i]; if(a==b) return a; for(int i=20;i>=0;i--) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i]; return fa[a][0]; } stack<int> Vtree; vector<int> son[N]; LL coo(int a,int b,LL ret=inf) {for(int i=20;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) ret=min(ret,hua[a][i]),a=fa[a][i];return ret;} LL dfs_ans(int now) { // if(vis[now]) return inf; LL ret=0,siz=son[now].size(); for(int i=0;i<siz;i++) ret+=min(dfs_ans(son[now][i]),coo(son[now][i],now)); son[now].clear(); if(vis[now]) return inf; return ret; } int main() { read(n); for(int i=1;i<n;i++) { int u,v,c; read(u),read(v),read(c); add(u,v,c),add(v,u,c); } dfs(1,1,inf); read(m); for(int cas=1,opt;cas<=m;cas++) { read(opt); for(int i=1;i<=opt;i++) read(ask[i]),vis[ask[i]]=1; sort(ask+1,ask+opt+1,cmp); Vtree.push(1); for(int i=1;i<=opt;i++) { int top=Vtree.top(),Lca=lca(top,ask[i]); while(dfn[top]>dfn[Lca]) { Vtree.pop(); if(Vtree.size()>=1&&dfn[Vtree.top()]>=dfn[Lca]) son[Vtree.top()].push_back(top); else { Vtree.push(Lca); son[Lca].push_back(top); } top=Vtree.top(); } Vtree.push(ask[i]); } while(!Vtree.empty()) { int top=Vtree.top(); Vtree.pop();if(Vtree.empty()) break; son[Vtree.top()].push_back(top); } printf("%lld\n",dfs_ans(1)); for(int i=1;i<=opt;i++) vis[ask[i]]=0; } return 0; }

密码保护:2018提高组赛前模拟赛day1—-T2:Easy LCA

这是一篇受密码保护的文章,您需要提供访问密码:

[Cqoi2010]内部白点

题意:

你有一个平面,然后你有一些黑点,然后内部白点(上下左右都有黑点的点)会被黑点染黑,询问最后有多少黑点……

分析:

我们发现所有被染黑的白点都是一开始上下左右都有黑点的点,然后我们把问题转换成了,上下左右都有黑点的点有多少个…..这个怎么求呢…..
当然我们先去哈希一下,得到了新的图,然后我们发现两个点在同一行,他们之间的点有可能被染黑,只要这些点上下也有黑点就好了,然后我们发现上下关系的黑点的贡献是一段,那么我们维护一个树状数组,从下往上枚举所有横线,然后维护竖线,当我们扫到下端点的时候,加入,扫到上端点时删除…..

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=998244353;
const LL inf=0x3f3f3f3f;
const double eps=1e-12;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,totx,toty,ans,last;
struct Node{int x,y;}node[N];
bool cmp1(Node a,Node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp2(Node a,Node b){return a.y==b.y?a.x<b.x:a.y<b.y;}
P Ve[N];
vector<int> be[N],en[N],vec[N];
namespace BIT
{
    int xx[N*4];
    int lowbit(int now){return now&-now;}
    void change(int now,int v){for(;now<=n;now+=lowbit(now)) xx[now]+=v;}
    int query(int now,int ret=0){for(;now;now-=lowbit(now)) ret+=xx[now];return ret;}
}
using namespace BIT;
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(node[i].x),read(node[i].y);
    sort(node+1,node+n+1,cmp2);last=-inf;
    for(int i=1;i<=n;i++)
    {
        if(last==node[i].y) node[i].y=node[i-1].y;
        else last=node[i].y,node[i].y=++toty;
    }
    sort(node+1,node+n+1,cmp1);last=-inf;
    for(int i=1;i<=n;i++) 
    {
        if(last==node[i].x) node[i].x=node[i-1].x;
        else last=node[i].x,node[i].x=++totx;
        vec[node[i].y].push_back(node[i].x);
        Ve[node[i].x].first = (Ve[node[i].x].first==0?node[i].y:min(node[i].y,Ve[node[i].x].first));
        Ve[node[i].x].second = (Ve[node[i].x].second==0?node[i].y:max(node[i].y,Ve[node[i].x].second));
    }
    for(int i=1;i<=totx;i++) 
        if(Ve[i].second-1>Ve[i].first)
            be[Ve[i].first].push_back(i),en[Ve[i].second-1].push_back(i);
    for(int i=1;i<=toty;i++)
    {
        int siz=vec[i].size();for(int j=1;j<siz;j++)
            ans += query(vec[i][j]-1) - query(vec[i][j-1]);
        siz=be[i].size();for(int j=0;j<siz;j++) change(be[i][j],1);
        siz=en[i].size();for(int j=0;j<siz;j++) change(en[i][j],-1);
    }
    printf("%d\n",ans+n);
    return 0;
}

UOJ #351.新年的叶子

题意:

给出一棵n个节点的树,我们每次随机染黑一个叶子节点(可以重复染黑),操作无限次后,这棵树的所有叶子节点必然全部会被染成黑色。定义R为这棵树不经过黑点的直径,求使R第一次变小期望的步数。

分析:

我们思考,我们思考,我们肯定要求出所有叶子节点,然后我们叫他tot,然后我们思考,如何让一条直径变短,那么假设我们求出了所有直径的端点…..对于直径长度为奇数,那么所有直径都经过一条边,边左右两棵子树中的端点构成两个集合,然后这两个集合中各选一个点连成的边构成了一条直径,当直径变短的情况下就是其中一个集合全被染黑了……我们考虑直径是偶数的情况,这样所有的直径过一个点,这个点把树拆成好多小子树,然后其中的直径端点就构成了很多集合,同理,这时直径减小的情况就是只剩下一个集合的情况…..
然后我们怎么求期望补数呢…..首先来说一个结论,假设一共有N个点,已经染黑了i个,然后我们随机染,多染黑一个的期望步数就是\frac{N}{N-i}….
所以我们现在开始求期望了,假设一共有num个元素(端点),tot个叶子节点.我们枚举最终剩下的集合为i,其中有siz_i个元素,然后这其中有j个元素被染黑,然后我们要枚举所有情况,(为了保证计算不重复,我们要保证最后的一个元素,不是在最终集合中的…..),然后由于我们要求的是方案,所有,前面的我们还要排序….然后式子大概
\binom{siz_i}{j}\times (num-siz_i+j-1)!\times \sum_{siz_i-j+1\leq k\leq num}{\frac{tot}{k}}
然后我们发现我们还要乘上前面的最后一的点,以及后面那siz_i-j的点的全排列,最后除以num!….
\binom{siz_i}{j}\times (num-siz_i+j-1)!\times \sum_{siz_i-j+1\leq k\leq num}{\frac{tot}{k}}\times (num-siz_i) \times (siz_i-j)! \times \frac{1}{num!}
所以ans的总式子就是…
\sum_{0\leq j \leq siz_i}\bigg(\binom{siz_i}{j}\times (num-siz_i+j-1)!\times \sum_{siz_i-j+1\leq k\leq num}{\frac{tot}{k}}\times (num-siz_i) \times (siz_i-j)! \times \frac{1}{num!} \bigg)
然后我们预处理各种东西就好了……

代码:

#pragma GCC optimise(2)
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=5e5+10;
const LL mod=998244353;
const double eps=1e-12;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,du[N];
int head[N],cnt;
struct Edge{int next,to;}edge[N*2];
void add(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
int Len,yuan;
int dfs1(int now,int fa,int dep)
{
    if(dep>Len) Len=dep,yuan=now;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to,now,dep+1);
    }
}
int son[N];
int dfs2(int now,int fa)
{
    int ret=0;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        int tmp=dfs2(to,now)+1;
        if(ret<tmp)
            ret=tmp,son[now]=to;
    }
    return ret;
}
int tot,jihe[N],num;
void dfs_ji(int now,int fa,int dep)
{
    if(dep==0) jihe[tot]++,num++;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs_ji(to,now,dep-1);
    }
}
int fac[N],inv[N];
int my_pow(int a,int b,int ret=1)
{
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }return ret;
}
int yjc[N],wzy[N],sb;
void init()
{
    fac[0]=fac[1]=inv[1]=1;
    for(int i=2;i<=N-10;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<=N-10;i++) inv[i]=my_pow(i,mod-2);
    wzy[N-10]=my_pow(fac[N-10],mod-2);
    for (int i=N-11;i>=0;i--) wzy[i]=(i+1)*wzy[i+1]%mod;
    for(int i=num;i>=1;i--) yjc[i]=(yjc[i+1]+sb*inv[i]%mod)%mod;
}
int C(int a,int b){return fac[a]*wzy[a-b]%mod*wzy[b]%mod;}
signed main()
{
    read(n);
    for(int i=1,u,v;i<n;i++)
        read(u),read(v),add(u,v),add(v,u),du[u]++,du[v]++;
    for(int i=1;i<=n;i++) if(du[i]==1) sb++;
    dfs1(1,0,1);
    Len=dfs2(yuan,0);
    if(Len%2==1)
    {
        int now=yuan,L,R;
        for(int i=0;i<=Len;i++)
        {
            if(i==Len/2) L=now;
            if(i==Len/2+1) R=now;
            now=son[now];
        }
        ++tot;dfs_ji(L,R,Len/2);
        ++tot;dfs_ji(R,L,Len/2);
    }
    else
    {
        int now=yuan;
        for(int i=1;i<=Len/2;i++)
            now=son[now];
        for(int i=head[now];i;i=edge[i].next)
        {
            ++tot;dfs_ji(edge[i].to,now,Len/2-1);
            if(!jihe[tot]) tot--;
        }
    }
    init();
    int ans=0;
    for(int i=1;i<=tot;i++)//枚举集合....
    {
        int siz=jihe[i];
        for(int j=0;j<siz;j++) //枚举集合里的点
            (ans+=C(siz,j)*fac[num-siz+j-1]%mod*(num-siz)%mod*yjc[siz-j+1]%mod*fac[siz-j]%mod*wzy[num]%mod)%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

[SDOI2009]HH的项链

跟随zzd的blog,我去写了这道题目,然后用了BIT和莫队,两种写法….

题意:

给你一个序列,询问区间数字种类……..

分析:

莫队就是裸的莫队,直接排序完,暴力就好了….
树状数组的写法就是我们把所有询问按R排序,然后把一个数值的贡献加到最右边的点上面,枚举询问,右移右端点…..然后左边直接写BIT就好了…..

代码:

BIT:

#pragma GCC optimise(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=998244353;
const double eps=1e-12;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,nowr,col[N],ans[N*4];
struct ASK{int l,r,name;}ask[N*4];
bool cmp(ASK a,ASK b){return a.r<b.r;}
int last[N*20];
namespace BIT
{
    int xx[N];
    int lowbit(int now){return now&-now;}
    void change(int now,int v){for(;now<=n;now+=lowbit(now)) xx[now]+=v;}
    int query(int now,int ret=0){for(;now;now-=lowbit(now)) ret+=xx[now];return ret;}
}
using namespace BIT;
signed main() 
{
    read(n);
    for(int i=1;i<=n;i++) read(col[i]);
    read(m);
    for(int i=1;i<=m;i++) read(ask[i].l),read(ask[i].r),ask[i].name=i;
    sort(ask+1,ask+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(nowr<ask[i].r)
        {
            nowr++;
            if(last[col[nowr]])
                change(last[col[nowr]],-1);
            last[col[nowr]]=nowr;
            change(last[col[nowr]],+1);
        }
        ans[ask[i].name]=query(ask[i].r)-query(ask[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

莫队:



\#pragma GCC optimise(2) #include<bits/stdc++.h> #define LL long long #define P pair<int,int> const LL N=5e4+10; const LL mod=998244353; const double eps=1e-12; using namespace std; template<typename tp> inline void read(tp &x) { x=0; char c=getchar(); bool f=0; for(;c<'0'||c>'9';f|=(c=='-'),c = getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar()); if(f) x=-x; } int n,m,k; int ans[N*4],block[N],col[N],tot; struct ASK{int l,r,name;}ask[N*4]; bool cmp(ASK a,ASK b) { if(block[a.l]==block[b.l]) return a.r<b.r; return block[a.l]<block[b.l]; } int flag[N*20],nowl=1,nowr,anss; signed main() { read(n);k=sqrt(n); for(int i=1;i<=n;i++) read(col[i]); for(int i=1;i<=n;i++){block[i]=tot;if(i%k==0&&i!=n) tot++;} read(m); for(int i=1;i<=m;i++) read(ask[i].l),read(ask[i].r),ask[i].name=i; sort(ask+1,ask+m+1,cmp); for(int i=1;i<=m;i++) { while(nowr<ask[i].r) anss+=(flag[col[++nowr]]++==0); while(nowl>ask[i].l) anss+=(flag[col[--nowl]]++==0); while(nowr>ask[i].r) anss-=(--flag[col[nowr--]]==0); while(nowl<ask[i].l) anss-=(--flag[col[nowl++]]==0); ans[ask[i].name]=anss; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }

块状链表的小结…..

今天补题,补到一道块状链表裸题,然后苦逼的调了一天…….

题意:(这是道内部题目,不能透露…)

给你一串数字,然后支持两种操作
1. 给出l,r,然后轮换l\to r内的数字….
例子:现在有a_l,a_{l+1},a_{l+2}…..a_r,操作一次以后变成a_r,a_l,a_{l+1},a_{l+2}…..a_{r-1}
2. 询问l\to r区间内有多少个数字值为k

分析:

一看这道题目,看到区间轮换什么的,秒解分块可以做,用的是可以支持单点插入,单点修改的块状链表….对于每一个块,维护一个数组表示一个数字出现多少遍,(因为数字大小小于10^5),然后我们维护块状链表,每次调到那个链再跳到目标点,然后我们还要维护重构和删除…..就好了,细节贼多,而且数据有锅,最后特判过了…..
对于实现上,有问题可以问我,然后如果你看得懂我的代码…..想必是个神仙…..

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL inf=0x3f3f3f3f;
const LL N=1e5+10;
const LL mod=1e9+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,k,tot=1;
struct Node{int next,cost;} node[N];
struct Top{int next,to,siz;int Map[N];} top[900];
int Delete(int nod)
{
    int now=1,sum=0,ret;
    while(sum+top[now].siz<nod) 
        sum+=top[now].siz,now=top[now].next;
    int block_nod=now,flag=0;now=top[now].to;
    while(nod-sum-flag>2) flag++,now=node[now].next;
    if(nod-sum==1)
    {
        ret=now;
        top[block_nod].to=node[now].next;
        top[block_nod].siz--;
        top[block_nod].Map[node[now].cost]--;
    }
    else 
    {
        ret=node[now].next;
        node[now].next=node[node[now].next].next;
        top[block_nod].Map[node[ret].cost]--;
        top[block_nod].siz--;
    }
    if(top[block_nod].siz==0)
    {
        now=1;
        while(top[now].next!=block_nod) now=top[now].next;
        top[now].next=top[block_nod].next;
    }
    return ret;
}
void Insert(int wei,int nod)
{
    int now=1,sum=0;
    while(sum+top[now].siz<wei)
         sum+=top[now].siz,now=top[now].next;
    int block_nod=now,flag=0;now=top[now].to;
    while(wei-sum-flag>1) flag++,now=node[now].next;
    if(wei==0)
    {
        top[block_nod].to=nod;
        node[nod].next=now;
        top[block_nod].siz++;
        top[block_nod].Map[node[nod].cost]++;
    }
    else 
    {
        top[block_nod].siz++;
        top[block_nod].Map[node[nod].cost]++;
        node[nod].next=node[now].next;
        node[now].next=nod;
    }
    if(top[block_nod].siz>=k*2)
    {
        int now=top[block_nod].to;
        for(int i=1;i<k;i++)
            now=node[now].next;
        top[++tot].to=node[now].next;
        top[tot].siz=top[block_nod].siz-k;
        top[block_nod].siz=k;int zz=node[now].next;
        node[now].next=0;
        top[tot].next=top[block_nod].next;
        top[block_nod].next=tot;now=zz;
        while(now)
        {
            top[block_nod].Map[node[now].cost]--;
            top[tot].Map[node[now].cost]++;
            now=node[now].next;
        }
    }
}
int main()
{
    read(n),read(m);k=sqrt(n);
    for(int i=1;i<=n;i++) read(node[i].cost);
    for(int i=1;i<=n;i++) 
    {
        if(i%k==1) top[tot].to=i;
        top[tot].siz++;top[tot].Map[node[i].cost]++;
        if(i%k==0&&n!=i) tot++;
    }
    for(int i=1;i<=n;i++) node[i].next=(i%k!=0&&i!=n?i+1:0);
    for(int i=0;i<tot;i++) top[i].next=i+1;
    for(int cas=1;cas<=m;cas++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r);
        if(opt==1)
        {
            if(l==r) continue;
            c=Delete(r);
            Insert(l-1,c);
        }
        else
        {
            read(c);
            int now=1,sum=0,ans=0;
            while(sum+top[now].siz<l) 
                sum+=top[now].siz,now=top[now].next; 
            int L=now,sum_l=sum;
            while(sum+top[now].siz<r) sum+=top[now].siz,now=top[now].next; int R=now,sum_r=sum;
            if(L==R)
            {
                int siz=top[L].siz;
                now=top[now].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum+i>=l&&sum+i<=r) ans++;
                    now=node[now].next;
                }
            }
            else if(top[L].next==R)
            {
                int siz=top[L].siz;
                now=top[L].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_l+i>=l) ans++;
                    now=node[now].next;
                }
                siz=top[R].siz;
                now=top[R].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_r+i<=r) ans++;
                    now=node[now].next;
                }
            }
            else 
            {
                int siz=top[L].siz;
                now=top[L].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_l+i>=l) ans++;
                    now=node[now].next;
                }
                siz=top[R].siz;
                now=top[R].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_r+i<=r) ans++;
                    now=node[now].next;
                }
                now=top[L].next;
                while(now!=R)
                {
                    ans+=top[now].Map[c];
                    now=top[now].next;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

提供一个对拍,可以用来测试正确性:屠龙宝刀,点击就送

[Ioi2007]training 训练路径

我们是从来不放网上的题目的,某神仙说过…..

(然后,啪啪啪,打脸)

题意:

马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。
他们国家有N个城市和M条道路。每条道路连接两个城市。这些道路中恰好有N-1条是铺设好的道路,其余道路是未经铺设的土路。幸运的是,每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说,这N个城市和N-1条铺设好的道路构成一个树状结构。
此外,每个城市最多是10条道路的端点。
一条训练路径由某个城市开始,途经一些道路后在原来起始的城市结束。因为马克和斯拉夫克喜欢去看新城市,所以他们制定了一条规则:绝不中途穿越已经去过的城市,并且绝不在相同的道路上骑行两次(不管方向是否相同)。训练路径可以从任何一个城市开始,并且不需要访问所有城市。
显然,坐在后座的骑行者更为轻松,因为坐在前面的可以为他挡风。为此,马克和斯拉夫克在每个城市都要调换位置。为了保证他们的训练强度相同,他们要选择一条具有偶数条道路的路径。
马克和斯拉夫克的竞争者决定在某些未经铺设的土路上设置路障,使得他们两人不可能找到满足上述要求的训练路径。已知在每条土路上设置路障都有一个费用值(一个正整数),并且竞争者不能在铺设好的道路上设置路障。

任务:

给定城市和道路网的描述,写一个程序计算出为了使得满足上述要求的训练路径不存在,而需要的设置路障的最小总费用。

输入格式:

输入的第一行包含两个整数NM(2≤N≤1000,N-1≤M≤5000),分别表示城市和道路的个数。

接下来的M行每行包含3个整数A, BC (1≤A≤N, 1≤B≤N, 0≤C≤10 000), 用来描述一条道路。AB是不同的整数,表示由这条道路直接相连的两个城市。对于铺设好的道路C0;对于土路,C是在该条路上设置路障所需的费用值。

每个城市最多是10条道路的端点。任意两个城市都不会有多于一条直接相连的道路。

输出格式

输出包含一个整数,表示求出的最小总费用。

分析:

我们已知我们已经建好整棵树,然后我们加入假边时,可以肯定,如果这条边在树上构成一个偶数简单环,那么这条边永远没有可能加入…..同时,如果两个环公用两个以上的点,那么尽管这两个环是奇环,可是他们的相交会导致无论如何都可以拼出小环……最后得出结论,最后的图是一个奇环仙人掌!!!!
然后我们要用最小代价找出最小的代价让图变成奇环仙人掌,反过来想,我们只要找到这个最大代价的奇环仙人掌,用总和减一减,就是答案…..
但是怎么求这个仙人掌的最大代价呢……
我们考虑DP,我们设计数组dp[i][j],i表示这是哪个点,j表示他的哪些儿子我们不考虑,意思就是我们只思考除了j中含有的以外的儿子产生的代价…..(因为一个点儿子非常少,所以我们这样考虑)
然后我们思考怎么转移….先来看官方的一组图片……

可以看出,我们可以在树上面枚举环,然后把环抠出来,然后加上被拆开的剩下的图的代价……
比如我们现在看一条假边x,y,他们的lcaLca_{xy}(我们为了方便统计,我们把环的贡献加到Lca上),他与树边连成了一个环,我们考虑怎么统计答案…..
假设x不是Lca_{xy},然后我们易得,这个点的整个子树的代价可以加到cost里面统计答案…..
由于他的子树里面都是可以考虑的边,所以先加上dp[x][0]…….
然后我们从x点往上面跳,直到成为Lca_{xy}的儿子,然后我们对于每一个点,假设他是从第k个儿子跳上来了,那么我们就给cost 加上dp[x][1 << k-1]的代价,然后我们把答案统计到根上…..
我们考虑,有状态dp[x][s],他是从dp[x][s|son_x|son_y]上转移来的,就好了…..
看不懂可以提问,因为评论要审核所以我会认真看的……

代码:

%%%acheing

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define LL long long
#define P pair<int, int>
const LL N = 1e3 + 10;
const LL mod = 1e4 + 7;
const LL inf = 0x3f3f3f3f;
using namespace std;
template <typename tp>
inline void read(tp &x)
{
    x = 0;char c = getchar();bool f = 0;
    for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
int n, m, ans;
int tree_head[N], tree_cnt;
struct Tree_Edge {int next, to;} tree_edge[N * 10];
inline void add(int from, int to)
{
    tree_edge[++tree_cnt].next = tree_head[from];
    tree_edge[tree_cnt].to = to;
    tree_head[from] = tree_cnt;
}
int cnt, fa[N][15], dep[N], du[N], dp[N][1 << 12];
struct Edge {int from, to, cost;} edge[N * 10];
vector<int> vec[N];
void dfs_init(int now, int fath)
{
    fa[now][0] = fath; dep[now] = dep[fath] + 1;
    for (int i = 1; i <= 12; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for (int i = tree_head[now]; i; i = tree_edge[i].next)
    {
        int to = tree_edge[i].to;
        if (to == fath) continue;
        du[now]++;dfs_init(to, now);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 12; i >= 0; i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 12; i >= 0; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
int son[N][12], son_fan[N];
void dfs_dp(int now)
{
    for (int i = tree_head[now]; i; i = tree_edge[i].next) if (fa[now][0] != tree_edge[i].to) dfs_dp(tree_edge[i].to);
    int son_cnt = 0;
    for (int i = tree_head[now]; i; i = tree_edge[i].next) if (fa[now][0] != tree_edge[i].to) son[now][++son_cnt] = tree_edge[i].to, son_fan[tree_edge[i].to] = son_cnt;
    for (int i = 0; i < (1 << du[now]); i++)
        for (int j = 1; j <= du[now]; j++)
            if (!(i & (1 << j - 1)))
                dp[now][i] += dp[son[now][j]][0];
    int siz = vec[now].size();
    for (int i = 0; i < siz; i++)
    {
        int from = edge[vec[now][i]].from,
        to = edge[vec[now][i]].to, cost = edge[vec[now][i]].cost;
        int L = son_fan[from], R = son_fan[to];
        if (from != now)
        {
            cost += dp[from][0];
            while (fa[from][0] != now)
            {
                int fath = fa[from][0];
                cost += dp[fath][1 << son_fan[from] - 1];
                if (fa[fath][0] == now) L = son_fan[fath];
                from = fath;
            }
        }
        if (to != now)
        {
            cost += dp[to][0];
            while (fa[to][0] != now)
            {
                int fath = fa[to][0];
                cost += dp[fath][1 << son_fan[to] - 1];
                if (fa[fath][0] == now) R = son_fan[fath];
                to = fath;
            }
        }
        from = edge[vec[now][i]].from, to = edge[vec[now][i]].to;
        for (int j = 0; j < 1 << du[now]; j++)
        {
            int res = j;
            if (from != now)
            {
                if (res & (1 << L - 1)) continue;
                res |= 1 << L - 1;
            }
            if (to != now)
            {
                if (res & (1 << R - 1)) continue;
                res |= 1 << R - 1;
            }
            dp[now][j] = max(dp[now][j], cost + dp[now][res]);
        }
    }
}
signed main()
{
    read(n), read(m);
    for (int i = 1, u, v, c; i <= m; i++)
    {
        read(u), read(v), read(c);
        if (!c) add(u, v), add(v, u);
        else edge[++cnt] = (Edge){u, v, c};
        ans += c;
    }
    dfs_init(1, 1);
    for (int i = 1; i <= cnt; i++)
    {
        int Lca = lca(edge[i].from, edge[i].to);
        int dis = dep[edge[i].from] + dep[edge[i].to] - 2 * dep[Lca];
        if (!(dis & 1)) vec[Lca].push_back(i);
    }
    dfs_dp(1);
    printf("%d\n", ans - dp[1][0]);
    return 0;
}

密码保护:2018提高组模拟赛18 – naive 的瓶子

这是一篇受密码保护的文章,您需要提供访问密码:

XJOI sequence CF407C Curious Array

题意:

给你一个序列,每次给出一个区间l,r和一个数字k,有i\in [l,r] ,a[i] += \binom{i-l+k}{k} ,然后让你输出最后的序列…..

数据范围(原题):

n,m \leqslant 100000,k\leqslant 100

分析:

我们发现我们每次操作就是给序列的一段区间加上杨辉三角一列…
假设我们有杨辉三角….(只需要处理100位,因为k\leqslant 100)
1
1 \ 1
1 \ 2 \ 1
1 \ 3 \ 3 \ 1
1 \ 4 \ 6 \ 4 \ 1
1 \ 5 \ 10 \ 10 \ 5 \ 1
1 \ 6 \ 15 \ 20 \ 15 \ 6 \ 1
我们每次操作的本质就是k=1我们就加上第二列就是1,2,3,4,5…
然后我们发现列和列之间的关系是原序列和前缀和的关系,比如第二层求一个前缀和就可以变成第三层…..最好自己打表找规律
那么对于一次操作,比如我们修改l,r 时,我们在l处打一个tag,在r+1处打一个抵消标记,然后求前缀和
举例子:现在有l=2,r=5

原序列:

0,0,0,0,0,0,0,0,0,0,0,0

tag :

0,1,0,0,0,-1,0,0,0,0,0,0

求一次前缀和,变成

0,1,1,1,1,0,0,0,0,0,0,0
然后我们得到了k=0的答案,然后求k=1

tag:

0,0,0,0,0,-4,0,0,0,0,0,0

求一次前缀和,变成

0,1,2,3,4,0,0,0,0,0,0,0
然后我们得到了k=1的答案,然后以此类推…..
我们发现除了第一次要在l处打+1tag,其余的我们在只要在r+1处打上消除标记就好了…..
第i次我们打的消除标记是\binom{r-l+1}{i}
然后我们得到了O(nk^2)的做法,我们对于每一种k,O(n)打标记,然后做k次前缀和…..
但是我们发现这样过不了,会TLE,怎么优化…
我们在这里提出一种做法,我们倒着做,先让k=100,然后减小k,逐层打入标记,然后这样就只要枚举O(nk)就好了,详细自己看代码(挺高妙的)

好题自己多想想

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+1000;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m;
LL ans[N],C[N][110],tag[N],yuan[N];
inline void init()
{
    C[0][0]=1;
    for(int i=1;i<=n+210;i++){C[i][0]=1; for(int j=1;j<=min(i,100);j++)C[i][j]=((C[i-1][j-1]+C[i-1][j])%mod+mod)%mod;}
    for(int i=1;i<=101;i++) for(int j=1;j<=n;j++) C[j][i]=C[j+i-1][i];
}
void add(LL &a,LL b){a+=b; while(a>=mod) a-=mod;}
struct Edge{int l,r,k;}len[N];
int main()
{
    read(n),read(m);init();
    for(int i=1;i<=n;i++) read(yuan[i]);
    for(int i=1;i<=m;i++) read(len[i].l),read(len[i].r),read(len[i].k);
    for(int i=102;i>=0;i--)
    {
        memset(tag,0,sizeof(tag));
        for(int j=1;j<=m;j++)
        {
            if(len[j].k+1>=i) tag[len[j].r+1]=(tag[len[j].r+1]+mod-C[len[j].r-len[j].l+1][len[j].k-i])%mod;
            if(len[j].k==i) (tag[len[j].l]+=1)%=mod;
        }
        for(int j=1;j<=n;j++) add(ans[j],((ans[j-1]+tag[j])%mod+mod)%mod);
    }
    for(int i=1;i<=n;i++) printf("%lld ",((ans[i]+yuan[i])%mod+mod)%mod);puts("");
    return 0;
}