J - Building a Space Station （最小生成树&kruskal） 思路：将所有两两的点的距离进行排序,然后用kruskal板子就行，唯一需要注意的是距离为负数不用加。 AC代码：ps(C++ac，G++wa) #include<cstdio> #include<cstring> #include<iostream> #include<queue>  #include<cmath> #include<algorithm> #include<vector> using namespa...

E. Weights Distributing （最短路&贪心） 题目传送门 题意：给定无权无向图,m条边和m个权值和三个点a,b,c。问如何分配能使a到b b再到c 的权值和最小。 思路：先求出a,b,c到每个点的最短路（用BFS实现即可）考虑a–b与b—c的路径是否相交，若不相交，显然从权值较小到权值到大的取，若相交设交点为x 则路径为： a–>x---->b—>x—>c ，由于b----x被加了两次，根据贪心则b–x路径取最小的权值，然后a—x----c依次取最小。 #include<bits/stdc++.h> using namespace...

C.十面埋伏(DFS&连通块） 题目传送门 题意：将”#“图案用星号围一圈并输出图。 思路：显然从外围DFS，判断一下四周有无#即可。 AC代码： #include<bits/stdc++.h> using namespace std; int n,m; char mp[505][505]; int vis[505][505],d[4][2]={0,1,0,-1,1,0,-1,0}; void dfs(int x,int y){ //printf("x=%d,y=%d\n",x,y); if(x<1||x>n||y<1||y>m)...

A.最短路(计算几何） 题目传送门 题意：给定A,B,坐标和，以C为圆心的坐标和半径r，求A到B的最短路径（不能经过圆C）。 思路：分两种情况：第一种：不需要沿圆的切线走，直接两点之间距离最短，这种情况判断两个切角是否大于圆心角即可。第二种情况：利用勾股定理和圆弧公式即可。 AC代码： #include<bits/stdc++.h> using namespace std; struct p{ double x,y; }a,b,c; double dis(p a,p b){ return hypot(a.x-b.x,a.y-b.y); } int main(){ double r;...

T - A Simple Problem with Integers （线段树&区间修改） 思路：线段树&lazy_tag板子题。 AC代码： #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=1e5+5; typedef long long ll; ll tr[N*10]; ll lz[N*10]; void re(int x){ tr[x]=tr[x<<1]+tr[x<<1|1]; } v...

L - 敌兵布阵 （线段树模板题） 思路：板子题。 AC代码： #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAX=50050; int t,N; int tr[MAX<<4]; void re(int x) { tr[x]=tr[x*2]+tr[x*2+1]; } void build(int st,int ed,int node) { if(st==ed) { scanf("%d",&tr[...

M - I Hate It （线段树&区间最值） 思路：板子题。 AC代码： #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=2e5+5; int tr[N*10]; void re(int x){ tr[x]=max(tr[x<<1],tr[x<<1|1]); } void build(int st,int ed,int x){ if(st==ed){ scanf("%d",&...

A.Jelly (简单BFS&三维) 思路：板子题。具体看代码。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e2+5; int n,d[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1}; char mp[N][N][N]; int a[N][N][N]; struct p{ int x,y,z; }s,e; #define jg(x,y,z) (x>=0&&x<n&&y>=0&&y...

「木」迷雾森林 (路径DP） 题目传送梦 思路：板子题，唯一需要注意的是数据较大要用到快读。 AC代码： #include<bits/stdc++.h> using namespace std; const int mod=2333,N=3e3+5; int m,n; int a[N][N],dp[N][N]; int read(){ //快读  int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();} while(ch>='0'&&...

D.表达式求值 (栈&后缀表达式） 题目传送门 思路：裸题，唯一需要注意的是会爆long,long 要一边取模一边操作。 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e4; int main(){ stack<ll>s; ll a,ans=0; scanf("%lld",&a); s.push(a%mod); char ch; while((ch=getchar())!='\n'){ scanf(&quo...

Sunscreen (贪心&map） 题目传送门 思路：  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e3+5; struct p{ int l,r; bool operator<(const p&a)const{ return l<a.l; } }a[N]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf...

P4568 [JLOI2011]飞行路线 （分层最短路&模板） 题目传送门 思路：板子题，具体看代码。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=5e6+5; struct edge{ int to,nt,w; }e[N]; struct node{ int d,id; bool operator<(const node&a)const{ return d>a.d; } }now; int cnt=1,n,m,k,st,ed,d[N],h[N],vis[N]; void ...

B. Nastya and Door （前缀和&暴力） 题目传送门 思路：给定区间长度的有关问题，可以考虑用前缀和实现对区间的查找。 #include<bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N],b[N]; int main(){ int t; scanf("%d",&t); while(t--){ int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf(&quo...

C. Nastya and Strange Generator （思维&找规律） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); vector<int>a(n+1); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ok...