给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。
思路很巧妙。先划分一下，第一步对≤√k的n暴力求。因为a%b也等于a-a div b(用pascal的术语，表整除)*b，所以第二步对于1到√k的每个数i，求一个区间[l,r]使得区间里每个数被k整除后商为i，然后就可以用数列求和公式求k div [l,r]*[l,r]的和，再用k减后做个累加即可，但要注意区间不要和之前在第一步求过的重叠。因为一个数%大于自己的数等于自己，所以可以对大于k的n直接做乘法。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define inc(i,j,k) for(long long i=j;i<=k;i++)
using namespace std;
int main(){
long long n,k; scanf("%lld%lld",&n,&k); long long ans=0;
long long sz=(long long)sqrt(k)+1;
if(n<=sz){
inc(i,1,n)ans+=k%i;
}else{
inc(i,1,sz)ans+=k%i;
inc(j,1,k/sz){
long long l=max(k/(j+1)+1,sz+1),r=min(min(k/j,k),n); if(l>r)continue;
ans+=(k*(r-l+1)-j*(l+r)*(r-l+1)/2);
}
if(n>k)ans+=k*(n-k);
}
printf("%lld",ans);
return 0;
}给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。
首先将数组中所有小于b的数置为-1，等于的置为0，大于的置为1。然后对b及其右边的数的前缀和（b的位置到该位置所有数的和）出现个数建一个数组r，对b左边的数的每个后缀和（该位置到b的位置所有数的和）的相反数在r中的数相乘就是答案。实际上，这种把数转化成1、-1、0的方法十分常用，但是我不会。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int l[400000],r[400000],s,n,b,a[200000],p;
int main(){
scanf("%d%d",&n,&b);
inc(i,1,n){
int a1; scanf("%d",&a1); if(a1==b)a[i]=0,p=i; if(a1<b)a[i]=-1; if(a1>b)a[i]=1;
}
l[p+1]=0; dec(i,p,1)l[i]=l[i+1]+a[i];
memset(r,0,sizeof(r)); s=0; inc(i,p,n)s=s+a[i],r[s+n]++;
int ans=0; inc(i,1,p)ans+=r[-l[i]+n];
printf("%d",ans);
}账本上记录了n个月以来的收入情况，其中第i 个月的收入额为Ai 。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。给出m段时间内的总收入，判断账本是否合法。
太神了，并查集还能这么用。每月作为一个节点，同时保存父节点表示的月份到该月份的盈利是多少，每次读入一个区间，如果左右端点在同一个集合内，就直接比较两个节点的权值差（因为路径压缩时已经使它们的父节点相同），注意路径压缩时要先递归再维护权值。如果左右端点在不同集合，则合并，设所在子树被合并的那个端点为a2，另一个为a1，a2的根节点为a5，给出的信息为a3，则a5的权值变为w[a5]=w[a1]-w[a2]+a3。因为：设a1根节点为a4，s[i]表示i的前缀和，则w[a1]=s[a1]-s[a4] w[a2]=s[a2]-s[a5] a3=s[a2]-s[a1] 显然s[a5]-s[a4]=w[a1]-w[a2]+a3=w[a5]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int fa[1000],w[1000];
int find(int x){if(x==fa[x])return x;else{int y=find(fa[x]); w[x]+=w[fa[x]]; return fa[x]=y;};}
int main(){
int t,n,m; scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m); inc(i,0,n)fa[i]=i,w[i]=0; bool f=0;
inc(i,1,m){
int a1,a2,a3; scanf("%d%d%d",&a1,&a2,&a3); a1--;
int a4=find(a1),a5=find(a2);
if(a4==a5&&a3!=w[a2]-w[a1]){printf("false\n");f=1;break;}
if(a4!=a5)w[a5]=w[a1]-w[a2]+a3,fa[a5]=a4;
}
if(!f)printf("true\n");
}
}n支队伍打单循环赛，赢的得3分，平局各得1分，输的不得分。已知n支队伍最终得分，求多少种可能的分数表。
爆搜，加入各种奇怪剪枝，比如：剩下的比赛全赢分数都不到要求就返回、当前分数超过了要求……还有一个重要的就是如果当前已经是最后一场就直接算出比赛结果，这个剪枝虽然表面上没什么用但实际上可以把程序从TLE的边缘拯救回来。这种题对我这种从不鸟常数的就是灾难。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int s2[10],ans[10],tot,n,sz;
void dfs(int x,int y,int z){
if(z==sz){inc(i,1,n)if(s2[i]!=ans[i])return; tot++; return;}if(x>n||y>n)return;
if(y!=n||(y==n&&ans[x]-s2[x]==3)){
s2[x]+=3;
if(s2[x]+3*(n-y)>=ans[x]&&s2[y]+3*(n-x)>=ans[y]&&s2[x]<=ans[x]&&s2[y]<=ans[y])y==n?dfs(x+1,x+2,z+1):dfs(x,y+1,z+1);
s2[x]-=3;
}
if(y!=n||(y==n&&ans[x]-s2[x]==1)){
s2[x]++; s2[y]++;
if(s2[x]+3*(n-y)>=ans[x]&&s2[y]+3*(n-x)>=ans[y]&&s2[x]<=ans[x]&&s2[y]<=ans[y])y==n?dfs(x+1,x+2,z+1):dfs(x,y+1,z+1);
s2[x]--; s2[y]--;
}
if(ans[x]==s2[x]||y!=n){
s2[y]+=3;
if(s2[x]+3*(n-y)>=ans[x]&&s2[y]+3*(n-x)>=ans[y]&&s2[x]<=ans[x]&&s2[y]<=ans[y])y==n?dfs(x+1,x+2,z+1):dfs(x,y+1,z+1);
s2[y]-=3;
}
}
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d",&ans[i]);
memset(s2,0,sizeof(s2)); tot=0; sz=(n*n-n)>>1;
dfs(1,2,0); printf("%d",tot);
}把N只袜子从1到N编号，每次求从编号为L到R的袜子中抽两只，有多大的概率抽到颜色相同的袜子。
不知道要用什么数据结构，但是可以用一个全局的数组保存每个颜色当前数量，使由区间[l,r]推出[l,r±1]的答案和[l±1,r]的复杂度为O(1)，对这种问题，可以用复杂度为O(nsqrt(n))的莫队算法解决。
莫队算法是一种离线算法，将询问按某种顺序排序，使得均摊复杂度为O(nsqrt(n))，那怎么排序呢？如果按左端点排序，那么r将有可能多次大幅度摆动，使复杂度退化成O(n^2)，正解是对端点分块，让后按左端点所在块为第一关键字排序，右端点为第二关键字排序。这样子当两个询问l在同一块时，l只有可能移sqrt(n)次。l在同一块的多次询问q只能右移n次，l在不同块时r可能左移n次，但因为只有sqrt(n)块，所以需移n次的操作都只有sqrt(n)次，因此均摊复杂度是O(sqrt(n))。所有的均摊复杂度都是玄学……
因为中间结果没有强制转化成long long，wa了好几发，本弱太弱了！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
struct nd1{
int l,pl,r,id; ll ans;
};
bool cmp1(nd1 a,nd1 b){
if(a.pl!=b.pl)return a.pl<b.pl; if(a.r!=b.r)return a.r<b.r;
return a.l<b.l;
}
bool cmp2(nd1 a,nd1 b){
return a.id<b.id;
}
nd1 a1[100000];int col[100000],pos[100000],n,m,l,r;ll ans,s[100000];
inline void update(int x,int y){
ans-=(s[col[x]]*(s[col[x]]-1));s[col[x]]+=(ll)y;ans+=(s[col[x]]*(s[col[x]]-1));
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
int main(){
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%d",&col[i]); int sz=(int)sqrt(n);
inc(i,1,n)pos[i]=(i-1)/sz+1;
inc(i,1,m){
int a,b;scanf("%d%d",&a,&b);a1[i]=(nd1){a,pos[a],b,i,0};
}
sort(a1+1,a1+1+m,cmp1); l=1; r=0; ans=0; memset(s,0,sizeof(s));
inc(i,1,m){
while(r<a1[i].r)update(r+1,1),r++;
while(l>a1[i].l)update(l-1,1),l--;
while(r>a1[i].r)update(r,-1),r--;
while(l<a1[i].l)update(l,-1),l++;
a1[i].ans=ans;
}
sort(a1+1,a1+1+m,cmp2);
inc(i,1,m){
if(a1[i].ans==0)printf("0/1\n");else{
ll a2=gcd(a1[i].ans,(ll)(a1[i].r-a1[i].l+1)*(a1[i].r-a1[i].l));
printf("%lld/%lld\n",a1[i].ans/a2,(ll)(a1[i].r-a1[i].l+1)*(a1[i].r-a1[i].l)/a2);
}
}
return 0;
}有 N 个城市，M 条双向的道路，有K次机会使通过某条道路时时间变慢 50%。注意在一条道路上最多只能使用一次机会，且不必使用完所有机会。 求从城市1 到城市N最少需要多长时间。（每条双向边等价于两条单向边）
分层图最短路。这道题数据弱，可以按次数拆点，但bzoj2763就不行了，正解是在作spfa时“拆点”，把d弄成二维数组。虽然感觉上是一样的，但时间却相差很大，不知道为什么。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3fffffff
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define turn(x,y) (y-1)*n+x
using namespace std;
struct e{int t,w,n;}; int ess,g[100]; e es[200000];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int n,m,k,s,t,d[100][100]; bool inq[100][100];
struct nd{int x,y;}; queue <nd> q;
void spfa(){
while(! q.empty())q.pop(); inc(i,1,n)inc(j,1,k+1)d[i][j]=INF;
d[1][1]=0; q.push((nd){1,1}); inq[1][1]=1;
while(! q.empty()){
nd x=q.front(); q.pop(); inq[x.x][x.y]=0;
for(int i=g[x.x];i;i=es[i].n)if(d[es[i].t][x.y]>d[x.x][x.y]+es[i].w){
d[es[i].t][x.y]=d[x.x][x.y]+es[i].w;
if(! inq[es[i].t][x.y])q.push((nd){es[i].t,x.y}),inq[es[i].t][x.y]=1;
}
if(x.y<=k)for(int i=g[x.x];i;i=es[i].n)if(d[es[i].t][x.y+1]>d[x.x][x.y]+(es[i].w>>1)){
d[es[i].t][x.y+1]=d[x.x][x.y]+(es[i].w>>1);
if(! inq[es[i].t][x.y+1])q.push((nd){es[i].t,x.y+1}),inq[es[i].t][x.y+1]=1;
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k); ess=0; memset(g,0,sizeof(g));
inc(i,1,m){
int a,b,c;scanf("%d%d%d",&a,&b,&c); pe(a,b,c),pe(b,a,c);
}
spfa(); int min=INF; inc(i,1,k+1)if(d[n][i]<min)min=d[n][i];
printf("%d",min);
return 0;
}n个城市，这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市（双向），并且航线有一定的价格，途中可以进行转机。规定可以免费在最多k种航线上搭乘飞机。已知起点终点和k，求这次出行最少花费多少？
同bzoj2662，但这次乱搞会TLE，本弱太弱了！
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3fffffff
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define turn(x,y) (y-1)*n+x
using namespace std;
struct e{int t,w,n;}; int ess,g[15000]; e es[200000];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int n,m,k,s,t,d[15000][11]; bool inq[15000][11];
struct nd{int x,y;}; queue <nd> q;
void spfa(){
while(! q.empty())q.pop(); inc(i,0,n-1)inc(j,1,k+1)d[i][j]=INF;
d[s][1]=0; q.push((nd){s,1}); inq[s][1]=1;
while(! q.empty()){
nd x=q.front(); q.pop(); inq[x.x][x.y]=0;
for(int i=g[x.x];i;i=es[i].n)if(d[es[i].t][x.y]>d[x.x][x.y]+es[i].w){
d[es[i].t][x.y]=d[x.x][x.y]+es[i].w; if(! inq[es[i].t][x.y])q.push((nd){es[i].t,x.y}),inq[es[i].t][x.y]=1;
}
if(x.y<=k)for(int i=g[x.x];i;i=es[i].n)if(d[es[i].t][x.y+1]>d[x.x][x.y]){
d[es[i].t][x.y+1]=d[x.x][x.y]; if(! inq[es[i].t][x.y+1])q.push((nd){es[i].t,x.y+1}),inq[es[i].t][x.y+1]=1;
}
}
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); ess=0; memset(g,0,sizeof(g));
inc(i,1,m){
int a,b,c;scanf("%d%d%d",&a,&b,&c); pe(a,b,c),pe(b,a,c);
}
spfa(); int min=INF;
inc(i,1,k+1)if(d[t][i]<min)min=d[t][i];
printf("%d",min);
return 0;
}赛场上一共有N辆车。赛道是一条无限长的直线。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖。已知所有赛车的起始位置（离起跑线距离）和速度，求出那些赛车将会得奖。
有人说是类似线性规划，用半平面交，反正我不会，数学考试是线性规划也错得一塌糊涂QAQ。
黄学长用的是维护斜率的方法，按照斜率排个序，依次插入一个单调栈，如果栈顶不满足XX条件（说不清楚，画个图）就弹掉，最后留在栈里的就是答案。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define eps 1e-8
using namespace std;
struct nd{
int s,v,id;
bool operator < (const nd& a)const{
if(v!=a.v)return v<a.v; return s<a.s;
}
};
double solve(nd a,nd b){
return (double)(a.s-b.s)/(double)(b.v-a.v);
}
nd nds[20000],s[20000]; int ans[20000],n,tp;
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d",&nds[i].s),nds[i].id=i; inc(i,1,n)scanf("%d",&nds[i].v); sort(nds+1,nds+1+n);
tp=1;s[tp]=nds[1];ans[tp]=nds[1].id;
inc(i,2,n){
while(tp>=1&&solve(s[tp],nds[i])<-eps)tp--;
while(tp>=2&&solve(s[tp-1],s[tp])>solve(s[tp],nds[i]))tp--;
s[++tp]=nds[i]; ans[tp]=nds[i].id;
}
sort(ans+1,ans+1+tp); printf("%d\n",tp);
inc(i,1,tp){
i==tp?printf("%d",ans[i]):printf("%d ",ans[i]);
}
return 0;
}平面上有n条直线L1,L2,…Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的。给出n条直线,已知其斜率和截距,且n条直线两两不重合，求出所有可见的直线。
和bzoj3190差不多，但是因为是比较随意的直线，所以还要多一些判断条件。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define eps 1e-8
using namespace std;
struct nd{
int a,b,id;
bool operator < (const nd& x)const{
if(a!=x.a)return a<x.a; return b<x.b;
}
};
double solve(nd a,nd b){
return (double)(a.b-b.b)/(double)(b.a-a.a);
}
nd nds[100000],s[100000]; int ans[100000],n,tp;
int main(){
scanf("%d",&n);inc(i,1,n)scanf("%d",&nds[i].a),scanf("%d",&nds[i].b),nds[i].id=i; sort(nds+1,nds+1+n);
tp=1;s[tp]=nds[1];ans[tp]=nds[1].id;
inc(i,2,n){
if(nds[i].a-s[tp].a==0)tp--;
while(tp>=2&&solve(s[tp-1],s[tp])>=solve(s[tp],nds[i]))tp--;
s[++tp]=nds[i]; ans[tp]=nds[i].id;
}
sort(ans+1,ans+1+tp);inc(i,1,tp)printf("%d ",ans[i]);
return 0;
}一共有n份资料，每天随机选一个区间[l,r]，Mato按文件从小到大的顺序看编号在此区间内的这些资料。他先把要看的文件按编号顺序依次拷贝出来，再用排序程序给文件大小排序。求每天排序时的交换次数。
还是莫队，但是转移的时候用树状数组维护逆序对个数，总复杂度为O(nsqrt(n)log2n)。因为是从大到小插入的，所以维护时要用r-l+1减。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define lowbit(a) a&(-a)
#define ll long long
using namespace std;
struct nd1{int x,y;};
bool cmp1(nd1 a,nd1 b){return a.x<b.x;}
struct nd2{int l,pl,r; ll ans; int id;};
bool cmp2(nd2 a,nd2 b){if(a.pl!=b.pl)return a.pl<b.pl; if(a.r!=b.r)return a.r<b.r; return a.l<b.l;}
bool cmp3(nd2 a,nd2 b){return a.id<b.id;}
ll c[100000],ans,l,r; int n,q,ls[100000],pos[100000]; nd1 f[100000]; nd2 ask[100000];
inline void add(int x,ll y){while(x<=n)c[x]+=y,x+=lowbit(x);}
inline ll query(int x){ll qy=0; while(x>=1)qy+=c[x],x-=lowbit(x); return qy;}
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d",&f[i].x),f[i].y=i; sort(f+1,f+n+1,cmp1);
inc(i,1,n)ls[f[i].y]=i; int sz=(int)sqrt(n); inc(i,1,n)pos[i]=(i-1)/sz+1;
scanf("%d",&q); inc(i,1,q){int a,b; scanf("%d%d",&a,&b); ask[i]=(nd2){a,pos[a],b,0,i};}
sort(ask+1,ask+1+q,cmp2); memset(c,0,sizeof(c)); ans=0; l=1; r=0;
inc(i,1,q){
while(r<ask[i].r){int x=r+1; x=n-ls[x]; ll a1=query(x); ans+=a1; add(x+1,1); r++;}
while(l>ask[i].l){int x=l-1; x=n-ls[x]; ll a1=(r-l+1)-query(x); ans+=a1; add(x+1,1); l--;}
while(r>ask[i].r){int x=r; x=n-ls[x]; ll a1=query(x); ans-=a1; add(x+1,-1); r--;}
while(l<ask[i].l){int x=l; x=n-ls[x]; ll a1=(r-l)-query(x); ans-=a1; add(x+1,-1); l++;}
ask[i].ans=ans;
}
sort(ask+1,ask+1+q,cmp3); inc(i,1,q)printf("%lld\n",ask[i].ans);
return 0;
}给你一个n个数的数列，求出现次数超过n div 2的数（只有1个）。
注意空间只有1M，显然不能开数组。用两个变量，一个存“当前数”，另一个存“当前数”的个数，如果读入的数与“当前数”相同就个数加一，如果不同就减一。如果个数减到0就换“当前数”为现在读入的数。因为如果那个“众数”个数超过ndiv2，所以一定不会被其他数抵消完，能够“坚持”到最后，所以答案就是最后的那个“当前数”。思路真巧。
#include <cstdio>
using namespace std;
int main(){
int n,x,t,tot; tot=0; scanf("%d",&n);
while(n--){
scanf("%d",&x);
if(tot==0)t=x,tot=1;else if(x==t)tot++;else tot--;
}
printf("%d",t);
}有N座岛屿，某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥是危桥。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2 到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。判断两人能否达成愿望。
网络流，每天边的容量就是这条边可以走几次，建一个超级源连a1b1，a2b2连超级汇，如果最大流大于等于2*(b1+b2)就行。但有可能出现a1流到b2导致原来的不可行被判断成可行，这样我们就需要把b2和b1调换位置，如果结果一样，说明这个方案是真正可行的，具体原因我还不懂，好像是如果两个结果一样，即使真的出现了a1流到b2的情况，也能通过调整变成正确的流动方案，蒟蒻太弱了！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3fffffff
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
struct e{int t,c,n;}; e es[10000]; int ess,g[100];
void pe(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;}
char map[100][100]; int n,a1,a2,an,b1,b2,bn,s,t;
queue <int> q; int h[100];
bool bfs(int s,int t){
while(! q.empty())q.pop(); memset(h,-1,sizeof(h)); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
if(h[t]==-1)return 0;else return 1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c)); es[i].c-=w; es[i^1].c+=w; f-=w; u+=w;
if(f==0)return u;
}
if(u==0)h[x]=-1; return u;
}
int dinic(int s,int t){int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;}
int main(){
while(scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF){
inc(i,1,n)scanf("%s",map[i]); a1++; a2++; b1++; b2++; s=0; t=n+1;
ess=-1; memset(g,-1,sizeof(g)); pe(s,a1,2*an); pe(s,b1,2*bn); pe(a2,t,2*an); pe(b2,t,2*bn);
inc(i,1,n)inc(j,0,n-1){
if(map[i][j]=='O')pe(i,j+1,2);
if(map[i][j]=='N')pe(i,j+1,INF);
}
if(dinic(s,t)>=2*an+2*bn){
ess=-1; memset(g,-1,sizeof(g)); pe(s,a1,2*an); pe(s,b2,2*bn); pe(a2,t,2*an); pe(b1,t,2*bn);
inc(i,1,n)inc(j,0,n-1){
if(map[i][j]=='O')pe(i,j+1,2);
if(map[i][j]=='N')pe(i,j+1,INF);
}
if(dinic(s,t)>=2*an+2*bn)printf("Yes\n");else printf("No\n");
}else printf("No\n");
}
return 0;
}给定一个整数N，求出\(\sum_{i=1}^N{gcd(i, N)}\)。
欧拉函数就是求比一个正整数且和它互质的正整数有几个，我不会，摘黄学长的题解：
题目中要求出\(\sum_{i=1}^N{gcd(i, N)}\)。 枚举n的约数k，令s(k)为满足gcd(m,n)=k,(1<=m<=n)的m的个数，则\(ans=\sum_k{k*s(k)},n|k\) 因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
long long phi(long long x){
long long a1=x,a2=(long long)sqrt(x);
inc(i,2,a2)if(x%i==0){
a1=a1/i*(i-1); while(x%i==0)x/=i;
}
if(x!=1)a1=a1/x*(x-1); return a1;
}
int main(){
long long n; scanf("%lld",&n); long long m=(long long)sqrt(n); long long ans=0;
inc(i,1,m)if(n%i==0){
ans+=i*phi(n/i); if(i*i<=n)ans+=n/i*phi(i);
}
printf("%lld",ans);
}一个数列，支持区间翻转操作。
splay裸题。注意涉及到区间操作的一般用splay不用treap。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define fa(x) nds[x].fa
#define ch(x,y) nds[x].ch[y]
#define tg(x) nds[x].tg
#define v(x) nds[x].v
#define sz(x) nds[x].sz
using namespace std;
struct nd{int fa,ch[2],v,sz,tg;};
nd nds[200000]; int size,root,n,m; bool first;
void pushdown(int x){
if(! x)return; if(tg(x)){
if(ch(x,0)&&ch(x,1))swap(ch(x,0),ch(x,1)),tg(ch(x,0))^=1,tg(ch(x,1))^=1;else
if(ch(x,0))ch(x,1)=ch(x,0),ch(x,0)=0,tg(ch(x,1))^=1;else ch(x,0)=ch(x,1),ch(x,1)=0,tg(ch(x,0))^=1;
tg(x)^=1;
}
}
void update(int x){if(! x)return; sz(x)=sz(ch(x,0))+sz(ch(x,1))+1;}
void rotate(int x){
if(x==0||fa(x)==0)return;
int a1=fa(x),a2=fa(a1); bool a3=(x==ch(a1,1)),a4=(a1==ch(a2,1));
if(a2)ch(a2,a4)=x; if(ch(x,!a3))fa(ch(x,!a3))=a1; ch(a1,a3)=ch(x,!a3); ch(x,!a3)=a1;
fa(x)=a2; fa(a1)=x; update(a1); update(x); if(a2)update(a2);
}
void splay(int x,int y){
if(x==0||y==0)return; int z=fa(y); if(y==root)root=x;
while(fa(x)!=z){
if(fa(fa(x))!=z){
if((x==ch(fa(x),1))^(fa(x)==ch(fa(fa(x)),1)))rotate(x);else rotate(fa(x));
}
rotate(x);
}
}
int build(int l,int r){
if(l>r)return 0;
++size; int ff=size; int m=(l+r)>>1; ch(ff,0)=build(l,m-1); ch(ff,1)=build(m+1,r);
if(ch(ff,0))fa(ch(ff,0))=ff; if(ch(ff,1))fa(ch(ff,1))=ff;
v(ff)=m; tg(ff)=0; update(ff); return ff;
}
int find(int p){
int x=root; while(1){
if(x==0)return 0; pushdown(x);
int a1=sz(ch(x,0)); if(a1+1==p)return x;
if(a1+1<p)p-=(a1+1),x=ch(x,1);else x=ch(x,0);
}
}
void rever(int l,int r){
int a1=find(l-1),a2=find(r+1); splay(a2,root);
if(l>1)splay(a1,ch(a2,0)),tg(ch(a1,1))^=1;else tg(ch(a2,0))=1;
}
void print(int x){
if(x==0)return; pushdown(x);
print(ch(x,0));
if(v(x)!=n+1)
if(!first)printf("%d",v(x)),first=1;else printf(" %d",v(x));
print(ch(x,1));
}
int main(){
//freopen("test.txt","r",stdin);
scanf("%d%d",&n,&m); size=0; root=build(1,n+1);
inc(i,1,m){
int a,b; scanf("%d%d",&a,&b); rever(a,b);
}
first=0; print(root);
return 0;
}有(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问能否拼出另一个向量(x,y)。
裴蜀定理（我不会）（实际上是与解同余方程的知识相关的）。题目可以转化为用(0,2a)、(2a,0)、(0,2b)、(2b,0)拼成(x,y)、(x+a,y+b)、(x+b,y+a)、(x+a+b,y+a+b)。这样就可以列方程了。题目要求判断方程是否有解，只要求出2a、2b的gcd，然后判断目标两个数能否整除这个gcd即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}
inline bool check(long long x,long long y,long long z){return x%z==0&&y%z==0;}
int main(){
int t; scanf("%d",&t);
while(t--){
long long a,b,x,y; scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
long long c=gcd(2*a,2*b);
if(check(x,y,c)||check(x+a,y+b,c)||check(x+b,y+a,c)||check(x+a+b,y+a+b,c))puts("Y");else puts("N");
}
return 0;
}共有n个学生，m个学习小组，每个学生只愿意参加其中的一些学习小组，且一个学生最多参加k个学习小组。每个学生参加学习小组财务处都收一定的手续费，不同的学习小组有不同的手续费。若有a个学生参加第i个学习小组，财务处支付奖励Ci*a^2元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱。
s连n个学生，流量为k，费用为0。每个学生向喜欢的小组的连边，流量为1，费用为手续费的相反数。每个小组向t连边，它的费用与流量的平方成正比的边，需要把它拆成k条流量为1，费用为1*ci、3*ci…(2*k-1)的边。本题的难点是要参与学生尽量多，所以我们需要每个学生至少参加一个组，因此每个学生再向t连一条流量为k-1，费用为0的边，就可以了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define visit(i,j) for(int i=g[j];i!=-1;i=es[i].n)
#define INF 0x3fffffff
using namespace std;
struct e{int f,t,c,w,n;}; e es[1000000]; int ess,g[400];
void pe(int f,int t,int c,int w){
es[++ess]=(e){f,t,c,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,0,-w,g[t]}; g[t]=ess;
}
void init(){ess=-1; memset(g,-1,sizeof(g));}
int d[400],fr[400]; queue <int> q; bool inq[400],vis[400];
bool spfa(int s,int t){
while(! q.empty())q.pop(); memset(inq,0,sizeof(inq)); memset(vis,0,sizeof(vis));
inq[s]=1; d[s]=0; vis[s]=1; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
visit(i,x)if(es[i].c&&(! vis[es[i].t]||d[es[i].t]>d[x]+es[i].w)){
d[es[i].t]=d[x]+es[i].w; vis[es[i].t]=1; fr[es[i].t]=i;
if(! inq[es[i].t])inq[es[i].t]=1,q.push(es[i].t);
}
}
if(! vis[t])return 0;else return 1;
}
int advanced(int s,int t){
int a=INF; for(int i=t;i!=s;i=es[fr[i]].f)a=min(a,es[fr[i]].c);
int cost=0; for(int i=t;i!=s;i=es[fr[i]].f)es[fr[i]].c-=a,es[fr[i]^1].c+=a,cost+=(es[fr[i]].w*a);
return cost;
}
int maxflowmincost(int s,int t){
int cost=0; while(spfa(s,t))
cost+=advanced(s,t); return cost;
}
int n,m,k,s,t,a1[400]; char a3[400];
int main(){
//freopen("test.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k); s=0; t=n+m+1; init(); inc(i,1,n)pe(s,i,k,0),pe(i,t,k-1,0);
inc(i,n+1,n+m){int a2; scanf("%d",&a2); inc(j,1,n)pe(i,t,1,(j*2-1)*a2);}
inc(i,1,m)scanf("%d",&a1[i]); inc(i,1,n){
scanf("%s",a3); inc(j,1,m){if(a3[j-1]=='1')pe(i,n+j,1,-a1[j]);}
}
printf("%d",maxflowmincost(s,t));
return 0;
}已知一个数列A对于所有的A[i]都是1~n的自然数，一些A[i]不能取一些值，求出所有可能的数列的积的和 mod 1000000007的值。
题目中的n≤109实际上是10^9……首先推个方程s[l,r]=s[l,k]*s[k+1,r]（s[l,r]表示l到r的所有l≤i≤r的a[i]的可能取值的和)因此s[1,n]等于所有a[i]的可能取值的和的乘积。因此我们先求出1到n的和，对每个约束条件按i排序，将这个和减掉约束条件中的不能取的数，就是这个a[i]所有可能取值的和。将这些a[i]乘起来，剩下的没限制的a[i]用快速幂解决。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define mod 1000000007
using namespace std;
struct nd{
ll a,b;
bool operator < (const nd &c)const{
if(a!=c.a)return a<c.a;else return b<c.b;
}
};
ll power(ll a,ll b){
if(b==0)return 1; if(b==1)return a; ll c=power(a,b>>1)%mod;
if(b&1)return c*c%mod*a%mod;else return c*c%mod;
}
nd ns[200000];
int main(){
ll n,m,a1=0,a2,a3,a4; ll k; scanf("%lld%lld%lld",&n,&m,&k);
inc(i,1,k)scanf("%lld%lld",&ns[i].a,&ns[i].b); sort(ns+1,ns+k+1);
inc(i,1,k)if(i==1||ns[i].a!=ns[i-1].a)a1++; a2=n*(n+1)/2%mod; a3=a4=1;
inc(i,1,k)if(i==1||ns[i].a!=ns[i-1].a)a4=a4*a3%mod,a3=a2,a3=(a3-ns[i].b)>=0?(a3-ns[i].b)%mod:(a3-ns[i].b)+mod;
else if(ns[i].b!=ns[i-1].b)a3=(a3-ns[i].b)>=0?(a3-ns[i].b)%mod:(a3-ns[i].b)+mod;
a4=a4*a3%mod; a4=a4*power(a2,m-a1)%mod; printf("%lld",a4);
}一些点，每个点有一个权值。有三种操作：点与点连边，单点修改权值，求两点之间路径上点的权值和（需要判输入是否合法）
以前一直想不通为什么神犇们的模板中LCT在link和cut后都要在根节点打翻转标记。现在明白了，因为只有这样才能保持深度的正确性，以前没有因此炸过是因为我以前都是把LCT拿来当链剖用的，根本不用link和cut~~这道题是LCT模板题也没什么好说的。不过CCZ大爷有更快的做法，就是离线读入所有连边操作，然后建一棵树用链剖，判断输入是否合法就在线用并查集查询与维护。orzCCZ！
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50000
using namespace std;
int fa[maxn],ch[maxn][2],sm[maxn],v[maxn];bool rev[maxn];
inline void update(int x){
if(x==0)return; sm[x]=v[x];
if(ch[x][0])sm[x]+=sm[ch[x][0]]; if(ch[x][1])sm[x]+=sm[ch[x][1]];
}
inline bool is_root(int x){
if(x==0||fa[x]==0)return 1;
return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
}
inline void pushdown(int x){
if(rev[x]){
swap(ch[x][0],ch[x][1]); if(ch[x][0])rev[ch[x][0]]^=1; if(ch[x][1])rev[ch[x][1]]^=1; rev[x]^=1;
}
}
void rotate(int x){
if(x==0||is_root(x))return;
int a1=fa[x],a2=fa[fa[x]],a3; bool b1=(x==ch[a1][1]),b2=(a1==ch[a2][1]),b3=is_root(a1); a3=ch[x][!b1];
if(!b3)ch[a2][b2]=x; fa[x]=a2; ch[a1][b1]=a3; if(a3)fa[a3]=a1; ch[x][!b1]=a1; fa[a1]=x;
update(a1); update(x); if(!b3)update(a2);
}
int dt[maxn],dts,y;
void splay(int x){
if(x==0)return; dts=0; y=x; while(! is_root(y))dt[++dts]=y,y=fa[y];
dt[++dts]=y; while(dts)pushdown(dt[dts]),dts--;
while(!is_root(x)){
if(!is_root(fa[x]))((x==ch[fa[x]][1])^(fa[x]==ch[fa[fa[x]]][1]))?rotate(x):rotate(fa[x]);
rotate(x);
}
}
int access(int x){
if(x==0)return 0; int t=0;
while(x){splay(x); ch[x][1]=t; update(x); if(t)fa[t]=x; t=x; x=fa[x];}
return t;
}
bool link(int x,int y){
if(x==0||y==0)return 0; access(x); splay(x); rev[x]^=1; fa[x]=y; return 1;
}
int querysum(int x,int y){
if(x==0||y==0)return 0; if(x==y)return v[x]; access(x); int a=access(y); splay(x);
if(x==a)return v[a]+sm[ch[a][1]];else return sm[x]+v[a]+sm[ch[a][1]];
}
void change(int x,int y){
splay(x); v[x]=y; update(x);
}
int find(int x){
access(x); splay(x); while(ch[x][0])x=ch[x][0]; return x;
}
int n,m; char s[20];
int main(){
//freopen("test.txt","r",stdin);
scanf("%d",&n); inc(i,1,n)scanf("%d",&v[i]),fa[i]=0,ch[i][0]=ch[i][1]=rev[i]=0,sm[i]=v[i]; scanf("%d",&m);
inc(i,1,m){
int a,b; scanf("%s%d%d",s,&a,&b);
if(s[0]=='b'){if(find(a)==find(b))puts("no");else link(a,b),puts("yes");}
if(s[0]=='p')change(a,b);
if(s[0]=='e')if(find(a)!=find(b))puts("impossible");else printf("%d\n",querysum(a,b));
}
return 0;
}平面上N个点(任意两个点的坐标都不相同)。现已知M个猴子的最大跳跃距离，还知道N个点坐标，统计有多少个猴子可以在所有点上觅食。
题目中隐含了一个条件，就是猴子可以从任意点出发。因此我们可以确定一个点，求出它到所有点的最小距离的最大值，然后判断每只猴子的跳跃距离是否大于等于这个最大值。这正是MST问题，用Kruscal排序后选的第n-1条边的长度就是根到所有点的最小距离的最大值。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
struct e{
int f,t,w;
bool operator < (const e &a)const{return w<a.w;};
};
e es[2000000]; int p[2000],n,m,a[2000],x[2000],y[2000];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
int main(){
scanf("%d",&m); inc(i,1,m)scanf("%d",&a[i]); scanf("%d",&n); inc(i,1,n)scanf("%d%d",&x[i],&y[i]);
inc(i,1,n)inc(j,1,n)es[(i-1)*n+j]=(e){i,j,(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])};
sort(es+1,es+1+n*n); inc(i,1,n)p[i]=i; int tot=0,mx=0;
inc(i,1,n*n){
int a1=find(es[i].f),a2=find(es[i].t);
if(a1!=a2){
tot++; p[a2]=a1; if(tot==n-1)mx=es[i].w;
}
}
tot=0; inc(i,1,m)if(a[i]*a[i]>=mx)tot++; printf("%d",tot);
}已知N个正整数，将它们分成M组，使各组数据的数值和最平均，即各组的均方差最小，求最小均方差。
\[ \sigma=\sqrt{\frac{\sum_{i=1}^{n}{(x_i-\overline{x})^2}}{n}} \]
\[ \overline{x}=\frac{\sum_{i=1}^{n}{x_i}}{n} \]
其中\(\sigma\)为均方差，\(\overline{x}\)是各组数据和的平均值，\(x_i\)为第i组数据的数值和。
神奇的模拟退火算法！它是爬山算法的加强版。爬山算法是一种贪心算法，对于每个状态，除非随机选出一个后继状态比它好，才会跳过去。但这样有可能“一叶障目不见泰山”，产生错误的答案。但模拟退火不一样，它如果找到一个后继状态比当前状态差，也有一定概率跳过去，但这概率和跳跃次数成反比。这样即使被“一叶障目”，也有机会绕过叶子，找到泰山。
关于爬山算法与模拟退火，有一个有趣的比喻： 爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
这个算法写法实际上是模拟一个物理降温过程，然而对我这种物理渣~~只能背代码框架了QAQ
回到本题，首先给每个数据随机分到一个组，做5000次模拟退火。当温度比较高时跳跃不稳定，所以贪心一下，随机找一个数据，然后把它放进当前和最小的那个组；当温度渐低后，就随机找一个数据然后随机放组。关于退火的次数，网上题解里是10000，我试过1000会不能过，但是5000能过且比10000要快一倍，所以代码给出的是5000。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
int n,m,pos[100]; double a[100],sum[100],ave,mn,T,ans,pre;
void solve(){
memset(sum,0,sizeof(sum)); inc(i,1,n)pos[i]=rand()%m+1,sum[pos[i]]+=a[i]; ans=0;
inc(i,1,m)ans+=(sum[i]-ave)*(sum[i]-ave); T=10000;
while(T>0.1){
pre=ans; int x=rand()%n+1,y;
if(T>500)y=min_element(sum+1,sum+1+m)-sum;else y=rand()%m+1; if(pos[x]==y)continue;
ans-=(sum[pos[x]]-ave)*(sum[pos[x]]-ave); ans+=(sum[pos[x]]-a[x]-ave)*(sum[pos[x]]-a[x]-ave);
ans-=(sum[y]-ave)*(sum[y]-ave); ans+=(sum[y]+a[x]-ave)*(sum[y]+a[x]-ave);
if(rand()%10000+1>T&&ans>pre)ans=pre;else sum[pos[x]]-=a[x],sum[y]+=a[x],pos[x]=y;
T*=0.9;
}
if(ans<mn)mn=ans;
}
int main(){
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%lf",&a[i]),ave+=a[i],swap(a[i],a[rand()%i+1]);
ave/=(double)m; mn=INF; inc(i,1,5000)solve();
printf("%.2lf",sqrt(mn/(double)m));
}有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。若两个数字 ai、aj 满足ai 是 aj 的倍数且 ai/aj 是一个质数，那么这两个数字可以配对，并获得 ci×cj 的价值。一个数字只能参与一次配对，可以不参与配对。在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
费用流。本题难点是每个数字只能参加一次配对，很容易建错图。正解是先对每个数字分解质因数，按照质因数个数的奇偶建二分图。原因是质因数奇数个和质因数偶数个的两个数相除的商必定不是质数，巧妙地解决了问题。在判断质数方面，如果朴素判断肯定会T，所以可以先筛法求一个质数表，判断的时候直接枚举能否整除质数。因为√109≤32000，所以质数表只要到32000就行了。不过时间复杂度我不会算，本弱太弱了！
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define inc(i,j,k) for(ll i=j;i<=k;i++)
#define ll long long
#define INF 10000000000000000
using namespace std;
ll p[32000],cnt,mx; bool vis1[32000];
void getprime(){
cnt=0; memset(vis1,0,sizeof(vis1)); inc(i,2,(ll)sqrt(mx))if(! vis1[i]){
p[++cnt]=i; for(ll j=i;j<=(ll)sqrt(mx);j+=i)vis1[j]=1;
}
}
inline bool is_prime(ll x){
if(x==1)return 0;
inc(i,1,cnt){if(p[i]*p[i]>x)return 1; if(x%p[i]==0)return 0;}
}
struct e{int f,t;ll c,w;int n;}; e es[1000000]; int ess,g[1000];
inline void pe(int f,int t,ll c,ll w){
es[++ess]=(e){f,t,c,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,0,-w,g[t]}; g[t]=ess;
}
void init(){ess=-1; memset(g,-1,sizeof(g));}
queue <int> q; ll d[1000],cost,flow; int fr[1000]; bool inq[1000],vis2[1000];
bool spfa(int s,int t){
while(! q.empty())q.pop(); memset(vis2,0,sizeof(vis2)); memset(inq,0,sizeof(inq));
q.push(s); vis2[s]=1; inq[s]=1; d[s]=0;
while(! q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&(!vis2[es[i].t]||d[es[i].t]<d[x]+es[i].w)){
vis2[es[i].t]=1; d[es[i].t]=d[x]+es[i].w; fr[es[i].t]=i;
if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1;
}
}
if(!vis2[t])return 0;else return 1;
}
ll maxflowmaxcost(int s,int t){
flow=0; cost=0;
while(spfa(s,t)){
ll a=INF,b=0;for(int i=t;i!=s;i=es[fr[i]].f)a=min(a,es[fr[i]].c);
for(int i=t;i!=s;i=es[fr[i]].f)es[fr[i]].c-=a,es[fr[i]^1].c+=a,b+=es[fr[i]].w; cost+=b*a; flow+=a;
if(cost<0){flow-=(cost%b==0?cost/b:cost/b+1); break;}
}
return flow;
}
ll a[1000],b[1000],c[1000];int n,s,t,sing[1000],doub[1000],tot,singn,doubn;
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%lld",&a[i]),mx=max(mx,a[i]);
inc(i,1,n)scanf("%lld",&b[i]); inc(i,1,n)scanf("%lld",&c[i]);
getprime(); s=0; t=n+1; singn=0; doubn=0;
inc(i,1,n){
int x=a[i]; tot=0; inc(j,1,cnt)if(x%p[j]==0){
while(x%p[j]==0)x/=p[j],tot++; if(x==1)break;
}
if(tot&1)sing[++singn]=i;else doub[++doubn]=i;
}
init(); inc(i,1,singn)pe(s,sing[i],b[sing[i]],0); inc(i,1,doubn)pe(doub[i],t,b[doub[i]],0);
inc(i,1,singn)inc(j,1,doubn)
if(max(a[sing[i]],a[doub[j]])%min(a[sing[i]],a[doub[j]])==0&&is_prime(max(a[sing[i]],a[doub[j]])/min(a[sing[i]],a[doub[j]])))
pe(sing[i],doub[j],INF,c[sing[i]]*c[doub[j]]);
printf("%lld",maxflowmaxcost(s,t));
return 0;
}一些点，三种操作：点与点连边、点与点分离、询问两个点是否连通。
比bzoj2843还弱的LCT，只要注意记得翻转就行。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50000
using namespace std;
int fa[maxn],ch[maxn][2],rev[maxn];
void pushdown(int x){
if(rev[x]){
swap(ch[x][0],ch[x][1]); if(ch[x][0])rev[ch[x][0]]^=1; if(ch[x][1])rev[ch[x][1]]^=1; rev[x]^=1;
}
}
bool is_root(int x){
if(x==0||fa[x]==0)return 1; return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
}
void rotate(int x){
if(x==0||is_root(x))return;
int a1=fa[x],a2=fa[fa[x]],a3; bool b1=(x==ch[a1][1]),b2=(a1==ch[a2][1]),b3=is_root(a1); a3=ch[x][!b1];
if(!b3)ch[a2][b2]=x; fa[x]=a2; ch[a1][b1]=a3; fa[a3]=a1; ch[x][!b1]=a1; fa[a1]=x;
}
int dts,dt[maxn],y;
void splay(int x){
if(x==0)return; dts=0; y=x; while(! is_root(y))dt[++dts]=y,y=fa[y];
dt[++dts]=y; while(dts)pushdown(dt[dts]),dts--;
while(! is_root(x)){
if(! is_root(fa[x]))(x==ch[x][1])^(fa[x]==ch[fa[fa[x]]][1])?rotate(x):rotate(fa[x]);
rotate(x);
}
}
int access(int x){
if(x==0)return 0; int t=0;
while(x){splay(x); ch[x][1]=t; if(t)fa[t]=x; t=x; x=fa[x];}
return t;
}
void link(int x,int y){
if(x==0||y==0)return; access(x); splay(x); rev[x]^=1; fa[x]=y;
}
void cut(int x,int y){
if(x==0||y==0)return; access(x); splay(x); rev[x]^=1; access(y); splay(y); ch[y][0]=fa[x]=0;
}
int find(int x){
access(x); splay(x); while(ch[x][0])x=ch[x][0]; return x;
}
int n,m; char s[10];
int main(){
scanf("%d",&n); inc(i,1,n)fa[i]=ch[i][0]=ch[i][1]=0; scanf("%d",&m);
inc(i,1,m){
int a,b; scanf("%s%d%d",s,&a,&b);
if(s[0]=='C')link(a,b);
if(s[0]=='D')cut(a,b);
if(s[0]=='Q')find(a)==find(b)?puts("Yes"):puts("No");
}
return 0;
}n个数，分成m段使每段和的方差尽可能小。
朴素的dp方程：f[i,m]=f[j,m-1]+(sum[i]-sum[j])2,j∈[1,i-1]（sum[i]-sum[j]不用减平均数的原因是最后可以化简成f[n,m]*m-sum[n]）复杂度为O(n3)会T，因为有个平方，所以考虑斜率优化，化简得到f[j,m-1]比f[k,m-1]好当且仅当((f[j,m-1]+sum[j]2)-(f[k,m-1]+sum[k]2))＜2*sum[i]*(sum[j]-sum[k])，因为递推时是从小到大的顺序，所以sum[j]-sum[k]<0，所以((f[j,m-1]+sum[j]2)-(f[k,m-1]+sum[k]2))/(sum[j]-sum[k])>2*sum[i]，用单调队列即可。多的那一维可以用滚动数组省空间。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 5000
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
long long x[maxn],y[maxn],sum[maxn],a[maxn];int q[maxn],n,m,l,r;
inline long long sqr(long long x){return x*x;}
inline double get(long long a1,long long a2){
return (double)((x[a1]+sqr(sum[a1]))-(x[a2]+sqr(sum[a2])))/(double)(sum[a1]-sum[a2]);
}
int main(){
scanf("%d%d",&n,&m); sum[0]=0; inc(i,1,n)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
inc(i,1,n)x[i]=sqr(sum[i]);
inc(i,2,m){
l=0,r=0; memset(y,0,sizeof(y)); x[1]=sqr(sum[1]); q[l]=1;
inc(j,2,n){
while(l<r&&get(q[l],q[l+1])<2*sum[j])l++;
while(l<r&&get(q[r-1],q[r])>get(q[r],j))r--;
q[++r]=j; y[j]=x[q[l]]+sqr(sum[j]-sum[q[l]]);
} swap(x,y);
}
printf("%lld",(x[n])*(long long)m-sqr(sum[n]));
}某种序列由n种数组成，每种数在该序列中正好出现5次。对于两个这样的序列s1和s2，如果存在一个序列u同时成为s1和s2的子序列，则称u是s1和s2的公共子序列。子序列的概念：若从一个序列s中任意抽取一些数字，将它们仍按在s中的顺序排列成一个新串u，则称u是s的一个子序列。已知两个等长DNA序列s1和s2，求s1和s2最长公共子序列的长度。
dp+树状数组，题解太难写，摘抄一下
LCS的决策+1的条件是a[i]==b[j] 于是我们记录a序列中每个数的5个位置 扫一下b[i] 对于每个b[i]找到b[i]在a中的5个位置 这5个位置的每个f[pos]值都可以被b[i]更新 于是找到f[1]到f[pos-1]的最大值+1 更新f[pos]即可 这个用树状数组维护 时间复杂度O(nlogn)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define lb(x) x&-x
using namespace std;
int c[200000],n,a[40000][6],an[40000],f[200000],ans;
inline int query(int x){int q=0; while(x)q=max(q,c[x]),x-=lb(x); return q;}
inline void update(int x,int y){while(x<=n*5)c[x]=max(c[x],y),x+=lb(x);}
int main(){
scanf("%d",&n); memset(an,0,sizeof(an)); memset(c,0,sizeof(c));
inc(i,1,n*5){int x; scanf("%d",&x); a[x][++an[x]]=i;} ans=0;
memset(f,0,sizeof(f));
inc(i,1,n*5){
int x; scanf("%d",&x);
dec(j,5,1){
int y=a[x][j]; f[y]=max(f[y],query(y-1)+1);
update(y,f[y]); ans=max(ans,f[y]);
}
}
printf("%d",ans);
return 0;
}给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y一起消除，同时得到x+y点分数。求消除的数对尽可能多的前提下分数的最大值。
每个数拆成两个点，s和左侧点连流量为1，费用为0的边；右侧点和t连流量为1，费用为0的边。如果i，j合法，则同时向左侧i向右侧j及左侧j向右侧i连流量为1，费用为i+j的边。这道题和bzoj4514不同，因为每个数只出现一次，所以当左侧i和右侧j被消掉时，左侧j和右侧i也会在下一次消掉，其它的数就无法再和它们相消了。而bzoj4514每个数都有多个，可能一边没消尽，如果用这道题的做法就可能会出现另一个数把它已经被消掉的部分重复消掉，导致结果不刚好为正解的2倍。因此bzoj4514不能拆点，而这道题就可以拆点，答案就分别为算法跑出来的最大流和最大“费用”除以2。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define maxn 5000
#define INF 0x3fffffff
using namespace std;
struct e{int f,t;int c,w;int n;}; e es[2000000]; int ess,g[maxn];
inline void pe(int f,int t,int c,int w){
es[++ess]=(e){f,t,c,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,0,-w,g[t]}; g[t]=ess;
}
void init(){ess=-1; memset(g,-1,sizeof(g));}
queue <int> q; int d[maxn],cost,flow,fr[maxn]; bool inq[maxn],vis[maxn];
bool spfa(int s,int t){
while(! q.empty())q.pop(); memset(vis,0,sizeof(vis)); memset(inq,0,sizeof(inq));
q.push(s); vis[s]=1; inq[s]=1; d[s]=0;
while(! q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&(!vis[es[i].t]||d[es[i].t]<d[x]+es[i].w)){
vis[es[i].t]=1; d[es[i].t]=d[x]+es[i].w; fr[es[i].t]=i;
if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1;
}
}
if(!vis[t])return 0;else return 1;
}
void advanced(int s,int t){
int a=INF; for(int i=t;i!=s;i=es[fr[i]].f)a=min(a,es[fr[i]].c); flow+=a;
for(int i=t;i!=s;i=es[fr[i]].f)es[fr[i]].c-=a,es[fr[i]^1].c+=a,cost+=a*es[fr[i]].w;
}
void maxflowmaxcost(int s,int t){
while(spfa(s,t))advanced(s,t);
}
int n,s,t,l,r;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
bool check(int x,int y){
if(x<=y)return 0; double z=sqrt(x*x-y*y); if(z!=(double)((int)z))return 0;
int zz=(int)z; if(gcd(y,zz)!=1)return 0; return 1;
}
int main(){
scanf("%d%d",&l,&r); n=l-1; s=0; t=2*(r-l+1)+1;
init(); inc(i,l,r)pe(s,i-n,1,0),pe(i-n+(r-l+1),t,1,0);
inc(i,l,r)inc(j,l,r)if(check(i,j))pe(i-n,j-n+(r-l+1),1,i+j),pe(j-n,i-n+(r-l+1),1,i+j); maxflowmaxcost(s,t);
printf("%d %d",flow>>1,cost>>1);
return 0;
}N点树，以点 1 为根，且树点有边权。三种操作：把某个节点点权增加 a 、某个节点为根的子树中所有点的点权都增加 a 、询问某个节点到根的路径中所有点的点权和。
本题链剖可过。第二个操作只要每次在构造链的时候找到子树中在链中位置最大的节点，然后区间修改就行。听说正解是DFS序，不过我不会。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200000
#define ll long long
using namespace std;
struct e{int t,n;}; e es[maxn]; int ess,g[maxn];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;}
int l[maxn*4],r[maxn*4],ch[maxn*4][2],fa[maxn],dep[maxn],pos[maxn],top[maxn],sz[maxn],sgs,mx[maxn];
ll v[maxn][2],sm[maxn*4],tg[maxn*4];
void dfs(int x){
sz[x]=1; for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]){
fa[es[i].t]=x; dep[es[i].t]=dep[x]+1; dfs(es[i].t); sz[x]+=sz[es[i].t];
}
}
void buildchain(int x,int ps){
pos[x]=mx[x]=++sgs; v[sgs][1]=v[x][0]; top[x]=ps; int mx1=0,mx2=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]&&mx2<sz[es[i].t])mx2=sz[es[i].t],mx1=es[i].t;
if(mx1)buildchain(mx1,ps),mx[x]=max(mx[x],mx[mx1]);
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]&&es[i].t!=mx1)
buildchain(es[i].t,es[i].t),mx[x]=max(mx[x],mx[es[i].t]);
}
void pushdown(int x){
if(x&&tg[x]){
int lc=ch[x][0],rc=ch[x][1];
if(lc)sm[lc]+=(r[lc]-l[lc]+1)*tg[x],tg[lc]+=tg[x];
if(rc)sm[rc]+=(r[rc]-l[rc]+1)*tg[x],tg[rc]+=tg[x];
tg[x]=0;
}
}
void build(int x,int L,int R){
if(L==R)sm[x]=v[L][1],ch[x][0]=ch[x][1]=0,l[x]=r[x]=L;else{
ch[x][0]=x<<1,l[x]=L,ch[x][1]=x<<1|1,r[x]=R; int M=(L+R)>>1;
build(ch[x][0],L,M); build(ch[x][1],M+1,R); sm[x]=sm[ch[x][0]]+sm[ch[x][1]];
}
}
ll query(int x,int L,int R){
pushdown(x);
if(L<=l[x]&&r[x]<=R)return sm[x];else{
ll q=0;int M=(l[x]+r[x])>>1; if(L<=M)q+=query(ch[x][0],L,R); if(M<R)q+=query(ch[x][1],L,R);
return q;
}
}
void add(int x,int L,int R,ll val){
pushdown(x);
if(L<=l[x]&&r[x]<=R)tg[x]+=val,sm[x]+=(r[x]-l[x]+1)*val;else{
int M=(l[x]+r[x])>>1; if(L<=M)add(ch[x][0],L,R,val); if(M<R)add(ch[x][1],L,R,val);
sm[x]=sm[ch[x][0]]+sm[ch[x][1]];
}
}
inline ll querysum(int x){ll q=0; while(x)q+=query(1,pos[top[x]],pos[x]),x=fa[top[x]]; return q;}
void init1(){ess=0; memset(g,0,sizeof(g));}
void init2(){dep[1]=fa[1]=0; dfs(1); sgs=0; buildchain(1,1); build(1,1,sgs);}
int n,m;
int main(){
//freopen("test.txt","r",stdin);
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%lld",&v[i][0]); init1();
inc(i,1,n-1){int a,b; scanf("%d%d",&a,&b); pe(a,b);} init2();
inc(i,1,m){
int opt,x;ll y; scanf("%d%d",&opt,&x);
if(opt==1)scanf("%lld",&y),add(1,pos[x],pos[x],y);
if(opt==2)scanf("%lld",&y),add(1,pos[x],mx[x],y);
if(opt==3)printf("%lld\n",querysum(x));
}
return 0;
}n点无根树，2类操作：将节点a到节点b路径上所有点都染成颜色c、询问节点a到节点b路径上的颜色段数量。
有点恶心的链剖，可以用包含区间颜色段数，左端点颜色，右端点颜色的结构体存储查询的结果。首先是线段树节点除了要保存区间颜色段数还要保存左右端点颜色，再者是查询的时候要注意合并区间：在线段树查询时，如果递归左端点，就左合并递归结果，如果右端点就右合并；在树链查询时，从下往上左合并查询结果，两段分开处理，当两段都查询完时将一段的结果中的左右端点颜色交换，然后合并。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200000
using namespace std;
struct e{int t,n;}; e es[maxn];int ess,g[maxn];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;}
int fa[maxn],sz[maxn],dep[maxn],pos[maxn],top[maxn],v[maxn][2],sgs;
int l[maxn*4],r[maxn*4],ch[maxn*4][2],ll[maxn*4],rr[maxn*4],sm[maxn*4],tg[maxn*4];
struct nd{
int sm,l,r;
void plusr(nd d){
sm=sm+d.sm+(r==d.l?-1:0); r=d.r;
}
void plusl(nd d){
sm=sm+d.sm+(d.r==l?-1:0); l=d.l;
}
};
void dfs(int x){
sz[x]=1; for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]){
dep[es[i].t]=dep[x]+1; fa[es[i].t]=x; dfs(es[i].t); sz[x]+=sz[es[i].t];
}
}
void buildchain(int x,int ps){
pos[x]=++sgs; top[x]=ps; v[sgs][1]=v[x][0]; int mx1,mx2=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]&&mx2<sz[es[i].t])mx2=sz[es[i].t],mx1=es[i].t;
if(mx2)buildchain(mx1,ps);
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]&&es[i].t!=mx1)buildchain(es[i].t,es[i].t);
}
int lca(int x,int y){
for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x,y);
return dep[x]<dep[y]?x:y;
}
void update(int x){
if(!x)return; if(!ch[x][0]&&!ch[x][1])sm[x]=0;
sm[x]=sm[ch[x][0]]+sm[ch[x][1]]+(rr[ch[x][0]]==ll[ch[x][1]]?-1:0);
ll[x]=ll[ch[x][0]]; rr[x]=rr[ch[x][1]];
}
void pushdown(int x){
if(!x||tg[x]==-1)return; int lc=ch[x][0],rc=ch[x][1];
if(lc)sm[lc]=1,ll[lc]=rr[lc]=tg[x],tg[lc]=tg[x];
if(rc)sm[rc]=1,ll[rc]=rr[rc]=tg[x],tg[rc]=tg[x]; tg[x]=-1;
}
void build(int x,int L,int R){
if(L==R)l[x]=r[x]=L,ch[x][0]=ch[x][1]=0,ll[x]=rr[x]=v[L][1],tg[x]=-1,sm[x]=1;else{
int M=(L+R)>>1; ch[x][0]=x<<1; ch[x][1]=x<<1|1; l[x]=L; r[x]=R; tg[x]=-1;
build(ch[x][0],L,M); build(ch[x][1],M+1,R); update(x);
}
}
nd query(int x,int L,int R){
pushdown(x); if(L<=l[x]&&r[x]<=R)return (nd){sm[x],ll[x],rr[x]};
int M=(l[x]+r[x])>>1; nd q;
if(L<=M){
q=query(ch[x][0],L,R); if(M<R)q.plusr(query(ch[x][1],L,R));
}else if(M<R)q=(query(ch[x][1],L,R));
return q;
}
void change(int x,int L,int R,int col){
pushdown(x); if(L<=l[x]&&r[x]<=R){ll[x]=rr[x]=tg[x]=col,sm[x]=1; return;}
int M=(l[x]+r[x])>>1; if(L<=M)change(ch[x][0],L,R,col);
if(M<R)change(ch[x][1],L,R,col); update(x);
}
void init1(){ess=0; memset(g,0,sizeof(g));}
void init2(){fa[1]=0; dep[1]=0; dfs(1); sgs=0; buildchain(1,1); build(1,1,sgs);}
int querysum(int a,int b){
if(a==b)return query(1,pos[a],pos[b]).sm; int c=lca(a,b);
nd q1; bool f=0;
while(dep[top[a]]>dep[top[c]]){
if(!f)q1=query(1,pos[top[a]],pos[a]),f=1;else q1.plusl(query(1,pos[top[a]],pos[a]));
a=fa[top[a]];
}
if(!f)q1=query(1,pos[c],pos[a]),f=1;else q1.plusl(query(1,pos[c],pos[a]));
nd q2; f=0;
while(dep[top[b]]>dep[top[c]]){
if(! f)q2=query(1,pos[top[b]],pos[b]),f=1;else q2.plusl(query(1,pos[top[b]],pos[b]));
b=fa[top[b]];
}
if(! f)q2=query(1,pos[c],pos[b]),f=1;else q2.plusl(query(1,pos[c],pos[b]));
swap(q1.l,q1.r); q1.plusr(q2); return q1.sm;
}
void changecol(int a,int b,int col){
if(a==b){change(1,pos[a],pos[b],col);} int c=lca(a,b);
while(dep[top[a]]>dep[top[c]])change(1,pos[top[a]],pos[a],col),a=fa[top[a]];
change(1,pos[c],pos[a],col);
while(dep[top[b]]>dep[top[c]])change(1,pos[top[b]],pos[b],col),b=fa[top[b]];
change(1,pos[c],pos[b],col);
}
int n,m; char op[3];
int main(){
//freopen("test.txt","r",stdin);
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%d",&v[i][0]); init1();
inc(i,1,n-1){int a,b; scanf("%d%d",&a,&b); pe(a,b);} init2();
inc(i,1,m){
int a,b,c; scanf("%s%d%d",op,&a,&b);
if(op[0]=='Q'){printf("%d\n",querysum(a,b));}
if(op[0]=='C'){scanf("%d",&c); changecol(a,b,c);}
}
return 0;
}粉刷N条木板，每条木板M 个格子，每个格子要被刷成红色或蓝色。每次只能选择一条木板上一段连续的格子涂上一种颜色。 每个格子最多只能被粉刷一次。 如果只能粉刷 T 次，求最多能正确粉刷的格子数。未被粉刷或者颜色错的格子算错误粉刷。
非常容易想的DP，但是我竟然调了0.5h+一个中午，不是一般的弱啊~~首先f[i][j][k]表示现在考虑第i行第j列，正在第k次粉刷，转移就考虑不粉刷跳到f[i][j+1][k]或粉刷x格跳到f[i][j+x][k+1]+max(红色j+1到j+x,蓝色j+1到j+x)。我主要错在几个方面：一是奇怪的打错；二是当j==m时，如果不涂往下一行跳转，j要变成0而不是1，因为是从j+1开始涂的；三是dp数组里因为有一个“正在第k次粉刷”，所以第三维要开到2500而不是50。错得好傻逼啊QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,m,k; int w[60][60],b[60][60],f[60][60][3000]; char s[60];
int dfs(int x,int y,int z){
if(x==n+1||z==k+1)return 0; if(f[x][y][z]!=-1)return f[x][y][z];
f[x][y][z]=0; f[x][y][z]=max(f[x][y][z],dfs(y==m?x+1:x,y==m?0:y+1,z));
inc(i,y+1,m)
f[x][y][z]=max(f[x][y][z],dfs(x,i,z+1)+max(w[x][i]-w[x][y],b[x][i]-b[x][y]));
return f[x][y][z];
}
int main(){
scanf("%d%d%d",&n,&m,&k);
inc(i,1,n){
scanf("%s",s);
inc(j,0,m-1)if(s[j]=='1')w[i][j+1]=w[i][j]+1,b[i][j+1]=b[i][j];
else b[i][j+1]=b[i][j]+1,w[i][j+1]=w[i][j];
}
memset(f,-1,sizeof(f)); printf("%d",dfs(1,0,1));
return 0;
}此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。