期望得分 200
实际得分 174
话说这个第三题sub都没有... 不好骗分啊
A 排 座位
( ( arrange .pas/c/cpp)
【问题描述】
信竞队有 n 名队员，竞赛机房有一张长桌，上面一字排开有 n 台电脑，供同学们坐成一
排使用。每学期开始前，老师都要给同学们排座位。
同学之间存在仰慕(膜拜)关系，如 A 同学仰慕 B 同学，那么 A 同学就要求座位必须与 B
同学相邻。同学之间存在 m 对仰慕关系。老师想要找到使得所有同学的要求都得到满足座位
安排方案。请你帮忙计算合法方案的总数，答案可能很大，mod 989999 后再输出。
主要说一下判环的问题
首先注意到一条边的环只用在读入的时候判断一下就行了
然后对于环不是一条边的情况 我们只需要在加进集合里的时候判断是不是在一个集合就行了
也可以用top排序求环
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 989999
#define maxnn 1000010
typedef pair<int,int > P;
map<P,int > mm;
ll n,m;
int r[maxnn];
int f[maxnn];
int ru[maxnn];
ll cnt1=1,cnt2;
ll size[maxnn];
#define GC getchar()
inline ll R()
{
char t;
ll f=1;
ll x=0;
t=GC;
while(!isdigit(t)) {if(t=='-') f=-1;t=GC;}
while(isdigit(t))
{
x=x*10+t-'0';
t=GC;
}
return x*f;
}
int gf(int v)
{
return f[v]==v?v:f[v]=gf(f[v]);
}
ll jie(ll v)
{
ll tmp=1;
for(int i=1;i<=v;i++)
{
tmp=(tmp*i)%mod;
}
return tmp%mod;
}
void FIE()
{
freopen("arrange.in","r",stdin);
freopen("arrange.out","w",stdout);
}
int main()
{
//FIE();
n=R();
m=R();
ll x,y;
for(int i=1;i<=n;i++)
{
f[i]=i;
size[i]=1;
}
for(int i=1;i<=m;i++)
{
x=R();
r[x]=R();
int y=r[x];
if(r[r[x]]==x) continue;
ru[y]++;
ru[x]++;
if(ru[x]>2||ru[y]>2)
{
puts("0");
return 0;
}
int fx=gf(x);
int fy=gf(y);
if(fx!=fy)
{
size[fy]+=size[fx];
f[fx]=fy;
}
else
{
puts("0");
return 0;
}
}
for(int i=1;i<=n;i++)
{
if(f[i]==i)
{
if(size[i]>1) cnt1=(cnt1*2)%mod;;
cnt2++;
}
}
cout<<(jie(cnt2)*cnt1)%mod;
}
B 数列截段
时间限制 : - MS 空间限制 : - KB
评测说明 : 1s,256m
问题描述
老师给出一个长度为N的整数数列A。现在要求你在A中截取一段连续子序列，使得该区间的数字总和不小于X，并且不大于Y。问总共有多少种不同的截取方式？
想到用前缀和+树状数组离散化
式子可以表示为 x<=sum[j]-sum[i-1]<=y
先求x<=sum[j]-sum[i-1] 然后容斥一下减去y<sum[j]-sum[i-1]的方案之和即为答案
code:
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 500000
#define ll long long
#define lowbit(i) i&(-i)
ll sum[maxnn];
ll n,x,y;
int id[maxnn];
ll zh[maxnn];
ll c[maxnn];
ll tr=0;
#define GC getchar()
inline ll R()
{
char t;
ll f=1;
ll x=0;
t=GC;
while(!isdigit(t)) {if(t=='-') f=-1;t=GC;}
while(isdigit(t))
{
x=x*10+t-'0';
t=GC;
}
return x*f;
}
void add(int x)
{
for(int i=x;i<=3*n+100000;i+=lowbit(i))
{
c[i]++;
}
}
ll get(int x)
{
ll ans=0;
for(int i=x;i;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
void FIE()
{
freopen("cutout.in","r",stdin);
freopen("cutout.out","w",stdout);
}
int main()
{
//FIE();
ll t=0;
ll ans=0;
n=R();
x=R();
y=R();
for(int i=1;i<=n;i++)
{
t=R();
sum[i]=sum[i-1]+t;
tr++;
sum[n+tr]=sum[i]-x;
tr++;
sum[n+tr]=sum[i]-y;
zh[i]=sum[i];
}
sort(sum,sum+1+n+tr);
int r=unique(sum,sum+1+n+tr)-sum-1;
for(int i=0;i<=n;i++)
{
id[i]=lower_bound(sum,sum+1+r,zh[i])-sum+1;
}
for(int i=0;i<=n;i++)
{
ll tmp1=lower_bound(sum,sum+1+r,zh[i]-x)-sum+1;
ans+=get(tmp1);
ll tmp2=lower_bound(sum,sum+1+r,zh[i]-y)-sum+1;
ans=ans-get(tmp2-1);
add(id[i]);
}
printf("%lld",ans);
}
C 水壶
JOI君所居住的IOI市以一年四季都十分炎热著称。
IOI市是一个被分成纵H*横W块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有P个，编号为1...P。
JOI君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。
JOI君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要1单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此IOI市的市民一般都携带水壶出行。大小为x的水壶最多可以装x单位的水，建筑物里有自来水可以将水壶装满。
由于携带大水壶是一件很困难的事情，因此JOI君决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。
现在给出IOI市的地图和Q个询问，第i个询问(1<=i<=Q)为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”，请你对于每个询问输出对应的答案。
解:
复习点：BFS+最小生成树+倍增LCA
一眼货车运输的既视感，然而需要先知道两个点之间的距离。
好在这种网格图是可以BFS的，所以把每个建筑物压到队列中，跑BFS，记录每个点被哪个点所搜到，以及与搜到点的距离是多少。
当搜到另一个被其它点搜到过的点时，将它们被搜到的建筑物之间连边，这样边集只有O(4wh)。然后跑Kruskal。
（这里需要注意的是直接将这两个点在并查集中合并是不行的，因为搜到的不一定是最短距离；而按照距离排序搜索也是不对的。必须把所有可能的边连上跑最小生成树才可行。）
这个过程中可以按照距离将所有的边放到类似于桶的东西中，形成若干个链表（或者使用vector），这样能够省去排序的过程。
然后get到最小生成树之后跑倍增LCA即可。注意跑LCA时求的答案是路径最大值，不是最小值。
另外，本题不仅仅是一棵树，可能是森林，所以需要把每棵树都遍历一遍。别忘判断-1的情况。
时间复杂度O(wh+mlogn)
一句话题解
BFS连边求网格图最短路
kruskal跑最小瓶颈森林 保证所有的树都满足题目条件
无根树转有根树 倍增求LCA
code:
//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define maxnn 2005
int n,m,q,p;
char ch[maxnn];
bool mapp[maxnn][maxnn];
int las[maxnn][maxnn];
int dis[maxnn][maxnn];
int f[200010];
int ff[200010][19];
int deep[200010];
int lass[400010],en[400010],le[400010],nex[400010],tot;
int fff[200010][19];
void add(int a,int b,int c)
{
en[++tot]=b;
nex[tot]=lass[a];
lass[a]=tot;
le[tot]=c;
}
struct node
{
int st,en,le;
}ed[4000100];
int in=0;
typedef pair<int ,int > P;
bool cmp(node a,node b){
return a.le<b.le;
}
queue<P > Q;
int dx[5]={1,-1,0,0};
int dy[6]={0,0,1,-1};
void bfs()
{
while(Q.size())
{
P s=Q.front();Q.pop();
for(int i=0;i<=3;i++)
{
int tmp1=dx[i]+s.first;
int tmp2=dy[i]+s.second;
if(tmp1>=1&&tmp2>=1&&tmp2<=m&&tmp1<=n)
{
if(mapp[tmp1][tmp2]==true) continue;
if((las[tmp1][tmp2]!=las[s.first][s.second])&&(las[tmp1][tmp2]))
{
ed[++in]=node{las[tmp1][tmp2],las[s.first][s.second],dis[s.first][s.second]+dis[tmp1][tmp2]};
}
else
if(!dis[tmp1][tmp2])
{
dis[tmp1][tmp2]=dis[s.first][s.second]+1;
las[tmp1][tmp2]=las[s.first][s.second];
Q.push(make_pair(tmp1,tmp2));
}
}
}
}
}
int gff(int v)
{
return f[v]==v?v:f[v]=gff(f[v]);
}
void gf(int v){
int x=ed[v].st;
int y=ed[v].en;
int fx=gff(x);
int fy=gff(y);
if(fx==fy) return ;
f[fx]=fy;
add(x,y,ed[v].le);
add(y,x,ed[v].le);
}
void dfs(int v,int fa)
{
fff[v][0]=fa;
deep[v]=deep[fa]+1;
int d=log2(p+1000);
for(int i=1;i<=d;i++)
{
fff[v][i]=fff[fff[v][i-1]][i-1];
ff[v][i]=max(ff[v][i-1],ff[fff[v][i-1]][i-1]);
}
for(int i=lass[v];i;i=nex[i])
{
int u=en[i];
if(u!=fa)
{
ff[u][0]=le[i];
dfs(u,v);
}
}
}
int go_up(int s,int k)
{
int d=log2(p+1000);
for(int i=d;i>=0;i--)
{
if(k&(1<<i))
{
s=fff[s][i];
}
}
return s;
}
int getlca(int x,int y)
{
int tmp=0;
if(deep[x]<deep[y]) swap(x,y);
int d=x;
x=go_up(x,deep[x]-deep[y]);
int k=deep[d]-deep[y];
{
int s=log2(p+1000);
for(int i=s;i>=0;i--)
{
if(k&(1<<i))
{
tmp=max(ff[d][i],tmp);
d=fff[d][i];
}
}
}
if(x==y) return tmp;
int s=log2(p+1000);
for(int i=s;i>=0;i--)
{
if(fff[x][i]!=fff[y][i])
{
tmp=max(ff[x][i],tmp);
tmp=max(ff[y][i],tmp);
x=fff[x][i];
y=fff[y][i];
}
}
tmp=max(tmp,ff[x][0]);
tmp=max(tmp,ff[y][0]);
return tmp;
}
void FIE()
{
freopen("kettle.in","r",stdin);
freopen("tesss","w",stdout);
}
int main()
{
//FIE();
scanf("%d%d%d%d",&n,&m,&p,&q);
for(int i=1;i<=p;i++)
{
f[i]=i;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ch+1);
for(int j=1;j<=m;j++)
{
if(ch[j]=='#')
{
mapp[i][j]=true;
}
}
}
int x1,y1;
int x,y;
for(int i=1;i<=p;i++)
{
scanf("%d%d",&x1,&y1);
las[x1][y1]=i;
dis[x1][y1]=0;
Q.push(make_pair(x1,y1));
}
bfs();
sort(ed+1,ed+1+in,cmp);
for(int i=1;i<=in;i++)
{
gf(i);
}
for(int i=1;i<=p;i++)
{
if(f[i]==i)
{
dfs(i,i);
}
}
while(q--)
{
scanf("%d%d",&x,&y);
if(gff(x)!=gff(y))
{
puts("-1");
}
else
{
printf("%d
",getlca(x,y));
}
}
}