当前位置:网站首页>2021ICPC网络赛第一场
2021ICPC网络赛第一场
2022-06-25 06:43:00 【mfy的1号小迷弟】
A Busiest Computing Nodes
题意:
有k个时间片编号为0到k-1,有n个任务,对于每个任务i(从0开始编号),从第i%k个时间片开始往后找到第一个空闲的时间片运行,到k-1后下一个是0。
线段树+二分
二分去找最靠近左边的符合的位置
#include<bits/stdc++.h>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int k,n,h,m=1,mn[maxn<<2],prf[maxn],he[maxn];
void update(int rt,int l,int r,int x,int val){
if(l==r){
mn[rt]=val;
return;
}
int mid=(l+r)>>1;
if(x<=mid)update(lson,x,val);
else update(rson,x,val);
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
int query(int rt,int l,int r,int x,int y){
if(x<=l&&r<=y)return mn[rt];
int mid=(l+r)>>1,ans=INF;
if(x<=mid)ans=min(ans,query(lson,x,y));
if(y>mid)ans=min(ans,query(rson,x,y));
return ans;
}
int main(){
scanf("%d%d",&k,&n);
for(int i=0,x,y;i<n;i++){
scanf("%d%d",&x,&y);
if(i<k){
update(1,0,k-1,i,x+y);he[i]++;
continue;
}
if(mn[1]>x)continue;
int d=i%k,l,r,ans;
int you=query(1,0,k-1,d,k-1);
if(you<=x)
l=d,r=k-1;
else
l=0,r=d-1;
while(l<=r){
int mid=(l+r)>>1;
if(query(1,0,k-1,l,mid)<=x)ans=mid,r=mid-1;
else l=mid+1;
}
update(1,0,k-1,ans,x+y),he[ans]++,m=max(m,he[ans]);
}
for(int i=0;i<k;i++)
if(he[i]==m)prf[++h]=i;
for(int i=1;i<=h;i++){
if(i!=1)printf(" ");
printf("%d",prf[i]);
}
}
D. Edge of Taixuan
题意:
一个1到n编号的图,对于每个[L,R]中的任意两点都有权值为 w i w_i wi的边,现在给出m对 [ L i , R i ] [L_i,R_i] [Li,Ri],求删除一些边后,剩下的边构成最小生成树。
思路:
线段树+思维
把m个 [ L i , R i ] [L_i,R_i] [Li,Ri]按照 w i w_i wi降序排列,后面的边把前面的边(区间)覆盖
#include<bits/stdc++.h>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using ll=long long;
using namespace std;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int t,n,m,c,mn[maxn<<2],lazy[maxn<<2];
struct node{
int l,r,w;
}e[maxn];
bool cmp(node a,node b){
return a.w>b.w;
}
void pushdown(int rt){
if(lazy[rt]){
mn[rt<<1]=mn[rt];
mn[rt<<1|1]=mn[rt];
lazy[rt<<1]=lazy[rt];
lazy[rt<<1|1]=lazy[rt];
lazy[rt]=0;
}
}
void update(int rt,int l,int r,int x,int y,int val){
if(x<=l&&r<=y){
mn[rt]=val;
lazy[rt]=val;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(x<=mid)update(lson,x,y,val);
if(y>mid)update(rson,x,y,val);
}
int query(int rt,int l,int r,int x){
if(l==r)return mn[rt];
int mid=(l+r)>>1;
pushdown(rt);
if(x<=mid)return query(lson,x);
else return query(rson,x);
}
int main(){
scanf("%d",&t);
while(t--){
ll he=0,sum=0,f=0;
scanf("%d%d",&n,&m);
memset(mn,INF,sizeof(mn));
memset(lazy,0,sizeof(lazy));
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].w);
he+=1ll*e[i].w*(e[i].r-e[i].l+1)*(e[i].r-e[i].l)/2;
}
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++)
update(1,1,n-1,e[i].l,e[i].r-1,e[i].w);
for(int i=1;i<n;i++){
int h=query(1,1,n-1,i);
if(h==INF)f=1;
sum+=h;
}
printf("Case #%d: ",++c);
if(f)printf("Gotta prepare a lesson");
else printf("%lld",he-sum);
if(t)printf("\n");
}
}
H. Mesh Analysis
手写离散化
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
struct node{
int id,code,x,y,z;
}e[maxn];
int n,m,t,k,p[maxn],a[maxn],b[maxn];
vector<int>gap[maxn];
map<int,int>mp1,mp2;
set<int>s1,s2;
int main(){
scanf("%d%d",&n,&m);
for(int i=1,s;i<=n;i++){
double x,y,z;
scanf("%d%lf%lf%lf",&s,&x,&y,&z);
}
for(int i=1,id,code,x,y,z;i<=m;i++){
scanf("%d%d%d%d",&id,&code,&x,&y);
e[i]={
id,code,x,y,0};
a[++k]=id,a[++k]=x,a[++k]=y;
if(code==203){
scanf("%d",&z);
e[i].z=z;
a[++k]=z;
}
}
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d",&p[i]);
a[++k]=p[i];
}
for(int i=1;i<=k;i++)b[i]=a[i];
sort(b+1,b+1+k);
int d=1;
for(int i=2;i<=k;i++){
if(b[i]!=b[i-1])b[++d]=b[i];
}
for(int i=1;i<=k;i++){
int s=lower_bound(b+1,b+1+d,a[i])-b;
mp1[a[i]]=s;
mp2[s]=a[i];
}
for(int i=1;i<=m;i++){
int a=mp1[e[i].x],b=mp1[e[i].y],c=mp1[e[i].z];
gap[a].push_back(b);
gap[b].push_back(a);
if(e[i].code==203){
gap[a].push_back(c);
gap[b].push_back(c);
gap[c].push_back(a);
gap[c].push_back(b);
}
}
for(int i=1;i<=t;i++){
s1.clear(),s2.clear();
int q=p[i],dui=mp1[q];
printf("%d\n",q);
if(dui==0){
printf("[][]");
}
else{
for(int i=0;i<gap[dui].size();i++){
s1.insert(mp2[gap[dui][i]]);
}
int f=0;
printf("[");
for(auto x:s1){
if(f)printf(",");
printf("%d",x);
f=1;
}
printf("]\n");
for(int j=1;j<=m;j++){
if(e[j].x==p[i]||e[j].y==p[i]||e[j].z==p[i])s2.insert(e[j].id);
}
f=0;
printf("[");
for(auto x:s2){
if(f)printf(",");
printf("%d",x);
f=1;
}
printf("]");
}
if(i!=t)printf("\n");
}
}
map+set
map<int,set<int>>mp;
mp[123].insert()
for(auto &x:mp[123]){
}
边栏推荐
- C#中如何调整图像大小
- 用函数的递归来解决几道有趣的题
- 50. Pow(x, n)-快速幂
- 一次弄清楚 Handler 可能导致的内存泄漏和解决办法
- 2265. 统计值等于子树平均值的节点数
- Four software 2021-10-14 suitable for beginners to draw PCB
- Take you through the normalization flow of GaN
- One "stone" and two "birds", PCA can effectively improve the dilemma of missing some ground points under the airborne lidar forest
- 机器学习笔记 - 时间序列的线性回归
- 挖掘微生物暗物质——新思路
猜你喜欢
Sword finger offer II 027 Palindrome linked list
(tool class) use SecureCRT as the communication medium
[distillation] pointdistiller: structured knowledge distillationwards efficient and compact 3D detection
Pcb|about FPC reinforcement type
Modular programming of oled12864 display controlled by single chip microcomputer
饮食干预减轻癌症治疗相关症状和毒性
Keil and Proteus joint commissioning
年后求职找B端产品经理?差点把自己坑惨了......
How to use printf of 51 single chip microcomputer
Application of can optical transceiver of ring network redundant can/ optical fiber converter in fire alarm system
随机推荐
50. pow (x, n) - fast power
How much do you know about electronic components on PCB?
2160. minimum sum of the last four digits after splitting
Microsoft Office Word 远程命令执行漏洞(CVE-2022-30190)分析与利用
基于STM32MP157调试MIPI-DSI屏幕
C#获取exe的版本号-文件版本and程序集版本
Requirements for Power PCB circuit board design 2021-11-09
【日常训练】207. 课程表
Analysis of kinsing dual platform mining family virus
搞清信息化是什么,让企业转型升级走上正确的道路
Understand the reasons for impedance matching of PCB circuit board 2021-10-07
[distillation] pointdistiller: structured knowledge distillationwards efficient and compact 3D detection
使用Adobe Acrobat Pro调整PDF页面为统一大小
Import data into Matlab
php入门基础记录
27. remove elements
[single chip microcomputer project training] multipoint temperature wireless acquisition system based on nRF905
取消word文档中某些页面的页眉
网络模型——OSI模型与TCP/IP模型
SCM Project Training