脚本宝典收集整理的这篇文章主要介绍了2021ICPC网络赛第一场部分题解-The 2021 ICPC Asia Regionals Online Contest (I)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
本来应该6题的，结果不知道哪个铸币发了H的clar，当即把我们的思路转向三维几何上。当时我们还在想这三维计算几何的正确率有点太高了还在感叹ICPC选手的含金量，直到赛后我才知道这H题的铸币出题人压根不想让我们知道他脑子里在想什么。还好赛时将机位让给了队友写A，不然抄了你吗半天的三维计算几何最后WA那真的是心态炸了。 其他题倒是没啥好说的，就是这H越想越气，有这瞎琢磨的时间去开个B或者C说不定又能++rank。 真的气。不过突然之间看到F。哦，出题人是原*啊，那就说得通了。
队友写。一开始直接交了发暴力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;
}
比赛时候没开，回来看了下是裸的二维凸包。虽然学过但是比赛没看到也是没用。但是好像要判断什么输入是否正确我就觉得离谱，算法竞赛还要考察ROBUST的嘛？MARK下，回头补。
队友写，图+线段树？
#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;
}
看着样例就直接猜中垂线(也就是(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("%.2lfn",2 * sqrt(a * a + (b-r) * (b - r)) - r);
else printf("%.2lfn", (double)(2*a - r));
}
return 0;
}
在给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;
}
第一个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;
}
队友写，应该是图的遍历（？），反正是模拟。题目太长压根没看，（其实是没学过计网）
#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今年太梦幻了。
以上是脚本宝典为你收集整理的2021ICPC网络赛第一场部分题解-The 2021 ICPC Asia Regionals Online Contest (I)全部内容，希望文章能够帮你解决2021ICPC网络赛第一场部分题解-The 2021 ICPC Asia Regionals Online Contest (I)所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。