A、最短路
思路：
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define dis(a,b,c,d) sqrt((a-c)*(a-c)+(b-d)*(b-d))
#define ll long long
using namespace std;
int main() {
js;
double x1,y1,x2,y2,x3,y3,r;
cin>>x1>>y1>>x2>>y2>>x3>>y3>>r;
double AB=dis(x1,y1,x2,y2);
double OA=dis(x1,y1,x3,y3);
double OB=dis(x2,y2,x3,y3);
double ao=acos(r/OA);
double bo=acos(r/OB);
double aob=acos((OA*OA+OB*OB-AB*AB)/(2*OA*OB));//余弦定理
if(ao+bo>aob) cout<<fixed<<setprecision(6)<<AB<<endl;
else cout<<fixed<<setprecision(6)<<sqrt(OA*OA-r*r)+sqrt(OB*OB-r*r)+(aob-ao-bo)*r<<endl;
return 0;
} B、组队：
大意：n个人都有自己的能力值，在里面选尽量多的人组成团队，但是任意两个人的能力值不能相差k。
思路：
贪心的策略。将n个人升序排序，要人数最多，团队的能力值一定是连续的，[cnt,i]就是这个团队的区间，cnt和i初始为1，不断增加i，如果第cnt个人的能力和刚加进来的人的能力值相差大于k，就不断增加cnt使其恰好满足题意，同时ans取区间的最大值就是答案了。复杂度 (nlog n)。
Code：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int t,n,k,a[200005],nx,ans;
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+1+n);
ans=nx=1;
for(int i=2;i<=n;++i) {
while(a[i]-a[nx]>k) ++nx;
ans=max(ans,i-nx+1);
}
cout<<ans<<endl;
}
} C、十面埋伏：
思路：
思维+bfs，通过bfs标记连通块外部的点，防止出现把连通块内部的点改成陷阱的情况，接着在士兵旁边放陷阱。
原理：
1.bfs是宽度优先遍历，遇到连通块上的点就让它返回，那它就不可能到达连通块的内部，从而连通块内部的空地就不会被标记。
2.由1知标记了的位置一定是连通块外部的空地，如果还满足上下左右任何一个邻居是士兵，那么这个地方一定可以放陷阱。
复杂度： (n^2)。
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
char s[505][505];
bool vis[505][505];
int n,m,d[4][2]={0,1,1,0,-1,0,0,-1};
struct node {
int x,y;
};
int main() {
js;
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>s[i]+1;
queue<node>q;
q.push(node{1,1});
while(!q.empty()) {
node u=q.front();
q.pop();
for(int i=0;i<4;++i) {
node v;
v.x=u.x+d[i][0],v.y=u.y+d[i][1];
if(v.x<1||v.x>n||v.y<1||v.y>m) continue;
if(s[v.x][v.y]=='#'||vis[v.x][v.y]) continue;
vis[v.x][v.y]=true;
q.push(v);
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(vis[i][j]&&(s[i-1][j]=='#'||s[i+1][j]=='#'||s[i][j+1]=='#'||s[i][j-1]=='#')) {
s[i][j]='*';
}
for(int i=1;i<=n;++i) puts(s[i]+1);
} D、牛妹吃豆子：
前背知识：差分，二维差分 (网上一些不错的博客，很好懂)。
题意：一个n * m的矩阵，k次操作，每次给一个子矩阵的左下角标和右上角标，然后这个子矩阵全部的格子放一个豆子，接着q次询问，同样的方式，输出询问的子矩阵有多少豆子。
思路：
k次区间加如果朴素的算法，矩阵大小200 * 200，加200 000次，然后再前缀和，直接TLE，这个时候就要套二维差分的板子了，每个位置初始为0，所以每个位置的差分也初始为0，一维差分是记录区间加的（起始位置）q[l]和（终点位置+1）q[r+1]，q[l]+=a，q[r+1]-=a,因为差分就是记录这个位置比前面大多少或者小多少，这样处理后利用前缀和从前往后就可以得到区间加操作结束后各位置的豆子数（a[i]=a[i-1]+q[i]）。二维差分也是一样的，只是要多处理一维。利用前缀和的原理（考虑每个差分对前缀和的贡献），得出一个子矩阵的差分应该是a[x][y]+=c,a[x][yy+1]-=c,a[xx+1][y]-=c,a[xx+1][yy+1]+=c。然后由差分根据前缀和得出每个位置的豆子数，再前缀和一次预处理(1,1)到(x,y)的子矩阵有多少豆子，使得下一次查询的复杂度为 (1)。
总复杂度 (k)。
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
long long sum[2001][2001];
int a[2001][2001],n,m,k,q,x,y,xx,yy;
int main() {
js;
cin>>n>>m>>k>>q;
while(k--) {
cin>>x>>y>>xx>>yy;
++a[x][y];
--a[x][yy+1];
--a[xx+1][y];
++a[xx+1][yy+1];
}//此时的a[i][j]记录的是差分。
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) {
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//此时的a[i][j]表示这个地方的豆子数量
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//二维前缀和
}
while(q--) {
cin>>x>>y>>xx>>yy;
cout<<sum[xx][yy]-sum[xx][y-1]-sum[x-1][yy]+sum[x-1][y-1]<<endl;
}
} E、旅旅旅游
思路：
根据题意先走一遍dijkstra构建最短路，然后模拟牛可从终点走到起点把全部的最短路径都走一遍并标记（删边），最后模拟牛妹从起点走到终点，判断能不能走遍n个城市。知识点：最短路、dfs。
原理：
1.从终点开始删边，主要是因为我是链式向前星存的图，所以两个相同的边u-v和v-u会存在相邻的位置，如果初始结点从2开始，head[u]指向u最后一次出现的边，那么这个边的结点一定是奇数，因为输入的一个边是成对存入，从2开始的，所以在标记的时候vis[e]=vis[e^1]=1，可以标记两个一样的无向边（一样指的不是重边）。
2.在模拟牛妹旅游时被1标记的边不能去，起到删边的原理。
3.通过记录牛妹走了几条边+1就可以表示去了几个城市，主要再开一个数组记录这个城市有没有没过，来过了就不去了，防止重边或者重复计数。
Code：
（抄错了快读的模板，debug了几小时，尴尬QAQ~）
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
struct node{
ll u,dis;
bool operator<(const node&a)const{
return dis>a.dis;
}
};
ll dis[100005],val[1000005];
int head[100005],Next[1000005],to[1000005],tot=1,n,m;
void add(int x,int y,int c) {
to[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
val[tot]=c;
}
bool done[100005];
void dijkstra(int s) {
fill(dis,dis+100005,0x3f3f3f3f3f3f3f3f);
dis[s]=0;
priority_queue<node>q;
q.push(node{s,0});
while(!q.empty()) {
node u=q.top();
q.pop();
if(done[u.u]) continue;
done[u.u]=true;
for(int i=head[u.u];i;i=Next[i]) {
int y=to[i];
if(done[y]) continue;
if(dis[y]>val[i]+u.dis) {
dis[y]=val[i]+u.dis;
q.push(node{y,dis[y]});
}
}
}
}
bool vis[1000005];
void dfs(int u){
if(u==1) return;
for(int e=head[u];e;e= Next[e]) {
if(!vis[e]&&dis[to[e]]+val[e]==dis[u]){
vis[e]=vis[e^1]=1;
dfs(to[e]);
}
}
}
int cnt,jud[100005];
void check(int u){
jud[u] = 1;
++cnt;
for(int e=head[u];e;e=Next[e]){
if(!jud[to[e]]&&!vis[e])check(to[e]);
}
}
int main() {
js;
cin>>n>>m;
for(int i=1;i<=m;++i) {
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dijkstra(1);
dfs(n);
check(1);
cnt==n?puts("YES"):puts("NO");
return 0;
} F、斗兽棋
题意：一个食物链，问牛妹的棋能不能吃掉牛牛的棋，能输出"tiangou txdy"，否则输出"tiangou yiwusuoyou"。显然是本场的签到题，写了很快乐，没写或者比较晚写就很难受咯。
思路：
map存字符串，并附键值进行比较，大的吃小的，老鼠和大象除外。
Code：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
string s1,s2;
map<string,int>mp;
int main() {
js;
mp["elephant"]=4;
mp["tiger"]=3;
mp["cat"]=2;
mp["mouse"]=1;
cin>>s1>>s2;
if(mp[s2]-mp[s1]==1||mp[s2]==1&&mp[s1]==4) puts("tiangou txdy");
else puts("tiangou yiwusuoyou");
} G、做题
题意：给n道题m分钟，每道题都要花a[i]分钟，问最多可以做多少题，贪心。
思路：
注意到题目最多5e5，而一道题最多要花的时间是1e5，所以我们可以存要花i分钟的题有多少道，然后从前往后贪心的去就算可以做多少题，这样可以节省sort (nlog n)排序的时间，降为
。而且还能节省空间同时提高枚举的效率。
注意：把m看成了5e5，没开long long，wa了一发。
Code：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll a[100005],n,m,k,ans,mx;
int main() {
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%lld",&k);
++a[k];
if(k>mx) mx=k;
}
for(int i=0;i<=mx;++i) {
if(!a[i]) continue;
if(m==0) break;
if(m>=a[i]*i) {
m-=a[i]*i;
ans+=a[i];
}
else {
while(m>=i) {
m-=i;
++ans;
}
break;
}
}
printf("%lld\n",ans);
} H、人人都是好朋友
题意：多组输入，输入a，b，c，c为1表示ab是好朋友，反之是敌人。
前面的碎碎念：紫书上的并查集练习都是1e7或者1e5，需要开的数组比较少，但是我写这题想到的就是要开好几个数组，加上写并查集是好久之前的事了担心数组开太多超时超内存，结束后听说真的是并查集加离散化我就继续昨天的代码和思路结果一发AC了，真的当你害怕的时候就真的输了。关于并查集，poj 1182是判断有多少句假话，但是这里没有那么复杂，只要判断有没有假话就可以了，比1182会简单。戳我看代码
思路：
虽然每个人的编号不一定连续，范围是1e9，是开不了这么大的数组的，自然也用不了并查集，于是我们就想能不能自己给他们重新编号使其连续，于是就可以通过离散化将他们映射到一个连续的集合里，最大的范围就是2*n的大小也就是2e5。接着将朋友和敌人的集合分别存到vector容器里，先通过朋友关系建立连通块，然后遍历敌人集合查看是否有矛盾。复杂度 (nlog n)。
Code:
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int a[1000005],b[1000005],d,c[2000005],fa[2000005],x,y,t,n;
int find(int x) {
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
vector<int>g[3];
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
for(int i=0;i<n;++i) {
scanf("%d%d%d",&a[i],&b[i],&d);
if(d&1) g[1].push_back(i);
else g[0].push_back(i);
c[i<<1]=a[i],c[i<<1|1]=b[i];
}
//for(int i=0;i<3;++i) cout<<g[1][i]<<endl;
sort(c,c+(n<<1));
int cnt=unique(c,c+(n<<1))-c;
for(int i=0;i<n;++i) {
a[i]=lower_bound(c,c+cnt,a[i])-c+1;
b[i]=lower_bound(c,c+cnt,b[i])-c+1;
//cout<<a[i]<<" "<<b[i]<<endl;
}
for(int i=1;i<=cnt;++i) fa[i]=i;
int x,y;
for(int i=0;i<g[1].size();++i) {
x=find(a[g[1][i]]),y=find(b[g[1][i]]);
fa[x]=y;
}
int i;
for(i=0;i<g[0].size();++i) {
x=find(a[g[0][i]]),y=find(b[g[0][i]]);
if(x==y) break;
}
if(i==g[0].size()) puts("YES");
else puts("NO");
g[0].clear(); g[1].clear();
}
} I、求和
题意：n个点组成k为根的树，给出每个结点的初始权值，接下来进行m次操作，1表示给结点a的权值加x，2询问结点a的子树的权值之和（包括自己）。
思路：
方法一：dfs序+树状数组实现。
树的括号表示法是父结点a左边一个括号包住它的子树，然后它的儿子如果有儿子也继续这样的操作，同时子树的dfs序(括号表示法)是连续的，结点a的子树权值之和就是括号里的各节点之和加上自己的权值。于是我们就把问题转化到了区间上，因为题目要求我们做单点修改和区间求和的操作，显然很适合用数组数组。
建树的时候可以得到dfs序，我们可以在建树的时候记录结点a的起始位置l[a]，和a最后一个儿子的位置，(看成记录括号表示法里结点a的位置和右括号前第一个儿子的位置)。这个位置是根据是结点a对应的dfs序(结点a第3个遍历到，位置就是3)，也就是它的新编号。
方法二：dfs序+线段树实现。
两个方法复杂度同级，但是树状数组明显优于线段树，编程复杂度也远小于线段树。线段树的适用范围大于数组数组，凡是可以使用数组数组解决的问题，使用线段树一定可以解决。因为是点修改，所以用不到lazy-tag方法，如果a结点需要加x，可以从根结点找到需要增加值的结点l[a]，因为l[a]的值改变了，包含l[a]的区间值都要跟新。求和时，存在两个情况，需要求和的区间[l[a],r[a]]与子区间交错，深入交错的子区间并求总和，需要求和的区间[l[a],r[a]]包含子区间，返回子区间的权值之和。戳我看代码
Code：
（树状数组实现，复杂度 (nlog n)）
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&-(x))
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll tree[1000005];
int n,m,k,a[1000005];
void add(int x,int d) {
while(x<=n) {
tree[x]+=d;
x+=lowbit(x);
}
}
ll sum(int x) {
ll ans=0;
while(x) {
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int head[1000005],Next[2000005],to[2000005],tot;
void addedge(int x,int y) {
to[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
int l[1000005],r[1000005],cnt;
void dfs(int u,int f) {
l[u]=++cnt;
for(int i=head[u];i;i=Next[i]) {
int v=to[i];
if(v==f) continue;
dfs(v,u);
}
r[u]=cnt;
}
int x,y,d;
int main() {
js;
cin>>n>>m>>k;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=2;i<=n;++i) {
cin>>x>>y;
addedge(x,y);
addedge(y,x);
}
dfs(k,0);
for(int i=1;i<=n;++i) add(l[i],a[i]);
while(m--) {
cin>>d;
if(d&1) {
cin>>x>>y;
add(l[x],y);
}
else {
cin>>x;
cout<< sum(r[x])-sum(l[x]-1) <<endl;
}
}
return 0;
} J、建设道路：
题意：连接任意两点，代价是 .
思路：
假设先连接结点1和其它点的边: ,化简后就是：
。于是就可以
(n)的去处理这个问题，用个后缀和就好了---前缀和变一下型。
注意：最后要+mod然后取余是因为有减法，可能出现取余后相减是负数的情况。
Code：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
ll a[500010],sum[500010],ans;
int main() {
ll n = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i) {
ans += (((n - 1) * a[i] % mod) * a[i]) % mod;
ans -= ((2 * a[i]) % mod) * ((sum[n] - sum[i]) % mod) % mod;
(ans += mod) %= mod;
}
printf("%lld\n", ans);
return 0;
} 
京公网安备 11010502036488号