HDU多校1
HDU多校1
赛中过了四题，代码能力真的捞，都是一眼思路然后敲大半个小时……
1011
题意：[0,1]随机生成n个数，然后m次操作，每次随机删除最小或最大的一个数，求最终剩下的数的和的期望。
思路：众所周知，期望这东西应用在随机数上，那就是他的平均值，即0.5。m次操作后剩下(n-m)个数，那么它的和的期望就是0.5*(n-m)，注意求下逆元即可。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=1e9+7,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;
bool cmp(qq u,qq v){
return u.x>v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;
void solve(){
scanf("%lld%lld",&n,&m);
printf("%lld\n",(n-m)*two%mod);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1012
题意：n个数，每次操作Alice可以把这些数分成两个集合，然后Bob可以删掉任意一个集合，然后将剩下的集合内所有元素-1。如果集合中出现了0，那么Alice获胜，如果集合内没有元素，则Bob获胜。
（一开始脑子卡了，队友开出的）
思路：考虑如何能让Alice获胜：一个0就可以获胜，两个1的把1分在两边也可以获胜，4个2的话每边两个2，Bob删除一边后剩下一边-1，又变成了上一步的两个1…… 由此我们可以发现，如果i的数量≥2^i的话，Alice就可以一直平分，最终一定会变成0。同样，考虑一个例子，一个1两个2，Alice可以将其分成一边一个1，另一边两个2，我们发现不论Bob删掉哪边，Alice必赢。 由此可以总结出规律，两个2等价于一个1，同理，两个(i+1)可以等价于一个i。因此，只需要将所有＞0的数不停往小的数等价下来，最终判断是否会出现0，即可判断Alice的输赢。
1002
题意：给定n*m的一张地图，有墙有路，求从起点到终点最少需要删除几座墙。
思路：因为墙的数量只有15，所以枚举所有删墙的情况，然后每次bfs一遍即可。（一开始把删墙理解成跨墙，WA卡了好久）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=40,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[M],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[M][M],mapp[M][M],flag;
struct qq{ll x0,y0,x1,y1;}q[M];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;
pair<ll,ll>pr[N];
vector<qq>v[N],vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi;
ll count(ll x){
ll res=0;
while(x){
if(x%2)res++;
x/=2;
}
return res;
}
void dfs(ll m){
if(m==0){
pr[++cnt]=mkp(count(key),key);
return;
}
dfs(m-1);
key^=b[m-1];
dfs(m-1);
key^=b[m-1];
}
void init(){
key=0;cnt=0;
ll p=1;
L(i,0,15){
b[i]=p;
p*=2;
}
dfs(k);
sort(pr+1,pr+cnt+1);
}
bool bfs(ll x0,ll y0,ll x1,ll y1){
while(!sq.empty())sq.pop();
vis[x0][y0]=1;
sq.push(mkp(x0,y0));
while(!sq.empty()){
pair<ll,ll> tmp=sq.front();sq.pop();
ll x=tmp.fi,y=tmp.se;
vis[x][y]=1;
if(x<0||y<0||x>n||y>m)continue;
if(mapp[x][y])continue;
if(x==x1&&y==y1)return 1;
L(i,0,3){
ll nx=x+dx[i],ny=y+dy[i];
if(!vis[nx][ny]){
vis[nx][ny]=1;
sq.push(mkp(nx,ny));
}
}
}
return 0;
}
void solve(){
ll x0,x1,y0,y1;
scanf("%lld%lld%lld",&n,&m,&k);
n*=2,m*=2;
scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
x0=x0*2+1,x1=x1*2+1,y0=y0*2+1,y1=y1*2+1;
init();
L(i,0,k-1){
scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
x*=2,y*=2,l*=2,r*=2;
if(r<y)swap(r,y);
if(l<x)swap(x,l);
q[i]={x,y,l,r};
}
L(op,1,cnt){
ll pp=pr[op].se;
L(i,0,n)L(j,0,m){
vis[i][j]=0,mapp[i][j]=0;
}
L(i,0,k-1){
if(pp%2==0){
x=q[i].x0,y=q[i].y0,l=q[i].x1,r=q[i].y1;
if(x==l){
L(j,y,r)mapp[x][j]=1;
}
else{
L(j,x,l)mapp[j][y]=1;
}
}
pp/=2;
}
//L(i,0,n){L(j,0,m)printf("%d",mapp[i][j]);printf("\n");}
if(bfs(x0,y0,x1,y1)){
ans=pr[op].fi;
break;
}
}
printf("%lld\n",ans);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1009
题意：棋盘中有n个点，判断是否存在一个点，使它朝8个方向射出的光线能包含所有点（米字形）。
思路：拿一个点出来枚举它被哪个方向的光线射到，然后再拿一个不在该光路上的点枚举它被哪个方向的光线射到，已知两条光路，然后求交点，判断即可，复杂度为O(43n)。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=40,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[M],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[M][M],mapp[M][M],flag;
struct qq{ll x0,y0,x1,y1;}q[M];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;
pair<ll,ll>pr[N];
vector<qq>v[N],vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
// queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi;
double eps=1e-5;
double sq(double x){return x*x;}
struct point{double x,y;}po[N],pox;
struct line{double A,B,C;}lin0,lin1;
line bd_line(point p,double a,double b){return {a,b,-a*p.x-b*p.y};}
point lin_inter(line l0,line l1){return {(l0.B*l1.C-l1.B*l0.C)/(l0.A*l1.B-l1.A*l0.B),(l0.C*l1.A-l1.C*l0.A)/(l0.A*l1.B-l1.A*l0.B)};}
double dis(point p,line k){return fabs(k.A*p.x+k.B*p.y+k.C)/sqrt(sq(k.A)+sq(k.B));}
bool judge(point px,point py){
double x=px.x,y=px.y,nx=py.x,ny=py.y;
if(fabs(y-ny)<=eps)return 1;
if(fabs(x-nx)<=eps)return 1;
if(fabs(y-ny-x+nx)<=eps)return 1;
if(fabs(y-ny-nx+x)<=eps)return 1;
return 0;
}
void solve(){
scanf("%lld",&n);
ans=0;
L(i,1,n)scanf("%lf%lf",&po[i].x,&po[i].y);
if(n<=2)ans=1;
else{
L(op1,1,4){
p=n+1;
if(op1==1)lin0=bd_line(po[1],0,1);
else if(op1==2)lin0=bd_line(po[1],1,0);
else if(op1==3)lin0=bd_line(po[1],1,1);
else lin0=bd_line(po[1],1,-1);
L(i,2,n){
if(fabs(dis(po[i],lin0))>eps){
p=i;
break;
}
}
if(p==n+1)ans=1;
else{
L(op2,1,4){
flag=1;
if(op1==op2)continue;
if(op2==1)lin1=bd_line(po[p],0,1);
else if(op2==2)lin1=bd_line(po[p],1,0);
else if(op2==3)lin1=bd_line(po[p],1,1);
else lin1=bd_line(po[p],1,-1);
pox=lin_inter(lin0,lin1);
L(i,p,n){
if(!judge(pox,po[i])){
flag=0;
break;
}
}
if(flag)ans=1;
// if(ans)printf("%lf %lf\n",pox.x,pox.y);
if(ans)break;
}
}
if(ans)break;
}
}
if(ans)printf("YES\n");
else printf("NO\n");
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1008
题意：给定n个点m条有向边，有边权，边分为普通边和特殊边，通过一条边的正常花费为这条边的边权。特殊的，假设通过特殊边到了点u，那么此时下一步可以去任意点v：如果点u到点v存在边，边权为w，那么此时通过该边的花费降低为(w-k)；假设点u到点v不存在边，那么此时花费为0。已知起点，求到每一个点的最小花费。
（一开场就先开了这题，由于读假，以为一眼最短路，直到写WA被拉去做签到，写完四题总算读对了，然后一直自闭WA到结束） 的 思路：考虑dijkstra最短路，将图分层，记录一个点由特殊边到的最小花费和非特殊边到的最小花费。我们可以发现如果一个点通过特殊边的能力（即花费为0）到达后，那么这个点的非特殊边到达的最小花费将不会再通过其他边到达了。即一个点通过原先不存在的边到达，最多只有一次。我们需要开set记录即可。其余按最短路标准。
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N][2],b[N],head[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg[N*2];
bool cmp(qq u,qq v){
return u.x<v.x;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
return u.y>v.y;
}};//shun序
pair<ll,ll>pr;
vector<ll>vt,vans;//v.assign(m,vector<ll>(n));
priority_queue<qq,vector<qq>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi;
void add(ll u,ll v,ll w,ll fg){
eg[++cnt].to=v;
eg[cnt].w=w;
eg[cnt].fg=fg;
eg[cnt].nxt=head[u];
head[u]=cnt;
}
void solve(){
scanf("%lld%lld%lld%lld",&n,&m,&p,&t);
cnt=0;key=0;
se.clear();
L(i,1,n){
head[i]=0,b[i]=0;
a[i][0]=inf,a[i][1]=inf;
if(p!=i)se.insert(i);
}
L(i,1,m){
scanf("%lld%lld%lld%lld",&x,&y,&z,&pp);
add(x,y,z,pp);
}
sp.push({p,0,0});
while(!sp.empty()){
qq tmp=sp.top();sp.pop();
ll x=tmp.x,w=tmp.y,op=tmp.z;
if(a[x][op]<=w)continue;
a[x][op]=w;//printf("%lld %lld %lld\n",x,op,w);
if(!op)se.erase(x);
key++;
ll k=head[x];
while(k){
ll y=eg[k].to,dw=eg[k].w,fg=eg[k].fg;
if(op)dw-=t,b[y]=key;
if(a[y][fg]>w+dw)
sp.push({y,w+dw,fg});
k=eg[k].nxt;
}
if(op){
vt.clear();
for(auto y:se){
if(b[y]!=key){
if(a[y][0]>w)sp.push({y,w,0});
vt.pb(y);
}
}
ll siz=vt.size();
L(i,0,siz-1){
se.erase(vt[i]);
}
}
}//printf("\n");
L(i,1,n){
ans=min(a[i][0],a[i][1]);
if(ans==inf)printf("-1 ");
else printf("%lld ",ans);
}printf("\n");
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%lld",&t);
while(t--)solve();
}
1003
题意：常规背包，每个物品有体积和价值，求当恰好塞满背包的前提下，物品价值异或和的最大值。
思路：bitset优化，考虑O(n^3)的做法，dp[i][j][k]表示前i位异或和为j体积为k的是否能取到。我们发现，考虑体积为v，价值为w的物品时，dp[i][j][k]可以由dp[i-1][j^w][k-v]转移过来，我们只需配合bitset的左右移操作即可区间赋值。
#include<bits/stdc++.h>
#define ll int
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e5+10,M=1100,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool flag;
struct qq{ll x0,y0,x1,y1;}q[M];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;
pair<ll,ll>pr;
vector<qq>v,vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi[M],dp[M];
void solve(){
scanf("%d%d",&n,&m);
L(i,0,1023)dp[i].reset();
dp[0][0]=1;
L(i,1,n){
scanf("%d%d",&x,&y);
L(j,0,1023)bi[j]=dp[j^y]<<x;
L(j,0,1023)dp[j]|=bi[j];
}
R(i,1023,0){
if(dp[i][m]){
printf("%d\n",i);
return;
}
}
printf("-1\n");
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
ll t=1;
scanf("%d",&t);
while(t--)solve();
}
1004
题意：有n个点在棋盘上，求一个三元组，满足三个点之间的距离的中位数是个质数。其中距离dis = (abs(x1 - x2) + abs(y1 - y2))。
思路：欧拉筛一遍质数。先n^2求出所有两点间距，然后按从小到大排序。遍历间距作为三边的中间值，假设此时间距所对应的两点为a,b，此时我们需要找到一个点c，满足dis(a,c)<=dis(a,b)&&dis(b,c)>=dis(a,b)（交换a,b也是一样的），因此我们能只需记录在此之前，我们有哪些点的间距已经被遍历过了。举个栗子，当前边是(a,b)，边(a,c)之前已经被记录了，而边(b,c)没被记录过，那么点(a,b,c)就是一个满足条件的三元组。放在bitset中，即bi[a][c]^bi[b][c]==1，(a,b,c)就是一个满足条件的三元组。
#include<bits/stdc++.h>
#define ll int
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=4e6+10,M=2010,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);
ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[M],b[M],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool flag;
struct qq{ll x,y,z;}q[N];
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w,fg;}eg;
bool cmp(qq u,qq v){
return u.z<v.z;
}
bool cmp1(qq u,qq v){
return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
return u>v;
}};//shun序
pair<ll,ll>pr;
vector<qq>v,vans;//v.assign(m,vector<ll>(n));
// priority_queue<qq,vector<qq>,cmps>sp;
queue<pair<ll,ll> >sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se,s0;
set<ll>::iterator it;
bitset<M>bi[M];
bool visprime[N];
ll prime[N];
void oulasai(ll n){
cnt=0;
visprime[1]=1;
L(i,2,n){
if(!visprime[i])prime[++cnt]=i;
L(j,1,cnt){
if(i*prime[j]>n) break;
visprime[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
void solve(){
scanf("%d%d",&n,&t);
L(i,0,n)bi[i].reset();
m=0;ans=0;
L(i,1,n){
scanf("%d%d",&a[i],&b[i]);
L(j,1,i-1){
q[++m]={i,j,abs(a[i]-a[j])+abs(b[i]-b[j])};
}
}
sort(q+1,q+m+1,cmp);
L(i,1,m){
ll x=q[i].x,y=q[i].y,z=q[i].z;//printf("%d ",z);
if(!visprime[z]){
ans+=(bi[x]^bi[y]).count();
}
bi[x][y]=1;
bi[y][x]=1;
}
printf("%d\n",ans);
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);//精度
oulasai(200000);
ll t=1;
scanf("%d",&t);
while(t--)solve();
}
2022杭电多校题解（补题记） 文章被收录于专栏
补完题必写！！
查看25道真题和解析
投递海康威视等公司10个岗位 >