当前位置:网站首页>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]){
}
边栏推荐
- [deep learning lightweight backbone] 2022 edgevits CVPR
- Importer des données dans MATLAB
- 权限、认证系统相关名词概念
- Force deduction 76 questions, minimum covering string
- Buckle 78: subset
- Force deduction 76 questions, minimum covering string
- 判断用户是否是第一次进入某个页面
- Hisilicon 3559 sample parsing: Vio
- Vscode is good, but I won't use it again
- 消息中间件之ActiveMQ的基本使用
猜你喜欢
传统的IO存在什么问题?为什么引入零拷贝的?
realsense d455 semantic_ Slam implements semantic octree mapping
挖掘微生物暗物质——新思路
Use the frame statistics function of the message and waveform recording analyzer royalscope to troubleshoot the accidental faults of the CAN bus
CAN总线工作状况和信号质量“体检”
What are the problems with traditional IO? Why is zero copy introduced?
网络模型——OSI模型与TCP/IP模型
TCP的那点玩意儿
Import data into Matlab
Five causes of PCB board deformation and six solutions 2021-10-08
随机推荐
MySQL interview - the response of executing SQL is relatively slow, and the troubleshooting ideas.
TCP与UDP
Atlas conference vulnerability analysis collection
27. 移除元素
机器学习笔记 - 时间序列的线性回归
CAN透传云网关CANIOT,CANDTU记录CAN报文远程收发CAN数据
C get the version number of exe - file version and assembly version
50. pow (x, n) - fast power
What are the benefits of reserving process edges for PCB production? 2021-10-25
NSIS silent installation vs2013 runtime
Application of can optical transceiver of ring network redundant can/ optical fiber converter in fire alarm system
云计算考试版本1.0
个人域名和企业域名的区别
[Video] ffplay uses MJPEG format to play USB camera
Lebel only wants an asterisk in front of it, but doesn't want to verify it
How much do you know about electronic components on PCB?
三台西门子消防主机FC18配套CAN光端机进行光纤冗余环网组网测试
Atlas conflict Remote Code Execution Vulnerability (cve-2022-26134 vulnerability analysis and protection
How to select lead-free and lead-free tin spraying for PCB? 2021-11-16
【日常训练】207. 课程表