2024 吉林 CCPC

題目鏈接：

Dashboard - The 2024 CCPC National Invitational Contest (Changchun) , The 17th Jilin Provincial Collegiate Programming Contest - Codeforces

L. Recharge（思維、分配）

• 如果k是偶數，(x+y*2)/k
• k為奇數，優先使用y+x的組合

G. Platform Game(模擬)

按照 y 進行排序，由于數據范圍比較小，可以直接枚舉找到小球接下來

落到的平臺。

E. Connect Components (排序、思維)

看到連通塊第一想到的就是并查集，但實際上用不到。

將公式變換，以a[i]-i 從小到大排序，此時前面的i-b[i] 同樣小于后面的就可以

聯通。

可以用一個對頂堆來維護。

每次將后面大于當前的點，加入并查集，并彈出。

但是這樣會漏掉。

如果以a[i]-i和b[i]-i分別排序，進行兩次就可以過。

不確定是不是卡過去，大概率不是

這里可以用小頂堆或者棧，如果后續出現一個較大的值，就將所有小于a[ i ].se的彈出去，

他們都可以形成連通塊，再將最小值給推進去，這樣保證每次都可以用最小值來連接。

int mod=998244353;
struct node{int l,r;
}a[N];
bool cmp(node u,node v){if(u.l==v.l)return u.r<v.r;return u.l<v.l;
}
void solve(){int n;cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;a[i].l=x-i;a[i].r=i-y;}sort(a+1,a+1+n,cmp);stack<int>q;q.push(a[1].r);for(int i=2;i<=n;i++){int f=0,tt;if(q.size()) tt=q.top();while(!q.empty()&&a[i].r>=q.top()){f=1;q.pop();}if(f==1){q.push(tt);}else{q.push(a[i].r);}}cout<<(int)q.size()<<'\n';
}  

D. Parallel Lines

題意：k條平行線 n個點。判斷每一條平行線上，點的x坐標

---

先暴力用第一個點和所有點，計算斜率。其中必有一個斜率是平行線斜率。

• 判斷有哪幾個點在一條平行線上：

可以用直線方程， y=kx+b 將 k ,x , y 帶入，如果b值相同，說明在同一條直線上。

由于直接求斜率會有誤差，可以兩邊同乘 （x1-x2）

• 剪枝：當 b 值 大于 k 個的時候，說明這個斜率是錯誤的
• 注意：一條直線上至少有兩個點。

PII a[N];
void solve()
{int n,k;cin>>n>>k;fir(i,1,n)cin>>a[i].fi>>a[i].se;fir(i,2,n){int dx=a[i].fi-a[1].fi,dy=a[i].se-a[1].se;map<int,vector<int> > mp;fir(i,1,n){int x=a[i].fi*dy-a[i].se*dx;mp[x].push_back(i);if(mp.size()>k) break; }if(mp.size()==k){int f=0;for(auto it:mp){if(it.se.size()==1) f=1;}if(f) continue;for(auto it:mp){cout<<it.se.size()<<' ';for(auto ii:it.se){cout<<ii<<' ';}cout<<'\n';}return;}}         
}