收获颇丰的两天···
题目1：序列操作
给定n个非负整数,进行m次操作,每次操作给出c,要求找出c个正整数数并将它们减去1,问最多能进行多少操作？n,m<=1000000
首先暴力贪心肯定是每次减去数中前c大的数··
因此我们考虑每次减去前c大的数后依然保持数列的有序性,假设数列为111223,c=5,为了保持有序性,2和3的部分可以正常减去1,但1的话我们需要从最左边开始减···
所以对应每次操作,我们需要找到减去的最小的数的区间··从最左边开始减···这样就能保持有序性,直接在线段树上维护区间最大与区间最小值,二分即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=1e6+;
int n,m,h[N],tag[N*],trmi[N*],trmx[N*],le,ri;
inline int R(){
char c;int f=,i=;
for(c=getchar();(c<''||c>'')&&c!='-';c=getchar());
if(c=='-') i=-,c=getchar();
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f*i;
}
inline bool cmp(int a,int b){return a>b;}
inline void build(int k,int l,int r){
if(l==r){
trmx[k]=trmi[k]=h[l];return;
}
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
trmi[k]=min(trmi[k<<],trmi[k<<|]);
trmx[k]=max(trmx[k<<],trmx[k<<|]);
}
inline void pushdown(int k){
if(tag[k]){
trmi[k<<]-=tag[k];trmi[k<<|]-=tag[k];trmx[k<<]-=tag[k];trmx[k<<|]-=tag[k];
tag[k<<]+=tag[k];tag[k<<|]+=tag[k];tag[k]=;
}
}
inline int query(int k,int l,int r,int x){
if(l==r) return trmi[k];
int mid=(l+r)>>;pushdown(k);
if(x<=mid) return query(k<<,l,mid,x);
else return query(k<<|,mid+,r,x);
}
inline void getle(int k,int l,int r,int x){
if(l==r){
le=l;return;
}
int mid=(l+r)>>;pushdown(k);
if(trmi[k<<]>x) getle(k<<|,mid+,r,x);
else getle(k<<,l,mid,x);
}
inline void getri(int k,int l,int r,int x){
if(l==r){
ri=l;return;
}
int mid=(l+r)>>;pushdown(k);
if(trmx[k<<|]<x) getri(k<<,l,mid,x);
else getri(k<<|,mid+,r,x);
}
inline void modify(int k,int l,int r,int x,int y){
if(l>=x&&r<=y){
tag[k]++;trmi[k]--;trmx[k]--;return;
}
int mid=(l+r)>>;pushdown(k);
if(x<=mid) modify(k<<,l,mid,x,y);
if(y>mid) modify(k<<|,mid+,r,x,y);
trmi[k]=min(trmi[k<<],trmi[k<<|]);
trmx[k]=max(trmx[k<<],trmx[k<<|]);
}
int main(){
//freopen("a.in","r",stdin);
//freopen("mine.out","w",stdout);
n=R(),m=R();int x;int ans=;
for(int i=;i<=n;i++) h[i]=R();
sort(h+,h+n+,cmp);build(,,n);
while(m--){
x=R();
int now=query(,,n,x);
if(!now) break;ans++;
getle(,,n,now);getri(,,n,now);
if(le==) modify(,,n,ri-x+,ri);
else modify(,,n,,le-),modify(,,n,ri+le-x,ri);
}
cout<<ans<<endl;
return ;
}
题目2：图：
题目题解见：http://blog.csdn.net/white_elephant/article/details/78418239?locationNum=5&fps=1
本来删边加边是可以用LCT维护的···然而考虑到时NOIP题这里暴力跳点维护也是可以过的··于是我就尝试写了一发暴力··调到怀疑人生··主要是跳点的时候细节有点多···
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+;
const int M=2e5+;
const int inf=0x3f3f3f3f;
struct node{int x,y,val;}A[M],B[M],C[M];
struct node1{double bsli;int pre,now;}ans[M];
struct node2{int x,id;}query[M];
int father[N],deep[N],dis[N],fa[N],n,q,a,b,cnt,from[N],visit[N],tim;
int first[N],next[N*],go[N*],tot,val[N*];
long long Anss[M];
inline int R(){
char c;int f=,i=;
for(c=getchar();(c<''||c>'')&&c!='-';c=getchar());
if(c=='-') i=-,c=getchar();
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f*i;
}
inline int getfa(int a){
if(father[a]==a) return a;
else return father[a]=getfa(father[a]);
}
inline void comb(int a,int b,int c){
next[++tot]=first[a],first[a]=tot,go[tot]=b,val[tot]=c;
next[++tot]=first[b],first[b]=tot,go[tot]=a,val[tot]=c;
}
inline void dfs(int u,int Fa){
for(int e=first[u];e;e=next[e]){
int v=go[e];if(v==Fa) continue;
deep[v]=deep[u]+;fa[v]=u;dis[v]=val[e];dfs(v,u);
}
}
inline bool cmp(const node &a,const node &b){
return a.val<b.val;
}
inline void modify(int a,int b,int now){
visit[a]=++tim;int tmp=a;
while(tmp!=) visit[fa[tmp]]=tim,tmp=fa[tmp];
int to=b;while(visit[to]!=tim) to=fa[to];
int maxx=-inf,pos,op,tempa=a,tempb=b;
if(fa[a]==to){
if(dis[a]>maxx) maxx=dis[a],pos=a,op=;
}
else if(a!=to){
while(fa[a]!=to){
if(dis[a]>maxx){
maxx=dis[a];pos=a;op=;
}
from[fa[a]]=a;a=fa[a];
}
if(dis[a]>maxx) maxx=dis[a],pos=a,op=;
}
if(fa[b]==to){
if(dis[b]>maxx) maxx=dis[b],pos=b,op=;
}
else if(b!=to){
while(fa[b]!=to){
if(dis[b]>maxx){
maxx=dis[b];pos=b;op=;
}
from[fa[b]]=b;b=fa[b];
}
if(dis[b]>maxx) maxx=dis[b],pos=b,op=;
}
ans[++cnt].pre=maxx;ans[cnt].now=B[now].val;
ans[cnt].bsli=(double)(B[now].val-maxx)/;
if(op==){
while(pos!=tempb){
dis[pos]=dis[from[pos]],fa[pos]=from[pos];pos=from[pos];
}
dis[tempb]=-*inf;fa[tempb]=tempa;
}
else{
while(pos!=tempa){
dis[pos]=dis[from[pos]],fa[pos]=from[pos];pos=from[pos];
}
dis[tempa]=-*inf;fa[tempa]=tempb;
}
}
inline void getans(){
sort(B+,B+b+,cmp);
for(int i=;i<=b;i++){
modify(B[i].x,B[i].y,i);
}
}
inline bool cmp2(node1 a,node1 b){
return a.bsli<b.bsli;
}
inline bool cmp3(node2 a,node2 b){
return a.x<b.x;
}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
n=R(),a=R(),b=R(),q=R();
for(int i=;i<=a;i++) A[i].x=R(),A[i].y=R(),A[i].val=R();
for(int i=;i<=b;i++) B[i].x=R(),B[i].y=R(),B[i].val=R();
for(int i=;i<=n;i++) father[i]=i;
int temp=;ans[cnt=].bsli=-(2e+);
long long sum=;
sort(A+,A+a+,cmp);
for(int i=;i<=a;i++){
int fx=getfa(A[i].x),fy=getfa(A[i].y);
if(fx!=fy){
sum+=A[i].val;temp++;father[fx]=fy;
comb(A[i].x,A[i].y,A[i].val);
}
if(temp==n-) break;
}
deep[]=;dis[]=;fa[]=;dfs(,);
temp=;for(int i=;i<=n;i++) father[i]=i;
sort(B+,B+b+,cmp);
for(int i=;i<=b;i++){
int fx=getfa(B[i].x),fy=getfa(B[i].y);
if(fx!=fy){
temp++;C[temp]=B[i];father[fx]=fy;
}
if(temp==n-) break;
}
b=temp;for(int i=;i<=b;i++) B[i]=C[i];
getans();sort(ans+,ans+cnt+,cmp2);
int tail=;
for(int i=;i<=q;i++) query[i].x=R(),query[i].id=i;
sort(query+,query+q+,cmp3);
tail=;
for(int i=;i<=q;i++){
double v=query[i].x*1.0;
while(tail<cnt&&v>=ans[tail+].bsli) tail++,sum+=ans[tail].now-ans[tail].pre;
Anss[query[i].id]=sum+(long long)(n--*(tail-))*v;
}
for(int i=;i<=q;i++) cout<<Anss[i]<<endl;
return ;
}
题目3：路径统计
已知一个有向图,有n个节点,每个节点只有一条n出边,边有权值,求两两节点之间最短路之和%1e^7,若两节点没有连通则最短路记为-1,n<=500000
先说题解：我们可以发现整个图就是一个森林,且每部分就是一颗奇环内向树··因此我们先处理环上对答案的贡献,再处理与环直接相连的点,最后再树形dp即可(只能口胡了··详细说起来有点麻烦··看代码吧)···
但是这道题真的是恶心到极点啊··首先统计答案的时候要时时刻刻记得取模,不然很容易错,想象一下考试时自己辛辛苦苦调出来对拍也没错但交上去全tmwa仅仅因为少tm取了几个模的情景··而且很容易爆int,以后遇到这种题能全开long long就全开long long······
但题的基本除去去模部分还是一道挺好的题··
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int mod=1e9+;
const int N=6e5+;
priority_queue< pair<long long,int> >que;
vector<int>cir[N];
long long fst[N],nxt[N*],go[N*],val[N*],tot=,n;
long long fst2[N],nxt2[N*],go2[N*],tot2=,val2[N*],dfn[N],low[N],Id[N],stk[N],top=,totg,from[N],dp[N];
long long dis[N],ans=,C[N],sum[N],f[N],cnt=,size[N];
bool vst[N],insta[N];
inline int R(){
char c;int f=,i=;
for(c=getchar();(c<''||c>'')&&c!='-';c=getchar());
if(c=='-') i=-,c=getchar();
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f*i;
}
inline void comb(int a,int b,int c){
nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b,val[tot]=c;
}
inline void comb1(int a,int b,int c){
nxt2[++tot2]=fst2[a],fst2[a]=tot2,go2[tot2]=b,val2[tot2]=c;
}
inline void tarjan(int u){
dfn[u]=low[u]=++cnt;stk[++top]=u,insta[u]=true;
for(int e=fst[u];e;e=nxt[e]){
int v=go[e];
if(!dfn[v]){
tarjan(v);low[u]=min(low[v],low[u]);
}
else if(insta[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
totg++;
while(stk[top]!=u){
cir[totg].push_back(stk[top]),Id[stk[top]]=totg,size[totg]++,insta[stk[top]]=false,top--;
}
cir[totg].push_back(stk[top]),Id[stk[top]]=totg,size[totg]++,insta[stk[top]]=false,top--;
}
}
inline void dfs(int u,int now){
vst[u]=true;
for(int e=fst[u];e;e=nxt[e]){
int v=go[e];if(Id[u]!=Id[v]) continue;
if(!vst[v]) C[now]=(C[now]+val[e])%mod,from[v]=val[e],dfs(v,now);
else{
C[now]=(C[now]+val[e])%mod,from[v]=val[e];return;
}
}
}
inline void dfs2(int u){
vst[u]=true;
for(int e=fst[u];e;e=nxt[e]){
int v=go[e];
if(vst[v]) dp[u]+=dp[v]+,f[u]=(f[u]+(f[v]+val[e]*(dp[v]+)%mod)%mod)%mod;
else{
dfs2(v);dp[u]+=dp[v]+,f[u]=(f[u]+(f[v]+val[e]*(dp[v]+)%mod)%mod)%mod;
}
}
cnt=(cnt+dp[u])%mod,ans=(ans+f[u])%mod;
}
inline void calc(int u){
long long temp1=;temp1=(temp1+from[cir[u][]])%mod,vst[cir[u][]]=true;
for(int i=;i<size[u];i++) temp1=(temp1+from[cir[u][i]]*(size[u]-i+)%mod)%mod,vst[cir[u][i]]=true;
sum[cir[u][]]=temp1-C[u];
for(int i=;i<size[u];i++) temp1=(temp1+C[u])%mod,temp1=((temp1-size[u]*from[cir[u][i]])%mod+mod)%mod,sum[cir[u][i]]=((temp1-C[u])%mod+mod)%mod;
}
int main(){
//freopen("road.in","r",stdin);
//freopen("road.out","w",stdout);
int _q=<<;
char *_p=(char*)malloc(_q)+_q;
__asm__("movl %0, %%esp\n"::"r"(_p));
n=R();int a,b;
for(int i=;i<=n;i++){
a=R(),b=R();if(a==i) continue;
comb(i,a,b);comb1(a,i,b);
}
for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int i=;i<=totg;i++) reverse(cir[i].begin(),cir[i].end());
cnt=;
for(int i=;i<=totg;i++){
if(size[i]<) continue;
dfs(cir[i][],i);
cnt=(cnt+size[i]*(size[i]-)%mod)%mod;
ans=(ans+(size[i]*(size[i]-)/)%mod*C[i]%mod)%mod;
calc(i);
}
for(int i=;i<=totg;i++){
if(size[i]==) continue;
for(int j=;j<size[i];j++){
int u=cir[i][j];
for(int e=fst2[u];e;e=nxt2[e]){
int v=go2[e];if(Id[v]==Id[u]) continue;
f[v]=(sum[u]+val2[e]*size[i]%mod)%mod;vst[v]=true;dp[v]=size[i];
ans=(ans+f[v])%mod;cnt=(cnt+size[i])%mod;
}
}
}
for(int i=;i<=n;i++)
if(!vst[i]) dfs2(i);
long long temp=((long long)n*(n-)-cnt)%mod;temp=(temp%mod+mod)%mod;
cout<<((ans-temp)%mod+mod)%mod<<endl;
return ;
}
题目4：小店购物
有n件商品,每件商品有自己的价值w和价格p,每次购买时会有k元,每次会购买价值最高(如果价值相等则选价格最低)且价格低于所剩的钱的商品,直到不能买为止(每件商品可以购买无数次)
有p次操作,两种类型:一是询问如果有k元能买价值总和多大的商品,二是将某个商品的价格价值更改,n<=10000,m<=100000
考虑暴力操作,我们按题意找到符合题意的商品,价格为pri,价值为val,所剩钱为k,那么本次购买对答案的贡献就是k/pri*val,且k变为k%pri,每次购买计算贡献次数不会超过logk次
很明显我们可以用线段树维护,区间为离散化后的商品价值,区间储存商品价格的最小值···每次查找时贪心先找右子树即可,然而一个商品价值可能对应多个价格,因此在线段树的叶子节点我们需要用一个multiset来维护一下节点中的元素
注意multiset在删除操作时如果是删除键值会将该键值的迭代器全部删完,所以要先找到迭代器再删除元素
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
const int N=2e5+;
const int inf=0x3f3f3f3f;
multiset<int>::iterator t;
multiset<int>st[N*];
struct node{int op,x,w,p;}q[N];
inline int R(){
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
int w[N],p[N],b[N*],cnt,n,m,tree[N*],pri,val,pos[N];
inline void lsh(){
sort(b+,b+cnt+);
cnt=unique(b+,b+cnt+)-b-;
for(int i=;i<=n;i++) w[i]=lower_bound(b+,b+cnt+,w[i])-b;
for(int i=;i<=m;i++) if(q[i].op==) q[i].w=lower_bound(b+,b+cnt+,q[i].w)-b;
}
inline void insert(int k,int l,int r,int x,int y,int now){
if(l==r){
p[now]=y;pos[now]=k;st[k].insert(y);tree[k]=min(tree[k],y);return;
}
int mid=(l+r)/;
if(x<=mid) insert(k*,l,mid,x,y,now);
else insert(k*+,mid+,r,x,y,now);
tree[k]=min(tree[k*],tree[k*+]);
}
inline void find(int k,int l,int r,int x){
if(l==r){
pri=tree[k];val=b[l];return;
}
int mid=(l+r)/;
if(tree[k]>x) return;
if(tree[k*+]>x) find(k*,l,mid,x);
else find(k*+,mid+,r,x);
}
inline void del(int k,int x,int y){
if(k==x){
st[k].erase(st[k].find(y));
if(st[k].empty()) tree[k]=inf;
else{
t=st[k].begin();tree[k]=*t;
}
del(k/,x,y);return;
}
tree[k]=min(tree[k*],tree[k*+]);
if(k==) return;
else del(k/,x,y);
}
int main(){
//freopen("shopping.in","r",stdin);
//freopen("shopping.out","w",stdout);
n=R(),m=R();
for(int i=;i<=n;i++) w[i]=R(),p[i]=R(),b[++cnt]=w[i];
for(int i=;i<=m;i++){
q[i].op=R();
if(q[i].op==){
q[i].x=R();q[i].w=R();q[i].p=R();b[++cnt]=q[i].w;
}
else q[i].x=R();
}
lsh();memset(tree,inf,sizeof(tree));
for(int i=;i<=n;i++) insert(,,cnt,w[i],p[i],i);
for(int i=;i<=m;i++){
if(q[i].op==){
int temp=q[i].x;long long ans=;
while(true){
pri=val=;find(,,cnt,temp);
if(pri==&&val==) break;
else ans+=(long long)temp/pri*val,temp%=pri;
}
cout<<ans<<endl;
}
else{
del(pos[q[i].x],pos[q[i].x],p[q[i].x]);
insert(,,cnt,q[i].w,q[i].p,q[i].x);w[q[i].x]=q[i].w;
}
}
return ;
}
其实也可以用splay写,和线段树实际上是差不多的
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=1e5+;
int w[N],p[N],son[N][],father[N],minn[N],root,val,pri,n,m;
inline int R(){
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
inline int get(int now){
return son[father[now]][]==now;
}
inline void clear(int now){
w[now]=p[now]=son[now][]=son[now][]=father[now]=minn[now]=;
}
inline void update(int now){
if(now){
minn[now]=p[now];
if(son[now][]) minn[now]=min(minn[now],minn[son[now][]]);
if(son[now][]) minn[now]=min(minn[now],minn[son[now][]]);
}
}
inline void rotate(int now){
int fa=father[now],ofa=father[fa],which=get(now);
son[fa][which]=son[now][which^],father[son[fa][which]]=fa;
son[now][which^]=fa,father[fa]=now,father[now]=ofa;
if(ofa) son[ofa][son[ofa][]==fa]=now;
update(fa),update(now);
}
inline void splay(int now){
while(father[now]){
if(father[father[now]]) rotate(get(father[now])==get(now)?father[now]:now);
rotate(now);
}
root=now;
}
inline void insert(int tw,int tp,int ID){
int now=root,fa=;
while(true){
if(!now){
now=ID;son[now][]=son[now][]=;father[now]=fa;w[now]=tw;p[now]=tp;
if(!root) root=now;
else{
if(w[now]>w[fa]) son[fa][]=now;
else if(w[now]<w[fa]) son[fa][]=now;
else if(w[now]==w[fa]&&p[now]<p[fa]) son[fa][]=now;
else son[fa][]=now;
}
update(now);update(fa);splay(now);break;
}
fa=now;
if(tw>w[now]) now=son[now][];
else if(tw<w[now]) now=son[now][];
else if(tw==w[now]&&tp<p[now]) now=son[now][];
else now=son[now][];
}
}
inline int findpre(){
int now=root;
if(son[now][]){
now=son[now][];
while(son[now][]) now=son[now][];
}
return now;
}
inline void del(int now){
splay(now);
if(!son[now][]){
root=son[now][];father[root]=;clear(now);return;
}
else if(!son[now][]){
root=son[now][];father[root]=;clear(now);return;
}
else{
int leftbig=findpre();
splay(leftbig);
son[root][]=son[now][];father[son[root][]]=root;
clear(now);update(root);return;
}
}
inline void find(int u,int v)
{
if(son[u][]&&minn[son[u][]]<=v) find(son[u][],v);
else if(p[u]<=v){
val=w[u];pri=p[u];return;
}
else if(son[u][]&&minn[son[u][]]<=v) find(son[u][],v);
}
int main(){
//freopen("a.in","r",stdin);
n=R(),m=R();int op,a,b,c;
for(int i=;i<=n;i++) a=R(),b=R(),insert(a,b,i);
while(m--){
op=R();
if(op==){
a=R(),b=R(),c=R();del(a);insert(b,c,a);
}
else{
a=R();long long ans=;
while(minn[root]<=a){
val=pri=;find(root,a);
if(!val&&!pri) break;
ans+=(long long)a/pri*val;a%=pri;
}
cout<<ans<<"\n";
}
}
}