2021ICPC網路賽第一場部分題解-The 2021 ICPC Asia Regionals Online Contest (I)
寫在前面
本來應該6題的，結果不知道哪個鑄幣發了H的clar，當即把我們的思路轉向三維幾何上。當時我們還在想這三維計算幾何的正確率有點太高了還在感嘆ICPC選手的含金量，直到賽後我才知道這H題的鑄幣出題人壓根不想讓我們知道他腦子裡在想什麼。還好賽時將機位讓給了隊友寫A，不然抄了你嗎半天的三維計算幾何最後WA那真的是心態炸了。
其他題倒是沒啥好說的，就是這H越想越氣，有這瞎琢磨的時間去開個B或者C說不定又能++rank。
真的氣。不過突然之間看到F。哦，出題人是原*啊，那就說得通了。
A Busiest Computing Nodes
隊友寫。一開始直接交了發暴力TLE，後來在我想H的時候，用線段樹維護下就過了。
這裡要提一嘴lexicographic了。由於三個大傻子都沒帶字典而且英語水平不夠，於是直接交了個大小順序，過了。後來看Clar不明白為啥要特意說不是字典序。
賽後查了下直接笑出聲。
不是你但凡提下dict我們也能懂啊。擱這考專八呢。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL N=100010;
LL t[N*8],a[N*2];
LL n,k;
LL query(LL l,LL r,LL p,LL x,LL y)
{
if(x<=l&&r<=y)
return t[p];
LL mid=l+r>>1;
if(y<=mid)
return query(l,mid,p<<1,x,y);
if(x>mid)
return query(mid+1,r,p<<1|1,x,y);
return min(query(l,mid,p<<1,x,y),query(mid+1,r,p<<1|1,x,y));
}
void modify(LL l,LL r,LL p,LL x,LL y)
{
if(l==r)
return void(t[p]=y);
LL mid=l+r>>1;
if(x<=mid)
modify(l,mid,p<<1,x,y);
if(x>mid)
modify(mid+1,r,p<<1|1,x,y);
t[p]=min(t[p<<1],t[p<<1|1]);
}
int main()
{
scanf("%lld%lld",&k,&n);
LL res=0;
for(LL i=0;i<n;++i)
{
LL arr,pro;
scanf("%lld%lld",&arr,&pro);
LL l=i%k+1,r=i%k+k;
if(query(1,2*k,1,l,r)>arr)
continue;
while(l<r)
{
LL mid=l+r>>1;
if(query(1,2*k,1,l,mid)<=arr)
r=mid;
else l=mid+1;
}
modify(1,2*k,1,l,arr+pro);
modify(1,2*k,1,(l+k-1)%(2*k)+1,arr+pro);
res=max(res,++a[(l-1)%k+1]);
}
bool flag=false;
for(LL i=1;i<=k;++i)
if(a[i]==res)
if(flag)
printf(" %lld",i-1);
else
{
printf("%lld",i-1);
flag=true;
}
return 0;
}
B Convex Polygon
比賽時候沒開，回來看了下是裸的二維凸包。雖然學過但是比賽沒看到也是沒用。但是好像要判斷什麼輸入是否正確我就覺得離譜，演算法競賽還要考察ROBUST的嘛？MARK下，回頭補。
D Edge of Taixuan
隊友寫，圖+線段樹？
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=100010;
struct Edge
{
int l,r,w;
bool operator < (const Edge &W) const
{
return w<W.w;
}
}e[N];
struct Node
{
LL idx,pri;
}tr[N*4];
int n,m,t;
void pushdown(int p)
{
tr[p<<1]=tr[p];
tr[p<<1|1]=tr[p];
tr[p]={0,0};
}
void modify(int l,int r,int p,int x,int y,int z,int w)
{
if(x<=l&&r<=y)
return void(tr[p]={z,w});
if(tr[p].idx)
pushdown(p);
int mid=l+r>>1;
if(x<=mid)
modify(l,mid,p<<1,x,y,z,w);
if(y>mid)
modify(mid+1,r,p<<1|1,x,y,z,w);
}
LL query(int l,int r,int p)
{
//cout<<l<<' '<<r<<' '<<p<<' '<<tr[p].idx<<' '<<tr[p].pri<<endl;
if(tr[p].idx)
return (LL)(r-l+1)*tr[p].pri;
if(l==r)
return 0;
int mid=l+r>>1;
LL res=query(l,mid,p<<1)+query(mid+1,r,p<<1|1);
return res;
}
bool cmp(Edge &a,Edge &b)
{
return a.l<b.l;
}
bool judge()
{
sort(e+1,e+m+1,cmp);
int l=e[1].l,r=1;
for(int i=1;i<=n;++i)
{
if(e[i].l>r)
return false;
r=max(e[i].r,r);
}
return e[1].l==1&&r==n;
}
int main()
{
bool _=false;
scanf("%d",&t);
for(int i=1;i<=t;++i)
{
memset(tr,0,sizeof tr);
LL res=0;
scanf("%d%d",&n,&m);
for(int j=1;j<=m;++j)
{
scanf("%d%d%d",&e[j].l,&e[j].r,&e[j].w);
res+=(LL)(e[j].r-e[j].l+1)*(e[j].r-e[j].l)/2*e[j].w;
}
sort(e+1,e+m+1);
for(int j=m;j>=1;--j)
modify(1,n,1,e[j].l+1,e[j].r,e[j].l,e[j].w);
if(_)
puts("");
_=true;
if(judge())
{
res-=query(1,n,1);
printf("Case #%d: %lld",i,res);
}
else
printf("Case #%d: Gotta prepare a lesson",i);
}
return 0;
}
F Land Overseer
看著樣例就直接猜中垂線(也就是(a,b-r)這個點，以及它和(2a,0)的連線和第二個圓的交點)，於是直接輸出2sqrt(aa+(b-r)*(b-r))-r交一發WA。後來就開始用純數學方法計算距離方程，結果是不管用什麼方法都做不出來，最主要的是其他比較合理的猜想都驗證不了樣例這個數據。最後思路回到原點，發現假如A圓的最低點低於X軸，也就是b<=r的時候，直接沿x軸走到圓B更近，遂加上特判，AC。這題不需要考慮兩圓相交，O在圓內之類的情況，因為條件已經將其排除。所以還是相當簡單的題目
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;cin >> t;
for (int i = 1;i <= t;++i) {
long long a,b,r;
cin >> a >> b >> r;
cout <<"Case #" << i << ": ";
if(b > r)
printf("%.2lf\n",2 * sqrt(a * a + (b-r) * (b - r)) - r);
else printf("%.2lf\n", (double)(2*a - r));
}
return 0;
}
H Mesh Analysis
在給Clar之前，讀完題我說：這neighboring不會是和它一起構成這個圖形的點吧。看了Clar，哦，原來要考慮在三角形內部的點啊，還是三維，挺難的。遂開始抄板子……
用set保存每個點相連的點以及屬於的圖形即可（因為會重複），最好用unordered_map映射下，誰知道id範圍是多少呢。
對，這題2~n+1行的輸入完全沒用。服了。
輸出要稍微考慮下，注意最後不能空行，空集輸出[]，也不是很難。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<ll,set<ll> > belongel;
unordered_map<ll,set<ll> > belongpo;
int main() {
int n,m;
cin >> n >> m;
for (int i = 0;i < n;++i) {
ll id;
double x,y,z;
cin >> id >> x >> y >> z;
}
for (int i = 0;i < m;++i) {
ll id,idx;
cin >> id >> idx;
if (idx == 102) {
ll x,y;
cin >> x >> y;
belongpo[x].insert(y);
belongpo[y].insert(x);
belongel[x].insert(id);
belongel[y].insert(id);
}else{
ll x,y,z;
cin >> x >> y >> z;
belongpo[x].insert(y);
belongpo[x].insert(z);
belongpo[y].insert(x);
belongpo[y].insert(z);
belongpo[z].insert(x);
belongpo[z].insert(y);
belongel[x].insert(id);
belongel[y].insert(id);
belongel[z].insert(id);
}
}
int L;cin >> L;
bool fir = 1;
while (L--) {
if (fir){
fir = false;
}else{
cout << endl;
}
ll id ;cin >> id;
cout << id << endl;
bool _ = true;
//point
set<ll> &outt = belongpo[id];
if (outt.empty()){
cout <<"[]\n";
_ = false;
}
if (_){
cout << '[';
for (auto it : outt) {
if (it != *outt.begin()) cout << ',';
cout << it;
}
cout << "]\n";
}
_ = true;
set<ll> &oute = belongel[id];
if (oute.empty()) {
cout << "[]";
_ = false;
}
if (_){
cout << '[';
for (auto it : oute) {
if (it != *oute.begin()) cout << ',';
cout << it;
}
cout << ']';
}
}
return 0;
}
I Neiborhood Search
第一個A的題目。題意：在數軸上找到被A為圓心，R為半徑包圍且屬於集合S的元素（除它自己）。這題關鍵是輸入，我們想了個辦法，先while(cin >> x)讀到eof，並且記錄個數n，然後最後兩個數拎出來為A和R，最後排序前n-2個元素找就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
long long tmp[maxn];
long long a[maxn];
int main() {
int n = 0;
long long x;
while (cin >> x) {
tmp[n++] = x;
}
n = n - 3;
sort(tmp,tmp+n+1);
long long A = tmp[n + 1];
long long r = tmp[n + 2];
//cout << A << ' ' << r << endl;
bool f = false;
for (int i = n;i >= 0;--i) {
if (tmp[i] <= A + r && tmp[i] >= A - r) {
cout << tmp[i] << ' ';
f = true;
}
}
if(!f) cout << '\n';
return 0;
}
K Segment Routing
隊友寫，應該是圖的遍歷（？），反正是模擬。題目太長壓根沒看，（其實是沒學過計網）
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=100010,M=2000010;
int t,n,m,h[N],e[M],d[N],r[N];
int main()
{
scanf("%d",&t);
bool _=false;
for(int i=1;i<=t;++i)
{
if(_) puts("");
_=true;
printf("Case #%d: ",i);
scanf("%d%d",&n,&m);
for(int j=1;j<=n;++j)
{
scanf("%d",&d[j]);
h[j]=h[j-1]+d[j-1];
for(int k=1;k<=d[j];++k)
scanf("%d",&e[h[j]+k-1]);
}
for(int j=1;j<=m;++j)
{
int s,l;
scanf("%d%d",&s,&l);
for(int k=1;k<=l;++k)
scanf("%d",&r[k]);
bool flag=true;
for(int k=1;k<=l&&flag;++k)
{
if(r[k]>d[s])
flag=false;
s=e[h[s]+r[k]-1];
if(s>n)
flag=false;
}
puts("");
if(flag)
printf("%d",s);
else
printf("Packet Loss");
}
}
return 0;
}
總結
下場總不是華為出題了吧。XCPC今年太夢幻了。
