int n;nstruct arr{n ll a[10000];n ll &operator[](int i) {n if (i<-n) i=-n; if (i>n) i=n;n return a[5000+i];n }n}f;n//这个数组写法好评
Category Archives: DefaultCategory
Pygame 语法速记
变量声明
BZOJ 五月胡乱补题
【BZOJ 4806: 炮】同BZOJ 1801
n【BZOJ 3242: [Noi2013]快餐店】树形dp,要么最远点在同一颗树上(dp),要么在不同树上,此时答案=去掉任何一条边后形成的树的答案的最小值,我们枚举去掉的那条边。
n由于答案=s[i]-s[j]+dis[i]+dis[j],i,j可以分开考虑,也可以用线段树解决。
n【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题,每次沿边染max,注意最后如果颜色数超过k,则可以按(k+1)-k-…-1的简单路径
n【4879: [Lydsy2017年5月月赛]失控的数位板】只要把所有的点的最后一次涂色时间求出来就行了。
n【BZOJ 4894: 天赋】有向图生成树计数的基尔霍夫矩阵
n【BZOJ 3534: [Sdoi2014]重建】 变元矩阵-树定理,求所有生成树边权积的和。把度数改为连出的边权和,A[i][j]=−边权,A[i][i]=连出的边权和.
n【BZOJ 4031: [HEOI2015]小Z的房间】矩阵树定理,注意gauss消元辗转相除的写法
n【BZOJ 4837: [Lydsy2017年4月月赛]LRU算法】模拟
n【BZOJ 4596: [Shoi2016]黑暗前的幻想乡】矩阵树定理+容斥
n【BZOJ 3517: 翻硬币】
我的WordPress数据库穿越到异世界了怎么办,在线等
RT
n由于博主sb的没有续费Godaddy以及本机备份丢失(主要是这个原因),一些博客文章丢失了。
广西邀请赛 出题and题解
日记 算法发表于 2个月前 (08-27)21条评论
n正在传网盘…… 链接:http://pan.baidu.com/s/1kVsZwRP 密码:ag46 好拉
BZOJ 1001([BeiJing2006]狼抓兔子-最大流转对偶图最短路)
1001: [BeiJing2006]狼抓兔子
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 5779 Solved: 1297
[Submit][Status][Discuss]
Description

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.
Input
Output
Sample Input
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
Sample Output
#include<cstdlib> #include<cstdio> #include<iostream> #include<functional> #include<algorithm> #include<cstring> using namespace std; #define MAXN (999*999*2+2+10) #define MAXM (MAXN*3) #define For(i,n) for(int i=1;i<=n;i++) int n,m,N,M,s,t,pre[MAXN]={0},edge[MAXM],next[MAXM],weight[MAXM],size=0; int no(int i,int j,int k){return (i-1)*2*M+j*2-(k^1);} void addedge(int u,int v,int w) { edge[++size]=v; weight[size]=w; next[size]=pre[u]; pre[u]=size; } void addedge2(int u,int v){int w;scanf("%d",&w);addedge(u,v,w),addedge(v,u,w);} int q[MAXN*9],d[MAXN]; void SPFA() { memset(d,127,sizeof(d));d[s]=0; int head=1,tail=1; q[1]=s; while (head<=tail) { int now=q[head]; for (int p=pre[now];p;p=next[p]) { int &v=edge[p]; if (d[now]+weight[p]<d[v]) { d[v]=d[now]+weight[p]; q[++tail]=v; } } head++; } } int main() { // freopen("bzoj1001.in","r",stdin); scanf("%d%d",&n,&m); N=n-1,M=m-1; s=N*M*2+1;t=s+1; For(i,n) For(j,m-1) { if (i==1) addedge2(s,2*j); else if (i==n) addedge2(no(i-1,j,0),t); else addedge2(no(i,j,1),no(i-1,j,0)); } For(i,n-1) For(j,m) { if (j==1) addedge2(t,2*M*(i-1)+1); else if (j==m) addedge2(2*M*i,s); else addedge2(no(i,j-1,1),no(i,j,0)); } For(i,n-1) For(j,m-1) addedge2(no(i,j,0),no(i,j,1)); SPFA(); cout<<d[t]<<endl; return 0; }
BZOJ 3132(上帝造题的七分钟-树状数组求和+2D逆求和数组)
3132: 上帝造题的七分钟
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 46 Solved: 18
[Submit][Status][Discuss]
Description
“第一分钟,X说,要有矩阵,于是便有了一个里面写满了0的n×m矩阵。
第二分钟,L说,要能修改,于是便有了将左上角为(a,b),右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。
第三分钟,k说,要能查询,于是便有了求给定矩形区域内的全部数字和的操作。
第四分钟,彩虹喵说,要基于二叉树的数据结构,于是便有了数据范围。
第五分钟,和雪说,要有耐心,于是便有了时间限制。
第六分钟,吃钢琴男说,要省点事,于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。”
——《上帝造裸题的七分钟》
所以这个神圣的任务就交给你了。
Input
输入数据的第一行为X n m,代表矩阵大小为n×m。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作:
L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。
k a b c d —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。
请注意,k为小写。
Output
针对每个k操作,在单独的一行输出答案。
Sample Input
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3
Sample Output
HINT
对于100%的数据,1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, 1 ≤ delta ≤ 500,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。
Source
2D树状数组支持单点修改+求和(1,1)-(x,y)矩形
因此按照zkw的思路用逆求和数组做(就是把区间修改结构-用2个单点修改的逆求和数组d',{i*d'}代替,神思路)
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define MAXN (2050) int lowbit(int x){return x&(-x);} int n,m,x1,x2,y1,y2,delta; struct arr_tree { int b[MAXN][MAXN]; arr_tree(){memset(b,0,sizeof(b)); } void add(int x,int y,int c,bool b1,bool b2) { if (!x||!y||x>n||y>m) return; if (b1) c*=(x-1);if (b2) c*=(y-1);if (!c) return; for (int i=x;i<=n;i+=lowbit(i)) for (int j=y;j<=m;j+=lowbit(j)) b[i][j]+=c; } int qur(int x,int y) { if (!x||!y) return 0; int ans=0; for (int i=x;i;i-=lowbit(i)) for (int j=y;j;j-=lowbit(j)) ans+=b[i][j]; return ans; } void add(int x1,int y1,int x2,int y2,int c,bool b1,bool b2) { add(x2+1,y2+1,delta,b1,b2),add(x1,y1,delta,b1,b2); add(x1,y2+1,-delta,b1,b2),add(x2+1,y1,-delta,b1,b2); } }d,di,dj,dij; int Dsum(int x,int y) { return d.qur(x,y)*x*y+dij.qur(x,y)-di.qur(x,y)*y-dj.qur(x,y)*x; } int main() { scanf("X %d %d",&n,&m); char c; while (scanf("%c",&c)==1) { while (c^'L'&&c^'k') if (scanf("%c",&c)!=1) return 0; switch(c) { case 'L': scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta); if (x1>x2) swap(x1,x2),swap(y1,y2); d.add(x1,y1,x2,y2,delta,0,0),di.add(x1,y1,x2,y2,-delta,1,0); dj.add(x1,y1,x2,y2,-delta,0,1),dij.add(x1,y1,x2,y2,delta,1,1); break; default: scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if (x1>x2) swap(x1,x2),swap(y1,y2); printf("%dn",Dsum(x2,y2)+Dsum(x1-1,y1-1)-Dsum(x1-1,y2)-Dsum(x2,y1-1)); } } }
BZOJ 2111([ZJOI2010]Perm 排列计数-乘法逆元+完全二叉树模型+数列分数表示法)
2111: [ZJOI2010]Perm 排列计数
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 478 Solved: 283
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
HINT
100%的数据中,1 ≤ � N ≤ 106, P� ≤ 10^9,p是一个质数。
#include<cstdio> #include<cmath> #include<functional> #include<iostream> #include<algorithm> using namespace std; #define MAXN (1000000+1) #define eps (1e-9) int n,F; int exgcd(int a,int b,long long &x,long long &y){if (!b) {x=1,y=0;return a;}int ans=exgcd(b,a%b,x,y);long long z=x;x=y;y=z-(a/b)*y;return ans;} long long f[MAXN],g[MAXN],jc[MAXN]; long long mulinv(int b) { long long x,y; exgcd(b,F,x,y); // return ((-x)/F*F+F+x)%F; return (x+abs(x)/F*F+F)%F; } int main() { scanf("%d%d",&n,&F); f[0]=g[0]=f[1]=g[1]=1%F; jc[0]=jc[1]=1; for (int i=2;i<=n;i++) jc[i]=jc[i-1]*i%F; for(int i=2;i<=n;i++) { int dep=(int)(log(i)/log(2)+eps)+1; int l=(int)pow(2.0,dep-2)-1; // cout<<l<<' '<<(int)(eps+pow(2.0,dep-2))<<' '<<(i-1-2*l)<<' '; l+=min((i-1-2*l),(int)(eps+pow(2.0,dep-2))); int r=i-l-1; // cout<<i<<' '<<dep<<' '<<l<<' '<<r<<' '<<f[l]<<' '<<f[r]<<endl; f[i]=f[l]*f[r]%F*jc[i-1]%F; g[i]=g[l]*g[r]%F*jc[l]%F*jc[r]%F; } // cout<<f[n]<<' '<<g[n]<<endl; cout<<f[n]*mulinv(g[n])%F<<endl; return 0; }
上学路线(递归sap-不完全)
Problem 2 上学路线(route.cpp/c/pas)
【题目描述】
可可和卡卡家住马赛克市的东郊,每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。
马赛克市一共设有N个公交车站,不妨将它们编号为1…N的自然数,并认为可可和卡卡家住在1号汽车站附近,而他们学校在N号汽车站。市内有M条直达汽车路线,执行第i条路线的公交车往返于站点pi和qi之间,从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N)
两个人坐在电脑前,根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子,他想趁卡卡不备,在卡卡的输入数据中删去一些路线,从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci:删去路线的ci越大卡卡就越容易发现这个玩笑,可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。
马赛克市的公交网络十分发达,你可以认为任意两个车站间都可以通过直达或转车互相到达,当然如果在你提供的删除方案中,家和学校无法互相到达,那么则认为上学需要的最短为正无穷大:这显然是一个合法的方案。
【输入格式】
输入文件中第一行有两个正整数N和M,分别表示马赛克市公交车站和公交汽车路线的个数。以下M行,每行(第i行,总第(i+1)行)用四个正整数(之间由一个空格隔开)描述第i条路线:pi, qi, ti, ci;具体含义见上文描述。
【输出格式】
输出文件最多有两行。 第一行中仅有一个整数,表示从可可和卡卡家到学校需要的最短时间。第二行输出一个整数C,表示Ci之和
【样例输入】
6 7
1 21 3
2 61 5
1 31 1
3 41 1
4 61 1
5 61 2
1 51 4
【样例输出】
2
5
【数据范围】
2<=N<=500,1<=M<=124 750, 1<=ti, ci<=10 000
这题我用的是递归sap(),谁知道狂Wa。
大家用递归sap的时候想必经常会莫名NTR。
结论://dfs_sap()的Z正确性目前有待考证。。。
根据我的研究,经验总结如下:
1.退出条件:
-PS:有可能某次增广flow=0,但是改距离标号可以继续flow
-PS:有时候无限增广,输答案能看出上面的错误
2.修改距离标号:
-PS:距离标号最好直接+1,minj等手段极有可能造成≈没有距离标号优化的状况
3.dfs时的flow
-PS:一定要提前return,要不然改距离标号a~
4.重构图:
-PS:这样是质的差别,递归不卡时间?
5.唯一重点:
PS:实在不行时,去掉距离标号优化!另可T到死,不能WA到爆
6.用递归sap唯一的好处是省事……(什么你1分钟BFS_sap()?当我没说)
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<functional> #define MAXN (500+10) #define MAXM (124750+10) #define MAXCi (10000+10) #define INF (2139062143) #define For(i,n) for(int i=1;i<=n;i++) #define Forp(p,u) for (int p=pre[u];p;p=next[p]) using namespace std; int n,m,edge[2*MAXM],weight[2*MAXM],c[2*MAXM],next[2*MAXM],pre[MAXN],size=1; void addedge(int u,int v,int w,int w2) { edge[++size]=v; weight[size]=w; c[size]=w2; next[size]=pre[u]; pre[u]=size; } int d[MAXN],q[MAXN*8]; void spfa() { memset(d,127,sizeof(d)); d[1]=0; int head=1,tail=1;q[1]=1; while (head<=tail) { int &u=q[head]; Forp(p,u) { int &v=edge[p]; if (d[v]==INF||d[u]+weight[p]<d[v]) { q[++tail]=v;d[v]=d[u]+weight[p]; } } head++; } } int d2[MAXN],cnt[MAXN]; void spfa2() { memset(d2,127,sizeof(d2)); memset(cnt,0,sizeof(cnt)); d2[n]=0;cnt[0]=1; int head=1,tail=1;q[1]=n; while (head<=tail) { int &u=q[head]; Forp(p,u) { int &v=edge[p]; if (d[u]-weight[p]!=d[v]) continue; if (d2[v]==INF) { q[++tail]=v;d2[v]=d2[u]+1; cnt[d2[v]]++; } } head++; } } bool sap_T=1,b[2*MAXM]={0}; int sap(int u,int flow) { if (u==n) return flow; int tot=0,minj=INF; Forp(p,u) { int &v=edge[p]; /* if (d2[v]==INF) continue; if (!(d[u]+weight[p]==d[v]||d[u]-weight[p]==d[v])) continue; */ if (!b[p]) continue; if (c[p]>0&&d2[u]==d2[v]+1) { int w=sap(v,min(flow-tot,c[p])); c[p]-=w;c[p^1]+=w;tot+=w; if (flow==tot) return tot; }else if (c[p]) minj=min(minj,d2[v]); } if (--cnt[d2[u]]==0) { d2[1]=n,sap_T=0;/*return tot;*/ }//d2[1]=n+1; // if (minj^INF) cnt[d2[u]=minj+1]++; /* else*/ cnt[++d2[u]]++; return tot; } int main() { freopen("route.in","r",stdin); freopen("route.out","w",stdout); memset(pre,0,sizeof(pre)); scanf("%d%d",&n,&m); For(i,m) { int u,v,w1,w2; scanf("%d%d%d%d",&u,&v,&w1,&w2); addedge(u,v,w1,w2); addedge(v,u,w1,w2); } spfa(); // for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<endl; cout<<d[n]<<endl; int ans=0; spfa2(); int de_bug_1=0; For(i,n) Forp(p,i) { if (d[i]>d[edge[p]]) c[p]=0; //*0 // if (d2[i]!=INF&&d2[edge[p]]!=INF&&c[p]) cout<<i<<' '<<edge[p]<<endl,de_bug_1++; if (d[i]+weight[p]==d[edge[p]]) b[p]=b[p^1]=1,/*cout<<i<<' '<<edge[p]<<endl,*/de_bug_1++; } // cout<<de_bug_1<<endl; b[0]=1; For(i,n) Forp(p,i) { while (next[p]&&!b[next[p]]) next[p]=next[next[p]]; } while(/*sap_T*/1) { if (d2[1]>=n) break; int w=sap(1,INF); // if (!w) break; // cout<<ans<<' '<<d2[1]<<endl; ans+=w; } cout<<ans<<endl; return 0; }
BZOJ 3097(Hash Killer I-哈希%u64的不可行)
3097: Hash Killer I
Time Limit: 5 Sec Memory Limit: 128 MBSec Special Judge
Submit: 76 Solved: 34
[Submit][Status][Discuss]
Description
这天天气不错,hzhwcmhf神犇给VFleaKing出了一道题:
给你一个长度为N的字符串S,求有多少个不同的长度为L的子串。
子串的定义是S[l]、S[l + 1]、... S[r]这样连续的一段。
两个字符串被认为是不同的当且仅当某个位置上的字符不同。
VFleaKing一看觉得这不是Hash的裸题么!于是果断写了哈希 + 排序。
而hzhwcmhf神犇心里自然知道,这题就是后缀数组的height中 < L的个数 + 1,就是后缀自动机上代表的长度区间包含L的结点个数,就是后缀树深度为L的结点的数量。
但是hzhwcmhf神犇看了看VFleaKing的做法表示非常汗。于是想卡掉他。
VFleaKing使用的是字典序哈希,其代码大致如下:
u64 val = 0;
for (int i = 0; i < l; i++)
val = val * base + s[i] - 'a';
u64是无符号int64,范围是[0, 2^64)。VFleaKing让val自然溢出。
base是一个常量,VFleaKing会根据心情决定其值。
VFleaKing还求出来了base ^ l,即base的l次方,这样就能方便地求出所有长度为L的子串的哈希值。
然后VFleaKing给哈希值排序,去重,求出有多少个不同的哈希值,把这个数作为结果。
其算法的C++代码如下:
typedef unsigned long long u64;
const int MaxN = 100000;
inline int hash_handle(const char *s, const int &n, const int &l, const int &base)
{
u64 hash_pow_l = 1;
for (int i = 1; i <= l; i++)
hash_pow_l *= base;
int li_n = 0;
static u64 li[MaxN];
u64 val = 0;
for (int i = 0; i < l; i++)
val = val * base + s[i] - 'a';
li[li_n++] = val;
for (int i = l; i < n; i++)
{
val = val * base + s[i] - 'a';
val -= (s[i - l] - 'a') * hash_pow_l;
li[li_n++] = val;
}
sort(li, li + li_n);
li_n = unique(li, li + li_n) - li;
return li_n;
}
hzhwcmhf当然知道怎么卡啦!但是他想考考你。
Input
没有输入。
Output
你需要输出一组数据使得VFleaKing的代码WA掉。我们会使用Special Judge检查你的结果的正确性。
输出文件共两行。
第一行两个用空格隔开的数n、l。
第二行是一个长度为n的字符串。只能包含'a'~'z'。
需要保证1 <= n <= 10^5, 1 <= l <= n,
不符合以上格式会WA。
不要有多余字符,很可能导致你WA。
Sample Input
Sample Output
buaabuaa
(当然这个输出是会WA的)
HINT
orz 波兰人 & fotile96 & sillycross
这题要一定的数论知识(其实不要……)
如果s[1]=1 s[i]=s[i-1]+s[i-1].flip(1...size)
则有
strlen(s[i])=2^(i-1)
若设f[i]=hash(s[i])-(hash(!s[i]))=2^k * t (t是奇数)
则易证(把hash值有base带,慢慢算……)
f[i]=f[i-1]*(base^[2^(i-2)]-1)
∵2^i-1=(2^(i-1)-1)*(2^(i-1)+1),
所以k很大。
如果base是偶数,那么只要最高位不同,其它都相同让其溢出就行。
#include<cstdio> #include<iostream> #include<functional> #include<bitset> #include<string> using namespace std; #define MAXN (100000+10) int n,l; bitset<MAXN> s; int main() { n=MAXN-10; int bin=1; s[1]=1; for (int i=2;i<=13;i++,bin<<=1) { for(int j=bin+1;j<=bin*2;j++) s[j]=s[j-bin]^1; } cout<<n<<' '<<bin/2<<endl; for (int i=1;i<=bin;i++) { if (s[i]) cout<<'a'; else cout<<'b'; } cout<<'b'; for (int i=bin+2;i<=n;i++) cout<<'a'; cout<<endl; return 0; }