原题链接：https://www.jisuanke.com/contest/2625?view=challenges
题意：给一个圆，Hana在圆(x0,y0,r)的底部，要走到Hinata（x,y)，要求Hana只能走圆的边界，且不能走圆的下半部分区域Y=y0以下非圆边界区域，要题目保证(x,y)在Y=y0区域，且在园外，求Hana到Hinata最小距离。 题解：两种情况，如果（x,y)是在1、2部分，答案就是弧(A,B)+直线BC；如果(x,y)在3部分，答案就是弧（ABE）+切线DE。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=100010; const double pi=acos(-1); int main() { int t; //printf("p:%.6f\n",pi); scanf("%d",&t); while(t--){ double x,y,r,x0,y0,ans; scanf("%lf%lf%lf",&x0,&y0,&r); scanf("%lf%lf",&x,&y); x-=x0;y-=y0; if(x>=r){ ans=pi*r/2+sqrt((x-r)*(x-r)+y*y); }else if(x<=-r){ ans=pi*r/2+sqrt((x+r)*(x+r)+y*y); } else{ double dis=sqrt(x*x+y*y); double len=sqrt((x*x+y*y)-r*r),du=r/dis; double ddu=(x>0?x:0-x)/dis; double dda=acos(ddu); double da=acos(du); ans=(pi/2+(dda-da))*r+len; } printf("%.4f\n",ans); } return 0; }题意：给一个带权图，每升一级，飞船飞行距离+d,飞行次数+e,升级费用为c,求飞船从1到n需要最小的升级次数。 题意：二分升级次数，每次根据最大飞行距离建图，跑bfs。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=100010; struct edge{ int v,nxt,w; }e[maxn],e2[maxn*2]; int head[maxn],tot; int n,m,c,d,ee; bool vis[maxn]; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v,int w) { e[tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++; } int head2[maxn],tot2; void init2() { memset(head2,-1,sizeof(head2)); tot2=0; } void addedge2(int u,int v) { e2[tot2].v=v; e2[tot2].nxt=head2[u]; head2[u]=tot2++; } struct node{ int id,deep; }cur,tmp; bool ok(int x) { int deep=x*ee,mx=x*d; init2(); for(int u=1;u<=n;u++){ for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v,w=e[i].w; if(w<=mx){ addedge2(u,v); addedge2(v,u); } } } queue<node> q; cur.id=1;cur.deep=0; q.push(cur); int u,v; memset(vis,0,sizeof(vis)); while(!q.empty()){ cur=q.front();q.pop(); u=cur.id; if(vis[u]) continue; vis[u]=1; if(u==n) return true; if(cur.deep>=deep) break;// for(int i=head2[u];~i;i=e2[i].nxt){ v=e2[i].v; if(vis[v]) continue; tmp.id=v;tmp.deep=cur.deep+1; q.push(tmp); } } return false; } int main() { while(~scanf("%d%d",&n,&m)){ scanf("%d%d%d",&c,&d,&ee); init(); int u,v,w,mx=-1; for(int i=0;i<m;i++){ scanf("%d%d%d",&u,&v,&w); mx=max(mx,w); addedge(u,v,w); } int l=1,r=max((n-1)/ee+1,mx/d+1),mid; int ans=-1; while(l<=r){// mid=(l+r)/2; if(ok(mid)){ ans=mid; r=mid-1; }else{ l=mid+1; } } if(ans==-1) printf("-1\n"); else printf("%lld\n",1LL*ans*c); } return 0; }给一个数组，能做两个变换， 1.将前后两部分交换，如果有中间元素，保持不动，如[1,2,3,4]->[3,4,1,2], [1,2,3,4,5]->[4,5,3,1,2] 2.将奇偶位置数交换，最后没有匹配的元素保留，如[1,2,3,4]->[2,1,4,3],[1,2,3,4,5]->[2,1,4,3,5] 求这个数组能得到多少排列。 题解：由于n只有10000，暴力模拟能过，但是这题有规律，找规律也能做。
#include <iostream> using namespace std; int ans[10005]; int num=0; int n,mid,x; bool judge() { bool flag=1; for(int j=1;j<=n&&flag;j++){ if(ans[j]!=j) flag=0; } return flag; } void dfs(bool type) { if(type==1){ if(n%2==0){ for(int j=1;j<=mid;j++) swap(ans[j],ans[j+mid]); if(judge()==0){ num++; dfs(0); } } else{ for(int j=1;j<=mid;j++) swap(ans[j],ans[j+mid+1]); if(judge()==0){ num++; dfs(0); } } } else{ if(n%2==0){ for(int j=2;j<=n;j+=2) swap(ans[j],ans[j-1]); if(judge()==0){ num++; dfs(1); } } else{ for(int j=2;j<=n-1;j+=2) swap(ans[j],ans[j-1]); if(judge()==0){ num++; dfs(1); } } } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>x; num=0; mid=n/2; for(int j=1;j<=n;j++) ans[j]=j; dfs(0); cout<<num+1<<endl; return 0; }给n个点，每个点有点权，m个对，每个队(a,b)代表a和b不能共在一个集合，求一个分配方案，使得分到的两个集合点权尽量接近，输出那个点权较大的集合的点权总和 题解：01背包，容量为V/2-tmp （充分利用好c[i]能整除100这个点，使得dp数组装的下） 因为题目保证有解，不会出现a-b 、b-c 、c-a这种情况，所以我们可以把同一条链上的点缩点，奇数层的点一点，偶数层同一个点 如果a-b不能共存，那么对于一个集合来说，只是取min(a,b)，对于取a还是取b,就相当于是否取max(a,b)-min(a,b)，即a-b可以缩成一个点来理解，该点权是max(a,b)-min(a,b)，而tmp要加上所以的min(a,b)
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=210; int n,m; vector<int> ve[maxn]; int color[maxn],c[maxn],b[maxn]; int a[2]; bool vis[maxn]; void dfs(int u,int f) { vis[u]=1; a[f]+=c[u]; for(int i=0;i<ve[u].size();i++){ int v=ve[u][i]; if(vis[v]) continue; dfs(v,1-f); } } int co; int dp[2][100010];//数组200*500 int main() { int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); int sum=0; for(int i=1;i<=n;i++){ scanf("%d",&c[i]); c[i]/=100; sum+=c[i]; ve[i].clear(); } int u,v,tmp=0; while(m--){ scanf("%d%d",&u,&v); ve[u].push_back(v); ve[v].push_back(u); } memset(vis,0,sizeof(vis)); co=1; for(int i=1;i<=n;i++){ if(vis[i]) continue; if(ve[i].size()>0){ a[0]=a[1]=0; dfs(i,0); tmp+=min(a[0],a[1]); b[co]=max(a[0],a[1])-min(a[0],a[1]); }else{ b[co]=c[i]; } co++; } n=co-1; int sum1=sum/2-tmp; int cur=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ cur=1-cur; for(int j=sum1;j>=0;j--) dp[cur][j]=dp[1-cur][j]; for(int j=sum1;j>=b[i];j--){ dp[cur][j]=max(dp[cur][j],dp[1-cur][j-b[i]]+b[i]); } } int ans=dp[cur][sum1]+tmp; printf("%d\n",(sum-ans)*100); } return 0; }