脚本宝典收集整理的这篇文章主要介绍了2021 ICPC网络赛第一场，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Powered by:NEFU AB_IN
有 k k k个点（ j = 0 , 1... k j=0,1...k j=0,1...k）， n n n个任务（ i = 0 , 1... n i =0,1...n i=0,1...n），每个任务有到达时间和持续时间，第 i i i个任务从 i % k i%k i%k的点开始往后找有没有空闲的点，如果没有找到则任务作废，问 k k k个点谁接的任务最多
如果暴力查找，从第二个点开始找，找完一遍发现是第一个点，碰到多个这种数据这样肯定会 T T T，所以考虑在查找方面减少复杂度，这里采取线段树+二分+set
/*
* @Author: NEFU AB-iN
* @Date: 2021-09-19 13:03:13
* @FilePath: Contesta.cpp
* @LastEdITTime: 2021-09-19 19:27:05
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N << 2], tr[N << 3], cnt[N];
set<int> s;
map<int, int> m;
void bulid(int i, int l, int r)
{@H_567_360@
if (l == r)
{
tr[i] = 0x3f3f3f3f;
return;
}
int mid = l + r >> 1;
bulid(i << 1, l, mid);
bulid(i << 1 | 1, mid + 1, r);
tr[i] = min(tr[i << 1], tr[i << 1 | 1]);
}
void update(int i, int l, int r, int x, int y)
{
if (l > x || x > r)
return;
if (l == r && l == x)
{
tr[i] = y;
return;
}
int mid = l + r >> 1;
update(i << 1, l, mid, x, y);
update(i << 1 | 1, mid + 1, r, x, y);
tr[i] = min(tr[i << 1], tr[i << 1 | 1]);
}
int query(int i, int l, int r, int x, int y)
{
if (y < l || x > r)
return 0x3f3f3f3f;
if (l >= x && r <= y)
return tr[i];
int mid = l + r >> 1;
return min(query(i << 1, l, mid, x, y), query(i << 1 | 1, mid + 1, r, x, y));
}
int f(int l, int r, int x, int k)
{
if (l == r)
return l;
int mid = (l + r) / 2;
if (query(1, 1, 2 * k, l, mid) < x)
f(l, mid, x, k);
else
f(mid + 1, r, x, k);
}
int main()
{
int k, n;
cin >> k >> n;
bulid(1, 1, 2 * k);
s.insert(0);
m[0] = k;
for (int i = 0; i < n; ++i)
{
int l, time;
cin >> l >> time;
if (*s.begin() >= l)
continue;
if (a[i % k] < l)
{
cnt[i % k]++;
m[a[i % k]]--;
if (m[a[i % k]] == 0)
s.erase(a[i % k]);
a[i % k] = l + time - 1;
if (s.find(a[i % k]) == s.end())
s.insert(a[i % k]);
m[a[i % k]]++;
update(1, 1, 2 * k, (i % k) + 1, l + time - 1);
update(1, 1, 2 * k, (i % k) + k + 1, l + time - 1);
}
else
{
int id = f(i % k + 1, i % k + k, l, k);
id--;
id %= k;
cnt[id]++;
m[a[id]]--;
if (m[a[id]] == 0)
s.erase(a[id]);
a[id] = l + time - 1;
if (s.find(a[id]) == s.end())
s.insert(a[id]);
m[a[id]]++;
update(1, 1, 2 * k, id + 1, l + time - 1);
update(1, 1, 2 * k, id + k + 1, l + time - 1);
}
}
int minx = 0, ans = 0;
for (int i = 0; i < k; i++)
minx = max(minx, cnt[i]);
for (int i = 0; i < k; i++)
{
if (cnt[i] == minx)
{
if (ans)
PRintf(" ");
printf("%d", i);
ans++;
}
}
return 0;
}
几何
/*
* @Author: NEFU AB-IN
* @Date: 2021-09-19 12:04:27
* @FilePath: Contestf.cpp
* @LastEditTime: 2021-09-19 12:28:19
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
{
double a, b, r;
cin >> a >> b >> r;
if (r >= b)
{
printf("Case #%d: %.2fn", i, 2 * a - r);
}
else
{
printf("Case #%d: %.2fn", i, 2 * sqrt(a * a + (b - r) * (b - r)) - r);
}
}
return 0;
}
队友出的，贴一下
/*
* @Author: NEFU AB-IN
* @Date: 2021-09-19 14:44:27
* @FilePath: Contesth.cpp
* @LastEditTime: 2021-09-19 15:01:14
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
set<int> s1[N], s2[N];
map<int, int> map1;
void insert111(int a, int b)
{
if (s1[map1[a]].find(b) == s1[map1[a]].end())
s1[map1[a]].insert(b);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int id, biao, a, b, c;
double x, y, z;
for (int i = 1; i <= n; i++)
{
cin >> id;
map1[id] = i;
cin >> x >> y >> z;
// printf("%lf %lf %lfn", x, y, z);
}
for (int i = 1; i <= m; i++)
{
cin >> id >> biao;
switch (biao)
{
case 102:
cin >> a >> b;
insert111(a, b);
s2[map1[a]].insert(id);
insert111(b, a);
s2[map1[b]].insert(id);
break;
case 203:
cin >> a >> b >> c;
insert111(a, b);
insert111(a, c);
insert111(b, c);
insert111(b, a);
insert111(c, a);
insert111(c, b);
s2[map1[a]].insert(id);
s2[map1[b]].insert(id);
s2[map1[c]].insert(id);
}
}
int t;
cin >> t;
while (t--)
{
cin >> id;
if (map1[id] == 0)
{
printf("%dn[]n[]n", id);
}
else
{
printf("%dn[", id);
for (auto i : s1[map1[id]])
{
if (i != *s1[map1[id]].begin())
printf(",");
printf("%d", i);
}
printf("]n[");
for (auto i : s2[map1[id]])
{
if (i != *s2[map1[id]].begin())
printf(",");
printf("%d", i);
}
printf("]n");
}
}
return 0;
}
签到题，数据范围也不给，考验选手读入能力，点赞
'''
Author: NEFU AB-IN
Date: 2021-09-19 12:10:49
FilePath: Contesti.py
LastEditTime: 2021-09-19 12:12:43
'''
lst = list(map(int, input().split()))
x = int(input())
r = int(input())
lst.sort()
flag = 0
for i in range(len(lst) - 1, -1, -1):
if abs(lst[i] - x) <= r:
print(lst[i], end=" ")
flag = 1
if flag == 0:
print()
模拟即可
/*
* @Author: NEFU AB-IN
* @Date: 2021-09-19 15:03:00
* @FilePath: Contestk.cpp
* @LastEditTime: 2021-09-19 19:55:10
*/
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1e5 + 50;
vector<int> v[N];
int main()
{
int t;
scanf("%d", &t);
for (int k = 1; k <= t; k++)
{
scanf("%d%d", &n, &m);
int xx, u;
for (int i = 1; i <= n; i++)
{
v[i].clear();
cin >> xx;
for (int j = 1; j <= xx; j++)
{
scanf("%d", &u);
v[i].push_back(u);
}
}
printf("Case #%d: n", k);
for (int j = 1; j <= m; j++)
{
bool flag = 0;
scanf("%d %d", &u, &k);
int vv = u, id;
for (int i = 1; i <= k; i++)
{
scanf("%d", &id);
if (id > v[vv].size() || id == 0)
flag = 1;
if (flag == 1)
continue;
vv = v[vv][id - 1];
}
if (flag)
printf("Packet Lossn");
else
{
printf("%dn", vv);
}
}
}
return 0;
}
明天补题。。
以上是脚本宝典为你收集整理的2021 ICPC网络赛第一场全部内容，希望文章能够帮你解决2021 ICPC网络赛第一场所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。