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(*)
咕咕咕：
究极甩锅[飞机]