BZOJ 4668: 冷战 LCT November 9, 2016 ###Description 1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。 美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。 Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。 Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有M 个操作，操作分为两类： • 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的; • 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0; 作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足 他的要求。 ###Input 第一行两个整数 N, M。 接下来 M 行，每行为 0 u v 或 1 u v 的形式。 数据是经过加密的，对于每次加边或询问，真正的 u, v 都等于读入的 u, v 异或上上一次询问的答案。一开始这个值为 0。 1 ≤ N, M ≤ 500000，解密后的 u, v 满足1 ≤ u, v ≤ N, u不等于v ###Output 对于每次 1 操作，输出 u, v 最早在加入哪条边后会联通，若到这个操 作时还没联通，则输出 0。 ###Sample Input 5 9 0 1 4 1 2 5 0 2 4 0 3 4 1 3 1 0 7 0 0 6 1 0 1 6 1 2 6 ###Sample Output ``` 0 3 5 ``` ###Solution 直接用LCT维护动态最小生成树就行了，虽然很暴力，但能AC ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> inline T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) const int N=1000001; struct node { node *c[2],*fa; int val,ma; bool rev; inline void rotate(bool f); inline void pushdown(); inline void pushup(); }s[N],_null,*null=&_null; inline void node::pushdown() { if(fa->c[0]==this||fa->c[1]==this) fa->pushdown(); if(rev) { rev=0; std::swap(c[0],c[1]); if(c[0]!=null)c[0]->rev=!c[0]->rev; if(c[1]!=null)c[1]->rev=!c[1]->rev; } } inline void node::rotate(bool f) { fa->c[f]=c[!f]; c[!f]=fa; fa=c[!f]->fa; if(c[!f]->fa->c[1]==c[!f]) c[!f]->fa->c[1]=this; else if(c[!f]->fa->c[0]==c[!f]) c[!f]->fa->c[0]=this; c[!f]->fa=this; c[!f]->c[f]->fa=c[!f]; c[!f]->pushup(); } inline void node::pushup() { ma=val; if(c[0]!=null)repr(ma,c[0]->ma); if(c[1]!=null)repr(ma,c[1]->ma); } inline void init(node *x,int v) { x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null; } inline void splay(node *a) { a->pushdown(); while(a->fa->c[0]==a||a->fa->c[1]==a) a->rotate(a==a->fa->c[1]); a->pushup(); } inline void access(node *a) { node *x=null; while(a!=null) { splay(a); a->c[1]=x; a->pushup(); x=a,a=a->fa; } } inline void movetoroot(node *x) { access(x); splay(x); x->rev=!x->rev; } inline void link(node *x,node *y) { movetoroot(x); x->fa=y; } inline void cut(node *x,node *y) { movetoroot(x); access(y); splay(y); x->fa=null; y->c[0]=null; y->pushup(); } inline void split(node *x,node *y) { movetoroot(x),access(y),splay(y); } inline node* findroot(node *x) { while(x->fa!=null) x=x->fa; return x; } int main() { int n,m,lstans=0,opt,x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) init(s+i,0); for(int i=1,ec=0;i<=m;i++) { scanf("%d%d%d",&opt,&x,&y); x^=lstans,y^=lstans; if(opt==0) { ec++; if(findroot(s+x)!=findroot(s+y)) { init(s+n+ec,ec); link(s+x,s+n+ec); link(s+y,s+n+ec); } } else { split(s+x,s+y); if(findroot(s+x)==s+y) lstans=s[y].ma; else lstans=0; printf("%d\n",lstans); } } } ```
BZOJ 3038: 上帝造题的七分钟2 November 9, 2016 ###Description XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 "第一分钟，X说，要有数列，于是便给定了一个正整数数列。 第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。" ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。 ###Input 第一行一个整数n，代表数列中数的个数。 第二行n个正整数，表示初始状态下数列中的数。 第三行一个整数m，表示有m次操作。 接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。 ###Output 对于询问操作，每行输出一个回答。 ###Sample Input 10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8 ###Sample Output 19 7 6 ###Solution 显然，一个数最多开根6次就会变成1 那么直接用线段树维护区间最大值，每次暴力修改即可 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} #define mp(a,b) std::make_pair(a,b) #define pb push_back int n,t=1; ll s[270000],ma[270000]; inline void up(int x) { s[x]=s[x<<1]+s[x<<1|1]; ma[x]=max(ma[x<<1],ma[x<<1|1]); } void modify(int x,int l,int r,int ql,int qr) { if(ma[x]<=1)return; if(x&t) { ma[x]=sqrt(ma[x]); s[x]=ma[x]; return; } int q=(l+r)>>1; if(ql<q)modify(x<<1,l,q,ql,min(q,qr)); if(qr>q)modify(x<<1|1,q,r,max(q,ql),qr); up(x); } int main() { int m; scanf("%d",&n); while(t<n+2)t<<=1; for(int i=1;i<=n;i++) scanf("%lld",ma+i+t),s[i+t]=ma[i+t]; for(int i=t-1;i;i--) up(i); scanf("%d",&m); while(m--) { int opt,x,y; scanf("%d%d%d",&opt,&x,&y); if(x>y)std::swap(x,y); if(opt==0) { modify(1,1,t,x,y+1); } else { x=x+t-1,y=y+t+1; ll ans=0; while(x^y^1) { if(~x&1)ans+=s[x^1]; if(y&1)ans+=s[y^1]; x>>=1,y>>=1; } printf("%lld\n",ans); } } } ```
BZOJ 3993: [SDOI2015]星际战争 October 26, 2016 ###Description 3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。 ###Input 第一行，两个整数，N、M。 第二行，N个整数，A1、A2…AN。 第三行，M个整数，B1、B2…BM。 接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。 ###Output 一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。 ###Sample Input 2 2 3 10 4 6 0 1 1 1 ###Sample Output 1.300000 ###HINT 战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值； 接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。 对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人 ###Solution 考虑二分答案，假设当前答案为time，那么从源点到Bi连容量为time*Bi的边，从Ai到汇点连容量为Ai的边，Bi,Ai间连inf，跑最大流即可 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} #define mp(a,b) std::make_pair(a,b) #define pb push_back const int N=200,M=3000; struct edge { int to,ne; double w; }e[M*2+2]; int p[N+1],em=2,dep[N+1],q[N],qe,fa[N+1]; double fl[N+1]; bool vis[N+1]; inline void add(int a,int b,double w) { e[em].to=b,e[em].w=w,e[em].ne=p[a],p[a]=em++; e[em].to=a,e[em].w=0,e[em].ne=p[b],p[b]=em++; } bool dfs(int s,int t) { if(s==t)return 1; for(int j=p[s];j;j=e[j].ne) if(!vis[e[j].to]&&e[j].w&&dep[e[j].to]>dep[s]) { vis[e[j].to]=1; fl[e[j].to]=min(e[j].w,fl[s]); fa[e[j].to]=j^1; if(dfs(e[j].to,t))return 1; } return 0; } inline double dinic(int s,int t) { double flow=0; while(1) { memset(dep,0,sizeof(dep)); q[0]=s,qe=1,dep[s]=1; for(int i=0;i^qe;i++) { for(int j=p[q[i]];j;j=e[j].ne) if(!dep[e[j].to]&&e[j].w) { dep[e[j].to]=dep[q[i]]+1; q[qe++]=e[j].to; } } if(!dep[t])break; while(1) { memset(vis,0,sizeof(vis)); fl[s]=0x7fffffff; dfs(s,t); if(!vis[t])break; flow+=fl[t]; for(int i=t;i!=s;i=e[fa[i]].to) e[fa[i]].w+=fl[t],e[fa[i]^1].w-=fl[t]; } } return flow; } int n,m,a[50],b[50],atk[50][50]; inline bool judge(double time) { int s=n+m,t=n+m+1; memset(p,0,sizeof(p)); em=2; double s1=0,s2; for(int i=0;i<m;i++) add(s,i,time*b[i]); for(int i=0;i<n;i++) add(i+m,t,a[i]),s1+=a[i]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(atk[i][j]) add(i,j+m,1e20); s2=dinic(s,t); if(abs(s1-s2)<1e-4)return 1;else return 0; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<m;i++) scanf("%d",b+i); for(int i=0;i<m;i++) for(int j=0;j<n;j++) { int k; scanf("%d",&k); atk[i][j]=k; } double l=0,r=1e4; while(r-l>1e-4) { if(judge((l+r)/2)) r=(l+r)/2; else l=(l+r)/2; } printf("%.6lf\n",r); } ```
BZOJ 2656: [Zjoi2012]数列(sequence) October 21, 2016 ###Description 小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式： ![1.jpg][1] 小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数N，小白则说出 的值，如果当N很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？ ###Input 输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行一个非负整数N。 ###Output 输出文件共包含T行。 第i行应包含一个不含多余前缀0的数，它的值应等于An(n为输入数据中第i+1行被读入的整数) ###Sample Input 3 1 3 10 ###Sample Output 1 2 3 ###HINT T<=20,N<=10^100 ###Solution 首先手推几个较小的值，可以发现当i为奇数时，递归算几次A(i)，会产生一些相同的值 那么直接记忆化就行了 至于证明，我也不会（从二进制的角度考虑的话，似乎大概就logn种值） ###Code ```c++ #include<cstdio> #include<cstring> #include<tr1/unordered_map> #define bas 1000000000 #define rep(a,b) if(a<(b))a=(b) struct hjd { int a[20],len; hjd(){ len=0; memset(a,0,sizeof(a)); } hjd(const hjd &x) { len=x.len; memset(a,0,sizeof(a)); for(int i=0;i<len;i++)a[i]=x.a[i]; } hjd(int x){ len=1; memset(a,0,sizeof(a)); a[0]=x; } bool operator ==(const hjd &x)const { if(len^x.len)return 0; for(int i=0;i<len;i++) if(a[i]^x.a[i])return 0; return 1; } inline void div2() { for(int i=len-1;i>0;i--) { if(a[i]&1)a[i-1]+=bas; a[i]>>=1; } a[0]>>=1; if(!a[len-1])len--; } inline void plus(const hjd &x) { rep(len,x.len); for(int i=0;i<len;i++) { a[i]+=x.a[i]; if(a[i]>bas)a[i]-=bas,a[i+1]++; } if(a[len])len++; } inline void print() { printf("%d",a[len-1]); for(int i=len-2;i>=0;i--) printf("%09d",a[i]); printf("\n"); } }; struct hjd_hash { size_t operator ()(const hjd &x)const//乱搞哈希 { int ans=0; for(int i=0;i<x.len;i++) ans^=x.a[i]; return ans; } }; std::tr1::unordered_map<hjd,hjd,hjd_hash> s; int aaa=0; hjd calc(hjd x) { hjd ret; if(!x.len)return ret; while((~x.a[0]&1)&&(x.len!=1||x.a[0]!=1))x.div2();//除去2 if(s.find(x)!=s.end())return s[x];//记忆化 hjd y=x; x.div2(); ret=calc(x); x.plus(1); ret.plus(calc(x));//计算A(x) s[y]=ret; return ret; } char buf[200]; int main() { s[1]=1; int T,n,uu[9],y=1; for(int i=0;i<9;i++) uu[i]=y,y*=10; scanf("%d",&T); while(T--) { s.clear(); s[1]=1; scanf("%s",buf); n=strlen(buf); hjd tmp; for(int i=n-1,j=0,ll=1;i>=0;i--)//输入，倒序 { tmp.len=ll; tmp.a[ll-1]+=(buf[i]-'0')*uu[j]; j++; if(j==9)j=0,ll++; } hjd t2=calc(tmp); if(!t2.len) printf("0\n"); else { t2.print(); } } } ``` [1]: /usr/uploads/2016/10/1978638953.jpg
BZOJ 3884: 上帝与集合的正确用法 October 16, 2016 ###Description 根据一些书上的记载，上帝的一次失败的创世经历是这样的： 第一天， 上帝创造了一个世界的基本元素，称做“元”。 第二天， 上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。 第三天， 上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。 第四天， 上帝创造了新的元素“γ”，“γ”被定义为“β”的集合。显然，一共会有16种不同的“γ”。 如果按照这样下去，上帝创造的第四种元素将会有65536种，第五种元素将会有2^65536种。这将会是一个天文数字。 然而，上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来，因此，日复一日，年复一年，他重复地创造着新的元素…… 然而不久，当上帝创造出最后一种元素“θ”时，他发现这世界的元素实在是太多了，以致于世界的容量不足，无法承受。因此在这一天，上帝毁灭了世界。 至今，上帝仍记得那次失败的创世经历，现在他想问问你，他最后一次创造的元素“θ”一共有多少种？ 上帝觉得这个数字可能过于巨大而无法表示出来，因此你只需要回答这个数对p取模后的值即可。 你可以认为上帝从“α”到“θ”一共创造了10^9次元素，或10^18次，或者干脆∞次。 一句话题意： ![1.png][1] ###Input 接下来T行，每行一个正整数p，代表你需要取模的值 ###Output T行，每行一个正整数，为答案对p取模后的值 ###Sample Input 3 2 3 6 ###Sample Output 0 1 4 ###HINT 对于100%的数据，T<=1000,p<=10^7 ###Solution 首先考虑欧拉定理，如果把这个数设为S，可以发现$$2^S=2^{S\ mod\ \phi(p)}$$ （当p是2的倍数时可以先除去所有2处理） 那么问题就转化为了求$$S\ mod\ \phi(p)$$，同样考虑，最终$$\phi(p)$$会等于1，直接处理即可 由于除了第一次，每次都会除去至少一个2，所以单次时间复杂度为$$O(logp)$$ ###Code ```c++ #include<cstdio> #define pmax 10000000 int prime[1000000],pm,fi[pmax+1],ans[pmax+1]; bool np[pmax+1],ga[pmax+1]; inline int pow(int a,long long t,int mod) { long long p=1,q=a,f=1; for(;f<=t;f<<=1) { if(f&t)p=p*q%mod; q=q*q%mod; } return p; } void exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return; } exgcd(b,a%b,y,x); y-=(a/b)*x; } inline int gen(int x,int t) { if(x==1)return 0; int a,b,p; if(x>t)exgcd(x,t,a,b);else exgcd(t,x,b,a); p=(long long)ans[x]*t%(x*t)*b%(x*t); if(p<0)p+=x*t; return p; } int getans(int x) { int t=1; while(~x&1)x>>=1,t<<=1; if(!ga[x])ga[x]=1,ans[x]=pow(2,1000ll*fi[x]+getans(fi[x]),x); return gen(x,t); } int main() { for(int i=2;i<=pmax;i++) { if(!np[i])prime[pm++]=i,fi[i]=i-1; for(int j=0;j<pm&&i*prime[j]<=pmax;j++) { np[i*prime[j]]=1; if(i%prime[j]) { fi[i*prime[j]]=fi[i]*(prime[j]-1); } else { fi[i*prime[j]]=fi[i]*prime[j]; break; } } } ga[1]=1,ans[1]=0; int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%d\n",getans(n)); } } ``` [1]: /usr/uploads/2016/10/774614809.png
Codeforces 723E.One-Way Reform October 3, 2016 ###Description There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads. The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it. 有一个无向图，n个点，m条边，无自环，无重边，现在要给每个边定方向，使得入度等于出度的点最多 ###Input The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input. Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland. The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities. It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200. Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one. ###Output For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it. In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once. ###Example input 2 5 5 2 1 4 5 2 3 1 3 3 5 7 2 3 7 4 2 output 3 1 3 3 5 5 4 3 2 2 1 3 2 4 3 7 ###Solution 将度数为奇的边间连上边，然后每次从任一点出发，走过一条边就定为走的方向，直到回到出发点。当所有边被定向后停止操作 那么对于度数为偶数的边，其入度一定等于出度，输出时去掉新加的边 ###Code ```c++ #include<bits/stdc++.h> struct edge { int to,ne; bool v; }e[50000]; int p[201],em=2,deg[201],n,m; bool ok[50000]; inline void add(int a,int b,bool v) { e[em].to=b,e[em].v=v,e[em].ne=p[a],p[a]=em++; } inline void solve() { scanf("%d%d",&n,&m); em=2; memset(p,0,n*4+4); memset(deg,0,n*4+4); while(m--) { int a,b; scanf("%d%d",&a,&b); add(a,b,1); add(b,a,1); deg[a]++; deg[b]++; } int lst=0,ans=n; for(int i=1;i<=n;i++) if(deg[i]&1) { if(lst) add(i,lst,0),add(lst,i,0),deg[i]++,deg[lst]++; else lst=i; ans--; } memset(ok,0,em); lst=1; printf("%d\n",ans); while(1) { while(lst<=n&&!deg[lst])lst++; if(lst>n)break; int k=lst; while(1) { bool f=1; for(int i=p[k];i;i=e[i].ne) if(!ok[i]) { f=0,ok[i]=1,ok[i^1]=1; if(e[i].v)printf("%d %d\n",k,e[i].to); deg[k]--; deg[e[i].to]--; k=e[i].to; break; } if(f)break; } } } int main() { int T; scanf("%d",&T); while(T--)solve(); } ```
BZOJ1041: [HAOI2008]圆上的整点 September 18, 2016 ###Description 求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。 ###Input 只有一个正整数n,n<=2000 000 000 ###Output 整点个数 ###Sample Input 4 ###Sample Output 4 ###Solution 只考虑x,y均大于0的情况 首先，暴力枚举肯定是O(n)的，T 对于勾股数有一个结论，就是如果$$x^2+y^2=n^2$$，那么$$x=t(a^2-b^2),y=2tab,n=t(a^2+b^2)$$ 那么我们可以枚举t，显然，只需要枚举n的每个质因数是否在t中就可以了（t中不需要有重复质因子） 枚举t后，需要将n/t写成a^2+b^2的形式，枚举a从1到sqrt(n/t)，时间复杂度O(sqrt(n/t)) 注意去掉重复的a,b，用map实现即可 总时间复杂度应该是根号乘log吧。。 <del>这显然不是正解，不过跑的还是挺快的</del> ###Code ```c++ #include<cstdio> #include<algorithm> #include<cmath> #include<map> std::map<int,bool> f; #define pmax 65536 int prime[10000],pm,x[10],y[10],cc,ans=0,n; bool np[pmax+1]; inline int solve(int nn) { int ans=0; for(int i=sqrt(nn);i>0;i--) { int a=nn-i*i,b=sqrt(nn-i*i); if(b*b==a) { int c=2*b*i,d=std::abs(b*b-i*i); if(!(c&&d))continue; if(!(f[c*(n/nn)]||f[d*(n/nn)])) { f[c*(n/nn)]=f[d*(n/nn)]=1; ans+=8; } } } return ans; } void dfs(int id,int nn) { if(id==cc) { ans+=solve(n/nn); return; } dfs(id+1,nn); dfs(id+1,nn*x[id]); } int main() { for(int i=2;i<=pmax;i++) { if(!np[i])prime[pm++]=i; for(int j=0;j<pm&&i*prime[j]<=pmax;j++) { np[i*prime[j]]=1; if(i%prime[j]==0)break; } } int m; scanf("%d",&n); if(n==0) { printf("1\n"); return 0; } m=n; for(int i=0;i<pm;i++) if(n%prime[i]==0) { x[cc]=prime[i]; while(n%prime[i]==0)n/=prime[i],y[cc]++; cc++; } if(n>1)x[cc++]=n; n=m; dfs(0,1); printf("%d\n",ans+4); return 0; } ```
BZOJ 1798: [Ahoi2009]Seq 维护序列 September 15, 2016 ###Description 老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。 ###Input 第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。 ###Output 对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。 ###Sample Input 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7 ###Sample Output 2 35 8 ###Solution 很显然，这是一道线段树区间修改+区间查询的裸题，每个节点存两个tag，分别表示乘多少，加多少，对于加的操作直接处理，乘的操作两个tag都乘 ###Code ```c++ #include<cstdio> #define LL long long int seg[270000],t=1,f=0,t1[270000],t2[270000]={0},p,ys[270000]; bool tag[270000]; inline int se(int x) { if(tag[x]) return ((LL)seg[x]*t1[x]+(LL)t2[x]*ys[x])%p; else return seg[x]; } inline void pd(int x) { if(tag[x]) { t1[x<<1]=(LL)t1[x<<1]*t1[x]%p,t2[x<<1]=((LL)t2[x<<1]*t1[x]+t2[x])%p; t1[x<<1|1]=(LL)t1[x<<1|1]*t1[x]%p,t2[x<<1|1]=((LL)t2[x<<1|1]*t1[x]+t2[x])%p; tag[x<<1]=tag[x<<1|1]=1; seg[x]=se(x); tag[x]=0,t1[x]=1,t2[x]=0; } } inline void up(int x) { if(!tag[x])seg[x]=(se(x<<1)+se(x<<1|1))%p; } int main() { int n,m; scanf("%d%d",&n,&p); while(t<n+2)t<<=1,f++; for(int i=0;i<t+t;i++)t1[i]=1; for(int i=1;i<=n;i++) { scanf("%d",seg+i+t); ys[i+t]=1; } for(int i=t-1;i>0;i--)seg[i]=(seg[i<<1]+seg[i<<1|1])%p,ys[i]=ys[i<<1]+ys[i<<1|1]; scanf("%d",&m); while(m--) { int a,b,c,ff; scanf("%d",&ff); if(ff==3) { scanf("%d%d",&a,&b); int l=a+t-1,r=b+t+1,ll,rr; LL ans=0; for(int i=f;i>=0;i--) { ll=l>>i,rr=r>>i; if(i)pd(ll),pd(rr); if((ll^rr)>1) { if((ll&1)==0)ans+=se(ll^1); if((rr&1)==1)ans+=se(rr^1); } } printf("%d\n",(int)(ans%p)); } else if(ff==2) { scanf("%d%d%d",&a,&b,&c); int l=a+t-1,r=b+t+1,ll,rr; for(int i=f;i>=0;i--) { ll=l>>i,rr=r>>i; if(i)pd(ll),pd(rr); if((ll^rr)>1) { if((ll&1)==0)t2[ll^1]=(t2[ll^1]+c)%p,tag[ll^1]=1; if((rr&1)==1)t2[rr^1]=(t2[rr^1]+c)%p,tag[rr^1]=1; } } for(;l;l>>=1,r>>=1) up(l>>1),up(r>>1); } else { scanf("%d%d%d",&a,&b,&c); c%=p; int l=a+t-1,r=b+t+1,ll,rr; for(int i=f;i>=0;i--) { ll=l>>i,rr=r>>i; if(i)pd(ll),pd(rr); if((ll^rr)>1) { if((ll&1)==0)t1[ll^1]=(LL)t1[ll^1]*c%p,t2[ll^1]=(LL)t2[ll^1]*c%p,tag[ll^1]=1; if((rr&1)==1)t1[rr^1]=(LL)t1[rr^1]*c%p,t2[rr^1]=(LL)t2[rr^1]*c%p,tag[rr^1]=1; } } for(;l;l>>=1,r>>=1) up(l>>1),up(r>>1); } } return 0; } ``` 这个也可以当成zkw线段树区间修改的模板。。
BZOJ 1407: [Noi2002]Savage September 14, 2016 ###Description ![1407.jpg][1] ###Input 第1行为一个整数N(1<=N<=15)，即野人的数目。 第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。 (1<=Ci,Pi<=100, 0<=Li<=10^6) ###Output 仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。 ###Sample Input 3 1 3 4 2 7 3 3 2 1 ###Sample Output 6 ###Solution 枚举m，每次枚举两个野人，将他们的ci,pi相减，记为c,p，那么如果有一个k在他们的年龄范围内，且c+pk模m等于0，则这个m不能取，k的最小值可以用扩展欧几里得求出 预处理每两个野人的ci,pi之差，li的最小值，可以优化时间 ###Code ```c++ #include<cstdio> int n,c[15],p[15],l[15],c2[105],p2[105],l2[105],n2=0; inline int min(int a,int b) { if(a<b)return a;else return b; } inline int max(int a,int b) { if(a>b)return a;else return b; } int sol,gcd; void exgcd(int a,int b,int &x,int &y) { if(!b) { x=sol/a;y=0; gcd=a; return; } exgcd(b,a%b,y,x); y-=x*(a/b); } inline int safeexgcd(int a,int b,int &x,int &y) { if(a<b)exgcd(b,a,y,x);else exgcd(a,b,x,y); } int main() { int maxc=0; scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d%d%d",c+i,p+i,l+i),maxc=max(c[i],maxc); for(int i=0;i<n;i++) for(int j=0;j<i;j++) { c2[n2]=c[i]-c[j]; p2[n2]=p[i]-p[j]; l2[n2]=min(l[i],l[j]); n2++; } for(int i=maxc;1;i++) { bool flag=true; int x,y; for(int j=0;j<n2;j++) { sol=-c2[j]; safeexgcd(p2[j],i,x,y); if(p2[j]*x+i*y!=sol)continue; int tmp=i/gcd; x%=tmp; if(x<0)x+=tmp; if(x<=l2[j]) { flag=false; break; } } if(flag) { printf("%d\n",i); return 0; } } } ``` 另外随便写的代码就第4了 ![puh.png][2] [1]: /usr/uploads/2016/09/2556788862.jpg [2]: /usr/uploads/2016/09/909201119.png
BZOJ 1265: [AHOI2006]斐波卡契的兔子 September 13, 2016 ###Description 卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎a对兔子，接着在出生后的二个月又将生出b对兔子，在第三个月和以后每个月都会繁殖c对兔子。(a <= b <= c) 由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在m个月后有k对兔子，以便分给他们的好友，他的愿望是否能够实现呢？ [任务] 编写一个程序：从输入文件中读入输入信息；计算m个月后卡卡将有多少对兔子，设之为P；计算如果m个月后卡卡要拥有至少k对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为Q；将结果输出至输出文件。 ###Input 输入文件的第一行有4个正整数：a, b, c和m；而第二行则仅含一个正整数k。它们的含义见上文描述。 ###Output 你的程序将向输出文件输出两行，第一行是一个整数P而第二行是一个整数Q。 ###Sample Input 0 1 1 10 10000 ###Sample Output 89 113 ###HINT 0 <= a <= b <= c <= 100, 1 <= m <= 3 000, 1 <= k <= 10^6000 ###Solution 我们用x,y,z表示一个月、两个月、三个月及以上的兔子，那么每次x=ax+by+cz,y=x,z=y+z就可以求出p，而q就是k/p向上取整 k/p可以用p,2p,4p,...,(2^t)p去求 然而为什么AC的人这么少呢。。 ###Code ```c++ #include<bits/stdc++.h> #define gm 1000 #define cas 10000000 #define max2 20050 int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3; int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm]; char tmp[10000]; inline void print(int *x,int xl) { printf("%d",x[xl-1]); for(int i=xl-2;i>=0;i--)printf("%07d",x[i]); } inline int max(int a,int b) { if(a>b)return a;else return b; } inline void add(int *x,int *y,int &xl,int yl) { int ll=max(xl,yl); for(int i=0;i<ll;i++) { x[i]+=y[i]; if(x[i]>=cas)x[i]-=cas,x[i+1]++; } if(x[ll])xl=ll+1;else xl=ll; } inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl) { zl=max(xl,yl); z[0]=0; for(int i=0;i<zl;i++) { z[i]+=x[i]+y[i]; if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0; } if(z[zl])zl++; } inline void multo(int *x,int y,int *z,int xl,int &zl) { z[0]=0; for(int i=0;i<xl;i++) { z[i]+=x[i]*y; z[i+1]=z[i]/cas; z[i]%=cas; } if(z[xl])zl=xl+1;else zl=xl; } inline bool larger(int *x,int *y,int xl,int yl) { if(xl>yl)return true; if(xl<yl)return false; for(int i=max(xl,yl)-1;i>=0;i--) { if(x[i]>y[i])return true; if(x[i]<y[i])return false; } return false; } inline void dec(int *x,int *y,int &xl,int yl) { for(int i=0;i<xl;i++) { x[i]-=y[i]; while(x[i]<0)x[i]+=cas,x[i+1]--; } while(xl&&!x[xl-1])xl--; } int main() { al=1,bl=0,cl=0; a[0]=1; scanf("%d%d%d%d",&aa,&bb,&cc,&m); scanf("%s",tmp); int tml=strlen(tmp),tmp2=1; std::reverse(tmp,tmp+tml); kl=(tml+6)/7; for(int i=0;i<tml;i++) { if(i%7==0)tmp2=1; k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2; tmp2*=10; } for(int i=0;i<m;i++) { multo(a,aa,r1,al,l1); multo(b,bb,r2,bl,l2); multo(c,cc,r3,cl,l3); add(c,b,cl,bl); memcpy(b,a,al*4); bl=al; addto(r1,r2,a,l1,l2,al); add(a,r3,al,l3); } add(a,b,al,bl); add(a,c,al,cl); print(a,al); printf("\n"); memcpy(f[0],a,al*4); fl[0]=al; tf[0][0]=1; tfl[0]=1; ansl=0; int ma; for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++) { multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]); multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]); } for(int i=ma-1;i>=0;i--) { if(!larger(f[i],k,fl[i],kl)) { dec(k,f[i],kl,fl[i]); add(ans,tf[i],ansl,tfl[i]); } } if(kl) { rrt[0]=1; add(ans,rrt,ansl,1); } print(ans,ansl); printf("\n"); return 0; } ```