19年东北四省省赛
做了J G C
补了E H
J签到题
G
题意：
给n个正方形的两个斜对角点坐标，问最小的移动可以重叠（移动上下左右一格）
思路：
一开始想的是中心pos移动，但是可能有小数，而且半径长度不知，可能有包含关系。
然后发现题目没说一定要某一个正方形移动的最小步数，那之间转换为点在面里面的移动最小，取中间的两个上下斜对角坐标就行了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<queue>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mod 998244353
const int maxn=1e5+;
struct node{
int x,y,xx,yy;
}a[maxn];
int t,n;
int x[maxn<<],y[maxn<<];
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int xt=,yt=;
for(int i=;i<n;i++){
scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].xx,&a[i].yy);
x[xt++]=a[i].x,x[xt++]=a[i].xx;
y[yt++]=a[i].y,y[yt++]=a[i].yy;
}
sort(x,x+xt);
sort(y,y+yt);
int zx=x[xt/],zy=y[yt/];
ll sum=;
for(int i=;i<n;i++){
if(zx<a[i].x || zx>a[i].xx){
sum+=(ll)min(abs(a[i].x-zx),abs(a[i].xx-zx));
}
if(zy<a[i].y || zy>a[i].yy){
sum+=(ll)min(abs(a[i].y-zy),abs(a[i].yy-zy));
}
}
printf("%lld\n",sum);
}
return ;
}
C
题意：
给n条直线，问有多少两两相交的线，重叠也算相交的线
思路：
总量n*（n-1）/2-平行的数量
一开始算斜率，但因为斜率的精确度，wa，然后想了用gcd或者用逆元
最后用了map存y/x的最小分数yy和xx，在特判一下重叠的
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<queue>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mod 998244353
const int maxn=1e5+;
int n,t;
ll a,b,c,d;
ll gcd(ll a,ll b){
return b==?a:gcd(b,a%b);
}
struct node{
ll x,y;
node(){}
node(ll xx,ll yy):x(xx),y(yy){}
bool operator<(const node &b)const
{
if(x==b.x)
return y<b.y;
else
return x<b.x;
}
};
struct node1{
ll x,y,chong;
node1(){}
node1(ll xx,ll yy,ll cc):x(xx),y(yy),chong(cc){}
bool operator<(const node1 &b)const
{
if(x==b.x){
if(y==b.y){
return chong<b.chong;
}
return y<b.y;
}
else
return x<b.x;
}
};
map<node,ll>mp;
map<node1,ll>cd;
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ll zong=(ll)n*(n-)/;
for(int i=;i<n;i++){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
ll xx=a-c,yy=b-d;
ll gd=gcd(xx,yy);
ll x=xx/gd,y=yy/gd;
ll f=x*b+y*a;
mp[node(x,y)]++;
zong-=mp[node(x,y)];
cd[node1(x,y,f)]++;
zong+=cd[node1(x,y,f)];
}
printf("%lld\n",zong);
mp.clear(),cd.clear();
}
return ;
}
E
题意：
给n个点，n-1条边，每条边都有权重，每个边形成一个最小生成树，形成线图
思路：
算每个点的贡献值，这个点的出度小于二，无贡献，大于二，就是相邻的边加一起，在最小的那个边*（相邻边数-2）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=;
struct node
{
int v,w;
node(){}
node(int n,int m):v(n),w(m){}
bool operator < (const node &r)const{
return w<r.w;
}
};
vector<node>G[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)G[i].clear();
for(int i=;i<=n-;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(node(v,w));
G[v].push_back(node(u,w));
}
ll ans=;
for(int i=;i<=n;i++){
sort(G[i].begin(),G[i].end());
int minn=0x3f3f3f3f;
int degree=G[i].size();
for(int j=;j<degree;j++){
ans+=G[i][j].w;
minn=min(minn,G[i][j].w);
}
ans+=(ll)minn*(degree-);
}
printf("%lld\n",ans);
}
return ;
}
H：