备战蓝桥杯---刷杂题2

显然我们直接看前一半，然后我们按照斜行看，我们发现斜行是递增的，而同一行从左向右也是递增的，因此我们可以直接二分，同时我们发现对称轴的数为Ck,2k.

我们从16斜行枚举即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL C(int a,int b){LL res=1;for(int i=a,j=1;j<=b;i--,j++){res=res*i/j;if(res>n) return res;}return res;
}
bool check(int k){LL l=k*2,r=n;if(l>r) return 0;while(l<r){LL mid=l+r>>1;if(C(mid,k)>=n) r=mid;else l=mid+1;}if(C(r,k)!=n) return 0;cout<<(r+1)*r/2+k+1;return 1;
}
int main(){cin>>n;for(int k=16;;k--){if(check(k)){break;}}
}

2.spfa的本质（妙）

我们令f[i][j]表示在i步以内可以生成j作物的方法的集合，我们记录其最小时间，答案就是f[n-1][t]，对于初始值，f[0][xi]=0，对于f[i][j]，我们可以看看j的生成方式即可，即f[i][j]=min(f[i][j],max(f[i-1][x],f[i-1][y])),复杂度为(n-1)k,我们加个spfa思想优化，j是由x,y更新的，只有x,y更新j才可能更新，

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=200010;
int n,m;
int h[N],e[M],w[N],target[M],ne[M],idx;
int dis[N];
queue<int> q;
bool st[N];
void add(int a,int b,int c){e[idx]=b,target[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(){while(q.size()){int x=q.front();q.pop();st[x]=0;for(int i=h[x];i!=-1;i=ne[i]){int y=e[i],z=target[i];if(dis[z]>max(dis[x],dis[y])+max(w[x],w[y])){dis[z]=max(dis[x],dis[y])+max(w[x],w[y]);if(!st[z]){q.push(z);st[z]=1;}}}}
}
int main(){int k,T;cin>>n>>m>>k>>T;memset(h,-1,sizeof(h));for(int i=1;i<=n;i++) scanf("%d",&w[i]);memset(dis,0x3f,sizeof(dis));while(m--){int x;scanf("%d",&x);dis[x]=0;q.push(x);st[x]=1;}while(k--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}spfa();cout<<dis[T];
}

3.欧拉函数：

下面是数学推导：

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;
}
LL phi(LL m){LL res=m;for(LL i=2;i<=m/i;i++){if(m%i==0){while(m%i==0) m/=i;res=res/i*(i-1);}}if(m>1) res=res/m*(m-1);return res;
}
int main(){int T;cin>>T;while(T--){LL a,m;cin>>a>>m;LL d=gcd(a,m);cout<<phi(m/d)<<endl;}
}