POI 是波兰高中生信息学全国竞赛,曾经和不少省选和 ICPC 区域赛撞过题,当然 POI 的题目出现的是更早。
这也从某一方面说明了 POI 题目质量非常高。
今天我们来看一看 POI 2004 年的题目。
想要做题的同学们,可以在 luogu、bzoj 等各大网站上直接搜 POI2004 即可。
Game
考虑所有空的格子排成一串,相邻两个空的格之间设为一级台阶(从左到右逐级降低),这级台阶上的石子数量即为这两空格之间的棋子数量
为了方便处理,我们把数组倒序排放
可以看出一次棋子移动等价于把第
号台阶上的任意颗石子移动到第
级。我们从
开始编号
那么,我们可以发现,其实奇数位是没有影响的,显然,移到
位置的时候会出现败态
从奇数位到偶数位,我们在移回来即可
但是可以发现,偶数位的移动
颗棋子,相当于去掉了这
颗棋子
也就是,现在转化成了nim取石子了。那么,我们判断偶数位的
值便可以得到先手的胜败态
现在要求的是先手胜利,第一步的方案数
显然,就是要求让每一个偶数位经过更改,使得
的情况
而
的性质就是,只有相等的时候才
,且
可逆,那么直接
枚举即可
不过要注意一些边界的情况
代码语言:javascript复制#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,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,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
首先考虑第一问
对于一个节点
,用
表示覆盖
为根节点的子树和
这条边所需的最少线段树
我们来讨论一个节点
的
求法
显然,不考虑合并线段的话,那么
(
是
的孩子)
但我们可以任意的把两两的线段合并起来(包括
),我们假设他有
和孩子,那么
也就是
(
是
的孩子)
对于第二问,考虑二分
我们二分线段的长度上界
设
表示将
的子树中所有边以及边
按上述方法覆盖(并满足
的限制)后,边
所在线条的最小长度
记
的孩子为
。不妨设
为偶数,恰好需要将
根线头两两配对(若
是奇数,添一根长度
的线头,不会影响结果)
假设与
配对的线头来自
,剩下的
的最优配法是排序后首尾配对,配完后检查能否都在
以内
从而可以二分出
的最小值,于是
代码语言:javascript复制#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,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,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
贪心地选择当前点
为观察员,那么
为
,则,下一个观察员为
用拓扑排序来实现。显然,当没有读入为
的点时,剩下的为环,那么,继续在环上贪心的找即可
代码语言:javascript复制#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,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,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
首先考虑暴力的做法, 枚举出发点和结束点,即
然后寻找
的不经过
的最短路
时间复杂度
,吃不消
考虑优化,我们变成枚举一个点
,那么我们需要得到
的最短路
,然后要保证现在
,那么我们用
表示到
的最短路的
后面一个点是
,这样,只要
,就是合法的;那么如果
的话,我们需要另找一条路径,也就是
的最短路
以上需要的最短路和次短路,可分别经过两边最短路算法得到,然后只需要枚举
即可
时间复杂度
代码语言:javascript复制#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,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,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、选择时间最少的
与他过去,
回去,
2、选择一个时间和他差不多的过去,在让另一个小的回来,
注意特判
的情况
代码语言:javascript复制#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,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,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结果类型一样的,说明是确定的,否则输出“?”
代码语言:javascript复制#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,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,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
考虑直接状压来做,对于当前状态
,表示每个人是否已经过去了,那么预处理的时候,首先把所有的人排序,然后我们可以找到时间最长的一个人,这个人一定要过去了
因为当前来说,他花费的时间最长,一定有一个时间是他的,然后暴力枚举他可以带走的人
这样,乍一看时间复杂度是
,会TLE?
我们来仔细证明一下复杂度:
求解
最坏情况下需暴力枚举
次,这样的集合
共有
个。对所有状态求和,总共需要枚举次数为
那么
,粗略看起来是卡的进去的....事实确实如此
代码语言:javascript复制#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 ]='