/2016/12/ 个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ /archives/159/ 2016-12-26T15:09:00+08:00 ###Description 给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。 对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1 /archives/158/ 2016-12-26T10:48:00+08:00 ###Description 菩萨为行，福慧双修，智人得果，不忘其本。 ——唐朠立《大慈恩寺三藏法师传》 有才而知进退，福慧双修，这才难得。 ——乌雅氏 如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有N块区域，M条小路，两块区域之间可通过小路连接起来。现在甄嬛站在1号区域，而她需要在御花园中绕一绕，且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近，因此她最后还是要回到1号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。 ###Input 第一行仅2个正整数n,m，意义如题。 接下来m行每行4个正整数s,t,v,w，其中s,t为小路所连接的两个区域的编号，v为甄嬛从s到t所需的时间，w为甄嬛从t到s所需的时间。数据保证无重边。 ###Output 仅一行，为甄嬛回到1号区域所需的最短时间，若方案不存在，则输出-1 ###Sample Input 3 3 1 2 2 3 2 3 1 4 3 1 5 2 ###Sample Output 8 ###Solution 一条合法路径一定是1->a->...->b->1这样的 考虑a和b一定有至少一个二进制位不同 所以按二进制分组，每次新建一个源点和汇点，分别连向某位为1和0的点，然后跑最短路 ###Code ```c++ #include #define mp(a,b) std::make_pair(a,b) int n,p[40001],dis[40001]; bool vis[40001]; std::priority_queueq; struct edge { int to,ne,w; }e[200001]; inline void add(int i,int a,int b,int w) { e[i].to=b,e[i].ne=p[a],e[i].w=w,p[a]=i; } inline void yjq(int andv,int anda,int &ans) { memset(dis,0x7f,sizeof(dis)); memset(vis,0,sizeof(vis)); for(int j=p[1];j;j=e[j].ne) if((e[j].to&andv)==anda) q.push(mp(dis[e[j].to]=e[j].w,e[j].to)); while(!q.empty()) { int k=q.top().second;q.pop(); if(vis[k])continue; vis[k]=1; for(int j=p[k];j;j=e[j].ne) if(e[j].to==1) { if((k&andv)!=anda&&ans>dis[k]+e[j].w)ans=std::min(ans,dis[k]+e[j].w); } else if(dis[e[j].to]>dis[k]+e[j].w) { q.push(mp(dis[e[j].to]=dis[k]+e[j].w,e[j].to)); } } } int main() { int m; scanf("%d%d",&n,&m); for(int i=0;i /archives/156/ 2016-12-20T09:03:00+08:00 ###Description 农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？ 聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为： 1 1 2 3 5 8 13 21 34 … 栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 … 给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。 ###Input 输入一行，包含三个正整数n, k, p。 ###Output 输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。 ###Sample Input 6 7 100 ###Sample Output 7 ###Solution 按模k余数写出数列，则为 1,1,...,a,0, a,a,...,b,0, b,b,...,c,0, ... 这个数列最后有可能每一排首项循环，也有可能不再出现0 每次求a的逆元，则其在fib数列中首次出现位置就是a后面下一个0的位置，如果没有0特判 ###Code ```c++ #include typedef long long ll; #define fo0(i,n) for(int i=0,i##end=n;i=s[tt].len;n-=s[tt++].len)r*=s[tt].x; return r*pow((mat){0,1,0,1,1,0,0,0,1},n); } int main() { scanf("%lld%d%d",&n,&k,&p); for(int i=3;;i++) { f[i]=f[i-1]+f[i-2]; if(f[i]>=k)f[i]-=k; if(!pos[f[i]])pos[f[i]]=i; if(f[i]==1&&f[i-1]==0)break; } int ns=1,sc=1; for(;!p2[ns];sc++) { s[sc].st=ns; p2[ns]=sc; int t1,t2; exgcd(k,ns,t1,t2); if(t2 /archives/154/ 2016-12-16T23:38:00+08:00 ###Description 给出正整数N（可能有前导0），请求出N!最右非零的数位的值。 ###Input 第一行一个数T表示数据组数 下接T行每行一个数N表示一组数据 ###Output 对于每组数据，输出一行一个数表示这组数据的答案 ###Sample Input 2 5 4 ###Sample Output 2 4 ###Solution 随便lucas一下就好了，然而懒得写高精，就用了python，于是实力rank last ###Code ```python T=int(raw_input()) for I in range(T): n=int(raw_input());t=n;a=0;b=0;c=1 while t>0:t/=2;a+=t while n>0:c=c*[1,1,2,1,4,4,4,3,4,1][n%10]%5;n/=5;b+=n a=a-b+1 if a>1:a=0 t=3 while b>0: if b&1:c=c*t%5 t=t*t%5 b/=2 print (a*5+c*6)%10 ``` /archives/149/ 2016-12-16T15:59:00+08:00 ###Description 小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1=k)return kth(s[a].lc,s[b].lc,l,f,k); return kth(s[a].rc,s[b].rc,f+1,r,k-t); } int root[N+1]; } int n,m,q; namespace t1 { int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1]; struct edge { int to,ne; }e[N /archives/97/ 2016-12-11T14:51:00+08:00 [传送门][1] [传送门][2] [传送门][3] 题目大意：单点加，矩阵查询 直接上kdtree就好了，定期暴力重构 1176题代码： ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} template T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) namespace kd { const int D=2,inf=1000000000; char dnow; struct point { int d[D],val; int operator[](int x){return d[x];} }; inline bool operator /archives/96/ 2016-12-05T13:02:00+08:00 ###Description 采药人的药田是一个树状结构，每条路径上都种植着同种药材。 采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。 采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。 ###Input 第1行包含一个整数N。 接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。 ###Output 输出符合采药人要求的路径数目。 ###Sample Input 7 1 2 0 3 1 1 2 4 0 5 2 0 6 3 1 5 7 1 ###Sample Output 1 ###HINT 对于100%的数据，N ≤ 100,000。 ###Solution 点分治，边权为0变成-1，dfs时记前缀和，休息站就判之前有没有出现过该权值，注意处理根节点 ###Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template 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 sqr(x) ((x)*(x)) int n,p[100001],em=1,sz[100001],ro,nro,apr[200000],cnt[200000][2]; ll ans; bool vis[100001]; struct edge { int to,ne,w; }e[200000]; inline void add(int a,int b,int w) { e[em].to=b,e[em].ne=p[a],e[em].w=w,p[a]=em++; } void dfs1(int x,int fa) { sz[x]=1; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs1(e[i].to,x),sz[x]+=sz[e[i].to]; } void dfs2(int x,int fa) { bool ok=sz[ro]sz[ro])ok=0; } if(ok)nro=x; } void dfs3(int x,int fa,int len) { if(len) { if(apr[len+n]) ans+=cnt[n-len][0]; else ans+=cnt[n-len][1]; } else { if(apr[len+n]) ans+=cnt[n][0]+1; else ans+=cnt[n][0]; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs3(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs4(int x,int fa,int len) { if(len) { if(apr[len+n]) cnt[n+len][0]++,cnt[n+len][1]++; else cnt[n+len][0]++; } else { cnt[n][0]++; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs4(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs5(int x,int fa,int len) { cnt[n+len][0]=cnt[n+len][1]=0; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs5(e[i].to,x,len+e[i].w); } void solve(int x) { dfs1(x,0); ro=x; dfs2(x,0); vis[nro]=1; for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])dfs3(e[i].to,0,e[i].w),dfs4(e[i].to,0,e[i].w); dfs5(nro,0,0); for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])solve(e[i].to); } int main() { scanf("%d",&n); for(int i=1;i /archives/90/ 2016-12-01T20:46:00+08:00 ###Description 敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有一台人形兵器，攻击力为ATK。战斗看作回合制， 每回合进程如下： ·1 我方选择对方某台人形兵器并攻击，令其护甲值减少ATK，若护甲值