T1
并查集维护联通图
预计得分100
#include<stdio.h>
#include<iostream>
#include<cmath>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
typedef long long ll;
typedef double db;
const int BIG=2333;
int f[BIG];
int n,T;
int s1[BIG],s2[BIG];
struct node{
ll x,y,z;
}p[BIG];
ll h,r;
int fi,fj;
inline int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
inline ll dis(int i,int j){
return -1ll*r*r+1ll*(p[i].x-p[j].x)*(p[i].x-p[j].x)-1ll*r*r+1ll*(p[i].y-p[j].y)*(p[i].y-p[j].y)-1ll*r*r+1ll*(p[i].z-p[j].z)*(p[i].z-p[j].z)-1ll*r*r;
}
int main(){
scanf("%d",&T);
die:;
while(T--){
scanf("%d%lld%lld",&n,&h,&r);
FOR(i,1,n)f[i]=i,s1[i]=s2[i]=0;
FOR(i,1,n)scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);
FOR(i,1,n)
FOR(j,i+1,n){
if(dis(i,j)<=0){
fi=find(i);
fj=find(j);
if(fi!=fj)f[fi]=fj;
}
}
FOR(i,1,n){
if(p[i].z-r<=0&&p[i].z+r>=0)
s1[find(i)]=1;
if(p[i].z-r<=h&&p[i].z+r>=h)
s2[find(i)]=1;
}
FOR(i,1,n)
if(s1[i]==1&&s2[i]==1){
puts("Yes");
goto die;
}
puts("No");
}
return 0;
}
T2
搜索+最优性剪枝
luogu上水过90
那就预计得分90
#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
int ans;
int dis[25][25];
int f[25];
int nxt[2333],las[25],to[2333],dep[25];
int w[2333];
int n,m,M;
int z;
int x,y,cnt,num,tot;
struct edge{
int l;
int r;
int v;
inline bool operator<(edge A)const{
return v<A.v;
}
}e[2333];
const int inf=(1<<28);
int p[2333];
inline void add(int x,int y,int z){
nxt[++tot]=las[x];
las[x]=tot;
to[tot]=y;
w[tot]=z;
}
inline int find(int x){
return f[x]==x?x:find(f[x]);
}
queue<int>q;
inline void bfs(int s){
int sum=0;
while(!q.empty())q.pop();
FOR(i,1,n)dep[i]=0;
dep[s]=1;
int now;
q.push(s);
while(!q.empty()){
now=q.front();
q.pop();
for(register int e=las[now];e;e=nxt[e])
if(!dep[to[e]]){
dep[to[e]]=dep[now]+1;
q.push(to[e]);
sum=sum+1ll*w[e]*dep[now];
}
}
ans=min(ans,sum);
}
inline void calc(){
tot=0;
for(register int i=1;i<=n;++i)
las[i]=0;
for(register int i=1;i<n;++i){
add(e[p[i]].l,e[p[i]].r,e[p[i]].v);
add(e[p[i]].r,e[p[i]].l,e[p[i]].v);
}
FOR(i,1,n)bfs(i);
}
inline void dfs(int t,int st,int sum){
if(sum>=ans)
return;
if(t==n){
calc();
return;
}
int l,r;
for(register int i=st;i<=cnt;++i){
l=find(e[i].l);
r=find(e[i].r);
if(l!=r){
p[t]=i;
f[l]=r;
dfs(t+1,i+1,sum+e[i].v);
f[l]=l;
}
}
}
inline int read(){
char c;while(c=getchar(),c==' '||c=='
');int data=c-48;
while(c=getchar(),c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data;
}
int main(){
n=read();m=read();
FOR(i,1,n)FOR(j,1,n)dis[i][j]=inf;
FOR(i,1,n)dis[i][i]=0;
FOR(i,1,n)f[i]=i;
FOR(i,1,m){
x=read();y=read();z=read();
dis[x][y]=min(dis[x][y],z);
dis[y][x]=min(dis[y][x],z);
}
FOR(i,1,n)FOR(j,i+1,n)if(dis[i][j]!=inf)e[++cnt]=(edge){i,j,dis[i][j]};
sort(e+1,e+cnt+1);
ans=inf;
dfs(1,1,0);
printf("%d
",ans);
return 0;
}
T3
30分暴力+10分块状链表
好像块状链表写挂了
预计得分30
#include<stdio.h>
#include<iostream>
#include<math.h>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
int nxt[200005],af[200005],sz[2001],to[200005],be[2001];
const int big=1001;
int a[5001][5001];
int blo,cnt;
int n,m,t,num,x,y;
inline int read(){
char c;while(c=getchar(),c==' '||c=='
');int data=c-48;
while(c=getchar(),c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data;
}
inline void solve1(){
blo=sqrt(m);
FOR(i,1,m){
if(i%blo==1)be[(i-1)/blo+1]=i;
nxt[i]=i-1;
++sz[(i-1)/blo+1];
to[i]=i;
af[i]=i+1;
}
register int i,j;
cnt=m;
while(t--){
x=read();y=read();
for(i=1;i<=blo<<1|1;++i)
if(y>sz[i])y-=sz[i];
else break;
for(j=be[i];;){
--y;
if(!y)break;
j=af[j];
}
printf("%d
",to[j]);
++cnt;
if(cnt%blo==1)be[(cnt-1)/blo+1]=cnt;
nxt[cnt]=cnt-1;
++sz[(cnt-1)/blo+1];
to[cnt]=to[j];
af[cnt]=cnt+1;
nxt[af[j]]=nxt[j];
af[nxt[j]]=af[j];
--sz[(j-1)/blo+1];
if(j%blo==1)
be[(j-1)/blo+1]=af[j];
}
return;
}
inline void solve2(){
FOR(i,1,n)FOR(j,1,m)a[i][j]=(i-1)*m+j;
while(t--){
x=read();y=read();
num=a[x][y];
a[x][y]=0;
FOR(i,y,m)a[x][i]=a[x][i+1];
FOR(i,x,n)a[i][m]=a[i+1][m];
a[n][m]=num;
printf("%d
",num);
}
}
int main(){
n=read();m=read();t=read();
if(n<=1000&&m<=1000){
solve2();
return 0;
}
if(n==1){
solve1();
return 0;
}
solve2();
return 0;
}
Day2得分100+90+30=220
NOIP2017总得分 100+50+30+100+90+30=400
Day2考得比Day1好[吐血]