Schi2oid's Blog文章
The 1st Universal Cup. Stage 15: Hangzhou 题解
I J 不会。
A. Turn on the Light
题意：交互题，给
�
n 盏灯，猜小明最喜欢的灯。每次可以点亮一盏灯，小明会告诉你他最喜欢的灯左侧灯数量减去右侧灯数量的绝对值。在
40
40 次询问内获得答案，
�
≤
1
0
6
n≤10
6
。
题解：简单二分题。考虑在剩余灯中从左到右第
⌊
�
4
⌋
⌊
4
n
⌋ 和第
�
−
⌊
�
4
⌋
n−⌊
4
n
⌋ 盏灯询问，这样每次可以将待定灯数减半，过程中发现返回值不变直接输出，若过程中没有找到，剩余
4
4 盏灯以内时依次询问即可。
#include <bits/stdc++.h>
using namespace std;
int ask(int x) {
int ret;
cout << "? " << x << endl;
cin >> ret;
return ret;
}
int id[2][2000005];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
id[0][i] = i;
bool op = 0;
int bef = 0;
while (n >= 4) {
int p1 = n / 4, p2 = n - n / 4;
int x = ask(id[op][p1]);
if (x == bef) {
cout << "! " << id[op][p1];
return 0;
}
int y = ask(id[op][p2]);
if (y == x) {
cout << "! " << id[op][p2];
return 0;
}
int delta = y - bef;
op ^= 1;
if (delta == 0) {
int cnt = 0;
for (int i = p1 + 1; i < p2; i++) {
id[op][++cnt] = id[op ^ 1][i];
}
n = cnt;
}
else {
int cnt = 0;
for (int i = 1; i < p1; i++) {
id[op][++cnt] = id[op ^ 1][i];
}
for (int i = p2 + 1; i <= n; i++) {
id[op][++cnt] = id[op ^ 1][i];
}
n = cnt;
}
bef = y;
}
for (int i = 1; i <= n; i++) {
int x = ask(id[op][i]);
if (x == bef) {
cout << "! " << id[op][i];
return 0;
}
bef = x;
}
return 0;
}
B. Equation Discovering
题意：给
�
n 个点
(
�
�
,
�
�
)
(x
i
,y
i
)，要求用
�
,
+
,
−
,
×
,
÷
,
sin
,
cos
,
(
,
)
x,+,−,×,÷,sin,cos,(,) 构造一个函数，经过每个点且表达式树中结点个数不超过
10
10，保证有解。
�
≤
20
n≤20。
题解：烂题中的烂题！烂题中的烂题！烂题中的烂题！明明可以出成拉插！还能稍微不那么烂！暴力搜索表达式树。注意
�
�
�
=
1
0
−
2
eps=10
−2
。
#include<bits/stdc++.h>
using namespace std;
int n;
int val[6];
long double x[25],y[25];
int ls[25],rs[25],typ[25];
int mi[25];
int idcnt=1;
mt19937 ra(time(0));
long double f(long double x,long double y,int typ){
if(typ==0) return x+y;
else if(typ==1) return x-y;
else if(typ==2) return x*y;
else if(typ==3){
if(abs(y)<=1e-2) return ra();
return x/y;
}
else if(typ==4) return sin(x);
else return cos(x);
}
void prt(int p){
printf("(");
if(p==-1) printf("x");
else if(typ[p]==0){
prt(ls[p]);printf("+");prt(rs[p]);
}
else if(typ[p]==1){
prt(ls[p]);printf("-");prt(rs[p]);
}
else if(typ[p]==2){
prt(ls[p]);printf("*");prt(rs[p]);
}
else if(typ[p]==3){
prt(ls[p]);printf("/");prt(rs[p]);
}
else if(typ[p]==4){
printf("sin(");prt(ls[p]);printf(")");
}
else if(typ[p]==5){
printf("cos(");prt(ls[p]);printf(")");
}
printf(")");
}
long double calc(int p,long double x){
long double lc=x,rc=x;
if(ls[p]!=-1) lc=calc(ls[p],x);
if(rs[p]!=-1) rc=calc(rs[p],x);
return f(lc,rc,typ[p]);
}
void check(){
for(int i=1;i<=n;i++) if(abs(calc(1,x[i])-y[i])/max((long double)1,abs(y[i]))>1e-3) return;
prt(1);
exit(0);
}
void dfs(int lim,vector<int>vec){
int tmp[25];
check();
int cnt=0;
for(int i=0;i<vec.size();i++) cnt+=val[typ[vec[i]]];
for(int i=1;i<=cnt;i++) tmp[i]=-1;
vector<int>nxt;
int befcnt=idcnt;
for(int i=1;i<mi[cnt];i++){
for(int j=1;j<=cnt;j++){
tmp[j]++;
if(tmp[j]==6) tmp[j]=-1;
else break;
}
int nxtcnt=0;
for(int i=1;i<=cnt;i++) if(tmp[i]!=-1) nxtcnt+=val[tmp[i]];
if(nxtcnt>lim) continue;
int poi=cnt;
for(int j=0;j<vec.size();j++){
if(typ[vec[j]]<=3){
if(tmp[poi]!=-1){
ls[vec[j]]=++idcnt;
typ[idcnt]=tmp[poi--];
nxt.push_back(idcnt);
}
else{
ls[vec[j]]=-1;
poi--;
}
if(tmp[poi]!=-1){
rs[vec[j]]=++idcnt;
typ[idcnt]=tmp[poi--];
nxt.push_back(idcnt);
}
else{
rs[vec[j]]=-1;
poi--;
}
}
else{
if(tmp[poi]!=-1){
ls[vec[j]]=++idcnt;
typ[idcnt]=tmp[poi--];
nxt.push_back(idcnt);
}
else{
ls[vec[j]]=-1;
poi--;
}
rs[vec[j]]=-1;
}
}
dfs(lim-nxtcnt,nxt);
nxt.clear();
idcnt=befcnt;
}
for(int i=0;i<vec.size();i++) ls[vec[i]]=rs[vec[i]]=-1;
}
int main(){
mi[0]=1;
for(int i=1;i<=9;i++) mi[i]=mi[i-1]*7;
val[0]=val[1]=val[2]=val[3]=2;
val[4]=val[5]=1;
for(int i=1;i<=20;i++) ls[i]=-1,rs[i]=-1;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%Lf%Lf",&x[i],&y[i]);
}
vector<int>vec;
vec.push_back(1);
for(int i=0;i<6;i++){
typ[1]=i;
ls[1]=-1,rs[1]=-1;
dfs(9-val[i],vec);
}
puts("-1");
return 0;
}
C. Puzzle: Kusabi
题意：给一棵有
�
n 个点的树，树上结点可能会有汉字“同”、“长”、“短”，要求对所有有标记的结点进行匹配，匹配上的点对之间连线，要求点对与点对之间的路径不经过相同的边。“同”要求匹配结点与该点深度相同；“长”要求该点深度大于匹配结点；“短”要求该点深度小于匹配结点。判断是否有解，若有解则输出匹配方案。
�
≤
1
0
5
n≤10
5
。
题解：简单贪心题。由于每棵子树只能有一条走出去的路径，所以最多只能有一个点是在子树内无法匹配的。对于每个点，排序其儿子子树内无法匹配的点和其自身，贪心地进行匹配，如果发现某个点有多于一个点是无法在内部进行匹配的则无解，否则不断递归构造即可。
#include<bits/stdc++.h>
using namespace std;
vector<int>edge[200005];
int typ[200005],dep[200005];
#define pii pair<int,int>
#define mkp(x,y) make_pair(x,y)
struct node{
int typ,dep,id;
};
void init(int x,int f){
dep[x]=dep[f]+1;
for(int i=0;i<edge[x].size();i++){
int v=edge[x][i];
if(v==f) continue;
init(v,x);
}
}
vector<pii>ans;
node dfs(int x,int f){
node ret=(node){0,0,0};
vector<pii>tmp[4];
if(typ[x]!=0) tmp[typ[x]].push_back(mkp(dep[x],x));
for(int i=0;i<edge[x].size();i++){
int v=edge[x][i];
if(v==f) continue;
node zzz=dfs(v,x);
if(zzz.typ==-1) return (node){-1,-1,-1};
if(zzz.typ>0) tmp[zzz.typ].push_back(mkp(zzz.dep,zzz.id));
}
for(int i=1;i<=3;i++) sort(tmp[i].begin(),tmp[i].end(),greater<pii>());
if(tmp[3].size()){
int cnt=1;
for(int i=1;i<tmp[3].size();i++){
if(tmp[3][i].first!=tmp[3][i-1].first){
if(cnt&1){
if(ret.typ!=0) return (node){-1,-1,-1};
ret=(node){3,tmp[3][i-1].first,tmp[3][i-1].second};
}
for(int j=i-cnt;j<i-1;j+=2) ans.push_back(mkp(tmp[3][j].second,tmp[3][j+1].second));
cnt=1;
}
else cnt++;
}
for(int j=tmp[3].size()-cnt;j<tmp[3].size()-1;j+=2) ans.push_back(mkp(tmp[3][j].second,tmp[3][j+1].second));
if(cnt&1){
if(ret.typ!=0) return (node){-1,-1,-1};
ret=(node){3,tmp[3][tmp[3].size()-1].first,tmp[3][tmp[3].size()-1].second};
}
}
if(tmp[1].size()==tmp[2].size()){
for(int i=0;i<tmp[1].size();i++){
if(tmp[1][i].first<=tmp[2][i].first) return (node){-1,-1,-1};
ans.push_back(mkp(tmp[1][i].second,tmp[2][i].second));
}
}
else if(tmp[1].size()>tmp[2].size()){
int poi=tmp[1].size()-1;
for(int i=tmp[2].size()-1;i>=0;i--){
while(poi>=0&&tmp[1][poi].first<=tmp[2][i].first){
if(ret.typ!=0) return (node){-1,-1,-1};
ret=(node){1,tmp[1][poi].first,tmp[1][poi].second},poi--;
}
if(poi>=0&&tmp[1][poi].first>tmp[2][i].first){
ans.push_back(mkp(tmp[1][poi].second,tmp[2][i].second));
poi--;
}
else return (node){-1,-1,-1};
}
while(poi>=0){
if(ret.typ!=0) return (node){-1,-1,-1};
ret=(node){1,tmp[1][poi].first,tmp[1][poi].second},poi--;
}
}
else{
int poi=0;
for(int i=0;i<tmp[1].size();i++){
while(poi<tmp[2].size()&&tmp[1][i].first<=tmp[2][poi].first){
if(ret.typ!=0) return (node){-1,-1,-1};
ret=(node){2,tmp[2][poi].first,tmp[2][poi].second},poi++;
}
if(poi<tmp[2].size()&&tmp[1][i].first>tmp[2][poi].first){
ans.push_back(mkp(tmp[1][i].second,tmp[2][poi].second));
poi++;
}
else return (node){-1,-1,-1};
}
while(poi<tmp[2].size()){
if(ret.typ!=0) return (node){-1,-1,-1};
ret=(node){2,tmp[2][poi].first,tmp[2][poi].second},poi++;
}
}
if(x==1&&ret.typ) return (node){-1,-1,-1};
return ret;
}
int main(){
int n,u,p;
cin>>n;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&p);
edge[u].push_back(p);
edge[p].push_back(u);
string str;
cin>>str;
if(str=="Chang") typ[u]=1;
else if(str=="Duan") typ[u]=2;
else if(str=="Tong") typ[u]=3;
}
init(1,0);
node final=dfs(1,0);
if(final.typ==-1) puts("NO");
else{
puts("YES");
for(int i=0;i<ans.size();i++) printf("%d %d\n",ans[i].first,ans[i].second);
}
return 0;
}
D. Master of Both III
题意：给定
�
n，定义对元素在
[
0
,
�
−
1
]
[0,n−1] 中的集合的操作为：选定该集合的一个子集，再选定一个
�
t，将子集中的所有数在
m
o
d
�
modn 意义下
+
�
+t，代价为
�
�
w
t
。求对于每一个可能的集合，将其变为
{
0
}
{0} 的最小代价。
�
≤
22
n≤22。
题解：好玩题。反过来考虑，相当于从
{
0
}
{0} 出发，用最小的代价将整个集合覆盖。由于覆盖的越多一定越好，所以对于某个集合和一个给定的
�
t，直接将其平移
�
t 再取并即可，统计答案时统计其所有超集的答案的最小值即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[10000005],w[25];
const int INF=1e18;
const int mod=998244353;
int n;
int mov(int x,int k){
return (x>>(n-k))|((x&((1<<(n-k))-1))<<k);
}
signed main(){
cin>>n;
for(int i=0;i<n;i++) scanf("%lld",&w[i]);
for(int i=2;i<(1<<n);i++) f[i]=INF;
for(int i=1;i<(1<<n);i++){
for(int t=1;t<n;t++){
int j=i|mov(i,t);
f[j]=min(f[j],f[i]+w[n-t]);
}
}
for(int i=(1<<n)-1;i>0;i--) for(int j=0;j<n;j++) if(i&(1<<j)) f[i^(1<<j)]=min(f[i^(1<<j)],f[i]);
int ans=0;
for(int i=1;i<(1<<n);i++) ans=(ans+f[i]%mod*i%mod)%mod;
cout<<ans<<endl;
return 0;
}
E. Puzzle: Tapa
题意：给定一个
2
�
+
1
×
2
�
+
1
2n+1×2m+1 的网格，每个行列都为奇数的格子上有一个该格子八联通格子数量
−
0
/
1
−0/1 的数，要求为所有没有数字的格子黑白染色，使每个有数字的格子周围恰好有其上数字个连续的黑格。
�
,
�
≤
50
n,m≤50。
题解：水题。注意到不会选择行列都为偶数的结点抠去，直接网络流跑匹配即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
int n,m;
int S,T;
int ban[2005][2005];
int dis[1000005];
int a[2005][2005];
int ecnt=1,nxt[1000005],head[1000005],val[1000005],cur[1000005],to[1000005];
void add_edge(int u,int v,int w){
nxt[++ecnt]=head[u];
to[ecnt]=v;
head[u]=ecnt;
val[ecnt]=w;
nxt[++ecnt]=head[v];
head[v]=ecnt;
to[ecnt]=u;
val[ecnt]=0;
}
bool bfs(){
queue<int>q;
memcpy(cur,head,sizeof cur);
q.push(S);
for(int i=S;i<=T;i++) dis[i]=-1;
dis[S]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int e=head[x];e;e=nxt[e]){
int v=to[e],w=val[e];
if((!w)||dis[v]!=-1) continue;
dis[v]=dis[x]+1;
q.push(v);
}
}
return dis[T]!=-1;
}
int dfs(int x,int in){
if(x==T) return in;
int out=0;
for(int e=cur[x];e;e=nxt[e]){
cur[x]=e;
int v=to[e],w=val[e];
if((!w)||dis[v]!=dis[x]+1) continue;
int tmp=dfs(v,min(w,in-out));
out+=tmp;
val[e]-=tmp;
val[e^1]+=tmp;
if(out==in) break;
}
return out;
}
int dinic(){
int ret=0;
while(bfs()) ret+=dfs(S,INF);
return ret;
}
int id(int x,int y){return (x-1)*m+y;}
int eid[2005][2005][4];
char ans[2005][2005];
int vx[4]={1,-1,0,0},vy[4]={0,0,1,-1};
signed main(){
cin>>n>>m;
S=0,T=n*m+1;
char ch;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ch=getchar();
while(ch<'1'||ch>'9') ch=getchar();
a[i][j]=ch-'0';
int cnt=(i==1||i==n)+(j==1||j==m);
if(cnt==2) a[i][j]-=3;
else if(cnt==1) a[i][j]-=5;
else a[i][j]-=8;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ban[i][j]=-1;
if(i==1&&j!=1&&j!=m) ban[i][j]=0;
if(i==n&&j!=1&&j!=m) ban[i][j]=1;
if(j==1&&i!=1&&i!=n) ban[i][j]=2;
if(j==m&&i!=1&&i!=n) ban[i][j]=3;
}
}
int tot=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0) continue;
tot++;
for(int k=0;k<4;k++){
int ni=i+vx[k],nj=j+vy[k];
if(ni<1||ni>n||nj<1||nj>m) continue;
if(k==ban[i][j]||(k^1)==ban[ni][nj]) continue;
if(ni<i||nj<j) continue;
if(a[ni][nj]!=-1) continue;
eid[i][j][k]=ecnt+1;
if((i&1)^(j&1)) add_edge(id(i,j),id(ni,nj),1);
else add_edge(id(ni,nj),id(i,j),1);
}
if((i&1)^(j&1)) add_edge(S,id(i,j),1);
else add_edge(id(i,j),T,1);
}
}
if(tot&1){
puts("NO");
return 0;
}
int ret=dinic();
if(ret!=tot/2){
puts("NO");
return 0;
}
puts("YES");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int cnt=(i==1||i==n)+(j==1||j==m);
if(cnt==2) ans[2*i-1][2*j-1]=a[i][j]+3+'0';
else if(cnt==1) ans[2*i-1][2*j-1]=a[i][j]+5+'0';
else ans[2*i-1][2*j-1]=a[i][j]+8+'0';
}
}
for(int i=2;i<=2*n-1;i+=2) for(int j=1;j<=2*m-1;j++) ans[i][j]='#';
for(int j=2;j<=2*m-1;j+=2) for(int i=1;i<=2*n-1;i++) ans[i][j]='#';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0) continue;
tot++;
for(int k=0;k<4;k++){
int ni=i+vx[k],nj=j+vy[k];
if(ni<1||ni>n||nj<1||nj>m) continue;
if(k==ban[i][j]||(k^1)==ban[ni][nj]) continue;
if(ni<i||nj<j) continue;
if(a[ni][nj]!=-1) continue;
if(!val[eid[i][j][k]]){
int posx=2*i-1+vx[k],posy=2*j-1+vy[k];
ans[posx][posy]='.';
}
}
}
}
for(int i=1;i<=2*n-1;i++){
for(int j=1;j<=2*m-1;j++) printf("%c",ans[i][j]);
puts("");
}
return 0;
}
F. Classic: Classical Problem
题意：给定一个集合
�
S，集合中包含一个质数
�
p，求所有
�
c，使得
mex
{
(
�
+
�
)
m
o
d
�
∣
�
∈
�
}
mex{(x+c)modp∣x∈S} 最小，并求出这个最小值。
�
≤
2
×
1
0
5
p≤2×10
5
。
题解：典但没见过题。乘法操作相当于在原根置换环上进行旋转，故考虑求出原根，设
�
≡
�
�
(
�
)
(
m
o
d
�
)
x≡g
I(x)
(modp)，将集合当中的每个数
�
x 换为
�
(
�
)
I(x)。接下来，考虑二分答案，考虑如何判定对于某一个答案
�
m 是否成立。由于乘法操作相当于在原根置换环上进行旋转，这相当于判定模意义下
�
(
1
)
−
�
,
�
(
2
)
−
�
,
…
,
�
(
�
−
1
)
−
�
I(1)−t,I(2)−t,…,I(m−1)−t 是否都在集合当中出现。考虑生成函数，设
�
(
�
)
f(x) 代表集合的生成函数，
�
(
�
)
g(x) 代表
{
�
(
1
)
,
�
(
2
)
,
…
,
�
(
�
−
1
)
}
{I(1),I(2),…,I(m−1)} 的生成函数，那么对于集合中的每一个元素
�
x，令其对
�
−
�
(
1
)
,
�
−
�
(
2
)
,
…
,
�
−
�
(
�
−
1
)
x−I(1),x−I(2),…,x−I(m−1) 位置产生
1
1 的贡献，即：
[
�
�
]
�
�
�
(
�
)
=
∑
�
−
�
≡
�
(
m
o
d
�
)
[
�
�
]
�
(
�
)
[
�
�
]
�
(
�
)
[x
w
]Ans(x)=
y−z≡w(mod p)
∑
[x
y
]f(x)[x
z
]g(x)
这是一个循环卷积过程，通过 FFT 快速实现。那么，如果某个位置
�
w 满足
[
�
�
]
�
�
�
(
�
)
=
�
−
1
[x
w
]Ans(x)=m−1，说明所有
�
(
1
)
+
�
,
�
(
2
)
+
�
,
…
,
�
(
�
−
1
)
+
�
I(1)+w,I(2)+w,…,I(m−1)+w 全部出现在集合中，即
�
=
−
�
t=−w 是一个解。提前处理出乘上每一个数相当于在原根置换环上旋转多少步，即可找到所有的答案。时间复杂度
�
(
�
log
2
�
)
O(plog
2
p)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long double pi=acos(-1);
struct CP{
long double x,y;
CP(long double X=0,long double Y=0) {x=X,y=Y;}
CP operator + (const CP& ano) const { return (CP){x+ano.x,y+ano.y}; }
CP operator - (const CP& ano) const { return (CP){x-ano.x,y-ano.y}; }
CP operator * (const CP& ano) const { return (CP){x*ano.x-y*ano.y,x*ano.y+y*ano.x}; }
};
int n;
int id[800005];
void get_id(){for(int i=1;i<n;i++) id[i]=(id[i>>1]>>1)^((n>>1)*(i&1));}
CP F[800005],G[800005],ret[800005];
void FFT(CP *A,bool op){
get_id();
for(int i=0;i<n;i++) if(id[i]<i) swap(A[id[i]],A[i]);
for(int i=2;i<=n;i<<=1){
CP T_SPIN=CP(cos(2*pi/i),sin(2*pi/i));
if(op) T_SPIN.y=-T_SPIN.y;
for(int j=0;j<n;j+=i){
CP BTB=CP(1,0);
for(int k=j;k<j+i/2;k++){
CP fl=A[k];
A[k]=fl+BTB*A[k+i/2];
A[k+i/2]=fl-BTB*A[k+i/2];
BTB=BTB*T_SPIN;
}
}
}
if(op) for(int i=0;i<n;i++) A[i].x=(int)(A[i].x/n+0.5),A[i].y=0;
}
vector<int>fac;
int qkp(int x,int k,int p){
int ret=1;
while(k){
if(k&1) ret=ret*x%p;
x=x*x%p;
k>>=1;
}
return ret;
}
int I[800005];
int a[800005];
vector<int>ans;
signed main(){
int t,sz,p;
cin>>t;
while(t--){
scanf("%lld%lld",&sz,&p);
n=1;
while(n<=p) n<<=1;
n<<=1;
fac.clear();
for(int i=2;i<=sqrt(p-1);i++) if((p-1)%i==0) fac.push_back(i),fac.push_back((p-1)/i);
int g=1;
for(int i=2;i<p;i++){
int ok=1;
for(int j=0;j<fac.size();j++){
if(qkp(i,fac[j],p)==1){ok=0;break;}
}
if(ok){
g=i;
break;
}
}
I[1]=0;
int tmp=1;
for(int i=1;i<p-1;i++){
tmp=tmp*g%p;
I[tmp]=i;
}
int ok=0;
for(int i=1;i<=sz;i++){
scanf("%lld",&a[i]);
if(a[i]==0) ok=1;
}
if(!ok){
printf("1 1\n0\n");
continue;
}
sort(a+1,a+1+sz);
for(int i=2;i<=sz;i++) a[i]=I[a[i]];
for(int i=0;i<n;i++) F[i]=CP(0,0);
for(int i=2;i<=sz;i++) F[a[i]]=CP(1,0);
FFT(F,0);
int l=1,r=p;
while(l<r){
int mid=l+r+1>>1;
for(int i=0;i<n;i++) G[i]=CP(0,0);
for(int i=1;i<mid;i++) G[p-1-I[i]]=CP(1,0);
FFT(G,0);
for(int i=0;i<n;i++) ret[i]=G[i]*F[i];
FFT(ret,1);
int ok=0;
for(int i=0;i<p-1;i++){
if(ret[i].x+ret[i+p-1].x==mid-1){
ok=1;
break;
}
}
if(ok) l=mid;
else r=mid-1;
}
ans.clear();
if(r==1) ans.push_back(0);
for(int i=0;i<n;i++) G[i]=CP(0,0);
for(int i=1;i<r;i++) G[p-1-I[i]]=CP(1,0);
FFT(G,0);
for(int i=0;i<n;i++) ret[i]=G[i]*F[i];
FFT(ret,1);
for(int i=0;i<p-1;i++) if(ret[i].x+ret[i+p-1].x==r-1) ans.push_back(qkp(g,p-1-i,p));
printf("%lld %lld\n",ans.size(),r);
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++) printf("%lld ",ans[i]);
puts("");
}
return 0;
}
G. Game: Celeste
题意：Madeline 刚刚学会了凌波微步，现在，她面前有
�
n 个柱子，依次位于
�
1
∼
�
�
x
1
∼x
n
。她每次可以从当前位置
�
x 移动到
[
�
+
�
,
�
+
�
]
[x+L,x+R] 区间内的任意一个柱子。她一开始站在
1
1 号柱子上，希望到达
�
n 号柱子。每个柱子上面都有一个草莓，草莓有大小
�
�
a
i
，Madeline 会收集她所在柱子上的草莓。现在，她希望你告诉她，她能收集到的所有草莓集合中，将其从大到小排序后字典序最大的一个是哪个。
�
≤
1
0
6
n≤10
6
。
题解：妙妙蔚蓝题。借助双指针和朴素线性的集合字典序比较，我们可以获得一个
�
(
�
2
)
O(n
2
) 的算法。考虑如何快速比较两个集合的字典序，我们可以为两个集合创建权值线段树，线段树上每个结点维护一个哈希值，这样我们就可以快速找到最大的两个集合数量不同的值。因此，单次比较的时间复杂度是
�
(
log
�
)
O(logn) 的。考虑主席树，这样每次修改也是
�
(
log
�
)
O(logn) 的。所以总时间复杂度优化至
�
(
�
log
�
)
O(nlogn)。
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
mt19937 ra(time(0));
ull val[1000005];
int a[1000005],b[1000005],bcnt=0;
int x[1000005];
#define mid ((l+r)>>1)
struct node{
int cnt,ls,rs;
ull hx;
node(int CNT=0,int LS=0,int RS=0,ull HX=0){
cnt=CNT,ls=LS,rs=RS,hx=HX;
}
}t[40000005];
int rt[2000005];
int idcnt=0;
void build(int &x){x=++idcnt;}
void push_up(int p){t[p].hx=t[t[p].ls].hx+t[t[p].rs].hx,t[p].cnt=t[t[p].ls].cnt+t[t[p].rs].cnt;}
void modi(int p,int q,int l,int r,int x){
if(l==r){
t[q].hx=t[p].hx+val[l];
t[q].cnt=t[p].cnt+1;
return;
}
t[q].ls=t[p].ls,t[q].rs=t[p].rs;
if(x<=mid) build(t[q].ls),modi(t[p].ls,t[q].ls,l,mid,x);
else build(t[q].rs),modi(t[p].rs,t[q].rs,mid+1,r,x);
push_up(q);
}
int find_pos(int p,int q,int l,int r){
if(t[p].hx==t[q].hx) return -1;
if(l==r) return l;
if(t[t[p].rs].hx==t[t[q].rs].hx) return find_pos(t[p].ls,t[q].ls,l,mid);
else return find_pos(t[p].rs,t[q].rs,mid+1,r);
}
int query(int p,int l,int r,int q){
if(l==r) return t[p].cnt;
if(q<=mid) return query(t[p].ls,l,mid,q);
else return query(t[p].rs,mid+1,r,q);
}
bool leq(int x,int y){
int p=find_pos(x,y,1,bcnt);
if(p==-1) return 0;
else return query(x,1,bcnt,p)<query(y,1,bcnt,p);
}
void prt(int p,int l,int r){
if(!p) return;
if(l==r) for(int i=1;i<=t[p].cnt;i++) printf("%d ",b[l]);
prt(t[p].rs,mid+1,r);
prt(t[p].ls,l,mid);
}
deque<int>dq;
int main(){
int T,n,l,r;
cin>>T;
while(T--){
scanf("%d%d%d",&n,&l,&r);
for(int i=1;i<=idcnt;i++) t[i]=node(0,0,0,0);
dq.clear();
bcnt=idcnt=0;
for(int i=1;i<=n;i++) rt[i]=-1;
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[++bcnt]=a[i];
}
sort(b+1,b+1+bcnt);
bcnt=unique(b+1,b+1+bcnt)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+bcnt,a[i])-b;
for(int i=1;i<=bcnt;i++) val[i]=ra()*ra();
build(rt[1]);
modi(0,rt[1],1,bcnt,a[1]);
int pt=0;
for(int i=2;i<=n;i++){
while(x[pt+1]<=x[i]-l){
pt++;
if(rt[pt]!=-1){
while((!dq.empty())&&leq(rt[dq.back()],rt[pt])) dq.pop_back();
dq.push_back(pt);
}
}
while((!dq.empty())&&x[dq.front()]<x[i]-r) dq.pop_front();
if(dq.size()){
build(rt[i]);
modi(rt[dq.front()],rt[i],1,bcnt,a[i]);
}
}
if(rt[n]==-1){
puts("-1");
continue;
}
printf("%d\n",t[rt[n]].cnt);
prt(rt[n],1,bcnt);
puts("");
}
return 0;
}
H. Classic: N Real DNA Pots
题意：给定
�
n 个二维平面上的点，要求选出
�
k 个点，最大化它们两两连线的斜率的最小值，
�
≤
1
0
5
n≤10
5
。
题解：水题。二分答案，问题转化成求截距数组上的最长不下降子序列，时间复杂度
�
(
�
log
2
�
)
O(nlog
2
n)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int x[2000005],y[2000005];
long double dp[2000005];
long double b[2000005];
signed main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
}
long double l=-1e9,r=1e9;
while(r-l>1e-9){
long double mid=(l+r)/2;
for(int i=1;i<=n;i++) b[i]=1.0*y[i]-mid*x[i];
int ans=0;
dp[0]=-1e18;
for(int i=1;i<=n;i++){
if(b[i]>=dp[ans]) dp[++ans]=b[i];
else{
int L=0,R=ans;
while(L<R){
int MID=L+R+1>>1;
if(dp[MID]<=b[i]) L=MID;
else R=MID-1;
}
dp[R+1]=min(dp[R+1],b[i]);
}
}
if(ans>=k) l=mid;
else r=mid;
}
printf("%.8Lf\n",l);
return 0;
}
I. MEXimum Spanning Tree
题意：给定一张
�
n 个点
�
m 条边的图，求其生成树中边权
mex
mex 的最大值。
�
,
�
≤
1000
n,m≤1000。
求
mex
mex 最小值的话可以做到
1
0
6
10
6
：P5631，但是这两道题并不是同一道题。
这题是神秘拟阵交，我不会。
J. Master of Polygon
题意：给定一个简单多边形，再给出
�
q 条线段，依次判断每条线段是否与这个简单多边形的边界有交。
神秘计算几何，我也不会，这题场上没人过，赛后只有
m
aroonrk
maroonrk 过了，想学的话去问他吧。
K. Shuttle Tour
题意：给定一棵有
�
n 个结点的树，叶子结点不超过
50
50 个，边有边权，结点是黑色或是白色的，每次操作会翻转一个点的颜色，询问从任取一个点出发，遍历在某个区间
[
�
,
�
]
[l,r] 内的所有黑色点，并回到起始点的最短总路程。
�
,
�
≤
200000
n,q≤200000。
题解：巧妙题。首先将树以任意方式剖分为
50
50 条链，考虑对于每次询问，先处理出每条链上最浅与最深的
[
�
,
�
]
[l,r] 内黑色结点。这容易通过构建一棵以结点下标为下标的线段树来实现。同时，构建一棵树用来表达链与链之间的连接关系，对这棵树进行搜索，即可递推求出每条链的答案，将其加起来即可，时间复杂度
�
(
�
�
log
�
)
O(qklogn)。
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
#define cle node(1000000000,0,0)
#define ncle node(loc[l],loc[l],1)
const int N=200005;
long long loc[N],fa[N],val[N],cid[N],top[N],dep[N],len[55],tot=0,ccnt=1;
char s[N];
vector<int>chain[55];
vector<int>cedge[55];
struct edg{
int v,w;
};
vector<edg>edge[N];
struct node{
int mn,mx,cnt;
node(int MN=1000000000,int MX=0,int CNT=0){
mn=MN,mx=MX,cnt=CNT;
}
}t[4*N][55],ret[55];
void merge(node &x,node y){
x.mn=min(x.mn,y.mn);
x.mx=max(x.mx,y.mx);
x.cnt+=y.cnt;
}
void push_up(int p){
for(int i=1;i<=ccnt;i++){
t[p][i]=t[ls(p)][i];
merge(t[p][i],t[rs(p)][i]);
}
}
void build(int p,int l,int r){
if(l==r){
t[p][cid[l]]=(s[l]=='0')?cle:ncle;
return;
}
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void modi(int p,int l,int r,int x){
if(l==r){
t[p][cid[x]]=(t[p][cid[x]].cnt)?cle:ncle;
return;
}
if(x<=mid) modi(ls(p),l,mid,x);
else modi(rs(p),mid+1,r,x);
push_up(p);
}
void query(int p,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr){
for(int i=1;i<=ccnt;i++) merge(ret[i],t[p][i]);
return;
}
if(ql<=mid) query(ls(p),l,mid,ql,qr);
if(qr>mid) query(rs(p),mid+1,r,ql,qr);
}
void dfs(int x,int f,int w,int tp){
fa[x]=f,val[x]=w;
cid[x]=cid[tp];
loc[x]=++len[cid[tp]];
chain[cid[tp]].push_back(x);
dep[x]=dep[f]+w;
int ok=0;
for(int i=0;i<edge[x].size();i++){
int v=edge[x][i].v,w=edge[x][i].w;
if(v==f) continue;
if(!ok) ok=1,dfs(v,x,w,tp);
else{
cid[v]=++ccnt;
top[ccnt]=v;
dfs(v,x,w,v);
}
}
}
long long cdfs(int x){
int l=ret[x].mn,r=ret[x].mx;
long long ans=0;
for(int i=0;i<cedge[x].size();i++){
int v=cedge[x][i];
ans+=cdfs(v);
int p=loc[chain[v][0]];
if(ret[v].cnt){
l=min(l,p);
r=max(r,p);
}
ret[x].cnt+=ret[v].cnt;
}
if(ret[x].cnt!=tot) l=0;
return ans+dep[chain[x][r]]-dep[chain[x][l]];
}
int main(){
int n,q,u,v,w;
cin>>n>>q;
for(int i=1;i<=50;i++) chain[i].push_back(0);
scanf("%s",s+1);
for(int i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back((edg){v,w});
edge[v].push_back((edg){u,w});
}
cid[1]=top[1]=1;
dfs(1,0,0,1);
for(int i=1;i<=ccnt;i++) chain[i][0]=fa[top[i]];
for(int i=2;i<=ccnt;i++) cedge[cid[fa[top[i]]]].push_back(i);
build(1,1,n);
int op,x,y;
for(int i=1;i<=q;i++){
scanf("%d",&op);
if(op==1){
scanf("%d",&x);
modi(1,1,n,x);
}
else{
scanf("%d%d",&x,&y);
for(int j=1;j<=ccnt;j++) ret[j]=cle;
query(1,1,n,x,y);
tot=0;
for(int j=1;j<=ccnt;j++) tot+=ret[j].cnt;
if(!tot) puts("-1");
else printf("%lld\n",2ll*cdfs(1));
}
}
return 0;
}
L. Barkley
题意：给定
�
n 个数，
�
q 次询问，要求在
[
�
,
�
]
[l,r] 内删去恰好
�
k 个数，最大化区间内其余数的 gcd。保证
�
≤
3
k≤3。
�
≤
1
0
5
n≤10
5
。
题解：简单性质题。先来考虑
�
=
1
k=1 的情况。定义
�
(
�
,
�
)
g(l,r) 表示区间 gcd 的值。相当于求
max
�
∈
[
�
,
�
]
gcd
(
�
(
�
,
�
−
1
)
,
�
(
�
+
1
,
�
)
)
x∈[l,r]
max
gcd(g(l,x−1),g(x+1,r))。观察发现，如果
�
(
�
,
�
)
=
�
(
�
,
�
+
1
)
=
…
=
�
(
�
,
�
)
g(l,s)=g(l,s+1)=…=g(l,t)，那么对于所有
[
�
+
1
,
�
+
1
]
[s+1,t+1] 之内的选择，
�
+
1
t+1 是最优的。这是因为，在这个区间内将删除的数向右移一定不会对上式左边的值产生任何影响，而有可能将右边的值变大。又因为固定一端的区间 gcd 值的种类只有
�
(
log
�
)
O(logV) 种，所以我们可以直接枚举所有的连续段的开头位置。
将这个做法推广到
�
k 更大的情况，我们引入一个新的参数
�
G，也就是说
�
�
�
�
�
(
�
,
�
,
�
,
�
)
solve(l,r,k,G) 表示将
[
�
,
�
]
[l,r] 内删去
�
k 个数后再和
�
G 取 gcd 得到的最大值，相当于求
max
�
∈
[
�
,
�
]
gcd
(
�
,
gcd
(
�
(
�
,
�
−
1
)
,
�
(
�
+
1
,
�
)
)
)
x∈[l,r]
max
gcd(G,gcd(g(l,x−1),g(x+1,r)))。容易发现上述观察依然成立。递归处理即可，单次询问复杂度
�
(
�
log
�
+
1
�
)
O(nlog
k+1
V)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[200005];
int st[25][200005];
int lg[200005];
int get_g(int l,int r){
if(l>r) return 0;
return __gcd(st[lg[r-l+1]][l],st[lg[r-l+1]][r-(1<<lg[r-l+1])+1]);
}
int solve(int l,int r,int k,int G){
if(k==0) return __gcd(G,get_g(l,r));
int ret=solve(l+1,r,k-1,G);
int now=l,g=__gcd(a[l],G);
while(1){
for(int i=20;i>=0;i--) if(now+(1<<i)-1<=n&&st[i][now]%g==0) now+=(1<<i);
if(now>r) break;
ret=max(ret,solve(now+1,r,k-1,g));
g=__gcd(g,a[now]);
}
return ret;
}
signed main(){
lg[1]=0;
for(int i=2;i<=200000;i++) lg[i]=lg[i>>1]+1;
int q,l,r,k;
cin>>n>>q;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),st[0][i]=a[i];
for(int i=1;i<=20;i++){
for(int j=1;j<=n;j++){
if(j+(1<<i)-1>n) continue;
st[i][j]=__gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
for(int i=1;i<=q;i++){
scanf("%lld%lld%lld",&l,&r,&k);
printf("%lld\n",solve(l,r,k,0));
}
return 0;
}
M. Stage Clear
题意：给定一张
�
n 个点
�
m 条边的有向图，每个点上有一只怪兽，遇到一只怪兽时会先消耗
�
�
x
i
点血量，打败这只怪兽之后会再获得
�
�
y
i
点血量，过程中如果血量变为负数就输了。现在，你最开始站在
1
1 号结点，需要把所有怪兽全部打败，并且过程中不能输掉，你只能走图上的边，或是选择飞回到
1
1 号结点。求最开始至少需要有多少点血量。
�
+
�
≤
72
n+m≤72。
题解：神秘分治题。首先可以直接状压，枚举每次新转移到的点，得到一个
�
(
�
2
�
−
1
)
O(n2
n−1
) 的做法，可以通过
�
≤
26
n≤26 的数据。
对于
�
>
26
n>26 的情况，我们发现
�
≤
45
m≤45。由于每个
1
1 号点之外的点一定都至少有
1
1 的入度，所以至多有
�
−
�
+
1
≤
19
m−n+1≤19 个点拥有大于
1
1 的入度。实际上，我们遇到怪兽的顺序可以视为一棵树，每次新遇到一只怪兽时经过的边视为树边。我们可以枚举每个点在树上连向父亲的边，那么最多只有
�
(
2
�
−
�
+
1
)
O(2
m−n+1
) 种情况。现在，问题转化为一个在树上的弱化版问题。
这是一个比较经典的贪心问题。首先令
�
�
=
�
�
−
�
�
y
i
=y
i
−x
i
表示净改变血量值。考虑去除掉必须先选择父亲的限制，点与点之间的顺序是任意的，那么显然我们会优先选择
�
�
y
i
是正值的，然后再选择
�
�
y
i
是负值的。对于正值，我们一定是先选择
�
�
x
i
更小的，即按照
�
�
x
i
升序排序，这是因为这样能够让后续的选择代价变少。对于负值，我们考虑对于一个确定的初始值
�
�
�
beg，如果它在过程中不会变成负数，那么最后它变成的值
�
�
�
�
rbeg 是确定的。因此，最小化
�
�
�
beg 相当于最大化
�
�
�
�
rbeg。观察
�
�
�
�
rbeg 的限制，考虑它上一步可能是从哪些
�
i 转移过来的，那么就有
�
�
�
�
−
�
�
≥
�
�
rbeg−y
i
≥x
i
，即
�
�
�
�
≥
�
�
+
�
�
rbeg≥x
i
+y
i
，同时倒推一步会让
�
�
�
�
rbeg 加上
−
(
�
�
)
−(y
i
)，也就是一个正值，因此对于负数部分，我们会按照
�
�
+
�
�
x
i
+y
i
降序排序。
这样，我们就会获得一个优先顺序。知道了顺序之后，考虑全局优先级最高的点
�
�
�
pri。那么，一旦它的父亲被选，由于它是当前最优的选择，它一定是下一个被选择的结点。因此，我们可以直接将其与其父亲结点进行合并，这会让它们合并成一个全新的点，然后问题规模缩小
1
1，不断取出全局优先级最高的点再将其与其父亲即可。单次贪心时间复杂度
�
(
�
log
�
)
O(nlogn)。
这一种情况下的时间复杂度为
�
(
2
�
−
�
+
1
�
log
�
)
O(2
m−n+1
nlogn)。可以通过。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e18;
int n,m;
vector<int>edge[105];
vector<int>fedge[105];
int x[105],y[105];
int bx[105],by[105];
int cnt[105];
int dp[70000005];
int ret=INF;
int solve1(){
dp[1]=0;
for(int i=2;i<(1ll<<n);i++) dp[i]=INF;
int sum=0;
for(int i=1;i<(1ll<<n);i++){
for(int j=0;j<n;j++){
if(((i>>j)&1)&&(!(((i-1)>>j)&1))){
sum+=y[j+1]-x[j+1];
for(int k=0;k<edge[j+1].size();k++) cnt[edge[j+1][k]]++;
}
else if((((i-1)>>j)&1)&&(!((i>>j)&1))){
sum-=y[j+1]-x[j+1];
for(int k=0;k<edge[j+1].size();k++) cnt[edge[j+1][k]]--;
}
else break;
}
for(int j=1;j<=n;j++) if(cnt[j]&&(!((i>>(j-1))&1))) dp[i^(1<<(j-1))]=min(dp[i^(1<<(j-1))],dp[i]+max(0ll,x[j]-dp[i]-sum));
}
return dp[(1ll<<n)-1];
}
struct node{
int x,y,id;
bool operator < (const node& ano) const {
if(y>=0&&ano.y<0) return 1;
else if(y<0&&ano.y>=0) return 0;
else if(y>=0){
if(x!=ano.x) return x<ano.x;
else if(y!=ano.y) return y<ano.y;
else return id<ano.id;
}
else{
if(x+y!=ano.x+ano.y) return x+y>ano.x+ano.y;
else if(x!=ano.x) return x<ano.x;
else if(y!=ano.y) return y<ano.y;
else return id<ano.id;
}
}
};
int fa[105],f[105];
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int a,int b){
x[a]=max(x[a],x[b]-y[a]);
y[a]+=y[b];
}
bool vis[105];
vector<int>tmp[105];
bool check(int x){
vis[x]=1;
int ret=1;
for(int i=0;i<tmp[x].size();i++){
int v=tmp[x][i];
if(vis[v]) return 0;
ret&=check(v);
}
return ret;
}
int calc(){
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++) tmp[i].clear();
for(int i=2;i<=n;i++) tmp[f[i]].push_back(i);
bool ttt=check(1);
if(!ttt) return INF;
for(int i=1;i<=n;i++) if(!vis[i]) return INF;
memcpy(x,bx,sizeof x);
memcpy(y,by,sizeof y);
set<node>s;
for(int i=2;i<=n;i++) s.insert((node){x[i],y[i],i});
for(int i=1;i<=n;i++) fa[i]=i;
while(s.size()){
int u=(*s.begin()).id;
s.erase(*s.begin());
int ffu=find(f[u]);
fa[u]=ffu;
if(ffu!=1) s.erase((node){x[ffu],y[ffu],ffu});
merge(ffu,u);
if(ffu!=1) s.insert((node){x[ffu],y[ffu],ffu});
}
return x[1];
}
void dfs(int x){
if(x==n+1){
ret=min(ret,calc());
return;
}
for(int i=0;i<fedge[x].size();i++){
f[x]=fedge[x][i];
dfs(x+1);
}
}
int solve2(){
for(int i=1;i<=n;i++) y[i]-=x[i];
memcpy(bx,x,sizeof bx);
memcpy(by,y,sizeof by);
dfs(2);
return ret;
}
signed main(){
int u,v;
cin>>n>>m;
for(int i=2;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&u,&v);
edge[u].push_back(v);
fedge[v].push_back(u);
}
if(n<=26) cout<<solve1()<<endl;
else cout<<solve2()<<endl;
return 0;
}