Codeforces 2018-2019 ICPC, NEERC, Southern Subregional Contest

2018-2019 ICPC, NEERC, Southern Subregional Contest

闲谈:

  被操哥和男神带飞的一场ACM,第一把做了这么多题,荣幸成为7题队,虽然比赛的时候频频出锅,差点被鸽,但还算打完了5h

  总的来说这场还是不算难的,7题还是少了点


A

题目:

  给出a,b,求出一个数满足是a的倍数,且数字和为b

题解:

  男神懒得写博客就甩锅了

  直接宽搜,宽搜时队列中的状态保存为x,y,x表示当前的数%a==x,y表示数字和

  然后记录状态和方案就行了

参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=,M=;
struct node {
int x,y; // %A=x, 和为y , 上一个为k
} a[N][M],from[N][M],list[N*M*]; int head,tail;
bool v[N][M]; int ans[];
int main() {
int A,B; scanf("%d%d",&A,&B);
head=; tail=; list[]=(node){,};
memset(v,false,sizeof(v)); v[][]=true;
while(head!=tail) {
int x=list[head].x,y=list[head].y;
for(int i=;i<=;i++) {
int tx=(x*+i)%A,ty=y+i;
if(v[tx][ty]==true||ty>B) continue;
v[tx][ty]=true;
from[tx][ty]=(node){x,y};
list[tail++]=(node){tx,ty};
} head++;
}
int len=;
int x=,y=B;
if(v[][B]==false) { printf("-1\n"); return ; }
while(x!=||y!=) {
int tx=from[x][y].x,ty=from[x][y].y;
ans[++len]=y-ty; x=tx; y=ty;
}
for(int i=len;i>=;i--) printf("%d",ans[i]);
printf("\n");
return ;
}

A(男神)


B(*)

题目:

  给出n个IPv4地址,表示n个区间

  形如a.b.c.d/x,相当于左端点为a*224+b*216+c*28+d,长度为232-x的区间(若形如a.b.c.d则与a.b.c.d/32相同)

  每个区间有颜色,黑区间或白区间,剩下没给出的地址中(也就是从0.0.0.0到255.255.255.255中没被覆盖的地址)非黑非白

  PS:这道题IPv4地址的定义是a.b.c.d/x中a*224+b*216+c*28+d的二进制位中后32-x位必须都是0

  求出最少的区间(以IPv4地址形式)能够覆盖所有黑区间(非黑非白的地址可以被覆盖,但是白区间不能被覆盖)

题解:

  用01字典树来做

  首先按照给出的区间的左端点的二进制位从大到小x位插进字典树中,之所以只插x位是因为这段区间实际上就是以插进最后一位的所在节点的满子树(也就是所有点都有01孩子(深度不超过32))

  那我们就可以用一个节点来表示一段区间,并可以保证满足IPv4的定义

  然后我们对字典树上的点染色,黑色区间左端点插字典树的时候就将点值或1,白色就将点值或2

  那么整棵字典树上,显然点值为1的节点就表示这个点可以用来覆盖黑区间(因为不受白区间影响)

  我们就可以直接DFS求出最少的点来覆盖所有叶子节点,那肯定是找到的点深度越浅越好

  对于-1的情况,就提前排序判断一下区间重叠的情况就行了

参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
struct bw
{
LL l;int d,col;
}p[];
bool cmp(bw n1,bw n2){return n1.l<n2.l;}
char st[];
void read(int x)
{
scanf("%s",st+);
int col;
if(st[]=='+') col=;
else col=;
int len=strlen(st+);
int b=;
LL l=,r=,d=;
for(int i=;i<=len;i++)
{
if(st[i]=='.')
{
l+=d*(1LL<<b);
b-=;d=;
}
else if(st[i]=='/')
{
l+=d*(1LL<<b);
d=;for(int j=i+;j<=len;j++) d=d*+st[j]-'';
break;
}
else
{
d=d*+st[i]-'';
if(i==len) l+=d*(1LL<<b),r=l,d=;
}
}
p[x]=(bw){l,-d,col};
}
struct trie
{
int c[],col;
trie()
{
col=;
memset(c,-,sizeof(c));
}
}t[];int tot;
struct answer
{
LL d;int x;
}ans[];int cnt;
void dfs(int x,LL k,int dep)
{
if(t[x].col==)
{
ans[++cnt]=(answer){k,dep};
return ;
}
if(t[x].c[]!=-) dfs(t[x].c[],k,dep-);
if(t[x].c[]!=-) dfs(t[x].c[],k+(1LL<<(dep-)),dep-);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) read(i);
sort(p+,p+n+,cmp);
for(int i=;i<n;i++)
{
if(p[i].col!=p[i+].col&&p[i].l+(1LL<<p[i].d)->=p[i+].l)
{
printf("-1\n");
return ;
}
}
tot=;
for(int i=;i<=n;i++)
{
LL l=p[i].l;int d=p[i].d,col=p[i].col;
int x=;t[x].col|=col;
for(int j=;j>=d;j--)
{
int y=(l>>j)&;
if(t[x].c[y]==-) t[x].c[y]=++tot;
x=t[x].c[y];t[x].col|=col;
}
}
cnt=;dfs(,,);
printf("%d\n",cnt);
LL mk=(<<)-;
for(int i=;i<=cnt;i++)
{
LL d=ans[i].d;
printf("%lld.%lld.%lld.%lld/%d\n",(d>>)&mk,(d>>)&mk,(d>>)&mk,d&mk,-ans[i].x);
}
return ;
}

B


C

咕咕咕:

  本来可以提前2hA掉的题目,结果因为男神没开long long,主席树又爆空间,贡献13发罚时

  结果操哥直接就又写了一发扫描线过掉了,结果男神重开long long,也过了

  一题两种解法。。直接出门直走[飞机]


D

咕咕咕:

  男神一波甩锅[飞机]


E(*)

题目:

  给出n个任务,每个任务有它需要花费的时间,每做完m个任务就要休息等同于做完这m个任务所需要的时间的时间

  求出一个值d,表示只有花费的时间<=d的任务才会被完成

  在符合d的条件下,任务需要按照初始的顺序依次完成

  给出总时间t,要求做完任务的时间(包括休息时间)要<=t,若完成了最后想要完成的任务后需要休息时,可以不休息,但也不能再做任务了

  求出一个d,使得能做完的任务尽量多,求出最大可完成任务数和任意一个能得到最大可完成任务数的d值

题解:

  一眼二分题(虽说是赛后才A的)

  先将原花费时间排序去重,然后二分位置,因为d值一定可以为其中一个任务的花费时间

  然后很容易想到实际上排序后每个任务的花费时间作为d值来求出的任务数,是呈单峰的

  那么我们就可以二分,然后对于前后的取值判断当前在单峰的哪个位置,然后再继续二分就好了

参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
int a[],s[];
int n,m;LL t;
int check(int x)
{
x=s[x];
int ans=,d=;
LL tt=,t1=;
for(int i=;i<=n;i++)
{
if(a[i]>x) continue;
if(tt+a[i]>t) return ans;
tt+=a[i];
t1+=a[i];d++;
ans++;
if(d==m)
{
if(tt+t1>t) return ans;
tt+=t1;
t1=;d=;
}
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%lld",&n,&m,&t);
for(int i=;i<=n;i++) scanf("%d",&a[i]),s[i]=a[i];
sort(s+,s+n+);int len=unique(s+,s+n+)-s-;
int l=,r=len,sum=,ans=;
while(l<=r)
{
int mid=(l+r)/;
int d=check(mid);
if(d>sum) sum=d,ans=mid;
if(check(mid+)>d) l=mid+;
else r=mid-;
}
printf("%d %lld\n",sum,min(t,LL(s[ans])));
}
return ;
}

E


F

题目:

  当前,有两位参与选拔的人Alice和Bob,有n个观众,每个观众有自己的影响力

  每个观众要么谁都不支持,要么支持Alice,要么支持Bob,要么两个都支持

  现在选拔现场的工作人员想要选出若干个观众来到现场(设人数为m),若a为支持Alice的人数,b为支持Bob的人数

  则现场的观众必须满足2a>=m且2b>=m,求出满足情况的条件下,能够请到的观众的影响力之和最大

题解:

  赤裸裸的贪心,比赛的时候叫AKC验了想法,就直接做了

  首先对于两者都支持的观众一定可以选,因为他们都对a,b有贡献,而只会让m+1,所以无论什么情况都可以请

  然后用三个大根堆分别保存只支持Alice和只支持Bob和谁都不支持的影响力

  然后在两者都有值的情况下,分别取两个堆的堆顶加到答案里,因为这样会使得a+1,b+1,m+2,也是不影响答案的

  接下来对于剩下的一个堆,和谁都不支持的堆,显然接下来只能取m-2*(若剩下的堆支持Alice,则为b,若支持Bob,则为a)

  因为直到最后一步为止,a和b的值一直是相等的,所以对于哪个堆已经被取完,哪个堆的a或b就会成为约束条件

  然后将剩下的堆和谁都不支持的堆合起来取最大的m-2*(a或b)个影响力就行了

参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
char st[];
int id()
{
if(st[]=='')
{
if(st[]=='') return ;
else return ;
}
else
{
if(st[]=='') return ;
else return ;
}
}
priority_queue<LL> A;
priority_queue<LL> B;
priority_queue<LL> C;
int main()
{
int n;
scanf("%d",&n);
LL ans=,a=,b=,m=;
for(int i=;i<=n;i++)
{
LL d;
scanf("%s%lld",st+,&d);
int p=id();
if(p==) A.push(d);
if(p==) B.push(d);
if(p==) C.push(d);
if(p==) ans+=d,m++,a++,b++;
}
while(A.empty()==&&B.empty()==)
{
ans+=A.top();
ans+=B.top();
a++;b++;m+=;
A.pop();B.pop();
}
if(A.empty()!=&&B.empty()!=)
{
while(2LL*a>=(m+)&&C.empty()==)
{
ans+=C.top();
m++;C.pop();
}
}
else
{
if(A.empty()==)
{
LL d=2LL*a-m;
while(d!=)
{
if(A.empty()!=&&C.empty()!=) break;
else if(A.empty()!=&&C.empty()==) ans+=C.top(),C.pop();
else if(C.empty()!=&&A.empty()==) ans+=A.top(),A.pop();
else if(A.top()>C.top()) ans+=A.top(),A.pop();
else ans+=C.top(),C.pop();
d--;
}
}
else
{
LL d=2LL*a-m;
while(d!=)
{
if(B.empty()!=&&C.empty()!=) break;
else if(B.empty()!=&&C.empty()==) ans+=C.top(),C.pop();
else if(C.empty()!=&&B.empty()==) ans+=B.top(),B.pop();
else if(B.top()>C.top()) ans+=B.top(),B.pop();
else ans+=C.top(),C.pop();
d--;
}
}
}
printf("%lld\n",ans);
return ;
}

F


G

咕咕咕:

  因为是AKC的,所以甩锅,出门直走[飞机]

  最后一小时捡的漏


H

题目:

  给出n个模式串,有Q个询问,每个询问给出一个字符串,求出这个字符串是多少个模式串的子串,并求出任意一个模式串

题解:

  签到题,直接字典树保存Q个询问的字符串,然后枚举每个模式串的每个子串,然后在字典树上跑,跑到尽头的时候将当前字典树的点权+1就行了

  然后判一下一个模式串中有多个相同子串的情况就行了

参考代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
char st[][];
char a[];
struct trie
{
int c[],s,t;
trie()
{
memset(c,-,sizeof(c));
}
}t[];int tot;
int to[];
int id(char cc)
{
if(cc>=''&&cc<='') return cc-''+;
if(cc>='a'&&cc<='z') return cc-'a'++;
return ;
}
void bt(int p)
{
int x=,len=strlen(a+);
for(int i=;i<=len;i++)
{
int y=id(a[i]);
if(t[x].c[y]==-) t[x].c[y]=++tot;
x=t[x].c[y];
}
to[p]=x;
}
int v[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%s",st[i]+);
int Q;
scanf("%d",&Q);
tot=;
for(int i=;i<=Q;i++)
{
scanf("%s",a+);
bt(i);
}
memset(v,,sizeof(v));
for(int i=;i<=n;i++)
{
int len=strlen(st[i]+);
for(int l=;l<=len;l++)
{
int x=;
for(int r=l;r<=len;r++)
{
int y=id(st[i][r]);
if(t[x].c[y]==-) break;
x=t[x].c[y];
if(v[x]!=i)
{
v[x]=i;
t[x].s++;
t[x].t=i;
}
}
}
}
for(int i=;i<=Q;i++)
{
printf("%d ",t[to[i]].s);
if(t[to[i]].s==) printf("-\n");
else printf("%s\n",st[t[to[i]].t]+);
}
return ;
}

H


I(*)

咕咕咕:

  赛后甩锅大法好[飞机]


J(*)

咕咕咕:

  甩锅大法好[飞机]


K

题目:

  给出n个数,要分成连续的k段,使得每段的和相同

  若有合法分段的的情况就输出Yes并输出每一段的数的个数

  否则输出No

题解:

  签到题,直接乱搞就行了,水题

参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int a[];
int ans[];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int sum=;
for(int i=;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
int tot=;
if(sum%k!=) printf("No\n");
else
{
sum/=k;int d=,cnt=;
int kk=;
for(int i=;i<=n;i++)
{
d+=a[i];cnt++;
if(d>sum){printf("No\n");return ;}
if(d==sum)
{
ans[++kk]=cnt;
cnt=;d=;
}
}
printf("Yes\n");
for(int i=;i<k;i++) printf("%d ",ans[i]);
printf("%d\n",ans[k]);
}
return ;
}

K


L(*)

咕咕咕:

  究极甩锅[飞机]

上一篇:窗体的扩展样式GWL_EXSTYLE用于SetWindowLong


下一篇:javascript--BOM对象