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
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; } ```
BZOJ 1009: [HNOI2008]GT考试 September 9, 2016 ###Description 阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0 ###Input 第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000 ###Output 阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果. ###Sample Input 4 3 100 111 ###Sample Output 81 ###Solution 我们把不吉利的数字用s表示，用f[i][j]表示n[i]匹配到s[j]的情况数，则可以用一个转移矩阵a通过f[i-1][j]求出f[i][j] a[i][j]表示在s中匹配了i位时，在后面添数，有多少种情况匹配到j位，也就是指s的前i位后面添数后最长的公共前后缀长度为j的情况数 kmp预处理，然后对于每个i，枚举添加的数，再仿照kmp进行处理，即可求出转移矩阵 矩阵快速幂优化就可以过了，时间复杂度$$O(logN*M^3)$$ ###Code ```c++ #include<cstdio> struct _matrix { int s[21][21],a,b; _matrix() { for(int i=0;i<21;i++) for(int j=0;j<21;j++) s[i][j]=0; } }temp; int mod; void mul(_matrix &x,_matrix y) { for(int i=0;i<x.a;i++) for(int j=0;j<y.b;j++) { temp.s[i][j]=0; for(int k=0;k<x.b;k++) temp.s[i][j]+=x.s[i][k]*y.s[k][j]; temp.s[i][j]%=mod; } temp.a=x.a; temp.b=y.b; x=temp; } int m[21],n,f[21]; int main() { int mm; scanf("%d%d%d",&n,&mm,&mod); char t[20]; scanf("%s",t); for(int i=0;i<mm;i++)m[i+1]=t[i]-48; f[1]=0; for(int i=2;i<=mm;i++) { int t=i-1; while(t!=0&&m[f[t]+1]!=m[i])t=f[t]; if(t==0) { if(m[1]==m[i]) f[i]=1; else f[i]=0; } else { f[i]=f[t]+1; } } _matrix a; a.a=mm+1; a.b=mm+1; a.s[0][0]=9,a.s[0][1]=1; for(int i=1;i<mm;i++) { for(int j=0;j<10;j++) { if(m[i+1]==j) { a.s[i][i+1]++; continue; } int t=i; while(t!=0&&m[f[t]+1]!=j)t=f[t]; if(t==0) { if(m[1]==j) a.s[i][t+1]++; else a.s[i][0]++; } else a.s[i][f[t]+1]++; } } _matrix b; b.a=1; b.b=mm+1; b.s[0][0]=9; b.s[0][1]=1; int ans=0,to=n-1,no=1; while(no<to) { if(to&no)mul(b,a); mul(a,a); no<<=1; } for(int i=0;i<mm;i++)ans+=b.s[0][i]; printf("%d\n",ans%mod); return 0; } ```
BZOJ 1089: [SCOI2003]严格n元树 September 8, 2016 ###Description 如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d （根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图： ![1.jpg][1] 给出n, d，编程数出深度为d的n元树数目。 ###Input 仅包含两个整数n, d(0 < n <= 32, 0 <= d <= 16) ###Output 仅包含一个数，即深度为d的n元树的数目。 ###Sample Input 【样例输入1】 2 2 【样例输入2】 2 3 【样例输入3】 3 5 ###Sample Output 【样例输出1】 3 【样例输出2】 21 【样例输出2】 58871587162270592645034001 ###Solution 我们用f(d)表示深度不大于d的n元树数目，则答案为f(d)-f(d-1) 当深度为d时，可以看做一棵深度为1的n元树，每个叶子节点向下都有d(n-1)种可能，再加上深度为0的情况，可得出f(d)=f(d-1)^n+1 ###Code ```c++ #include<cstdio> #include<memory.h> #include<cstring> #define maxnum 100 #define cas 1000000000 int a[maxnum],b[maxnum],t[maxnum],al=1,bl; inline void mul() { memset(t,0,(al+bl+1)*4); for(int i=0;i<al;i++) for(int j=0;j<bl;j++) { long long f=(long long)a[i]*b[j]; t[i+j]+=f%cas; if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++; t[i+j+1]+=f/cas; if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++; } if(t[al+bl-1])al=al+bl;else al=al+bl-1; memcpy(a,t,al*4); } inline void print(int *a) { printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n"); } int main() { int n,d; scanf("%d%d",&n,&d); a[0]=1; while(d--) { memcpy(b,a,al*4); bl=al; for(int i=1;i<n;i++)mul(); a[0]++; for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++; if(a[al])al++; } for(int i=0;i<bl;i++)a[i]-=b[i]; for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--; if(!a[al-1])al--; print(a); printf("\n"); return 0; } ``` [1]: /usr/uploads/2016/09/1813884886.jpg