- A题 Ares, Toilet Ares 阅读理解题、签到
大意：题目有点难懂，有个数字 a代表已经写对了,对于一道题有k 次获得代码的机会，每次获得的代码长度为 x,错误的概率为 p (分数形式)。当代码长度为 L 才能写对这道题，题目保证 k 次 的 x 的和为 L。求写对的题目数的期望值，结果对质数取模
思路：因为题目已经确保 x 的和为 L , 所以直接计算概率算出的就是写对这道题的期望值。最后加上 a。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int M=4933;
typedef long long LL;
int qmi(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=(LL)res*a%M;
a=(LL)a*a%M;
b>>=1;
}
return res;
}
int n,m,k,a,l;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k>>a>>l;
LL res=1;
for(int i=1,x,y,z;i<=k;i++)
{
cin>>x>>y>>z;
if(x==0)continue;// x 为 0 不获得代码，不计算概率
y=z-y;
res=res*y*qmi(z,M-2)%M;
}
cout<<(res+a)%M<<"\n";
return 0;
}
- D题 Dohna Dohna 思维，二进制
大意：给定 b数组和 c 数组，
b
=
(
b
2
.
.
.
.
.
.
b
n
)
b=(b_2......b_n)
b=(b2?......bn?)
c
=
(
c
2
.
.
.
.
.
.
c
n
)
c=(c_2......c_n)
c=(c2?......cn?) 并且定义
b
i
=
a
i
∣
a
i
?
1
b_i=a_i|a_{i-1}
bi?=ai?∣ai?1?
c
i
=
a
i
+
a
i
?
1
c_i=a_i+a_{i-1}
ci?=ai?+ai?1? 给出 b 数组和 c 数组，求满足条件的 a 数组的个数
思路：对于 b 数组，代表的是a数组进行或运算，对于有关位运算的题目，很多都是从二进制的角度思考问题，单独考虑每个位的影响，但是还有个 c 数组涉及到加法，涉及到进位，不能单独考虑每个位了。但是我们有个公式
a
+
b
=
(
a
∣
b
)
+
(
a
&
b
)
a+b=(a|b)+(a\&b)
a+b=(a∣b)+(a&b) 这样我们就将根据题目中的加法和或运算的限制转化成于运算，然后我们就可以单独考虑每个为了。我们对于每个位，要么取0,要么取1.我们可以设置两个变量，0代表不能取，1代表能取，对于每一位的贡献就是乘法原理。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long LL;
int n,b[N],c[N],d[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=2;i<=n;i++)cin>>b[i];
for(int i=2;i<=n;i++)cin>>c[i];
for(int i=2;i<=n;i++)d[i]=c[i]-b[i];
LL ans=1;
for(int i=30;i>=0;i--)
{
int bit1=1,bit0=1;
for(int j=2;j<=n;j++)
{
int nw1=0,nw0=0;
int x=b[j]>>i&1,y=d[j]>>i&1;
if(x&&y)nw1=bit1;
if(x&&!y)nw1=bit0,nw0=bit1;
if(!x&&!y)nw0=bit0;
bit1=nw1,bit0=nw0;
}
ans=ans*(bit0+bit1);
}
cout<<ans<<"\n";
return 0;
}
- E题 Rise of Shadows 签到
- F题 Robots 思维，预处理，dp
大意：给定一个 n * m 的格子，n,m<=500。格子中有些点不能走，有三种机器人，第一种只能往下走，第一种只能往右走，第三种既可以往下又可以往右走。q次询问 (q<=5e5)，每次询问给出机器人的类型，以及起点和终点的坐标，问是否能到达。
思路：这题暴力写可以过，官方解给的是分治。先来看看暴力怎么写。我们看到n,m 不大，但是询问很多，所以我们想到先进行预处理。我们先预处理出从该点能到的点，可以用bitset，0/1 表示某个点能不能到。但是呢？这样空间复杂度太大了，我们把点坐标映射成数字，那么也得 500*500 个数字，也就是要开个 二维都是500 * 500 的 bitset。但是呢，仔细想想，我们从后往前预处理枚举起点(x,y)的时候只会用到 (x+1,y) 和 (x,y+1) 两个起点去更新，所以对于起点我们可以不用开这么大，我们可以用把所有的询问存下来，用滚动数组，边求点，边更新询问。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=505;
typedef pair<int,int> PII;
int n,m,q;
char g[N][N];
bitset<N*N>f[2][N];
vector<PII> qer[N*N];
bool ans[N*1000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)cin>>g[i];
cin>>q;
for(int i=1;i<=q;i++)
{
int op,sx,sy,ex,ey;
cin>>op>>sx>>sy>>ex>>ey;
sx--,sy--,ex--,ey--;
if(sx>ex||sy>ey)continue;
if(op==1&&sy!=ey)continue;
if(op==2&&sx!=ex)continue;
qer[sx*m+sy].push_back({i,ex*m+ey});
}
for(int i=n-1;i>=0;i--)
{
for(int j=m-1;j>=0;j--)
{
if(g[i][j]=='1')f[i&1][j]=0;
else
{
f[i&1][j]=f[i&1^1][j]|f[i&1][j+1];
f[i&1][j][i*m+j]=1;
}
for(auto &x:qer[i*m+j])ans[x.first]=f[i&1][j][x.second];
}
}
for(int i=1;i<=q;i++)
{
if(ans[i])cout<<"yes"<<"\n";
else cout<<"no"<<"\n";
}
return 0;
}
直接暴力写虽然是过了，但是复杂度还是有点高，采用分治优化，快了将近 10 倍。
分治思路如下：首先还是对前两种类型的机器人特殊处理，对于剩下的，如果能从起点走到终点，那么我们可以起点和终点之间的行任意选取一行，从起点在向终点走的过程中必然会经过改行上的某个点。所以我们可以以改行为中转行，处理出从起点能走到该行的哪些点，从该行的哪些点能走到终点，然后求交集就是合法的中转点。并且我们每次可以将mid 为中转行，我们只需要求起点终点的行跨过mid 的，对于其他的可以根据mid 将大区间一分为二进行分治。代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=505;
struct node{
int sx,sy,ex,ey;
int id;
};
bitset <N> f[N][N];
int n,m,q;
char g[N][N];
bool ans[N*1000];
void dfs(vector<node> q,int l,int r)
{
if(q.size()==0||l==r)return ;
vector<node> L,R,T;
int mid=l+r >> 1;
for(auto &x:q)
{
if(x.ex<=mid)L.push_back(x);
else if(x.sx>mid)R.push_back(x);
else T.push_back(x);
}
dfs(L,l,mid);
dfs(R,mid+1,r);
for(int i=mid;i>=l;i--)
for(int j=m-1;j>=0;j--)
{
if(g[i][j]=='1')
{
f[i][j].reset();
continue;
}
if(j<m-1)f[i][j]=f[i][j+1];
else f[i][j].reset();
if(i<mid)f[i][j]|=f[i+1][j];
else f[i][j][j]=1;
}
for(int i=mid+1;i<=r;i++)
for(int j=0;j<m;j++)
{
if(g[i][j]=='1')
{
f[i][j].reset();
continue;
}
if(j>0)f[i][j]=f[i][j-1];
else f[i][j].reset();
if(i>mid+1)f[i][j]|=f[i-1][j];
else f[i][j][j]=1;
}
for(auto &x:T)ans[x.id]=((f[x.sx][x.sy]&f[x.ex][x.ey]).count()>0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)cin>>g[i];
cin>>q;
vector<node> qer;
for(int i=1;i<=q;i++)
{
int op,sx,sy,ex,ey;
cin>>op>>sx>>sy>>ex>>ey;
sx--;sy--;ex--;ey--;
if(sx>ex||sy>ey)continue;
if(op==1&&sy!=ey)continue;
if(op==2&&sx!=ex)continue;
// 特殊处理在同一行和同一列的，便于递归结束条件的确定
if(sx==ex)
{
while(sy<=ey&&g[sx][sy]!='1')sy++;
ans[i]=sy>ey;
}
else if(sy==ey)
{
while(sx<=ex&&g[sx][sy]!='1')sx++;
ans[i]=sx>ex;
}
else qer.push_back({sx,sy,ex,ey,i});
}
dfs(qer,0,n-1);
for(int i=1;i<=q;i++)cout<<(ans[i]? "yes":"no")<<"\n";
return 0;
}
总结：对于某些有共同性质的部分，我们可以进行划分成若干个小部分，分而治之。
- J题 Tree 树上博弈
大意：给定一棵树，节点编号1-n。有两个人，给出两个人的初始时所在的节点编号。每个人会把之前走过的点以及和点相连的边删除，当两人都无法移动时比赛结束。两人的都是自己走过的点的个数。两人都想尽可能使得自己的得分尽可能高，对方的得分尽可能低，且都以最优策略走，求最终二者得分的差值（先手得分-后手得分）
思路：假设先手在 u 处，后手在 v 处，则有 u-v 存在一条最短路径，一旦某个人从某点开始离开了这条路径，因为是一棵树，那么之后两人接着走就是互不影响的了，所以我们可以先将最短路径纪录下来，然后预处理出从每个点离开所能走的最大得分。记先手的得分为 s1,后手的得分为 s2。从先手的角度来看 尽可能使得 s1-s2尽可能大，从后手的角度尽可能使s1-s2小。如果只考虑先手走，我们可以遍历从每个点离开最短路径，计算此时s1-s2 的值，维护最大值。对于 此时的 s2 实际上就是 后手在 一段区间上的得分最大值，我们可以提前 st 表预处理。只考虑后手同理，维护个 s1-s2 最小值。同时考虑二者，通过对抗搜索轮流进行。总体时间复杂福
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int n,s,t;
int path[N],path1[N],path2[N],len;
int st1[N][20],st2[N][20];
vector<int> G[N];
bool st[N];
int lg[N];
void init()
{
for(int i=0;i<20;i++)
{
int t=1<<i;
if(t>=N)break;
lg[t]=i;
}
for(int i=1;i<N;i++)if(!lg[i])lg[i]=lg[i-1];
for(int j=0;j<20;j++)
{
for(int i=1;i+(1<<j)-1<=len;i++)
{
if(!j)
{
st1[i][j]=path1[i];
st2[i][j]=path2[i];
}
else
{
st1[i][j]=max(st1[i][j-1],st1[i+(1<<j-1)][j-1]);
st2[i][j]=max(st2[i][j-1],st2[i+(1<<j-1)][j-1]);
}
}
}
}
int query1(int l,int r)
{
int k=r-l+1;
k=lg[k];
return max(st1[l][k],st1[r-(1<<k)+1][k]);
}
int query2(int l,int r)
{
int k=r-l+1;
k=lg[k];
return max(st2[l][k],st2[r-(1<<k)+1][k]);
}
bool dfs1(int u,int from,int dep)
{
if(u==t)
{
len=dep;
path[dep]=u;
st[u]=1;
return 1;
}
for(auto v:G[u])
{
if(v==from)continue;
if(dfs1(v,u,dep+1))
{
path[dep]=u;
st[u]=1;
return 1;
}
}
return 0;
}
int dfs2(int u,int from,int dep)
{
int mx=dep;
for(auto v:G[u])
{
if(st[v]||v==from)continue;
mx=max(mx,dfs2(v,u,dep+1));
}
return mx;
}
int dfs3(int l,int r,int tp)
{
if(!tp)
{
int mx=path1[l]-query2(l+1,r);
if(l+1<r)mx=max(mx,dfs3(l+1,r,1));
return mx;
}
else
{
int mx=query1(l,r-1)-path2[r];
if(l+1<r)mx=min(mx,dfs3(l,r-1,0));
return mx;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>s>>t;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(s,0,1);//纪录最短路径上的点并标记
for(int i=1;i<=len;i++)path[i]=dfs2(path[i],0,0); //预处理出从某个点离开最短路径所能得到的最多的分
for(int i=1;i<=len;i++) //预处理出两人若从某点离开已经得到的分数
{
path1[i]=path[i]+i;
path2[i]=path[i]+len-i+1;
}
init(); //st 表预处理区间最大值，用于 O(1)计算某段区间的最大分数
cout<<dfs3(1,len,0)<<"\n";
return 0;
}
- Yet Another Problem About Pi 计算几何，问题抽象转化
大意：一个平面区域被分成无穷多个长为d，宽为 w 的格子，求一条连续不断的长度为
π
\pi
π 的线能经过的做多的格子数目。对于格子的边界线不属于任何一个格子
思路：先来改一下题目，如果边界的也算在内，那么我们肯定是想办法经过尽可能多的格点，我们起始的时候直接在一个格点，即初始数目为 4，接下来我们每经过一个格点都会使得数目加2，如果我们是沿着方格的边走，那么显然我们沿着 w,d 小的那个走，并且尽量走直线，对于斜着走，显然是映射的方格边上更省长度。但是有个例外，对于方格的对角线虽然耗费长度，但是我们通过走一条对角线到达的格点可以使数目+3，这样可能使得答案更优。记 t=min(w,d)。
t
?
x
+
w
2
+
d
2
?
y
<
=
π
t*x+\sqrt{w^2+d^2}*y<=\pi
t?x+w2+d2
??y<=π 我们求的是
2
?
x
+
3
?
y
2*x+3*y
2?x+3?y 的最大值。
不妨令 w<=d， 原式化为
a
?
x
+
b
?
y
<
=
π
a*x+b*y<=\pi
a?x+b?y<=π
a
=
w
,
b
>
=
2
w
a=w, b>=\sqrt{2}w
a=w,b>=2
?w 当 b=1.5w 时，则有 3a=2b, 如果 y>=2 , 我们可以通过去掉y-2,x+3 使得结果不变， 当 b>1.5w 时，对于 y>=2 时，必然可以y-2使得 x增加的>3, 也就使得 2x+3y更大。当 b<1.5w 时，同理证得 x>=3 可以通过转化使得结果更优。所以最优解 一定满足 x<3或y<2 枚举就好了。题目说的是边界是不算，但是
π
\pi
π 无限小数，所以我们总有长度可以在边界位置反复横跳，所以边界是可以的
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
double pi=acos(-1);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin>>_;
while(_--)
{
double w,d;
cin>>w>>d;
if(w>d)swap(w,d);
double dg=sqrt(w*w+d*d);
LL ans=0;
for(int i=0;i<=2;i++)
{
if(i*w<=pi)ans=max(ans,(LL)(4+i*2+floor((pi-i*w)/dg)*3));//枚举直线
if(i*dg<=pi)ans=max(ans,(LL)(4+i*3+floor((pi-i*dg)/w)*2));//枚举对角线
}
cout<<ans<<"\n";
}
return 0;
}
以下是打了湖南省省赛的重现赛需要补的题，一并加到这里面了
一行盒子 思维，链表
大意：有一行盒子，从左到右依次编号为1, 2, 3,…, n。你可以执行四种指令：
- 1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令）。
- 2 X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令）。
- 3 X Y表示交换盒子X和Y的位置。
- 4 表示反转整条链。
指令保证合法，即X不等于Y。例如，当n=6时在初始状态下执行1 1 4后，盒子序列为2 3 1 4 5 6。接下来执行2 3 5，盒子序列变成2 1 4 5 3 6。再执行3 1 6，得到2 6 4 5 3 1。最终执行4，得到1 3 5 4 6 2。
思路：我们注意到题目中只有交换位置的操作，没有删除插入操作，所以我们可以利用链表的思想，数组模拟链表纪录每个数左右两边相邻的数，这样我们每次交换位置的时候相当于直接交换相关的指针。对于操作 4 我们并不需要实际进行操作，翻转一次也就相当于变了一次遍历的方向，翻转两次又变了回来，我们只需要纪录翻转了多少次就好了。值的注意的时，我们如果翻转了一次，因为我们并没有实际的翻转，这时候的操作 1 实际上相当于操作 2，对于操作 2 同理。另外对于操作 3 ，x,y 相邻和不相邻的时候改变的指针是不一样的，模拟一下就明白了。具体见代码：
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long LL;
int n,m;
int L[N],R[N];
void lk(int x,int y)
{
R[x]=y;
L[y]=x;
}
int main()
{
int cs=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++) //把 队头和队尾全变成 0
{
L[i]=i-1;
R[i]=(i+1)%(n+1);
}
R[0]=1,L[0]=n;
int op,x,y,to=0;
while(m--)
{
scanf("%d",&op);
if(op==4)
{
to^=1;
continue;
}
scanf("%d%d",&x,&y);
if(op==3&&R[y]==x)swap(x,y);// 要存下lx等，所以先交换好 x,y 在写 lx，
int lx=L[x],rx=R[x],ly=L[y],ry=R[y];
if(op!=3&&to)op=3-op;
if(op==1)
{
if(x==ly)continue;
lk(lx,rx);lk(ly,x);lk(x,y);
}
if(op==2)
{
if(x==ry)continue;
lk(lx,rx);lk(y,x);lk(x,ry);
}
if(op==3)
{
if(rx==y)
{
lk(lx,y);lk(y,x);lk(x,ry);
}
else
{
lk(lx,y);lk(y,rx);lk(ly,x);lk(x,ry);
}
}
}
LL ans=0;
if(to==0)for(int i=R[0],cnt=1;cnt<=(n+1)/2;cnt++,i=R[R[i]])ans+=i;
else for(int i=L[0],cnt=1;cnt<=(n+1)/2;cnt++,i=L[L[i]])ans+=i;
printf("Case %d: %lld\n",cs++,ans);
}
return 0;
}
|