#include#include#include#define OJ_AC 0 #define OJ_WA 1 bool dcmp(double x, double y) { return fabs(x-y) <= fabs(y*0.05); } char *daStr; void diff(double R, double Wa) { FILE *out = fopen("diff.out", "a+");//错误详情文件，a+是append追加方式 fprintf(out, "====================%s\n", daStr); fprintf(out, "Right : %lf\n", R); fprintf(out, "--------------------\n"); fprintf(out, "Your : %lf\n", Wa); fprintf(out, "====================\n"); fclose(out); } int main(int argc, char* argv[]){ FILE *fo, *fu, *fi; double a, b; daStr = strrchr(argv[1], '/');//测试点文件名 fi = fopen(argv[1], "r");//测试点输入文件 in fo ...继续阅读 (39)

RT.#include#include#include#include#includeusing namespace std; #define OJ_AC 0 #define OJ_WA 1 #define OJ_PE 5 #define eps 1e-6 double out[1010],ans[1010]; int main(int argc,char*argv[]){ FILE*fin,*fans,*fout; fin=fopen(argv[1],"r"); fans=fopen(argv[2],"r"); fout=fopen(argv[3],"r"); int n,i,j; fscanf(fin,"%d",&n;); for(i=1;i<=n;++i) fscanf(fans,"%lf",&ans;[i]); for(i=1;i<=n;++i) fscanf(fout,"%lf",&out;[i]); int ok=0; for(i=1;i<=n;++i){ if(fabs(ans[i])<=7;++i) p*=_p; int score=int(p); if(score!=5) return OJ_WA; return OJ_AC; } ...继续阅读 (46)

题解:思路非常朴素了吧...令数值最大值为$mx$,则可以做到$O(mxlnmx)$.然后就是狗血的常数优化了.代码:#include#include#include#include#include#includeusing namespace std; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return *S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int a[100010],c[1000010],d[1000010]; int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #en ...继续阅读 (57)

题解:首先我们用Fib贪心的找出一组解.假如我们利用二进制存储得到的那组解.例如15=13+2就是(从小到大)010001,分别代表1,2,3,5,8,13.由于我们知道由于Fib数列的性质,001等价于110.所以我们需要知道找到的那组解一共能够变换出多少方案.我们依次考虑得到的那组解中的每个1,令$f[i][0]$表示第$i$个一在变换后的方案中是$0$的方案数,$f[i][1]$同理.我们首先观察001变换出110的性质,我们不难发现只能变换出这样的形式:1->110->11010即如果有$k$个空位,则有$\lfloor\frac{k}{2}\rfloor$种方案,知道了这些就不难dp了.详情见代码.代码:#include#include#include#include#include#includeusing namespace std; typedef long long ll; ll f[90][2]; ll fib[90]; int ins[90],cnt; int main(){ ll n; cin>>n; int i,j; for(fib[1]=1,fib[2]=2,i=3;i<=88;++i) fib[i]=fib[i-1]+fib[i-2]; for(i=88;i>=1;--i) if(n>=fib[i]) n-=fib[ins[+ ...继续阅读 (56)

题解:首先暴力连边匹配肯定是不行的...由于$200$以内的质数仅有$46$个,我们构造三类点$ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$分别表示参数1能被$p_1$整除,参数2能被$p_2$整除,剩下的依此类推.然后对于左侧的点向符合条件的中间点连边.对于右侧的点从符合条件的中间点连边.这样做事实上是边分组,很显然是正确的.直接用dinic玩就行了.代码:#include#include#include#include#include#include#includeusing namespace std; #define inf 0x3f3f3f3f struct Solver{ static const int V=100010; static const int E=3000010; int head[V],next[E],flow[E],end[E],ind,d[V]; inline void reset(){ memset(head,-1,sizeof head); ind=0; } inline void addedge(int a,int b,int f){ int q=ind++; end[q]=b; ...继续阅读 (88)

题解:首先预处理出$l_i$表示第$i$个数左侧比第$i$个数大的个数,$r_i$右侧同理.首先脑补出我们应该将序列排成先单调不降,后单调不增的形式.我们从大到小将数插入序列,考虑插入某个数,比这个数大的已经全部插入完毕了,由于排成那种形式,我们只能将这个数放在当前序列的头或尾.若放在开头,则带来$l_i$的逆序对;否则带来$r_i$的逆序对.显然每个数之间都是独立的,我们直接贪心就行了.时间复杂度$O(nlogn)$.代码:#include#include#include#include#includeusing namespace std; typedef long long ll; #define N 300010 int n,_n,a[N],b[N]; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc ...继续阅读 (95)

题解:(我这个大傻叉连这题都不会做了)首先肯定是转移了...我们单独考虑每个球,变化的概率都是$\frac{1}{m}$.于是令$f_i$表示编号为$i$的球的个数,考虑一次操作$f_i$的变化.考虑单个标号为$i$的球对$f_i$的影响:$\frac{1}{m}\times{0}+(1-\frac{1}{m})\times{1}$考虑单个标号为$i-1$的球对$f_i$的影响:$\frac{1}{m}\times{1}+(1-\frac{1}{m})\times{0}$然后我们就搞出了转移矩阵.有意思的是,这是一个循环矩阵!也就是说,从第二行开始,每一行都是上一行右移一位得到的.显而易见,循环矩阵的乘积依然是循环矩阵.所以我们只要暴力算出第一行就行了,所以可以$O(n^2)$暴力,也可以利用FFT优化至$O(nlogn)$.这样的话就能做这道题目了.代码:#include#include#include#include#includeusing namespace std; typedef double f2; #define N 1010 int n,m,k,a[N]; struct Vector{ f2 line[N],row[N]; inline void operator*=(const Vector&B;){ static f2 ...继续阅读 (42)

题解:我们单独考虑每个格子,如果这个格子在一次染色中不被染色的概率为$p$,则这个格子在$k$次染色中被染色的概率就是$1-p^k$.对于每个格子如何求$p$:看着代码自己脑补一下吧= =代码:#include#include#include#include#include#include#includeusing namespace std; typedef double f2; typedef long long ll; ll calc(int n,int m){ return(ll)n*m*n*m; } ll C[1010][1010]; int main(){ int k,w,h; cin>>k>>w>>h; ll total; f2 ans=0; for(int i=0;i<=w;++i) for(int j=0;j<=h;++j) C[i][j]=calc(i,j); for(int i=1;i<=w;++i){ for(int j=1;j<=h;++j){ total=0; total-=C[i-1][j-1]+C[i-1][h-j]+C[w-i][j-1]+C[w-i][h-j]; ...继续阅读 (38)

题解:考虑任意一个串都是两个前缀之差.如果这个串要满足$num(J)=num(O)=num(I)$,那么两个前缀$num(J),num(O),num(I)$的相对大小关系必须是相同的.我们对于每个前缀记下$num(J)-num(O),num(J)-num(I)$,然后利用map随便搞搞就行了.代码:#include#include#include#include#include#includeusing namespace std; typedef pairpii; #define mp make_pair #define N 200010 char s[N]; mapM; int main(){ int n; scanf("%d",&n;); scanf("%s",s+1); M[mp(0,0)]=0; int J=0,O=0,I=0,ans=0; for(int i=1;i<=n;++i){ if(s[i]=='J') ++J; if(s[i]=='O') ++O; if(s[i]=='I') ++I; if(M.count(mp(J-O,J-I))) ...继续阅读 (133)

题解:考虑三个点在树上的形态:(1)成一条链(其实就是中心是三个点中的一个点)(2)存在一个唯一中心连接三个点，且中心到三个点的路径除了中心之外不相交(定义自己脑补一下吧...)显然只有在(2)情况下,并且唯一中心到三个点的路径长度相等才能满足条件.我们直接枚举唯一中心,以其为根做有根树,则三个点必须分布在不同的子树中,且深度相同.这个就很容易搞了,看代码搞搞就行了.代码:#include#include#include#include#includeusing namespace std; typedef long long ll; #define N 5010 int head[N],next[N<<1],end[N<<1]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q++; } inline void make(int a,int b){ addedge(a,b); addedge(b,a); } int sum1[N]; ll sum2[N]; struct Array{ int a[N],t[N],tclock; inline int operator[](int x){ ...继续阅读 (40)

题解:首先如果对于一条边的两个端点均满足$>k$,则显然可以缩到一起变成一个点.然后对于剩下的边,我们需要添加若干条使得不出现环,因为如果出现了环肯定有$\leq{k}$的点在环上.我们可以按任意顺序添加,因为最后图的形态是固定的.所以直接并查集水过就可以.代码(非常蠢):#include#include#include#include#includeusing namespace std; #define N 1000010 #define M 2000010 struct Edge{ int a,b; Edge(){} Edge(int _a,int _b):a(_a),b(_b){ if(a>b) swap(a,b); } bool operator<(const Edge&B;)const{ return a>B.a; } }E[M]; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) ...继续阅读 (50)

题解:首先枚举$k$,那我们需要知道给定$k$,最少进行多少次操作.显然应该从小到大进行扫描,考虑当前位置$i$,若颜色不对,则反转$[i,i+k-1]$.然后再判定剩下的位置颜色对不对.这个过程可以利用单调队列轻松实现,详情见代码.代码:#include#include#include#include#includeusing namespace std; #define N 5010 bool a[N]; int q[N],fr,ta; int main(){ int n; scanf("%d",&n;); int i,j; char s[10]; for(i=1;i<=n;++i){ scanf("%s",s); a[i]=(s[0]=='F'); } int ans=0x3f3f3f3f,temp,k; for(i=1;i<=n;++i){ fr=ta=0; for(temp=0,j=1;j+i-1<=n;++j){ while(fr!=ta&&q;[fr]+i-1<=n;++j){ while(fr!=ta&&q;[fr]+i-1<<<" "< ...继续阅读 (40)

题目大意:自己看.题解:利用AC自动机顺序扫描.在AC自动机上的每个终止节点上记录串的长度.每当发现完全匹配到某一个串,就将当前状态回退[串的长度]那么多,回到那个节点继续.实在不懂的就看代码吧.代码:#include#include#include#include#include#includeusing namespace std; #define N 100010 char s1[N],s2[N]; int tr[N][26],cnt,fail[N],len[N]; bool end[N],del[N]; int stack[N],top,ins[N]; int main(){ scanf("%s",s1+1); int n=strlen(s1+1),i,j,m,_n; scanf("%d",&m;); int p; while(m--){ scanf("%s",s2+1); _n=strlen(s2+1); for(p=0,i=1;i<=_n;++i){ if(!tr[p][s2[i]-'a']) tr[p][s2[i]-'a']=++cnt; p=tr[p][s2[i]-'a']; } ...继续阅读 (33)

题目大意:(1)给定一个排列,问排列的序号.(2)给定一个序号,要求构造出给定序号的排列.题解:首先要知道怎么得出排列的序号.假如序列的长度为$n$,且第$i$个元素为$P_i$.则序号为:$\sum_{i=1}^{n}(n-i)!\sum_{j=i+1}^{n}[P_i>P_j]$这样的话可以$O(n^2)$算出排列的序号.构造序列的话也是一个道理,我是暴力的,没管复杂度...代码:#include#include#include#include#include#includeusing namespace std; typedef unsigned long long llu; int a[21],ans[21]; llu fac[21]; bool ok[21]; int main(){ int n,Q,i,j; char s[10]; cin>>n>>Q; llu x; for(fac[0]=i=1;i<=20;++i) fac[i]=fac[i-1]*i; int temp; while(Q--){ scanf("%s",s); if(s[0]=='P'){ cin>>x; --x; for(i=1;i<=n;++i) a[i]=x/fac[n-i],x-=a[i]*fac[n-i]; memset(ok,1, ...继续阅读 (32)

题目大意:最大生成树裸题.题解:Kruskal,$O(mlogm)$.代码:#include#include#include#include#includeusing namespace std; #define N 1010 #define M 100010 int r[N]; inline int find(int x){ int q=x,rq; for(;x!=r[x];x=r[x]); for(;q!=x;rq=r[q],r[q]=x,q=rq); return x; } struct Edge{ int u,v,l; Edge(){} Edge(int _u,int _v,int _l):u(_u),v(_v),l(_l){} bool operator<(const Edge&B;)const{ return l>B.l; } }E[M]; int main(){ int n,m,i,j; scanf("%d%d",&n;,&m;); for(i=1;i<=m;++i) scanf("%d%d%d",&E;[i].u,&E;[i].v,&E;[i].l); sort(E+1,E+m+1); int ans=0,cnt=0; ...继续阅读 (41)

意料之外的事情,居然NOI之后还没有滚粗...其实这才是最大的侥幸吧...我回忆起北大夏令营之后的我的心情,和现在的心情比较,真是一个天上,一个地下啊.所以我以后做的每一道题目,都不会像前段时间那样仓促,而是尽量写详细的题解,贴上代码.(当然是因为这些都是水题了啊!) ...继续阅读 (38)

最近的状态非常爆炸,几乎所有题都不能想出第一步QwQ.只能尽可能调整一下状态了.bzoj3489如果允许离线显然是水题.强制在线的话我们用主席树维护就行啦.bzoj1019令$f[i][j]$表示一开始在柱子$i$上有$j$个盘子,要移动到另外一个的最少步数.令$g[i][j]$表示一开始在柱子$i$上有$j$个盘子,在最小字典序意义下会移动到哪一个柱子.转移就非常显然了.bzoj1021我又不会做的水题...不同的钞票之间显然是独立的.令$f[i][j][k]$表示前$i$种钞票,第一个人有$j$元,第二个人有$k$元的最小钞票数,简单dp即可.bzoj1935将询问转化为前缀相减并离线,离散化后利用树状数组维护即可.bzoj2024把所有男生女生都按照身高从小到大排序,令$g[i][j]$表示排名前$i$小的女生参与匹配,且至少存在$j$对女大于男的方案数.令$num[i]$表示比排名第$i$的女生身高矮的男生数目.那么有转移:$g[i][j]=g[i-1][j]+g[i-1][j-1]\times{(num[i]-(j-1))}$.然后这样会有重复的方案,所以要容斥一下,然后就行了. ...继续阅读 (30)

弱省胡策Round6 A大意:首先注意到就是求出一个最大的循环串集合,使得集合中的任意两个循环串在模$a$意义下相等或者模$b$意义下相等.思路:首先找出哪些循环串是模$a$相等的,哪些循环串是模$b$相等的,然后找出模$a$相等的最大集合,再找出模$b$相等的最大集合,取个最大值.利用反证法易证这样是对的.利用hash很容易实现,时间$O(n)$.#include#include#include#include#includeusing namespace std; typedef long long ll; typedef pairpii; #define N 1000010 int A[N<<1],B[N<<1]; struct Hash_system{ static const int mod1=1000000007; static const int mod2=1000000009; static const int seed1=200019; static const int seed2=13131; int f1[N<<1],f2[N<<1],pow1[N<<1],pow2[N<<1]; inline void init(){ int i; for(pow1[0]=1,i=1;i<=2000000;++i) pow1[i]=(ll)po ...继续阅读 (24)

BZOJ2709二分+最短路,主要是精度问题,可以根据我的程序调整精度.#include#include#include#include#include#includeusing namespace std; typedef double f2; int head[10010],next[100010],end[100010],ind; f2 len[100010]; inline void reset(){ ind=0; memset(head,0,sizeof head); } inline void addedge(int a,int b,f2 l){ int q=++ind; end[q]=b; next[q]=head[a]; head[a]=q; len[q]=l; } bool map[110][110]; char s[110]; int lab[110][110],id; static const int dx[]={-1,1,0,0}; static const int dy[]={0,0,-1,1}; f2 d[10010]; queueq; bool inq[10010]; inline void spfa(int s){ int i,j; for(i=1;i<=id ...继续阅读 (17)

A.沼跃鱼的FFFBy wyfcyx来自BZOJ2891,但是上一次AC已经是近两年前,而且多位神犇都是利用随机很多次这种方法过的.其实这个题很简单.注意到$n\leq{6}$,显然要在这个上面做文章啦.令$f[i][j]$表示在前$i$个Po姐参与匹配的情况下,大爷匹配状态的集合为$j$这种情况发生的概率.何谓匹配状态:就是指一个二进制数,第$i-1$位以0/1表示第$i$个大爷是否在匹配中.考虑第$i+1$个Po姐,我们可以$O(2^n)$枚举她可以和哪些大爷进行匹配,那么现在的集合会变成什么样子呢?对于原集合的所有状态,以及现在新增的若干匹配边,若这个状态加上这条匹配边得到的新状态不在原集合中,我们就将这个新状态加入集合.于是这样的集合数明面看来是$O(2^{2^n})$的,看起来直接要爆炸了.其实很容易注意到每个大爷只会在第一次出现在匹配边时造成影响,那么有用的信息只有最终所有匹配边中大爷的并集,以及加入大爷的顺序.于是可用的集合数最多只有$O(n!2^n)$这么多.这样算一下感觉很爆炸,但其实还有很多重复,最坏只有$4000$个状态.这样简单的dp就可以了.状态数为$O(n!2^nm)$,转移数为$O(2^n)$,总时间复杂度为$O(n!4^nm)$.当然需要一些简单的预处理,不过这里就不说了.http://ch.ezoj.tk/record/45061B.沼跃鱼的Mus ...继续阅读 (18)

思路:本题的模型转换十分巧妙:仅考虑空格移动,注意到空格移动的路径事实上是黑白相间,且不自交的路径.这样我们黑白染色变成二分图,转化为二分图上的博弈问题.显然的性质是从一个点出发先手必胜当且仅当这个点是二分图最大匹配的必须点.若这个点没有匹配点,先手必败;否则将这个点的匹配点的匹配点设为0,删除这个点,并从这个点的匹配点开始增广.若能够增广,显然这个点不是必须点.这样只需增广\(O(K)\)次,时间复杂度\(O(KN^4)\).(另外本沙茶终于明白匈牙利算法是怎回事了...)#include#include#include#include#include#define N 41 int ano[N*N]; bool changed[N*N]; int head[N*N],next[N*N<<2],end[N*N<<2]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q++; } inline void make(int a,int b){ addedge(a,b); addedge(b,a); } bool del[N*N]; inline bool dfs(int x){ if(del[x]) ...继续阅读 (42)

思路:对于每次询问,暴力枚举所有编辑距离为1的串,然后用Trie判断存不存在并判重.妈呀这是\(O(10000*26*20*20)=10^8\),居然也能过.其实用Hash感觉就好多了.有没有更好的方法?目前没想出来.#include#include#include#include#include#includeusing namespace std; int ch[200010][26],end[200010],vis[200010],cnt; char s[21],ss[22]; int tclock; inline bool judge(int len){ int p=0; for(int i=0;i1){ for(i=0;i<26;++j)if(j!=s[i]-'a'){ memcpy(ss,s,sizeof s),ss[i]='a'+j; re+=judge(len); } for(i=0;i<=len;++i)for(j=0;j<26;++j){ id=0; for(k=0;k ...继续阅读 (77)

思路:首先将颜色分段.令\(f[i][j]\)表示第\(i\)段到第\(j\)段全部清除最小的代价.转移一:\[f[i][j]=\min_{k=i}^{j-1}f[i][k]+f[k+1][j]\]转移二:\(i=j\),直接转移转移三:\(col[i]=col[j]\),\(f[i][j]=f[i+1][j-1]+blabla...\)可是这样是不一定对的.(做到这里在OJ上就可以AC了.)他不能处理三个离散的珠子合并的情况.比如1 2 2 1 3 3 1.正确答案应该是2.我们加一步判断,如果区间两端都是只有一个的话,尝试在区间中寻找同样颜色的,然后合并.由于数据问题,这样判断是会WA的.但是这应该是正确答案.(在OJ上可以AC的代码)#include#include#include#include#includeusing namespace std; #define N 510 int a[N],col[N],cnt[N],id; int f[N][N]; int main(){ int n;scanf("%d",&n;); register int i,j,k,p; for(i=1;i<=n;++i)scanf("%d",&a;[i]); for(i=1;i<=n;){ col[++id]=a[i],cnt[id]= ...继续阅读 (37)

思路:首先将图黑白二染色变成二分图.然后求出一组最大匹配.如果某个点不在匹配中,那么先手选择这个点.那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.最后总是后手无路可走.因此先手必胜.因此如果某个点不是最大匹配的必须点.就可以选择这个点.如何找出这个呢?在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)(注意总点数要开2W,我不知道为什么)#include#include#include#include#includeusing namespace std; #define INF ~0U>>1 struct Solver{ static const int V=20010; static const int E=V<<2; int head[V],next[E],end[E],flow[E],ind; int gap[V],d[V],stk[V],top,cur[V]; inline void reset(){ ind=top=0,memset(head ...继续阅读 (18)

思路:暴力枚举答案,然后将点分层,边总是从该层连向下一层.然后判断最大流是不是满足题意.具体连边看代码.#include#include#include#include#includeusing namespace std; #define INF ~0U>>1 struct Solver{ static const int V=50*100; static const int E=2450*100*2; int head[V],next[E],end[E],flow[E],ind; int d[V],gap[V],stk[V],top,cur[V]; inline void reset(){ ind=top=0,memset(head,-1,sizeof head); } inline void addedge(int a,int b,int f){ int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f; } inline void make(int a,int b,int f){ /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0 ...继续阅读 (37)

思路:AC自动机的Fail树有很多奇妙的性质.例如串\(a\)是串\(b\)在Fail树上的祖先,那么\(a\)在\(b\)中应该出现\(dep[b]-dep[a]\)次.(不过好像跟这题没什么关系)把Alice的\(n\)个字符串插入AC自动机.然后每插入一个修改串,都动态维护一下每个自动机中的节点,如果出现在修改串中,则该节点答案+1.我们用修改串在自动机上走,每走到一个节点,我们都想要这个节点在Fail树上到根的路径上的答案均+1.遗憾的是,这样有可能重复!利用树链的并.将所有要处理的节点按照dfs序排序,然后首先把它们到根的路径+1.随后将相邻两个节点的LCA到根的路径-1.非常科学.怎么加?树链剖分?等TLE吧.直接将标记累加在节点上,询问时就询问子树内的标记之和.这样只需用树状数组维护DFS序即可.可惜卡常数!用倍增LCA会超时.于是我们换用RMQlca,并用ZKW线段树维护.估计ST表预处理也会超时.反正总算还是水过去了.#include#include#include#include#include#include#include#includeusing namespace std; #define N 2002010 int ch[N][26],fail[N],ins[N],cnt; char s[N]; int head[N],next[N],en ...继续阅读 (80)

思路:首先发现如果根确定的话,我们要求的答案就是根和关键点们组成的虚树的边长之和的2倍减去根到所有关键点的距离最大值.这个应该不难理解.然后觉得虚树很难处理,就抛弃虚树,弄了一个繁琐至极的两遍dp.(这个我就不写是怎么dp的啦,大家应该都会.)然后看到某个题解说最上面说的那个东西bfs就行.如何呢?一个关键的性质:树上距离一个点最远的点必定是直径的一端!这个想想很显然.然后就简单了.下面是我的傻叉dp:#include#include#include#include#includeusing namespace std; #define INF 1ll<<59 #define N 500010 int head[N],next[N<<1],end[N<<1],len[N<<1]; inline void addedge(int a,int b,int c){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=c;} inline void make(int a,int b,int c){addedge(a,b,c),addedge(b,a,c);} bool c[N]; long long max_dis[N],cnt[N],total_dis[N]; inline void dp1(int x,in ...继续阅读 (72)

思路:首先有一个性质:当前的矩形必定可以被划分成两个子矩形.无脑dp.记录四个状态表示当前矩形的四条边是不是原来的大矩形的边.然后记忆化搜索即可.(要非常注意常数优化)#include#include#include#include#include#includeusing namespace std; #define INF 1ll<<60 #define N 310 long long f[2][2][2][2][N][N]; int n,m,k; inline long long calc(int w,int h,int a,int b,int c,int d){ if(w>h){ swap(w,h); int aa=c,bb=d,cc=b,dd=a; a=aa,b=bb,c=cc,d=dd; if(a>b)swap(a,b); if(c>d)swap(c,d); } if(f[a][b][c][d][w][h]!=-1)return f[a][b][c][d][w][h]; if(!a&&!b&&!c&&!d)return f[a][b][c][d][w][h]=INF; long long re=(long long)(w*h-k)*(w*h ...继续阅读 (44)

思路:首先不难想到排序后dp,可是这样就\(O(n^2)\)超时了.一开始想的是按照列从前往后做,然后给每一个之前的列维护一个单调队列.可是发现这样是\(O(m^3)\)的.我们可以注意到一条性质:由于\(a,b>0\)时,\((a+b)^2>a^2+b^2\),且价值均\(>0\),所以路径上相邻两个点形成的矩形中不能存在别的点.也就是说对于之前的每一列,只有最下面的才有用.我们在扫的时候顺便记录一下这个就好了.时间复杂度\(O(nm)\).#include#include#include#include#includeusing namespace std; #define N 200010 #define M 1010 struct Pos{ int x,y,lab; bool operator<(const Pos&B;)const{return x<=n;++i)scanf("%d%d",&P;[i].x,&P;[i].y),x[i]=P[i].x,y[i]=P[i].y,P[i].lab=i,scanf("%d",&w;[i]); sort(P+1,P+n+1); f[P[1].lab]=w[P[1].lab],g[1]=P[1].lab; for(i=2;i<=n;++i){ f[P[i].lab]=-1<<30; for(j=1;j<=P[i ...继续阅读 (55)

利用一下对偶原理建模什么的都非常裸,就放一下代码吧.#include#include#include#include#includeusing namespace std; typedef double f2; #define INF ~0U>>1 struct Solver{ static const int N=10010;//变量个数 static const int M=1010;//限制个数 int n,m; int B[M];//基变量集合 int NB[N];//非基变量集合 f2 c[N],v;//目标函数的各项系数以及常数 f2 A[M][N],b[N];//限制的系数 Solver(){} Solver(int _n,int _m):n(_n),m(_m){} void debug(){ puts("Function"); printf("Maximize "); for(int i=1;i<=n;++i){ if(i>1)putchar('+'); printf("%.2lfx_%d",c[i],NB[i]); } pr ...继续阅读 (32)