T1.

大力并查集一下就ok

考试的时候差点把n+1写成n，幸好最后时候检查出来了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 2005using namespace std;long long x[N],y[N],z[N];int a[N];int n,T;long long h,r;long long heickr(long long x){ return x*x;}int find(int x){ if (x==a[x]) return x; a[x]=find(a[x]); return a[x];}void make(int x,int y){ a[find(x)]=find(y);}int main(){ scanf("%d",&T); while (T--){ scanf("%d%lld%lld",&n,&h,&r); for (int i=0;i<=n+1;i++) a[i]=i; for (int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]); for (int i=1;i<=n;i++){ if (z[i]-r<=0) make(0,i); } for (int i=1;i<=n;i++){ if (z[i]+r>=h) make(i,n+1); } for (int i=1;i
          
         
        
       
      
     

T2.

其实是一道傻逼题，考场上最后时候想出来了，但是没有写粗来，来不及了

考虑暴力枚举从哪个点开始

然后进行dfs，用dp[i]表示已经打通的集合状态为i的最小代价

只有在集合中的元素才有dis值

然后暴力进行dfs，枚举j和k（j在集合中，k不在），表示打通j和k，然后计算一波贡献

讲k加入集合，给kdis值，注意回溯的时候还原k的dis即可

代码：

#include
     
      #define N 15using namespace std;int dp[1<
      
       1e9) continue;					int now=(1<<(j-1))+S;					if (dp[now]>dp[S]+f[i][j]*dis[i]){						dp[now]=dp[S]+dis[i]*f[i][j];						int tmp=dis[j];						dis[j]=dis[i]+1;						dfs(now);						dis[j]=tmp;					}				}			}		}	}}inline void solve(int x){	memset(dp,127,sizeof(dp));	memset(dis,127,sizeof(dis));	dp[1<<(x-1)]=0;dis[x]=1;	dfs(1<<(x-1));	ans=min(ans,dp[(1<
      
     

T3.当时太单纯了，以为noip一定不会考数据结构，于是就想了半天都没有结果，然后敲了一个50分大暴力上去（最后还只拿了30分）<---弱

其实说真的，这题也不是很难，只要弄清楚它的操作过程的特点就行了

我们对于每一行开一棵动态开点线段树维护它除了最后一列的情况，然后0表示这个位置还存在，1表示没有了(这样就可以操作了，不会因为空间问题了)

对于最后一列我们专门开一个动态开点线段树来维护(之后动态开点线段树都简称为线段树)

然后对于每行以及最后一列开一个vector来存放后来放进去的元素

然后每次查询，假设查到的是线段树中第x位置，那么判断x<m还是>=m

如果<m说明是原来的，直接算

如果>=m说明后来进来的，直接在vector中查询即可,行列均同理的呀

注意特判查询的时候y==m的情况

代码:

#include
     
      #define N 9000005#define M 300005using namespace std;int d[N],ls[N],rs[N],root[M],n,m,x,y,Q,tot,cnt;vector
      
       G[M];void insert(int &k,int l,int r,int x){    if (!k) k=++cnt; d[k]++; if (l==r) return;    int mid=(l+r)>>1; if (x<=mid) insert(ls[k],l,mid,x);    else if (x>mid) insert(rs[k],mid+1,r,x);}int query(int k,int l,int r,int kth){    if (l==r) return l; int mid=(l+r)>>1;    int summ=mid-l+1-d[ls[k]]; if (summ>=kth) return query(ls[k],l,mid,kth);    else if (summ