[COGS 741]负载平衡
这个网络流题挺简单的……
首先从[tex]S[/tex]向每个点连容量为该点存货量的边（费用为0）。首先注意最后所有存货量都要变成总的平均值，所以要从每个点向[tex]T[/tex]连一条容量为总的平均值的边（费用为0）。最后根据题目要求在相邻点之间连边（容量都是无限大，费用为1）。
跑一遍最小费用最大流，得出的费用就是答案。
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
namespace MCMF{
struct Edge{
int u,v,cap,flow,cost;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap,int cost){
edges.push_back((Edge){u,v,cap,0,cost});
edges.push_back((Edge){v,u,0,0,-cost});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int a[maxn];
bool inQueue[maxn];
int d[maxn],p[maxn];
bool BellmanFord(int s,int t,long long& cost){
register int i,u;
queue<int> Q;
memset(d,0x7f,sizeof(d));
memset(inQueue,0,sizeof(inQueue));
d[s]=0;
inQueue[s]=true;
p[s]=0;
a[s]=0x7f7f7f7f;
Q.push(s);
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!inQueue[e.v]){
Q.push(e.v);
inQueue[e.v]=true;
}
}
}
}
if(d[t]==0x7f7f7f7f)
return false;
cost+=((long long)d[t])*((long long)a[t]);
for(u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
long long MincostMaxflow(int s,int t){
register long long ans=0;
while(BellmanFord(s,t,ans));
return ans;
}
};
int A[maxn];
int main(){
register int i,ave=0;
int n;
freopen("overload.in","r",stdin);
freopen("overload.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
ave+=A[i];
MCMF::AddEdge(0,i,A[i],0);
}
ave/=n;
for(i=1;i<=n;i++){
MCMF::AddEdge(i,n+1,ave,0);
if(i>1){
MCMF::AddEdge(i-1,i,0x7f7f7f7f,1);
MCMF::AddEdge(i,i-1,0x7f7f7f7f,1);
}
if(i<n){
MCMF::AddEdge(i+1,i,0x7f7f7f7f,1);
MCMF::AddEdge(i,i+1,0x7f7f7f7f,1);
}
}
MCMF::AddEdge(1,n,0x7f7f7f7f,1);
MCMF::AddEdge(n,1,0x7f7f7f7f,1);
printf("%lld\n",MCMF::MincostMaxflow(0,n+1));
fclose(stdin);
fclose(stdout);
return 0;
}
[BZOJ 3155]Preprefix sum
蛮有意思的一题……
考虑询问[tex]SS_i[/tex]，[tex][1,i][/tex]中的每个位置[tex]j[/tex]在答案中被计算的次数为[tex]i-j+1[/tex]，然后式子就可以变成这样：
[tex]\Sigma_{j=1}^{i} A[j]*(i-j+1)[/tex]
[tex](i+1)*\Sigma_{j=1}^{i} A[j]-\Sigma_{j=1}^{i} A[j]*j[/tex]
这样问题就简单多了，开两个树状数组乱搞搞即可。
代码：
/**************************************************************
Problem: 3155
User: danihao123
Language: C++
Result: Accepted
Time:464 ms
Memory:3164 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
const int maxn=100005;
typedef long long ll;
int n;
ll A[maxn];
ll C_1[maxn]; // 正常的BIT
inline int lowbit(int x){
return x&(-x);
}
inline void add(int p,ll v){
while(p<=n){
C_1[p]+=v;
p+=lowbit(p);
}
}
inline ll sum(int p){
register ll ans=0;
while(p>0){
ans+=C_1[p];
p-=lowbit(p);
}
return ans;
}
ll C_2[maxn]; // 累积的BIT
inline void add_2(int p,ll v){
register int pos=p;
while(pos<=n){
C_2[pos]+=((ll)p)*v;
pos+=lowbit(pos);
}
}
inline ll sum_2(int p){
register ll ans=0;
while(p>0){
ans+=C_2[p];
p-=lowbit(p);
}
return ans;
}
int main(){
int m,p;
ll v;
register int i;
char *buf=(char*)calloc(10,1);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
add(i,A[i]);
add_2(i,A[i]);
}
while(m--){
scanf("%s%d",buf,&p);
if(buf[0]=='Q'){
printf("%lld\n",((ll)p+1LL)*sum(p)-sum_2(p));
}else{
scanf("%lld",&v);
add(p,v-A[p]);
add_2(p,v-A[p]);
A[p]=v;
}
}
free(buf);
return 0;
}
[BZOJ 3333]排队计划
传说中的大结论题TAT
假设每个数的后面小于它的数的个数为[tex]f[i][/tex]（其位置为[tex]i[/tex]），那么逆序对数显然为[tex]\Sigma f[i][/tex]。
每次操作，只需要将涉及到的数的[tex]f[i][/tex]清为0即可。
为什么呢？任何数的后面比他小的数肯定也被一起拉出来排序了，所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢？因为这之后的比他小的位置，有的可能没被操作，有的可能被操作了。但是就算被操作了，放到后面位置的数照样会比这个数小（因为这个数如果在第一个选定位置的后面（在前面更是不受影响）还没被操作，肯定比那个第一个位置数还大）。
还有一个细节，一个被操作过的数不需要再被操作一遍，操作完了直接设为INF即可。
代码：
/**************************************************************
Problem: 3333
User: danihao123
Language: C++
Result: Accepted
Time:7920 ms
Memory:24264 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
if(L==R){
minv[o]=make_pair(A[L],L);
}else{
int M=L+(R-L)/2;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
maintain(o);
}
}
int ql,qr;
pii query_min(int o,int L,int R){
if(ql<=L && R<=qr){
return minv[o];
}else{
int M=L+(R-L)/2;
pii ans=make_pair(INF,INF);
if(ql<=M)
ans=min(ans,query_min(o<<1,L,M));
if(qr>M)
ans=min(ans,query_min(o<<1|1,M+1,R));
return ans;
}
}
int p;
void update(int o,int L,int R){
if(L==R){
minv[o].first=INF;
}else{
int M=L+(R-L)/2;
if(p<=M)
update(o<<1,L,M);
else
update(o<<1|1,M+1,R);
maintain(o);
}
}
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
return x&(-x);
}
inline void add(int p){
while(p<=lsh_siz){
C[p]++;
p+=lowbit(p);
}
}
inline int sum(int p){
int ans=0;
while(p>0){
ans+=C[p];
p-=lowbit(p);
}
return ans;
}
inline int readint(){
register int x;
register char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
register int i,p=0;
if(!x){
bf[p++]=0;
}else{
while(x){
bf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(bf[i]+'0');
putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
register int i,m,pos;
register ull ans=0;
pii temp;
n=readint();
m=readint();
for(i=1;i<=n;i++){
A[i]=readint();
A2[i]=A[i];
}
sort(A2+1,A2+1+n);
lsh_siz=unique(A2+1,A2+1+n)-A2-1;
for(i=n;i>=1;i--){
pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
f[i]=sum(pos-1);
ans+=f[i];
add(pos);
}
putint(ans);
build_tree(1,1,n);
while(m--){
pos=readint();
ql=pos;
qr=n;
while(true){
temp=query_min(1,1,n);
if(temp.first>A[pos])
break;
p=temp.second;
ans-=f[p];
f[p]=0;
update(1,1,n);
}
putint(ans);
}
return 0;
}
[BZOJ 3306]树
这个题其他操作都不难（DFS序+线段树水过），就是换根有点头疼……直接做的话要TopTree吧。
不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根，如果这个根最初不在x的子树中，那么对目前的查询值没有影响；如果就是x，那么整个树都是x的子树；如果是x的某个后代，那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树（试着翻转一下就明白了）。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现，问题就这样简单了。
代码：
/**************************************************************
Problem: 3306
User: danihao123
Language: C++
Result: Accepted
Time:2308 ms
Memory:17544 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
if(L==R){
minv[o]=A[L];
}else{
MAKE_MID;
build_tree(LCH);
build_tree(RCH);
maintain(o);
}
}
int ql,qr;
int query(SEG_STD){
if(ql<=L && R<=qr){
return minv[o];
}else{
MAKE_MID;
int ans=INF;
if(ql<=M)
ans=min(ans,query(LCH));
if(qr>M)
ans=min(ans,query(RCH));
return ans;
}
}
int p,v;
void update(SEG_STD){
if(L==R){
minv[o]=v;
}else{
MAKE_MID;
if(p<=M)
update(LCH);
else
update(RCH);
maintain(o);
}
}
inline int query(int l,int r){
if(l<1 || l>n || r<1 || r>n)
return INF;
ql=l;
qr=r;
return query(1,1,n);
}
inline void update(int pos,int value){
p=pos;
v=value;
update(1,1,n);
}
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
dfs_clk++;
tid[x]=dfs_clk;
A[dfs_clk]=d[x];
anc[x][0]=fa;
dep[x]=depth;
siz[x]=1;
int i;
for(i=first[x];i;i=next[i]){
dfs(to[i],x,depth+1);
siz[x]+=siz[to[i]];
}
}
void process(){
register int i,j;
for(j=1;(1<<j)<n;j++)
for(i=1;i<=n;i++)
if(anc[i][j-1]!=-1)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
register int p=root,j;
if(dep[p]<dep[x])
return false;
for(j=18;j>=0;j--)
if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
p=anc[p][j];
return p==x;
}
int findAnc(int x,int y){
register int j;
for(j=18;j>=0;j--)
if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
y=anc[y][j];
return y;
}
int getAns(int x){
if(x==root){
return query(1,n);
}else{
if(isAnc(x)){
register int t=findAnc(x,root);
register int l=tid[t],r=tid[t]+siz[t]-1;
return min(query(1,l-1),query(r+1,n));
}else{
return query(tid[x],tid[x]+siz[x]-1);
}
}
}
int main(){
int q,x,f;
register int i;
char buf[3];
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++){
scanf("%d%d",&f,&d[i]);
if(!f){
root=i;
}else{
AddEdge(f,i);
}
}
memset(anc,-1,sizeof(anc));
dfs(root,-1,0);
process();
build_tree(1,1,n);
while(q--){
scanf("%s%d",buf,&x);
if(buf[0]=='V'){
scanf("%d",&f);
update(tid[x],f);
}else{
if(buf[0]=='Q'){
printf("%d\n",getAns(x));
}else{
root=x;
}
}
}
return 0;
}
[BZOJ 2186]沙拉公主的困惑
这个题啊……亦可赛艇！
答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单，把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段，除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex]（否则，[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。
麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数，它的所有因子在前面都有了，只能把他自己贡献出来；如果这个数是质数（假设为[tex]p[/tex]），出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex]，最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~
并且……[tex]n-m[/tex]可能非常大，所以说除去[tex]m![/tex]那块要用逆元做。
（顺便说下阶乘也要递推）
代码：
/**************************************************************
Problem: 2186
User: danihao123
Language: C++
Result: Accepted
Time:9408 ms
Memory:166836 kb
****************************************************************/
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
register int i,j,m=sqrt(maxn+0.5);
for(i=2;i<=m;i++)
if(!vis[i])
for(j=i*i;j<=maxn;j+=i)
vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
register int i;
fac[0]=1%R;
for(i=1;i<=maxn;i++)
fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
register int i;
phifac[1]=1%R;
for(i=2;i<=maxn;i++){
if(vis[i])
phifac[i]=(phifac[i-1]*(i%R))%R;
else
phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
}
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
ull inv(ull a){
ull d,x,y;
exgcd(a,R,d,x,y);
return (x+R)%R;
}
int main(){
int T;
int n,m;
scanf("%d%llu",&T,&R);
sievePrime();
sieveFac();
sievePhiFac();
while(T--){
scanf("%d%d",&n,&m);
printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
}
return 0;
}
[BZOJ 3339]Rmq Problem
万恶的标题党啊~
这个题明显扫描线辣……但是怎么扫呢？
我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值，然后用线段树维护。
从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时，需要将[tex][l,next[l]-1][/tex]（[tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置）中的所有大于[tex]A[l][/tex]（[tex]l[/tex]的值）的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats？
答案是否定的。注意到我们真正需要的只是叶子结点，所以其他非叶子结点的最小值全部弄成无限大，然后这样做就可以把最小值当做标记来弄了……非常精巧。
代码：
/**************************************************************
Problem: 3339
User: danihao123
Language: C++
Result: Accepted
Time:1988 ms
Memory:10396 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
if(L==R){
minv[o]=A[L];
}else{
int M=L+(R-L)/2;
minv[o]=INF;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
}
}
inline void paint(int o,int v){
minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
paint(o<<1,minv[o]);
paint(o<<1|1,minv[o]);
minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
if(L==R)
return minv[o];
if(minv[o]<INF)
pushdown(o);
int M=L+(R-L)/2;
if(pos<=M)
return query(o<<1,L,M);
else
return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
if(ql<=L && R<=qr){
paint(o,v);
}else{
if(minv[o]<INF)
pushdown(o);
int M=L+(R-L)/2;
if(ql<=M)
update(o<<1,L,M);
if(qr>M)
update(o<<1|1,M+1,R);
}
}
inline int readint(){
register int x=0;
register char c;
fread(&c,1,1,stdin);
while(!isdigit(c))
fread(&c,1,1,stdin);
while(isdigit(c)){
x=x*10+c-'0';
fread(&c,1,1,stdin);
}
return x;
}
int buf[21];
inline void putint(int x){
register int i,p=0;
if(!x){
buf[p++]=0;
}else{
while(x){
buf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(buf[i]+'0');
putchar('\n');
}
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
int id;
int l,r;
int ans;
};
bool cmp1(const Query& x,const Query& y){
if(x.l==y.l)
return x.r<y.r;
else
return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
int n,q;
register int i,l=1,k=0;
n=readint();
q=readint();
for(i=1;i<=n;i++){
V[i]=readint();
vis[V[i]]=true;
if(k==V[i])
while(vis[k])
k++;
A[i]=k;
}
build_tree(1,1,n);
for(i=n;i>=1;i--){
if(!last[V[i]])
next[i]=n+1;
else
next[i]=last[V[i]];
last[V[i]]=i;
}
for(i=1;i<=q;i++){
QS[i].id=i;
QS[i].l=readint();
QS[i].r=readint();
}
sort(QS+1,QS+1+q,cmp1);
for(i=1;i<=q;i++){
while(l<QS[i].l){
ql=l;
qr=next[l]-1;
v=V[l];
update(1,1,n);
l++;
}
pos=QS[i].r;
QS[i].ans=query(1,1,n);
}
sort(QS+1,QS+1+q,cmp2);
for(i=1;i<=q;i++){
putint(QS[i].ans);
}
return 0;
}
[POJ 3974]Palindrome
Manacher……妙，妙啊……
这个题就要是给一个字符串，输出最大回文字串长度。Manacher即可。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000005;
char buf[maxn],s[maxn<<1];
int p[maxn<<1];
inline void FactStr(){
register int i,j=0,n=strlen(buf);
s[j++]='$';
s[j++]='#';
for(i=0;i<n;i++){
s[j++]=buf[i];
s[j++]='#';
}
s[j]='\0';
}
inline int Manachar(){
register int i,n=strlen(s);
register int mx=0,id;
register int ans=-1;
for(i=1;i<n;i++){
if(i<mx)
p[i]=min(p[2*id-i],mx-i);
else
p[i]=1;
while(s[i-p[i]]==s[i+p[i]])
p[i]++;
if((p[i]+i)>mx){
id=i;
mx=p[i]+i;
}
ans=max(ans,p[i]-1);
}
return ans;
}
int main(){
register int Case=0;
while(scanf("%s",buf)==1){
if(buf[0]=='E')
break;
Case++;
FactStr();
printf("Case %d: %d\n",Case,Manachar());
}
return 0;
}
[BZOJ 1468]Tree
点分治第一题……
这个也就是最经典的那个点分治问题了吧……参照qzc大爷的论文吧。
代码：
/**************************************************************
Problem: 1468
User: danihao123
Language: C++
Result: Accepted
Time:816 ms
Memory:2736 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 40005;
const int maxm = maxn * 2;
struct Edge {
Edge *next;
int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
graph_cnt = 0;
memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
Edge *e = &pool[graph_cnt++];
e->next = first[u];
first[u] = e;
e->to = v;
e->dist = d;
}
int k;
int calc(vector<int>& V) {
int size = V.size();
int rc = size - 1;
int ans = 0;
if(size <= 1){
return 0;
}
for(int i = 0; i < size; i++) {
while(i < rc && V[i] + V[rc] > k) {
rc--;
}
if(i == rc) {
break;
}
ans += rc - i;
}
return ans;
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
siz[x] = 1;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
bool OK = siz[x]*2 >= siz[now_root];
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_best_root(v, x);
OK = OK && (siz[v]*2 <= siz[now_root]);
}
}
if(OK) {
best_root = x;
}
}
void add_to_V(int x, int fa, int d, vector<int>& V) {
V.push_back(d);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
add_to_V(v, x, d + e->dist, V);
}
}
}
int divide(int x) {
gen_siz(x, 0);
now_root = x;
gen_best_root(x, 0);
x = best_root;
vis[x] = true;
vector<int> V, CV;
int ans = 0;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(vis[v]) {
continue;
}
CV.clear();
add_to_V(v, x, e->dist, CV);
sort(CV.begin(), CV.end());
ans -= calc(CV);
for(int i = 0; i < CV.size(); i++) {
V.push_back(CV[i]);
}
}
V.push_back(0);
sort(V.begin(), V.end());
ans += calc(V);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(vis[v]) {
continue;
}
ans += divide(v);
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
clear_graph();
for(int i = 1; i <= (n - 1); i++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
add_edge(u, v, d);
add_edge(v, u, d);
}
scanf("%d", &k);
printf("%d\n", divide(1));
return 0;
}
[BZOJ 1051]受欢迎的牛
Tarjan缩点第一题……
很容易想到找出度为0的点（当且仅当这样的点有一个时有解），但是在有环图上这个方法会失效。
处理方法是，用Tarjan的强联通分量算法求出所有SCC，然后把每个SCC缩成一个点，然后再在缩点之后的图上求解即可（这个图是DAG。原因很简单，要是有环还能接着缩）。
代码：
/**************************************************************
Problem: 1051
User: danihao123
Language: C++
Result: Accepted
Time:72 ms
Memory:1692 kb
****************************************************************/
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
dfs_clk++;
pre[x]=low[x]=dfs_clk;
S.push(x);
int i,u;
for(i=first[x];i;i=next[i]){
u=to[i];
if(!pre[u]){
dfs(u);
low[x]=min(low[x],low[u]);
}else{
if(!sccno[u])
low[x]=min(low[x],pre[u]);
}
}
if(low[x]==pre[x]){
scc_cnt++;
sccsiz[scc_cnt]=0;
while(true){
u=S.top();
S.pop();
sccno[u]=scc_cnt;
sccsiz[scc_cnt]++;
if(u==x)
break;
}
}
}
int n;
inline void Tarjan(){
register int i;
for(i=1;i<=n;i++)
if(!pre[i])
dfs(i);
}
bool Out[maxn];
int main(){
int m,u,v;
register int i,j,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
}
Tarjan();
for(i=1;i<=n;i++){
for(j=first[i];j;j=next[j]){
u=to[j];
if(sccno[i]!=sccno[u])
Out[sccno[i]]=true;
}
}
for(i=1;i<=scc_cnt;i++){
if(!Out[i]){
if(ans){
ans=0;
break;
}
ans=sccsiz[i];
}
}
if(n==1)
ans=0;
printf("%d\n",ans);
return 0;
}
[CodeVS 1217]借教室
很容易想到线段树水过。
很可惜，这样估计也就70分。
然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定？
不知道诸位还记得差分序列？记得就好，用差分序列的方法维护即可。
等等，我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的，能过？
推荐一个行之有效的优化：注意一下每一次修改都是在之前的基础上反悔或前进几次，所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~
代码：
#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
register int i,cnt=0;
if(x>last)
for(i=last+1;i<=x;i++){
C[l[i]]+=d[i];
C[r[i]+1]-=d[i];
}
if(x<last)
for(i=x+1;i<=last;i++){
C[l[i]]-=d[i];
C[r[i]+1]+=d[i];
}
last=x;
for(i=1;i<=n;i++){
cnt+=C[i];
if(cnt>A[i])
return false;
}
return true;
}
int main(){
register int i,L,M,R;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
for(i=1;i<=m;i++){
scanf("%lld%d%d",&d[i],&l[i],&r[i]);
}
L=1;
R=m+1;
while(L<R){
M=L+(R-L)/2;
if(Check(M)){
L=M+1;
}else{
R=M;
}
}
if(L==m+1)
puts("0");
else
printf("-1\n%d\n",L);
return 0;
}
