| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/12 | O | Ø | O | O | Ø | . | O | O | O | Ø | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：2015-2016 NEERC Moscow Subregional Contest
A Anagrams
题目描述
$b$进制下，$x$和$y$称为$b-anagram$当且仅当$y$是由$x$数位变换得到的。
$k$被称作$b-stable$当且仅当任意能被$k$整除的$m$，其所有$b-anagram$都能被$k$整除。
给定$b$，求出所有$b-stable$。
解题思路
打表发现（？答案就是$b-1$的因数
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
typedef long long ll;
int n;
int main()
{
cin >>n ;
int inf=sqrt(n-1)+0.1;
vector<int> ans;
for(int i=1;i<=inf;i++){
if((n-1)%i==0){
ans.push_back(i);
if(i!=(n-1)/i) ans.push_back((n-1)/i);
}
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
}
B Banana Brain’s Bracelet
题目描述
有一个绕成一圈的字符串$A$，求一个最长的$A$的子串$B$满足$B$绕成一圈后，$C$是$B$的子串。
解题思路
绕成一圈的字符串$A$中选择子串，等价于将$A$扩充为$AA$之后选择一段长度$\leq strlen(A)$的子串。设$A’=AA$。
显然可以将$C$划分为前缀和后缀。现在要求的就是：$A ‘$中，选择出一段靠后的$C$的前缀$c_1…c_{l}$，靠前的$C$的后缀$c_{l+1}…c_{strlen(c)}$。枚举前缀的长度$l$，如果能够知道对于每个$i$，其能够向后匹配的最长$A’$前缀的长度，那便能求出对于每个$i$，其能够向前匹配的最长$A’$后缀的长度（翻转字符串求出即可），就能用$set$存储所有$len\geq strlen(c)-l$的后缀匹配的终止下标，从而$O(\log n)$地更新答案。
然后这就是个$z-box$模板。$z-box$和$exkmp$有异曲同工之妙，因此本题也可用$exkmp$求解。注意$kmp$求出的$next$是不容易求出对于每个$i$向后匹配的最大长度的，不能够直接用$kmp$更新。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef long long ll;
using namespace std;
char c[N],revc[N],a[N],b[N];
vector<int>pre[N],suf[N];
set<int>S;//合法后缀对应前缀
int len1[N],len2[N];//i开头maxlen
void getzbox(int box[],char a[],int len){
int i,l=0,r=0,now;
for(i=1;i<len;i++){
if(i>r){
now=0;while(a[now]==a[now+i])now++;
if(now){
r=i+now-1;
l=i;
}
box[i]=now;
}else{
if(box[i-l]<r-i+1)box[i]=box[i-l];
else{
now=1;while(a[r+now]==a[r+now-i])now++;
box[i]=r-i+now;
r+=now-1;
l=i;
}
}
}
}
int main(){
int i;
scanf("%s%s",a,b);int la=strlen(a),lb=strlen(b);
for(i=0;i<lb;i++)c[i]=b[i];
for(i=0;i<lb;i++)revc[i]=c[lb-1-i];
c[lb]=revc[lb]='#';
for(i=0;i<la;i++)c[i+lb+1]=c[i+lb+la+1]=a[i];
for(i=0;i<2*la;i++)revc[i+lb+1]=c[lb+2*la-i];
getzbox(len1,c,lb+2*la+1);
getzbox(len2,revc,lb+2*la+1);
for(i=lb+1;i<lb+2*la+1;i++){
pre[len1[i]].push_back(i-(lb+1));//prefix最左下标
suf[len2[i]].push_back(lb+2*la-i);//suffix最右下标
}
int ans=-1;
for(i=0;i<=lb;i++){
for(auto j:suf[lb-i])S.insert(j);//S: 长度>=lb-i的后缀，最左下标的集合
for(auto j:pre[i]){
auto k=S.lower_bound(j-la+(lb-1));//保证长度<=la
int num=*k;
if(k!=S.end()&&(*k)<j)
ans=max(ans,j-(*k)+lb-1);
}
}
printf("%d",ans);
return 0;
}
C Colder-Hotter
题目描述
交互题，二维平面上有一个点，每次告诉你这次询问的点比上次询问的点离这个点近还是远，求出这个点。
解题思路
分别对$x,y$二分查找即可。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
typedef long long ll;
int x,y;
int L=1,R=0;
int main()
{
int xl=0,xr=(int)1e9,yl=0,yr=(int)1e9;
int x=0,y=0,mid,c;
while(xr-xl>1){
printf("%d %d\n",xl,y); cout.flush();scanf("%d",&c);
printf("%d %d\n",xr,y); cout.flush();scanf("%d",&c);
if(c==0){
xr=((xl+xr)>>1);
}
else xl=(xl+xr)>>1;
}
printf("%d %d\n",xl,y); cout.flush();scanf("%d",&c);
printf("%d %d\n",xr,y); cout.flush();scanf("%d",&c);
if(c==0) x=xl;else x=xr;
while(yr-yl>1){
printf("%d %d\n",x,yl); cout.flush();scanf("%d",&c);
printf("%d %d\n",x,yr); cout.flush();scanf("%d",&c);
if(c==0){
yr=(yl+yr)>>1;
}
else yl=(yl+yr)>>1;
}
printf("%d %d\n",x,yl); cout.flush();scanf("%d",&c);
printf("%d %d\n",x,yr); cout.flush();scanf("%d",&c);
if(c==0) y=yl;else y=yr;
printf("A %d %d\n",x,y);
return 0;
}
D Delay Time
题目描述
计算重力加速度$g$的过程中，产生了一些误差，是由开始时间的测量产生的，求这个$delay\space time$。
解题思路
高中物理，推式子即可。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
const int ms = 1e5 + 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
double t1, t2, h1, h2;
cin >> h1 >> t1 >> h2 >> t2;
h1 = sqrt(h1 / h2);
printf("%.6lf", (t1 - h1 * t2) / (1 - h1));
}
E Entertainment
题目描述
有$tot=2^n$个人，编号$1-tot$。随机安排淘汰赛，淘汰赛形成一棵满二叉树。每次如果第$i$个人和第$j$个人比赛，将会产生$a_ia_j$的娱乐值，求总娱乐值的期望。
解题思路
最底层的排列一共有$A_{tot}^{tot}=tot!$种排列方式。如果能求出所有方案的娱乐值之和$sum$，那么答案即为$\frac{sum}{tot!}$。
考虑计算$i,j(i<j)$在第满二叉树从上往下数第$k+1$层相遇产生的娱乐值对答案的贡献（$2\leq k+1\leq n$）。
单考虑$i$，以这一层的$i$为根的满二叉树中，除了$i$，其他所有叶子节点都为$<i$的某个值，而叶子节点共有$2^{n-k}$个，从前$i-1$个数中选择$2^{n-k}-1$个数字进行排列，再将$i$插入到$2^{n-k}-1+1$个空中，故共有$A_{i-1}^{2^{n-k}-1}\times 2^{n-k}$种排列方式。
再考虑$j$，$j$的子树一共能够从前$j-1-2^{n-k}$个数中选取（因为需要除掉$i$子树中已经选过的人），同理可得排列方式为$A_{j-1-2^{n-k}}^{2^{n-k}-1}\times 2^{n-k}$。
由于$i,j$要在第$k+1$层相遇，他们的胜者必然在$k$层的某个位置出现。第$k$层共有$2^{k-1}$个位置，故排列方式还需乘$2^{k-1}$；$ij$位置可以互换，故还需乘$2$；剩余元素任意排列，还需乘$(2^{n}-2\times 2^{n-k})!$。
于是$i,j,k$对答案的贡献即为：$(2^n-2^{n-k+1})!\times 2^{2n-k}A_{i-1}^{2^{n-k}-1}a_i\times A_{j-1-2^{n-k} }^{2^{n-k}-1}a_j$
显然，单这么算的复杂度为$O(n4^n)$，需要优化。很容易看出来，$i$无论怎么选，不会影响到$j$的方案数。于是可以前缀和优化，预处理出来$> i$的$j$对于$i$的影响之和，这样就可以$O(n2^n)$求解了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef long long ll;
using namespace std;
ll fac[N],inv[N],mod=1000000007;
ll qp(ll x,int p){
ll ans=1;
for(;p;p>>=1,x=x*x%mod)if(p&1)ans=ans*x%mod;
return ans;
}
ll a(int n,int m){
if(n<m||m<0)return 0;
return fac[n]*inv[n-m]%mod;
}
int b[N];
int main(){
int i,j,k,n;
fac[0]=inv[0]=1;
for(i=1;i<N;i++)fac[i]=fac[i-1]*i%mod,inv[i]=qp(fac[i],mod-2);
scanf("%d",&n);
for(i=1;i<=(1<<n);i++)scanf("%d",&b[i]);
reverse(b+1,b+(1<<n)+1);
ll ans=0;
for(k=1;k<=n;k++){
ll sum=0;
for(j=(1<<n);j>1;j--){
(sum+=b[j]*a(j-1-(1<<(n-k)),(1<<(n-k))-1))%=mod;
(ans+=b[j-1]*a(j-2,(1<<(n-k))-1)%mod*sum%mod*fac[(1<<n)-(1<<(n-k+1))]%mod*((1LL<<(2*n-k))%mod)%mod)%=mod;
}
}
printf("%lld\n",ans*inv[1<<n]%mod);
return 0;
}
F Flow Management
题目描述
解题思路
AC代码
2
G Garden Gathering
题目描述
给定一堆二维平面上的整数点，点与点之间的距离定义为，在方格上只能沿着上下、左右以及斜对角方向走到整数格上，两点间最短需要的路线总长度。求最远两个点的距离。
解题思路
对于两个点$(x_1,y_1),(x_2,y_2)$，其距离为$\sqrt2 min(\Delta x,\Delta y)+((max(\Delta x,\Delta y)-(min(\Delta x,\Delta y)))=(\sqrt2-1)min(\Delta x,\Delta y)+max(\Delta x,\Delta y)$，即为$((\sqrt2-1)x_1,y_1)((\sqrt2-1)x_2,y_2)$之间的曼哈顿距离$((\sqrt2-1)\Delta x+\Delta y)$与$(x_1,(\sqrt2-1)y_1)(x_2,(\sqrt2-1)y_2)$之间的曼哈顿距离$((\sqrt2-1)\Delta y+\Delta x)$的最大值（$\sqrt 2-1<1$）。
曼哈顿距离的最大值只需要拆开绝对值符号存一下$x+y,x-y,y-x,-x-y$四个值的最大最小值即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
typedef long long ll;
using namespace std;
int n,idm[4],idn[4];
struct Point{double x,y;}p1[N],p2[N];
double mx[4],mn[4];
double sol(Point a[],int &ans1,int &ans2){
int i;double ans=0;
for(i=0;i<4;i++)mx[i]=-1e18,mn[i]=1e18;
for(i=0;i<n;i++){
double x=a[i].x,y=a[i].y;
if(mx[0]<x+y)mx[0]=x+y,idm[0]=i;
if(mx[1]<-x+y)mx[1]=-x+y,idm[1]=i;
if(mx[2]<x-y)mx[2]=x-y,idm[2]=i;
if(mx[3]<-x-y)mx[3]=-x-y,idm[3]=i;
if(mn[0]>x+y)mn[0]=x+y,idn[0]=i;
if(mn[1]>-x+y)mn[1]=-x+y,idn[1]=i;
if(mn[2]>x-y)mn[2]=x-y,idn[2]=i;
if(mn[3]>-x-y)mn[3]=-x-y,idn[3]=i;
}
for(i=0;i<4;i++)if(ans<mx[i]-mn[i])ans=mx[i]-mn[i],ans1=idm[i],ans2=idn[i];
return ans;
}
int main(){
int a,b,c,d,i,x,y;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d",&x,&y);
p1[i]={(sqrt(2)-1)*x,y};p2[i]={x,(sqrt(2)-1)*y};
}
if(sol(p1,a,b)>sol(p2,c,d))printf("%d %d",a+1,b+1);
else printf("%d %d",c+1,d+1);
return 0;
}
H Hashing
题目描述
从一列$0\leq a_i\leq 255$的数中，选取一个不要求连续的子序列$s_i$，其$hash$值定义为$\sum_{i=0}^{len(s)}i\oplus a_{s_i}$，求所有子串中最大的$hash$值。
解题思路
$dp[i][j]$ 表示到了第$i$个元素，当前已选择的数列$s$长度为$j$的当前最大$hash$值。于是有$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+j\oplus a_{i})$
这样的复杂度是$O(n^2)$的，不太可行。
考虑到所有$a_i$都在$255$以内，在$j$对$a_i$异或操作的时候，只会修改后半部分。考虑用$dp[i][j]$表示到了第$i$个元素，已选择的长度$mod\space 256$为$j$的当前最大$hash$值。因为所有$a_i\geq 0$，选择更长的序列必然是不劣的，于是根据余数$j$可以算出对应的原长度$len$，采用同样的$dp$方式解决即可。
AC代码 - by Mogg & Potassium
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
const int ms = 1e5 + 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[ms];
ll dp[ms][300];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> hex >> a[i];
}
ll mx = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 256; ++j)
{
int temp = (i / 256) * 256 + j;
if (temp > i)temp -= 256;
if (temp >= 0)
{
if(i>=1)dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j + 255) % 256] + (a[i] ^ temp));
else dp[i][j]=(a[i] ^ temp);
mx = max(dp[i][j], mx);
}
}
}
cout << mx;
}
I Illegel or Not?
题目描述
判断护照的合法使用。
解题思路
模拟一下即可
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
typedef long long ll;
const int maxn = 1e5+23;
int a[maxn],b[maxn];
int vis[maxn];
int n,m;
int main()
{
cin >>n ;
for(int i=1;i<=n;i++){
scanf("%d %d",a+i,b+i);
for(int j=a[i];j<=b[i];j++) vis[j]=1;
}
int pre=0;
for(int i=1;i<=180;i++) pre+=vis[i];
if(pre>90) return 0*printf("No");
for(int i=181;i<=1826;i++){
pre-=vis[i-180];
pre+=vis[i];if(pre>90) return 0*printf("No");
}
printf("Yes");
}
J Jealousy
题目描述
有$k$个男生$m$个女生，$n$个照片，第$i$个照片上有$size_i$个女生，每次钦定每个女生$x$和某个男生$y$互为情侣，按照照片顺序钦定所有照片上出现的女生。当某次钦定时，男生$y$之前已经被钦定过和另一个女生互为情侣，那么需要额外花费$q_x$。问如何钦定使得总花费最少。
解题思路
这个费用流绝了。因为男生是谁不重要，重要的是这个男生以前有没有被钦定过。于是对于某个女生$x$的出现，考虑几种情况：
- 如果这个女生不是第一次出现，沿用上次钦定给她的女生；否则钦定一个没被钦定过的男生给她
- 从渣男里面找一个男生钦定给她。
没了。
按照片顺序可以建一个关于时间的图：$s=0,t=n+1$，$i\rightarrow i+1$流量为$k$，花费为$0$
一个流量代表一个男生。按照上面的两种情况建图，对于每个照片中的女生$x$：
- 拆点，连流量$1$花费$-inf$的边，保证被选到；
- 如果女生之前出现过，那么从上次出现的点连流量$1$花费$0$的边，否则从$1$连过来流量$1$花费$0$的边；
- 从时间轴上拉一条流量$1$花费$q[x]$的边，找一个渣男；
- 连向时间轴一个流量$1$花费$0$的边，表示这个男生可能去变成渣男。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
typedef long long ll;
using namespace std;
ll inf=1e9;
struct Edge{
int e,n;ll len,cost;
}e[20*N];
int hd[N],cnt=1;
struct Pre{
int pre,e;
}pre[N];
ll dis[N],flow[N];
int vis[N],n,m,s,t;
ll maxflow,mincost;
void adde(int a,int b,ll l,ll c){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
e[cnt].len=l;e[cnt].cost=c;
}
void add(int a,int b,ll l,ll c){
adde(a,b,l,c);
adde(b,a,0,-c);
}
queue<int>Q;
int spfa(){
memset(vis,0,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
while(!Q.empty())Q.pop();
int i,top,q;
Q.push(s);vis[s]=1;dis[s]=0;pre[t].pre=0;
while(!Q.empty()){
top=Q.front();
Q.pop();
vis[top]=0;
for(i=hd[top];i;i=e[i].n){
q=e[i].e;
if(e[i].len&&dis[q]>dis[top]+e[i].cost){
dis[q]=dis[top]+e[i].cost;
pre[q].pre=top;
pre[q].e=i;
flow[q]=min(flow[top],e[i].len);
if(!vis[q]){
vis[q]=1;
Q.push(q);
}
}
}
}
return pre[t].pre;
}
void ek(){
int i;
while(spfa()){
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
for(i=t;i!=s;i=pre[i].pre){
e[pre[i].e].len-=flow[t];
e[pre[i].e^1].len+=flow[t];
}
}
}
int added[N],tot,q[N];
int start[N],res[N];
void get(int num,int p){//p:当前节点 num:当前npy编号
int i;
res[p]=num;
if(!p)return;
for(i=hd[p];i;i=e[i].n){
if(i%2&&e[i].len){
e[i^1].len++;
e[i].len--;
get(num,e[i].e);
return;
}
}
}
int main(){
int i,j,k;
scanf("%d%d%d",&n,&k,&m);
for(i=1;i<=m;i++)scanf("%d",&q[i]);
s=0,t=n+1,tot=t+1;
ll sum=0;
for(i=0;i<=n;i++)add(i,i+1,k,0);
for(i=1;i<=n;i++){
int x,y;
start[i]=tot;
scanf("%d",&x);
sum+=x;
while(x--){
scanf("%d",&y);
add(tot,tot+1,1,-inf);//拆点，必选这个女生
if(added[y])add(added[y],tot,1,0);//继承上次的npy
else add(1,tot,1,0);//新找个npy
add(i,tot,1,q[y]);//从以前被分配过的npy中找
add(tot+1,i+1,1,0);//方便下一个女生使用这个npy
added[y]=tot+1;
tot+=2;
}
}
start[i]=tot;
ek();
printf("%lld\n",mincost+sum*inf);
for(i=1;i<=k;i++)get(i,t);
for(i=1;i<=n;i++){
for(j=start[i];j<start[i+1];j+=2)printf("%d ",res[j]);
puts("");
}
return 0;
}
K King’s Rout
题目描述
给两个数列$a,b$，要求$a_i$比$b_i$早出现，且出现的顺序数列满足字典序最小。
解题思路
考虑反向建边，每次选出最大的元素拓扑排序，反向输出即可。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
const int ms = 200000 + 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int res[ms];
int d[ms];
vector<int> g[ms];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int a, b;
for (int i = 0; i < m; ++i)
{
cin >> a >> b;
g[b].push_back(a);
d[a]++;
}
priority_queue<int>q;
for (int i = 1; i <= n; ++i)
{
if (d[i] == 0)
q.push(i);
}
int cnt = 0;
while (!q.empty())
{
int cur = q.top(); q.pop();
res[++cnt] = cur;
for (auto i : g[cur])
{
if (!--d[i])
{
q.push(i);
}
}
}
for (int i = n; i > 0; --i)
{
cout << res[i] << " ";
}
}
L Locomotive
题目描述
解题思路
AC代码
2