频频和省选、ICPC 区域赛撞题的 POI ，是何方神圣？

ACM算法日常

发布于 2021-10-27 15:03:10

6940

发布于 2021-10-27 15:03:10

文章被收录于专栏：ACM算法日常

POI 是波兰高中生信息学全国竞赛，曾经和不少省选和 ICPC 区域赛撞过题，当然 POI 的题目出现的是更早。

这也从某一方面说明了 POI 题目质量非常高。

今天我们来看一看 POI 2004 年的题目。

想要做题的同学们，可以在 luogu、bzoj 等各大网站上直接搜 POI2004 即可。

Game

考虑所有空的格子排成一串，相邻两个空的格之间设为一级台阶（从左到右逐级降低），这级台阶上的石子数量即为这两空格之间的棋子数量

为了方便处理，我们把数组倒序排放

可以看出一次棋子移动等价于把第

n+1

号台阶上的任意颗石子移动到第

级。我们从

开始编号

那么，我们可以发现，其实奇数位是没有影响的，显然，移到

位置的时候会出现败态

从奇数位到偶数位，我们在移回来即可

但是可以发现，偶数位的移动

颗棋子，相当于去掉了这

颗棋子

也就是，现在转化成了nim取石子了。那么，我们判断偶数位的

xor

值便可以得到先手的胜败态

现在要求的是先手胜利，第一步的方案数

显然，就是要求让每一个偶数位经过更改，使得

xor=0

的情况

而

xor

的性质就是，只有相等的时候才

，且

xor

可逆，那么直接

O(n)

枚举即可

不过要注意一些边界的情况

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#define LL long long

using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,m,a[1000010],b[4000100];

bool cmp(int x,int y)
{
 return x>y; 
}

int main()
{
 read(n);read(m);
 for (int i=1;i<=m;i++)
  read(a[i]);
 sort(a+1,a+1+m,cmp);
 int x=n,p=-1;
 for (int i=1;i<=m;i++)
  if (a[i]==x) b[p]++,x--;
  else
  {
   if (x-a[i]==2) b[++p]=0,b[++p]=1;
   else if ((x-a[i])%2==0) b[++p]=0,b[++p]=0,b[++p]=0,b[++p]=1;
   else if (x-a[i]==1)b[++p]=1;
   else b[++p]=0,b[++p]=0,b[++p]=1;
   x=a[i]-1;
  }
 int f=0;
 for (int i=0;i<=p;i++)
  if (i%2==0) f^=b[i];
 if (f==0) {print(f),putchar('\n');return 0;}
 int ans=0,t;
 if (p%2==0)
 {
  t=f^b[p];
  if (b[p]>t) ans++;
 }
 ans+=b[0];
 t=f^b[0];
 for (int i=2;i<p;i++)
  if (i%2==0)
  {
   t=f^b[i];
   if (b[i]>t || b[i]<t && b[i]+b[i+1]>=t) ans++;
  }
 print(ans),putchar('\n');
 return 0;
}

Strings

首先考虑第一问

对于一个节点

，用

f[i]

表示覆盖

为根节点的子树和

(i,fa(i))

这条边所需的最少线段树

我们来讨论一个节点

的

f[x]

求法

显然，不考虑合并线段的话，那么

f[x]=\sum f[y]

(

是

的孩子)

但我们可以任意的把两两的线段合并起来（包括

(i,fa(i))

）,我们假设他有

和孩子，那么

f[x]

也就是

\sum f[y]

(

是

的孩子)

+1-[(d+1)/2]

对于第二问，考虑二分

我们二分线段的长度上界

设

g[u]

表示将

的子树中所有边以及边

(u,p[u])

按上述方法覆盖（并满足

的限制）后，边

(u,p[u])

所在线条的最小长度

记

的孩子为

v_1,v_2,…,v_d

。不妨设

d+1

为偶数，恰好需要将

d+1

根线头两两配对（若

d+1

是奇数，添一根长度

g[v]=0

的线头，不会影响结果）

假设与

(u,p[u])

配对的线头来自

v_k

，剩下的

g[v_1],g[v_2],…g[v_k-1],g[v_k+1],…,g[v_d]

的最优配法是排序后首尾配对，配完后检查能否都在

以内

从而可以二分出

g[v_k]

的最小值，于是

g[u]=g[v_k]+1

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#define LL long long

using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,d[10010],f[10010],fa[10010],g[10010];
bool c[10010];
vector <int > b[10010];

void dfs(int x)
{
 c[x]=true;
 int s=0,y=0;
 for (int i=0;i<b[x].size();i++)
  if (!c[b[x][i]]) 
  {
   fa[b[x][i]]=x;
   dfs(b[x][i]);
   s+=f[b[x][i]];
   y++;
  }
 f[x]=s+1-((int)(y+1)/2);
}

bool check(int y,int x)
{
 vector<int > p;
 c[x]=true;
 int s=0;
 bool flag=true;
 for (int i=0;i<b[x].size();i++)
  if (!c[b[x][i]]) 
  {
   flag&=check(y,b[x][i]);
   p.push_back(g[b[x][i]]);
  }
 if (p.size()==0)
 {
  g[x]=1;
  return flag&&(g[x]<=y);
 }
 else if (p.size()%2==0) p.push_back(0);
 sort(p.begin(),p.end());
 int l=0,r=p.size()-1,mid,res=-1;
 while (l<=r)
 {
  mid=(l+r)>>1;
  int xx=-1,yy=p.size(),Max=0;
  while (xx+1<yy-1)
  {
   xx++;yy--;
   if (xx==mid) xx++;
   if (yy==mid) yy--;
   if (p[xx]+p[yy]>Max) Max=p[xx]+p[yy];
  }
  if (Max<=y) res=mid,r=mid-1;
  else l=mid+1;
 }
 if (res>=0) g[x]=p[res]+1;
 return flag&&(g[x]<=y)&&(res>=0);
}

int main()
{
 read(n);
 int x,y,w;
 for (int i=1;i<n;i++)
  read(x),read(y),d[x]++,d[y]++,b[x].push_back(y),b[y].push_back(x);
 for (int i=1;i<=n;i++)
  if (d[i]==1) {w=i;break;}
 memset(f,0,sizeof(f));
 memset(c,false,sizeof(c));
 fa[b[w][0]]=w;c[w]=true; 
 dfs(b[w][0]);
 print(f[b[w][0]]);putchar(' ');
 int l=1,r=n,mid,res;
 while (l<=r)
 {
  mid=(l+r)>>1;
  memset(c,false,sizeof(c));c[w]=true;
  memset(g,0,sizeof(g));
  if (check(mid,b[w][0])) res=mid,r=mid-1;
  else l=mid+1;
 }
 print(res);putchar('\n');
 return 0;
}

Spies

贪心地选择当前点

为观察员，那么

a[x]

为

spy

，则，下一个观察员为

a[a[x]]

用拓扑排序来实现。显然，当没有读入为

的点时，剩下的为环，那么，继续在环上贪心的找即可

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<queue>
#define LL long long

using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,a[1000010],d[1000000];
bool v[1000010];
queue<int> q;

int main()
{
 read(n);
 memset(d,0,sizeof(d));
 for (int i=1;i<=n;i++)
  read(a[i]),d[a[i]]++;
 for (int i=1;i<=n;i++)
  if (d[i]==0) q.push(i);
 memset(v,false,sizeof(v));
 int ans=0;
 while (!q.empty())
  if (!v[q.front()] && !v[a[q.front()]])
  {
   int x=q.front();q.pop();
   v[x]=true;v[a[x]]=true;
   d[a[a[x]]]--;
   ans++;
   if (d[a[a[x]]]==0) q.push(a[a[x]]);
  }
  else q.pop();
 for (int i=1;i<=n;i++)
  if (!v[i])
  {
   int x=i,i=0;
   while (!v[x] && !v[a[x]])
   {
    ans++;i++;
    v[x]=true;v[a[x]]=true;
    x=a[a[x]];
   }
  }
 print(ans);putchar('\n');
 return 0;
}

The Competition

首先考虑暴力的做法，枚举出发点和结束点，即

1->x->...->y->1

然后寻找

x->y

的不经过

的最短路

时间复杂度

O(n^2logn)

，吃不消

考虑优化，我们变成枚举一个点

，那么我们需要得到

1->x->...->y

的最短路

d[y]

，然后要保证现在

x!=y

,那么我们用

p[y]

表示到

的最短路的

后面一个点是

p[y]

，这样，只要

y!=p[y]

，就是合法的；那么如果

y=p[y]

的话，我们需要另找一条路径，也就是

p[y]!=y

的最短路

以上需要的最短路和次短路，可分别经过两边最短路算法得到，然后只需要枚举

即可

时间复杂度

O(2*nlogn)

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<queue>
#include<cmath>
#define LL long long

using namespace std;

inline char nc(){
  ///*
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
  //*/getchar();
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,m,d1[5010],p1[5010],d2[5010],p2[5010];
bool v[5010];
struct data
{
 int x,y;
 data(int a=0,int b=0):x(a),y(b) {}
};
struct cmp
{
 bool operator() (data x,data y)
 {
  return x.x>y.x;
 }
};
vector <data> a[5010];
priority_queue<data,vector<data>,cmp> q;
const int inf=1000000000;

int main()
{
 read(n);read(m);
 int x,y,Z1,Z2;
 for (int i=1;i<=m;i++)
  read(x),read(y),read(Z1),read(Z2),a[x].push_back(data(y,Z1)),a[y].push_back(data(x,Z2));
 memset(v,false,sizeof(v));
 for (int i=1;i<=n;i++)
  d1[i]=inf;
 d1[1]=0;
 for (int i=0;i<a[1].size();i++)
  p1[a[1][i].x]=a[1][i].x,d1[a[1][i].x]=min(d1[a[1][i].x],a[1][i].y),q.push(data(d1[a[1][i].x],a[1][i].x));
 while (!q.empty())
 {
  int x=q.top().y,y=q.top().x;q.pop();
  if (y>d1[x]) continue;
  //d1[x]=y;
  if (x==1) continue;
  for (int i=0;i<a[x].size();i++)
   if (d1[a[x][i].x]>d1[x]+a[x][i].y)
    p1[a[x][i].x]=p1[x],d1[a[x][i].x]=d1[x]+a[x][i].y,q.push(data(d1[a[x][i].x],a[x][i].x));
 }
 for (int i=1;i<=n;i++)
  d2[i]=inf;
 d2[1]=0;p2[1]=1;
 for (int i=0;i<a[1].size();i++)
  if (p1[a[1][i].x]!=a[1][i].x)
   p2[a[1][i].x]=a[1][i].x,d2[a[1][i].x]=min(d2[a[1][i].x],a[1][i].y),q.push(data(d2[a[1][i].x],a[1][i].x));
  else
  {
   p2[a[1][i].x]=a[1][i].x,q.push(data(d2[a[1][i].x],a[1][i].x));
   if (d2[a[1][i].x]==inf) d2[a[1][i].x]=a[1][i].y;
  }
 while (!q.empty())
 {
  int x=q.top().y,y=q.top().x;q.pop();
  if (x==1) continue;
  for (int i=0;i<a[x].size();i++)
   if (d2[a[x][i].x]>d1[x]+a[x][i].y && (p1[a[x][i].x]!=p1[x] || p2[a[x][i].x]==0 || p2[a[x][i].x]==p1[a[x][i].x]) || p1[a[x][i].x]==p2[a[x][i].x] && p1[x]!=p2[a[x][i].x])
    p2[a[x][i].x]=p1[x],d2[a[x][i].x]=d1[x]+a[x][i].y,q.push(data(d2[a[x][i].x],a[x][i].x));
  for (int i=0;i<a[x].size();i++)
   if (d2[a[x][i].x]>d2[x]+a[x][i].y && (p1[a[x][i].x]!=p2[x] || p2[a[x][i].x]==0 || p2[a[x][i].x]==p1[a[x][i].x]) || p1[a[x][i].x]==p2[a[x][i].x] && p2[x]!=p2[a[x][i].x])
    p2[a[x][i].x]=p2[x],d2[a[x][i].x]=d2[x]+a[x][i].y,q.push(data(d2[a[x][i].x],a[x][i].x));
 }
 int ans=inf;
 for (int i=2;i<=n;i++)
  for (int j=0;j<a[i].size();j++)
   if (a[i][j].x==1)
   {
    if (i!=p1[i]) ans=min(ans,a[i][j].y+d1[i]);
    else if (i!=p2[i]) ans=min(ans,a[i][j].y+d2[i]);
   }
 print(ans),putchar('\n');
 return 0;
}

The Bridge

显然，对于一个人

，他有两种最有的方法过桥：

1、选择时间最少的

a[1]

与他过去，

a[1]

回去，

t=a[x]+a[1]

2、选择一个时间和他差不多的过去，在让另一个小的回来，

t=a[x+1]+a[1]+a[2]*2

注意特判

n=1

的情况

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#define LL long long

using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n;
LL a[100010],f[100010];

int main()
{
 read(n);
 for (int i=1;i<=n;i++)
  read(a[i]);
 if (n<=2) return print(a[n]),putchar('\n'),0; 
 for(int i=n;i>1;i--)
 {
  f[i]=f[i+1]+a[i]+a[1];
  if (i>2 && i<n) f[i]=min(f[i],f[i+2]+a[1]+a[2]*2+a[i+1]);
 }
 f[1]=f[2]-a[1];
 print(f[1]),putchar('\n');
 return 0;
}

Gates

一次尽可能的把所有的点标向

，另一次尽可能的把所有的点标向

具体的BFS方法是：以标为

为例，先把出去

、

以外的所有点的输入全部标为

，然后从

开始拓展，一旦一个点的类型发生了改变，入队，以此BFS即可

最后，两边BFS结果类型一样的，说明是确定的，否则输出“？”

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<queue>
#include<cmath>
#define LL long long

using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,d[10010],f[10010];
vector <int > a[10010];
struct data
{
 int a[3];
 int cal()
 {
  if (a[0]>a[1]) return 0;
  if (a[1]>a[0]) return 1;
  if (a[0]==a[1])return 2;
 }
}f1[10010],f2[10010];

int main()
{
 read(n);
 int x,y;
 memset(d,0,sizeof(d));
 memset(f1,0,sizeof(f1));
 memset(f2,0,sizeof(f2));
 for (int i=2;i<n;i++)
 {
  read(x);
  while (x--) read(y),d[i]++,a[y].push_back(i);
  f1[i].a[0]=d[i];f2[i].a[1]=d[i];
 }
 f1[0].a[0]=1;f1[1].a[1]=1;
 f2[0].a[0]=1;f2[1].a[1]=1;
 queue<int> q;
 q.push(1);
 f[1]=0;f[0]=0;
 for (int i=2;i<n;i++)
  f[i]=f1[i].cal();
 while (!q.empty())
 {
  int x=q.front(),y;q.pop();
  if (f1[x].cal()==f[x]) continue;
  y=f[x],f[x]=f1[x].cal();
  for (int i=0;i<a[x].size();i++)
  {
   f1[a[x][i]].a[y]--;
   if (f1[x].cal()==1) f1[a[x][i]].a[1]++;
   else if (f1[x].cal()==2) f1[a[x][i]].a[2]++;
   else f1[a[x][i]].a[0]++;
   if (f1[a[x][i]].cal()!=f[a[x][i]]) q.push(a[x][i]);
  }  
 }
 q.push(0);
 f[1]=1;f[0]=1;
 for (int i=2;i<n;i++)
  f[i]=f2[i].cal();
 while (!q.empty())
 {
  int x=q.front(),y;q.pop();
  if (f2[x].cal()==f[x]) continue;
  y=f[x],f[x]=f2[x].cal();
  for (int i=0;i<a[x].size();i++)
  {
   f2[a[x][i]].a[y]--;
   if (f2[x].cal()==0) f2[a[x][i]].a[0]++;
   else if (f2[x].cal()==2) f2[a[x][i]].a[2]++;
   else f2[a[x][i]].a[1]++;   
   if (f2[a[x][i]].cal()!=f[a[x][i]]) q.push(a[x][i]);
  }
 }
 for (int i=0;i<n;i++)
  if (f1[i].cal()==f2[i].cal())
  {
   if (f2[i].cal()<=1) print(f2[i].cal()),putchar('\n');
   else putchar('1'),putchar('/'),putchar('2'),putchar('\n');
  }
  else putchar('?'),putchar('\n');
 return 0;
}

Passage

考虑直接状压来做，对于当前状态

，表示每个人是否已经过去了，那么预处理的时候，首先把所有的人排序，然后我们可以找到时间最长的一个人，这个人一定要过去了

因为当前来说，他花费的时间最长，一定有一个时间是他的，然后暴力枚举他可以带走的人

O(2^n)

这样，乍一看时间复杂度是

O((2^n)^2)

，会TLE？

我们来仔细证明一下复杂度：

求解

f[X]

最坏情况下需暴力枚举

2^(k-1)

次,这样的集合

C_n^k

个。对所有状态求和，总共需要枚举次数为

T(\sum_{k1}^{n}C_n^k*2^{k-1})=T(3^n)

那么

3^{16}=4kw+

，粗略看起来是卡的进去的....事实确实如此

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
 char c=nc();int len=0;
 for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
 for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
 s[len++]='\0';
 return len;
}

inline void read(char &x){
  for (x=nc();!(x=='R' || x=='B');x=nc());
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-'); 
 if (!x) putchar(48); else {
 for (wt=0;x;ss[++wt]=x%10,x/=10);
 for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,f[50010]; 
vector <int> a[50010];
set <int > s[50010];
bool v[50010];

void dfs(int x)
{
 v[x]=true;int flag=0,Max=-1;
 int b[20];
 memset(b,0,sizeof(b));
 set<int>::iterator j;
 for (int i=0;i<a[x].size();i++)
  if (!v[a[x][i]])
  {
   flag=1;
   dfs(a[x][i]);
   for (j=s[a[x][i]].begin();j!=s[a[x][i]].end();j++)
    b[*j]++,s[x].insert(*j);
  }
 if (flag==0)
 {
  f[x]=0;
  s[x].insert(0);
  return ;
 }
 for (int i=1;i<20;i++)
  if (b[i]>1) Max=max(Max,i);
 Max++;
 while (*s[x].begin()<=Max)
 {
  if (Max==*s[x].begin()) Max++;
  s[x].erase(*s[x].begin());
  if (s[x].empty()) break;
 }
 s[x].insert(Max);f[x]=*s[x].rbegin();
}

int main()
{
 read(n);
 int x,y;
 for (int i=1;i<n;i++)
  read(x),read(y),a[x].push_back(y),a[y].push_back(x);
 memset(v,false,sizeof(v));
 dfs(1);
 int res=0;
 for (int i=1;i<=n;i++)
  res=max(res,f[i]);
 print(res),puts("");
 return 0;
}

The Tournament

几个结论：

1、出度最大的点，一定是可以胜利的点

2、和可能胜利的点之间没有直接输赢关系的点，均是可能胜利的点

那么，我们可以根据性质1，直接求出一个点来

然后剩下的问题就是求和第一个点在补图上联通的点

直接bfs就可以解决，具体的方法是次枚举一个未在连通块的点，然后从它开始宽搜出它所在的连通块

具体是枚举它的所有原图的边，标记起来，枚举边之后再枚举所有的点，将未标记的点加入该连通块，并加入队列继续宽搜

为了加快速度，开了链表来存未在当前联通块中的点

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<list>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
 char c=nc();int len=0;
 for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
 for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
 s[len++]='\0';
 return len;
}

inline void read(char &x){
  for (x=nc();!(x=='R' || x=='B');x=nc());
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-'); 
 if (!x) putchar(48); else {
 for (wt=0;x;ss[++wt]=x%10,x/=10);
 for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,a[100010],v[100010],ans[100010];
vector<int> b[100010];
list <int> q,c;

int main()
{
 read(n);
 int x,y;
 for (int i=1;i<=n;i++)
 {
  read(x);a[i]=x;
  b[i].push_back(0);
  while (x--) read(y),b[i].push_back(y);
  b[i].push_back(n+1);
 }
 int Max=-1,w=0;
 for (int i=1;i<=n;i++)
  if (a[i]>Max) Max=a[i],w=i;
 q.push_back(w);
 for (int i=1;i<=n;i++)
  if (i!=w) c.push_back(i);
 int s=0;
 while (!q.empty())
 {
  x=*q.begin();q.pop_front();s++;ans[s]=x;
  for (int i=0;i<b[x].size();i++)
   v[b[x][i]]=s;
  for (list<int>::iterator i=c.begin(),z;i!=c.end();)
   if (v[*i]!=s) q.push_back(*i),z=i,i++,c.erase(z,i),i=c.begin();else i++;
 }
 print(s),putchar(' ');
 sort(ans+1,ans+1+s);
 for (int i=1;i<s;i++)
  print(ans[i]),putchar(' ');
 print(ans[s]),putchar('\n');
 return 0;
}

East-West

mdzz....内存卡的好紧啊

假设我们已经找到了分割点（就是能把东海岸的点和西海岸的点分开的点）

那么，显然，对于分割点到西海岸的时间局势他们的距离

g[i]

因为从东海岸到西海岸必经这个点，所以从这个点出发的火车，出发时间各不相同，显然不会冲突

那么考虑东边的怎么处理，我们用

f[i]

表示东海岸结点

到分割点的距离，那么求完以后排序

显然，为了解决冲突，排序以后

f[i]=max{f[i],f[i-1]+1}

这样以后，我们把

f[i]

和

g[i]

大小搭配，求得最小解即可

现在的关键是怎么求分割点，显然我们可以用lca来做，但是无论是倍增求LCA还是树剖来做，都要爆内存......

考虑用染色来解决:方法是把所有西端节点标号

，如果一个点有

≥2

个的有标号节点儿子则标号

，如果有

个有标号儿子标号

，深度最小的标号为

的点即为关键结点，可以直观的画个图来理解

那么，在求出关键点以后，直接dfs一遍就可以求出

f[i]

和

g[i]

了咯

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
 char c=nc();int len=0;
 for(;!(c>='A' && c<='Z');c=nc()) if (c==EOF) return 0;
 for(;(c>='A' && c<='Z');s[len++]=c,c=nc());
 s[len++]='\0';
 return len;
}

inline void read(char &x){
  for (x=nc();!(x>='A' && x<='Z');x=nc());
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-'); 
 if (!x) putchar(48); else {
 for (wt=0;x;ss[++wt]=x%10,x/=10);
 for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,m,w,z,po,f[1000010],a[1000010];
vector<int> b[1000010];

void work(int x)
{
 int s=0;
 for (int i=0;i<b[x].size();i++)
  if (f[b[x][i]]==0)
  {
   f[b[x][i]]=f[x]+1;
   work(b[x][i]);
   if (a[b[x][i]]>0) s++;
  }
 if (s>1 || x>=n-z+1) a[x]=2;
 else if (s==1) a[x]=1;
 else a[x]=0;
}

void dfs(int x)
{
 a[x]=1;
 for (int i=0;i<b[x].size();i++)
  if (!a[b[x][i]])
  {
   f[b[x][i]]=f[x]+1;
   dfs(b[x][i]);
  }
}

int main()
{
 read(n);read(w),read(z);
 int x,y;
 for (int i=1;i<n;i++)
  read(x),read(y),b[x].push_back(y),b[y].push_back(x);
 memset(f,0,sizeof(f));
 memset(a,0,sizeof(a));
 f[1]=1;work(1);
 int D=INT_MAX,LCA=0;
 for (int i=1;i<=n;i++)
  if (a[i]==2) if (f[i]<D) D=f[i],LCA=i;
 memset(a,0,sizeof(a));
 memset(f,0,sizeof(f));
 dfs(LCA);
 read(m);
 for (int i=1;i<=m;i++)
  read(x),a[i]=f[x];
 sort(a+1,a+1+m);
 for (int i=2;i<=m;i++)
  a[i]=max(a[i-1]+1,a[i]);
 for (int i=n-z+1;i<=n;i++)
  f[i-(n-z)]=f[i];
 sort(f+1,f+1+z);
 int ans=0;
 for (int i=1;i<=m;i++)
  ans=max(ans,f[i]+a[m-i+1]);
 print(ans),puts("");
 return 0;
}

Maximal Orders of Permutations

先不考虑字典序的问题，我们先来解决第一个问题：有

\sum_{i=1}^{k} x_i\leq n

(

\sum_{i=1}^{k} x_i<n

的时候用

填充)求

LCM\{x_1,x_2,...,x_k\}

的最大值

容易证明

x_i

均为质数的幂次且两两互异的时候LCM最大，于是

LCM\{x_1,x_2,...,x_k\}=\prod_{i=1}^{k}x_i

的乘积

那就打一张质数表，然后直接用背包问题解决这个最大值即可，需要注意乘积会很大，我们直接取个对数做加法就好

然后怎么求得方案呢？显然对于每一个状态记录下所有的值会MLE

我是直接记录了前一个状态的下标，然后倒着做一遍，求得结果就好

试几组大数据后发现，我们的质数表打到

400

以内就够了，不到

100

个质数

现在还剩一个问题，求得了

\{x_1,x_2,...,x_k\}

，怎么使得字典序最小

这个其实观察一下样例就可以发现，首先我们要把

\{x_1,x_2,...,x_k\}

按照升序排序，然后每一个置换都是从第二个开始，把第一个放在最后，这样是最优的

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
 char c=nc();int len=0;
 for(;!(c>='A' && c<='Z');c=nc()) if (c==EOF) return 0;
 for(;(c>='A' && c<='Z');s[len++]=c,c=nc());
 s[len++]='\0';
 return len;
}

inline void read(char &x){
  for (x=nc();!(x>='A' && x<='Z');x=nc());
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-'); 
 if (!x) putchar(48); else {
 for (wt=0;x;ss[++wt]=x%10,x/=10);
 for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int T,n,m,P,p[110],ans[110],a[10010];
struct data
{
 double x;int prex,prey;
} f[110][10010];

bool check_prime(int x)
{
 for (int i=2;i<=sqrt(x);i++)
  if (x%i==0) return false;
 return true;
}

void init()
{
 P=0;
 for (int i=2;i<=400;i++)
  if (check_prime(i)) p[++P]=i;
}

int main()
{
 read(T);
 init();
 while (T--)
 {
  read(n);
  for (int i=0;i<=n;i++)
   f[1][i].x=-1.0;
  f[1][0].prex=0,f[1][0].prey=0,f[1][0].x=0.0;
  int x=p[1];
  while (x<=n) f[1][x].prex=0,f[1][x].prey=0,f[1][x].x=log((double)x),x*=p[1];
  for (int i=2;i<=P;i++)
  {
   for (int j=0;j<=n;j++)
   {
    f[i][j].x=f[i-1][j].x;
    f[i][j].prex=i-1,f[i][j].prey=j;
    x=p[i];
    while (j-x>=0)
    {
     if (f[i-1][j-x].x>=0.0)
     if (f[i-1][j-x].x+log(double(x))>f[i][j].x)
     {
      
      f[i][j].x=f[i-1][j-x].x+log(double(x));
      f[i][j].prex=i-1,f[i][j].prey=j-x;
     }
     x*=p[i];
    }
   }
  }
  double Max=0;int w=0;
  for (int i=0;i<=n;i++)
   if (f[P][i].x>Max) Max=f[P][i].x,w=i;
  x=P;int y=w,s=0,u,v,k=0;
  while (x!=0)
  {
   if (f[x][y].prey!=y) ans[++s]=y-f[x][y].prey,k+=y-f[x][y].prey;
   u=x,v=y;
   x=f[u][v].prex,y=f[u][v].prey;
  }
  while (k<n) k++,ans[++s]=1;
  sort(ans+1,ans+1+s);
  int q=1;
  for (int i=1;i<=s;i++)
  {
   if (ans[i]==1) a[q]=q;
   else
   {
    for (int j=q;j<q+ans[i]-1;j++)
     a[j]=j+1;
    a[q+ans[i]-1]=q;
   }
   q+=ans[i];
  }
  for (int i=1;i<n;i++)
   print(a[i]),putchar(' ');
  print(a[n]),puts("");
 }
 return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

poi

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

poi