Jan.6th
注：黑粗体为超链接
看一眼就知道是DP对不对（其实我看了标签）
f[i]表示离根距离为i的点的个数,a[j]表示输入树上每个点距离为j的儿子的个数
然后$f[i]=\sum_{j=1}^{100}f_{i-j}*a_j$
因为x≤10^9所以显然我们需要矩乘来优化到$log_{2}x$
然后对于x≤100直接输出$\sum_{i=0}^{x}f[x]$ x＞100的就矩乘一下好了
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define MOD 1000000007 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int f[105],a[105],n,x,c[105][105],b[105][105],d[105][105]; void Pow(int cs){ if (cs==1){memcpy(c,b,sizeof b);return;} Pow(cs/2); Rep(i,1,101) Rep(j,1,101) Rep(k,1,101) (d[i][j]+=1ll*c[i][k]*c[k][j]%MOD)%=MOD; memcpy(c,d,sizeof c);memset(d,0,sizeof d); if (cs%2){ Rep(i,1,101) Rep(j,1,101) Rep(k,1,101) (d[i][j]+=1ll*c[i][k]*b[k][j]%MOD)%=MOD; memcpy(c,d,sizeof c);memset(d,0,sizeof d); } } int main(){ n=IN(),x=IN(); Rep(i,1,n){int v=IN();a[v]++;} f[0]=f[101]=1; Rep(i,1,100){ Rep(j,1,i) (f[i]+=1ll*f[i-j]*a[j]%MOD)%=MOD; (f[101]+=f[i])%=MOD; } if (x<=100){ int Ans=0; Rep(i,0,x) (Ans+=f[i])%=MOD; printf("%d\n",Ans); return 0; } memset(b,0,sizeof b); Rep(i,1,99) b[i][i+1]=1; Rep(i,1,100) b[100][i]=b[101][i]=a[101-i]; b[101][101]=1; Pow(x-100); int Ans=0; Rep(i,1,101) (Ans+=1ll*f[i]*c[101][i]%MOD)%=MOD; printf("%d\n",Ans); } |
SB模拟看着办
先把-1特判掉
把鬼到达的时间按照先后排序
然后每次贪心在每只鬼来之前的最后能放蜡烛的时间放蜡烛就行
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define ZERO 305 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } bool lt[610]; int m,t,r,a[305],b[1005]; int main(){ m=IN(),t=IN(),r=IN(); if (t<r){ if (!m) puts("0");else puts("-1"); return 0; } Rep(i,1,m) a[i]=IN()+ZERO; sort(a+1,a+m+1); int Ans=0; Rep(i,1,m){ while (b[a[i]]<r){ int pos=a[i]-1; while (lt[pos]) pos--; Rep(i,pos+1,pos+t) b[i]++; lt[pos]=1;Ans++; } } printf("%d\n",Ans); } |
欧拉路径 对于每个字符串 把它前两个到后两个连一条边
然后跑欧拉路就行 注意要删边优化 不然会被卡到$n^2$
其实我这个优化有点萎……然而能过就是好代码
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int in[3900],out[3900],st,n,Ans[200005],cnta,cnt; char s[5]; int head[3900],to[200005],next[200005]; bool use[200005]; void AddEdge(int u,int v){ to[cnt]=v;next[cnt]=head[u];use[cnt]=0;head[u]=cnt++; } char solve(int v){ if (v<10) return v+'0'; else if (v<36) return v-10+'A'; return v-36+'a'; } void DFS(int u){ for (int i=head[u];~i;i=next[i]){ if (use[i]) continue;use[i]=1; head[u]=next[i]; DFS(to[i]); Ans[++cnta]=to[i]; if (to[i]==u) return; } } int main(){ n=IN(); cnt=0; memset(head,-1,sizeof head); Rep(i,1,n){ gets(s); Rep(j,0,2){ if (isdigit(s[j])) s[j]=s[j]-'0'; else if (s[j]<='Z') s[j]=s[j]-'A'+10; else s[j]=s[j]-'a'+36; } int from=s[0]*62+s[1]; st=from; int to=s[1]*62+s[2]; out[from]++;in[to]++; AddEdge(from,to); } int inb=0,oub=0; Rep(i,0,62*62-1){ if (out[i]-in[i]==1){ st=i;oub++; } else if (in[i]-out[i]==1) inb++; else if (in[i]!=out[i]) inb=2; } if (inb>=2||inb!=oub) return puts("NO"),0; DFS(st); if (cnta<n) return puts("NO"),0; puts("YES"); printf("%c%c",solve(st/62),solve(st%62)); Per(i,cnta,1) printf("%c",solve(Ans[i]%62)); } |
——————————————————————————————
评论 (0)
