A
知识点：计算几何
难度预估：1900
题意：给两个点和一个圆，用一条曲线（或直线）连结两点但不能触碰到圆内部，求线的最短距离。
思路：首先要明确的是两种使用直线的情况：第一个是圆心到过两点的直线的距离大于或等于 。第二个是圆心在线段的两侧。
第一个判断很简单，求点到直线距离可以用面积除以2倍高的方法。
第二个判断只需要判断对应角是钝角就可以了，钝角可以用点乘为负数判断。
然后就是使用曲线的情况，曲线可以分为两个线段和一段圆弧，分别求长度即可。注意圆弧长为 ，其中
为对应圆心角。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi 3.14159265358979
struct point{
double x,y;
};
double dis(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int jud(point a,point b,point c){
return (b.x-a.x)*(b.x-c.x)+(b.y-a.y)*(b.y-c.y)<=0;
}
double ar(point a,point b,point c){
double pa=dis(a,b),pb=dis(a,c),pc=dis(b,c);
double p=(pa+pb+pc)/2;
return sqrt(p*(p-pa)*(p-pb)*(p-pc));
}
double dis(point a,point b,point c){
return 2*ar(a,b,c)/dis(b,c);
}
double ang(point a,point b,point c){
double A=dis(b,c),B=dis(a,c),C=dis(a,b);
return acos((A*A+C*C-B*B)/(2*A*C));
}
int main(){
point p1,p2,p3;
double r;
cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>r;
if(jud(p3,p1,p2)||jud(p3,p2,p1)){
printf("%.7lf",dis(p1,p2));
return 0;
}
if(dis(p3,p1,p2)>=r){
printf("%.7lf",dis(p1,p2));
return 0;
}
double d1=sqrt(dis(p1,p3)*dis(p1,p3)-r*r),d2=sqrt(dis(p2,p3)*dis(p2,p3)-r*r);
double rd=r*(ang(p1,p3,p2)-acos(r/dis(p1,p3))-acos(r/dis(p2,p3)));
printf("%.7lf",d1+d2+rd);
}B
知识点：排序，尺取/二分
题意：选出尽可能多的数，使得 不大于
预估难度：1300
思路：应该是见过很多类似的原题了。排序后遍历左端点，尺取或二分右端点即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
long long n,m,i,a[555555];
ll t;
cin>>t;
while(t--){
cin>>n>>m;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)if(a[i]-a[n]>m)break;
ll ma=i,r=i;
for(i=1;i<n;i++){
while(r<n&&a[r]<=a[i]+m)r++;
ma=max(ma,r-i);
}
cout<<ma<<endl;
}
}C
知识点：dfs
预估难度：1800
题意：类似围棋的规则，将一个连通块围起来，使其没有外气。
思路：这道题稍微要一点思维或者小技巧。我的方法是先把连通块的外部所有点标记，然后对应每个点check已标记的邻点即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
char a[555][555];
ll n,m;
void dfs(int x,int y){
a[x][y]='x';
if(x>0&&a[x-1][y]=='.')dfs(x-1,y);
if(y>0&&a[x][y-1]=='.')dfs(x,y-1);
if(x<n-1&&a[x+1][y]=='.')dfs(x+1,y);
if(y<m-1&&a[x][y+1]=='.')dfs(x,y+1);
}
int main(){
int i,j;
cin>>n>>m;
for(i=0;i<n;i++)cin>>a[i];
dfs(0,0);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(a[i][j]=='#'){
if(a[i-1][j]=='x')a[i-1][j]='*';
if(a[i+1][j]=='x')a[i+1][j]='*';
if(a[i][j-1]=='x')a[i][j-1]='*';
if(a[i][j+1]=='x')a[i][j+1]='*';
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++)
if(a[i][j]=='x')a[i][j]='.';
}
for(i=0;i<n;i++)cout<<a[i]<<endl;
}D
知识点：差分、前缀和
预估难度：1700
题意：每次对应矩形内部所有点权值加1。然后多次询问某矩形内部权值之和。
思路：二维差分前缀和板子题。(x1,y1),(x2,y2)对应矩形权值加一，只需要(x1,y1)、(x2+1,y2+1)两点加一，(x1,y2+1)、(x2+1,y1)两点减一之后做二维前缀和即可。询问时同理，需要预处理前缀和、之后每次询问对应4点即可。
（吐槽：卡cin超时惨惨惨）
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[2020][2020];
const int mod = 1e9+7;
int main(){
int n,m,k,q,i,j;
cin>>n>>m>>k>>q;
while(k--){
ll x1,y1,x2,y2;
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
a[x1][y1]++;
a[x2+1][y2+1]++;
a[x1][y2+1]--;
a[x2+1][y1]--;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
a[i][j]+=a[i][j-1];
}
}
for(j=1;j<=m;j++){
for(i=1;i<=n;i++)
a[i][j]+=a[i-1][j];
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
a[i][j]+=a[i][j-1];
}
}
for(j=1;j<=m;j++){
for(i=1;i<=n;i++)
a[i][j]+=a[i-1][j];
}
while(q--){
ll x1,y1,x2,y2;
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
printf("%lld\n",a[x2][y2]+a[x1-1][y1-1]-a[x2][y1-1]-a[x1-1][y2]);
}
}E
知识点：最短路、dfs
预估难度：2000
题意：给一个无向图，把所有最短路的并集删了，问所有点是否仍然连通。
思路：先用dijkstra求最短路并用dfs标记，然后再dfs check一下连通块即可。
（吐槽：没开ll导致wa了惨惨惨）
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 1e5 + 5;
const ll MAXM = 1e6 + 5;
long long head[MAXN],d[MAXN],nxt[MAXM],to[MAXM],val[MAXM],vis[MAXM],sze=1,n,m;
inline void AddEdge(int u, int v, int w) {
nxt[++sze]=head[u];
to[head[u]=sze]=v;
val[sze]=w;
}
struct HeapNode{
ll dist, u;
HeapNode(ll dist=0,ll u=0) : dist(dist),u(u){}
bool operator <(const HeapNode& rhs)const{
return dist>rhs.dist;
}
};
void dij(int s){
int i;
for(i=1;i<=n;i++)d[i]=1e17;
d[s]=0;
priority_queue<HeapNode> q;
q.push(HeapNode(0,s));
while (!q.empty()) {
while(!q.empty()&&q.top().dist!=d[q.top().u])q.pop();
if(q.empty())break;
HeapNode t=q.top();
q.pop();
for(ll e=head[t.u];e;e=nxt[e]){
if(d[to[e]]>d[t.u]+val[e]){
d[to[e]]=d[t.u]+val[e];
q.push(HeapNode(d[to[e]],to[e]));
}
}
}
}
long long ans=0;
void dfs(int u){
if(u==1) return;
for(int e=head[u];e;e= nxt[e]) {
if(!vis[e]&&d[to[e]]+val[e]==d[u]){
ans+=val[e],vis[e]=vis[e^1]=1;
dfs(to[e]);
}
}
}
long long jud[MAXN],cnt;
void check(int u){
jud[u] = 1;
cnt++;
for(int e=head[u];e;e=nxt[e]){
if(!jud[to[e]]&&!vis[e])check(to[e]);
}
}
int main(){
int i;
scanf("%lld%lld",&n,&m);
for(i=1;i<=m;i++) {
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
AddEdge(u,v,w);
AddEdge(v,u,w);
}
dij(1);
dfs(n);
check(1);
cnt==n?puts("YES"):puts("NO");
return 0;
}F
知识点：无
预估难度：600
题意：给定大小关系，判断两个字符串的大小。
思路：模拟即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
string a,b;
cin>>a>>b;
if((a[0]=='t'&&b[0]=='e')||(a[0]=='c'&&b[0]=='t')||(a[0]=='m'&&b[0]=='c')||(a[0]=='e'&&b[0]=='m'))
cout<<"tiangou txdy";
else cout<<"tiangou yiwusuoyou";
}
G
知识点：贪心
预估难度：1000
题意：给定一些数以及一个上限k，选出尽可能多的数，满足这些数之和不超过k。
思路：显然从小到大取为优。排序后模拟即可。（也可以用最小堆不过没必要）
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,m,i,a[555555];
cin>>n>>m;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
long long sum=0;
for(i=0;i<n;i++){
if(sum+a[i]>m)break;
sum+=a[i];
}
cout<<i;
}H
知识点：并查集、离散化
预估难度：1700
题意：给定一些人之间的关系（朋友或敌人），已知朋友的朋友也是朋友。问是否矛盾。
思路：离线处理。先把所有朋友的关系用并查集连结，然后查询是否存在某对敌人是朋友。
注意要先离散化。本题数据量很大所以要使用sort离散化而不能用map
（我就是因为用map，wa了十几次，惨惨惨）
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[1111111][3];
const int mod = 1e9+7;
ll fa[2222222],kdm[2222222];
int f(int x){
if(fa[x]==x)return fa[x];
return fa[x]=f(fa[x]);
}
void uni(int x,int y){
int p=f(x),q=f(y);
if(p!=q){
if(kdm[p]>kdm[q]){
fa[q]=p;
kdm[p]+=kdm[q]+1;
}
else{
fa[p]=q;
kdm[q]+=kdm[p]+1;
}
}
}
ll sub[2000020],a1[2000020];
int main(){
int n,k,q,i,j,t;
cin>>t;
while(t--){
map<int,int>m;
cin>>n;
for(i=1;i<=n;i++){
for(j=0;j<3;j++)a[i][j]=read();
a1[i]=sub[i]=a[i][0];
a1[n+i]=sub[n+i]=a[i][1];
}
sort(sub+1,sub+2*n+1);
int sz=unique(sub+1,sub+2*n+1)-sub;
for(i=1;i <= 2*n; i++)
a1[i]=lower_bound(sub,sub+sz,a1[i])-sub;
for(i=1;i<=2*n;i++)fa[i]=i,kdm[i]=0;
for(i=1;i<=n;i++){
if(a[i][2]){
uni(a1[i],a1[n+i]);
}
}
for(i=1;i<=n;i++){
if(!a[i][2]&&f(a1[i])==f(a1[n+i]))break;
}
if(i==n+1)cout<<"YES\n";
else cout<<"NO\n";
}
}
/*
2
3
1 2 1
2 3 1
1 3 0
*/
I
知识点：dfs序、线段树
预估难度：1900
题意：给一棵树，有多次操作，分别为单点修改、询问子树权值和。
思路：先用dfs序，将树形结构转化为线性结构，然后就变成查询区间和，可以用线段树解决。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 2000005;
int to[MAXN<<1],Next[MAXN<<1],head[MAXN],tol;
void add_edge(int u,int v){
Next[++tol]=head[u];to[tol]=v;head[u]=tol;
Next[++tol]=head[v];to[tol]=u;head[v]=tol;
}
int L[MAXN], R[MAXN], id[MAXN], dfn;
ll sum[MAXN<<2];
int n,m,k;
int val[MAXN];
void dfs(int u, int f){
L[u]=++dfn;
id[dfn]=u;
for(int e=head[u];e;e=Next[e]){
int v=to[e];
if(v==f)continue;
dfs(v,u);
}
R[u]=dfn;
}
void build(int nd,int l,int r){
if(l==r){
sum[nd]=val[id[l]];
return;
}
ll mid=l+r>>1;
build(nd<<1,l,mid);
build(nd+nd+1,mid+1,r);
sum[nd]=sum[nd<<1]+sum[nd+nd+1];
}
void update(int nd, int l, int r, int pos, int v){
if(l==r){
sum[nd]+=v;
return;
}
ll mid=l+r>>1;
if(pos<=mid)update(nd<<1,l,mid,pos,v);
else update(nd+nd+1,mid+1,r,pos,v);
sum[nd]=sum[nd<<1]+sum[nd+nd+1];
}
ll query(int nd, int l, int r, int L, int R){
if(L<=l&&r<=R){
return sum[nd];
}
ll mid=l+r>>1;
ll res=0;
if(L<=mid)res+=query(nd<<1,l,mid,L,R);
if(R>=mid+1)res+=query(nd+nd+1,mid+1,r,L,R);
return res;
}
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add_edge(u,v);
}
dfs(k,0);
build(1,1,n);
for(int i=1;i<=m;++i){
int op;
op=read();
if(op==1){
int a=read(),x=read();
update(1,1,n,L[a],x);
}else{
int a=read();
ll ret=query(1,1,n,L[a],R[a]);
cout<<ret<<endl;
}
}
return 0;
}
J
知识点：前缀和、dp
预估难度：1800
题意：给定 个数，求
思路：我们可以假定前 个数的上述算式的结果为
，那么对于第
个数而言，相较于前
个数，新增的部分为：
后两部分可以用前缀和预处理达成 ，因此总复杂度可以
解决。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[555555],sum[555555],sum2[555555],dp[555555];
const int mod = 1e9+7;
int main(){
int n,i,j;
cin>>n;
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
ll s=0,s2=0;
for(i=1;i<=n;i++){
s+=a[i];
s2+=a[i]*a[i]%mod;
s%=mod;
s2%=mod;
sum[i]=s;
sum2[i]=s2;
}
for(i=2;i<=n;i++){
dp[i]=dp[i-1]+(i-1)*a[i]%mod*a[i]%mod+sum2[i-1]-2*a[i]*sum[i-1]%mod;
dp[i]=(dp[i]+mod)%mod;
}
cout<<dp[n];
}
京公网安备 11010502036488号