题解：广义斐波那契数列 矩阵乘法
#include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; LL n,A,B; inline LL read(){ char ch=getchar();LL x=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; return x*f; } struct maxtix{ int t[5][5]; }ans; maxtix maxtix_mul(maxtix a,maxtix b){ maxtix tmp; for(int i=1;i<=4;i++){ for(int j=1;j<=4;j++){ tmp.t[i][j]=0; for(int k=1;k<=4;k++){ tmp.t[i][j]=(tmp.t[i][j]%7+a.t[i][k]*b.t[k][j]%7)%7; } } } return tmp; } maxtix maxtix_mul(maxtix a,LL b){ maxtix ret=a;b--; while(b){ if(b&1)ret=maxtix_mul(ret,a); a=maxtix_mul(a,a); b>>=1; } return ret; } int main(){ freopen("attack.in","r",stdin); freopen("attack.out","w",stdout); A=read();B=read();n=read(); A%=7;B%=7; if(n<=1000000){ LL f1=1,f2=1,f3; for(int i=3;i<=n;i++){ f3=(A*f2+B*f1)%7; f1=f2;f2=f3; } printf("%lld ",f2); fclose(stdin);fclose(stdout); return 0; } ans.t[1][1]=0;ans.t[1][2]=B;ans.t[2][1]=1;ans.t[2][2]=A; ans=maxtix_mul(ans,n-2); printf("%d ",(ans.t[1][2]+ans.t[2][2])%7); fclose(stdin);fclose(stdout); return 0; }
#include <cstdio> #include <iostream> #include <algorithm> #include <set> #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 20006 int a[Max], s[Max]; std :: string data; std :: set <std :: string> lis; int main (int argc, char *argv[]) { // freopen ("tb.txt", "w", stdout); int T, x, y, N, C, r ; rg int i; for (x = 1; x <= 12; ++ x) { for (y = 1; y <= x; ++ y) { N = x + y; data.resize (N); C = 0, r = 0; printf ("%d %d ", x, y); if (y == 0) { puts ("1.000000"); continue; } if (x == 0) { puts ("0.000000"); continue; } if (y > x) { puts ("0.000000"); continue; } for (i = 1; i <= x; ++ i) a[i] = 0; for (i = x + 1; i <= N; ++ i) a[i] = 1; do { // for (i = 0; i < N; ++ i) data[i] = a[i + 1] - '0'; // if (lis.count (data)) continue; // else lis.insert (data); s[N + 1] = 0; for (i = N; i >= 1; -- i) { s[i] = s[i + 1] + a[i]; if (s[i] > (N - i + 1) - s[i]) { ++ r; break; } } ++ C; } while (std :: next_permutation (a + 1, a + 1 + N)); printf ("%.6lf ", (C - r) * 1.0 / C); // puts (""); } } return 0; }
打表找规律 n相同m不同时是等差数列。
注意特判
#include<iostream> #include<cstdio> using namespace std; int t,n,m; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); if(n<m){puts("0.000000");continue;} printf("%.6lf ",1.0-m/(n+1.0)); } }
题解：
暴力40
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #define N 20009 using namespace std; queue<int>q; int n,m,sumedge; int head[N]; int sum_col,tim,top; int instack[N],Stack[N],bel[N],low[N],dfn[N],ans[N]; int sumEDge,hed[N],d[N],vis[N],dis[N],cnt[N],po[N]; struct Edge{ int x,y,z,nxt; Edge(int x=0,int y=0,int z=0,int nxt=0): x(x),y(y),z(z),nxt(nxt){} }edge[(N*10)<<1]; void add(int x,int y,int z){ edge[++sumedge]=Edge(x,y,z,head[x]); head[x]=sumedge; } struct EDge{ int x,y,z,nxt; EDge(int x=0,int y=0,int z=0,int nxt=0): x(x),y(y),z(z),nxt(nxt){} }e[N<<1]; void add_(int x,int y,int z){ e[++sumEDge]=EDge(x,y,z,hed[x]); hed[x]=sumEDge; } inline int read(){ char ch=getchar();int x=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; return x*f; } void tarjian(int x,int fa){ low[x]=dfn[x]=++tim; instack[x]=true;Stack[++top]=x; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; // if(v==fa)continue; if(instack[v]&&v!=fa){ low[x]=min(low[x],dfn[v]); }else if(dfn[v]==0){ tarjian(v,x); low[x]=min(low[x],low[v]); } } if(low[x]==dfn[x]){ sum_col++; while(Stack[top+1]!=x){ bel[Stack[top]]=sum_col; instack[Stack[top]]=false; top--; } } } void spfa(int s){ memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); while(!q.empty())q.pop(); dis[s]=0;vis[s]=true;q.push(s); while(!q.empty()){ int now=q.front();q.pop();vis[now]=false; for(int i=hed[now];i;i=e[i].nxt){ int v=e[i].y; if(dis[v]>dis[now]+e[i].z){ dis[v]=dis[now]+e[i].z; ans[s]=max(ans[s],dis[v]); if(vis[v]==0){ vis[v]=true;q.push(v); } } } } } int main(){ // freopen("prize.in","r",stdin); // freopen("prize.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } tarjian(1,0); // cout<<sum_col<<endl; for(int x=1;x<=n;x++){ for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; if(bel[v]!=bel[x]&&(po[bel[v]]==0||po[bel[x]]==0)){ cnt[bel[x]]++;cnt[bel[v]]++;po[bel[v]]=true;po[bel[x]]=true; add_(bel[v],bel[x],edge[i].z);add_(bel[x],bel[v],edge[i].z); d[bel[x]]++;d[bel[v]]++; } } } for(int i=1;i<=sum_col;i++)spfa(i); for(int i=1;i<=n;i++)printf("%d ",ans[bel[i]]); // fclose(stdin);fclose(stdout); return 0; }
缩点后就是一棵树 ，某个点到树直径的两端距离最大值就是答案
边没判重一直死循环，我觉得重边没关系呀，保险还是判重吧。
#include<cstdio> #include<cstring> #include<map> #include<iostream> #include<algorithm> #define N 20010 using namespace std; map<int,int>ma[N]; int n,m; int sumedge,head[N]; int top,tim,sumcol; int bel[N],Stack[N],instack[N],dfn[N],low[N]; int sume,hed[N]; int maxn,t,d1,d2,dis1[N],dis2[N]; struct Edge{ int x,y,z,nxt; Edge(int x=0,int y=0,int z=0,int nxt=0): x(x),y(y),z(z),nxt(nxt){} }edge[(N*10)<<1]; struct EDGE{ int x,y,z,nxt; EDGE(int x=0,int y=0,int z=0,int nxt=0): x(x),y(y),z(z),nxt(nxt){} }e[(N*10)<<1]; void add(int x,int y,int z){ edge[++sumedge]=Edge(x,y,z,head[x]); head[x]=sumedge; } void add_(int x,int y,int z){ e[++sume]=EDGE(x,y,z,hed[x]); hed[x]=sume; } void tarjian(int x,int fa){ low[x]=dfn[x]=++tim; Stack[++top]=x;instack[x]=true; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; if(instack[v]&&v!=fa)low[x]=min(low[x],dfn[v]); else if(!dfn[v]){ tarjian(v,x); low[x]=min(low[x],low[v]); } } if(low[x]==dfn[x]){ sumcol++; while(Stack[top+1]!=x){ bel[Stack[top]]=sumcol; instack[Stack[top]]=false; top--; } } } void dfs(int x,int fa){ for(int i=hed[x];i;i=e[i].nxt){ int v=e[i].y; if(v==fa)continue; dis1[v]=dis1[x]+e[i].z; if(dis1[v]>maxn)maxn=dis1[v],t=v; dfs(v,x); } } void dfs_(int x,int fa){ for(int i=hed[x];i;i=e[i].nxt){ int v=e[i].y; if(v==fa)continue; dis2[v]=dis2[x]+e[i].z; dfs_(v,x); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } for(int i=1;i<=n;i++)if(!dfn[i])tarjian(i,-1); for(int x=1;x<=n;x++){ for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; if(bel[x]!=bel[v]) if(ma[bel[x]].find(bel[v])==ma[bel[x]].end()){ ma[bel[x]][bel[v]]=1; ma[bel[v]][bel[x]]=1; add_(bel[x],bel[v],edge[i].z); add_(bel[v],bel[x],edge[i].z); } } } dfs(1,-1); d1=t;memset(dis1,0,sizeof(dis1));maxn=0; dfs(d1,-1); d2=t; dfs_(d2,-1); for(int i=1;i<=n;i++)printf("%d ",max(dis1[bel[i]],dis2[bel[i]])); return 0; }