# Test "20201012 test summary"

T1T2 points to the face, T3 directly dissuades.

## T1

Count triangles.

First fix a straight line and find how many triangles it can form with other straight lines. This is good.

Let \ (S \) be the set of all straight lines, \ (k_i \) represent the slope of straight line \ (I \), and \ (c_k \) represent the number of straight lines with slope \ (K \), then the number of triangles that straight line \ (l \) can form with other straight lines is:

\begin{aligned} \frac{1}{2}\sum_{i\in S,k_i\not =k_l}c_{k_i}\times (n-c_{k_l}-c_{k_i})&=\frac{1}{2}\sum_{i\in S,k_i\not =k_l}(c_{k_i}\times (n-c_{k_l})-c_{k_i}^2)\\ &=\frac{1}{2}((n-c_{k_l})\sum_{i\in S,k_i\not =k_l}c_{k_i}-\sum_{i\in S,k_i\not =k_l}c_{k_i}^2)\\ &=\frac{1}{2}((n-c_{k_l})^2-(\sum_{i\in S}c_{k_i}^2-c_{k_l}^2)) \end{aligned}

Discretize the slope and preprocess \ (\ sum {I \ in s} C {K _i} ^ 2 \) and enumerate \ (l \).

Because each triangle will be calculated \ (3 \) times in the end, the final answer will be divided by \ (3 \).

$$\text{Code}:$$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=3e5+5;
typedef long long lxl;

template <typename T>
{
x=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}

int n;
double k[maxn],b[maxn];
int a[maxn];
lxl cnt[maxn],sum;

int main()
{
// freopen("trokuti.in","r",stdin);
// freopen("trokuti.out","w",stdout);
for(int i=1,A,B,C;i<=n;++i)
{
if(!B) k[i]=b[i]=1e9+1;
else k[i]=b[i]=-(double)A/B;
}
sort(b+1,b+n+1);
int m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)
{
a[i]=lower_bound(b+1,b+m+1,k[i])-b;
++cnt[a[i]];
}
for(int i=1;i<=m;++i)
sum+=cnt[i]*cnt[i];
lxl ans=0;
for(int i=1;i<=n;++i)
ans+=1ll*((n-cnt[a[i]])*(n-cnt[a[i]])-(sum-cnt[a[i]]*cnt[a[i]]));
printf("%lld\n",ans/6ll);
return 0;
}


## T2

Use the balanced tree to simulate the inbound process. Each time, find the queue with the smallest number of the tail element in the queue whose tail element number is greater than the inbound number and enter this queue. If there is no such queue, enter a new queue.

Because only the elements at the end of the queue will have an impact, you only need to save the element number at the end of the queue. Query precursors and single point modification are supported. You can use the balance tree.

$$\text{Code}:$$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <climits>
using namespace std;
const int maxn=1e5+5;

template <typename T>
{
x=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}

int n;

struct node
{
int siz,val;
node *ls,*rs;
node(int siz,int val,node *ls,node *rs):siz(siz),val(val),ls(ls),rs(rs){}
node(){}
}*root,*null,*st[maxn<<2],tt[maxn<<2];
const int ratio=4;
int cnt;
#define new_node(a,b,c,d) (&(*st[cnt++]=node(a,b,c,d)))
#define merge(a,b) new_node(a->siz+b->siz,b->val,a,b)

inline void update(node *p)
{
if(!p->ls->siz) return;
p->siz=p->ls->siz+p->rs->siz;
p->val=p->rs->val;
}

inline void rotate(node *p)
{
if(p->ls->siz > p->rs->siz*ratio)
p->rs=merge(p->ls->rs,p->rs),st[--cnt]=p->ls,p->ls=p->ls->ls;
if(p->rs->siz > p->ls->siz*ratio)
p->ls=merge(p->ls,p->rs->ls),st[--cnt]=p->rs,p->rs=p->rs->rs;
}

void insert(node *p,int d)
{
if(p->siz==1)
{
p->ls=new_node(1,min(p->val,d),null,null);
p->rs=new_node(1,max(p->val,d),null,null);
}
else insert(p->ls->val>=d ? p->ls : p->rs,d);
update(p);rotate(p);
}

void erase(node *p,int d)
{
if(p->ls->siz==1&&p->ls->val==d)
st[--cnt]=p->ls,st[--cnt]=p->rs,*p=*p->rs;
else if(p->rs->siz==1&&p->rs->val==d)
st[--cnt]=p->ls,st[--cnt]=p->rs,*p=*p->ls;
else erase(p->ls->val>=d ? p->ls : p->rs,d);
update(p);rotate(p);
}

int kth(node *p,int k)
{
if(p->siz==1) return p->val;
return p->ls->siz>=k ? kth(p->ls,k) : kth(p->rs,k-p->ls->siz);
}

int rnk(node *p,int d)
{
if(p->siz==1) return 1;
return p->ls->val>=d ? rnk(p->ls,d) : p->ls->siz+rnk(p->rs,d);
}

int nxt(int d) {return kth(root,rnk(root,d+1));}

void print(node *p)
{
if(p->siz==1) printf("%d ",p->val);
else print(p->ls),print(p->rs);
}

inline void init()
{
null=new node(0,0,0,0);
for(int i=0;i<=(maxn<<1);++i) st[i]=&tt[i];
root=new_node(1,INT_MAX,null,null);
}

int main()
{
// freopen("manage.in","r",stdin);
// freopen("manage.out","w",stdout);
init();
for(int i=1,p;i<=n;++i)
{
int x=nxt(p);
if(x==INT_MAX)
insert(root,p);
else
{
erase(root,x);
insert(root,p);
}
// print(root);puts("");
}
printf("%d\n",root->siz-1);
return 0;
}


## T3

A randomization algorithm was written in the examination room and got 10pt/kk.

Solution:

• 10 points: any violent method, such as enumerating all possible \ (maxG \) and \ (maxS \), and then judging the connectivity.
• 30 points: sort from small to large according to the \ (g \) attribute, enumerate \ (maxG \), sort all roads that meet the \ (maxG \) attribute from small to large according to the \ (s \) attribute, and then do kruskal, time complexity \ (O(m^2\log m) \).
• 50 point method: on the basis of 30 points, it is found that only one edge is added at a time. Insert it into the last edge set and then do kruskal. The time complexity \ (O(m^2) \).
• 100 points: still sort according to the \ (g \) attribute from small to large. During the process of adding new edges, it is found that the current minimum spanning tree can only be composed of \ (n-1 \) selected from the total \ (n \) edges composed of the edge of the minimum spanning tree without adding new edges and the current new edge. Therefore, maintain a minimum spanning tree edge set, and only make the minimum spanning tree in \ (n \) edges each time, with time complexity \ (O(mn) \).

As for why it is right to do so, just kill the person who wrote the question.

$$\text{Code}:$$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const int maxn=405,maxm=5e4+5;

template <typename T>
{
x=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}

struct edge
{
int u,v;
lxl g,s;
edge(int u,int v,lxl g,lxl s):u(u),v(v),g(g),s(s){}
edge(){}
}e[maxm];

inline bool cmp_g(const edge &a,const edge &b)
{
return a.g<b.g;
}

inline bool cmp_s(const edge &a,const edge &b)
{
return a.s<b.s;
}

int n,m;
int fa[maxn];
lxl wG,wS;

int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

inline lxl Kruskal(vector<edge> &S,vector<edge> &T)
{
for(int i=1;i<=n;++i) fa[i]=i;
T.clear();
sort(S.begin(), S.end(),cmp_s);
int cnt=0;
lxl MaxG=0,MaxS=0;
for(auto e:S)
{
int u=e.u,v=e.v;
int x=find(u),y=find(v);
if(x==y) continue;
MaxG=max(MaxG,e.g);
MaxS=max(MaxS,e.s);
fa[x]=y;
T.push_back(e);
++cnt;
if(cnt==n-1) break;
}
return cnt==n-1?MaxG+MaxS:LLONG_MAX;
}

vector<edge> vec[2];

int main()
{
int u,v;lxl g,s;
for(int i=1;i<=m;++i)
{
e[i]=edge(u,v,g*wG,s*wS);
}
sort(e+1,e+m+1,cmp_g);
lxl ans=LLONG_MAX;
for(int i=1;i<=m;++i)
{
int id=i&1;
vec[id].push_back(e[i]);
ans=min(ans,Kruskal(vec[id],vec[id^1]));
}
printf("%lld\n",ans);
return 0;
}


Posted by brokencode on Thu, 12 May 2022 00:14:50 +0300