当前位置：首页 > news >正文

外链代发工具/日照网站优化公司

news 2025/8/7 1:17:47

外链代发工具,日照网站优化公司,阳江招聘网最新消息今天招聘,做网站月入过万A 假如全部都一样，那么显然不能操作，否则肯定存在一个最大值，它旁边的值比他小，将他们合并之后最大值唯一，可以用这个新的最大值与其他全部合并起来。代码如下： #include <cstdio> #include <…

A

假如全部都一样，那么显然不能操作，否则肯定存在一个最大值，它旁边的值比他小，将他们合并之后最大值唯一，可以用这个新的最大值与其他全部合并起来。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 200010int T,n;int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);int last=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);if(!last)last=x;else if(x!=last)last=-1;}if(last==-1)printf("1\n");else printf("%d\n",n);}
}

B

假如全部都一样，那么操作一次之后全部变成 $0$ ，再操作下去不会变化。

否则就先操作一次，操作完后，此时最大值肯定大于 $0$ ，并且一定存在一个位置为 $0$ （即上一次操作的位置）。

容易发现，假如最大值大于 $0$ 并且存在一个位置是 $0$ ，那么操作 $2$ 次之后序列不变，所以可以让 $k$ 对 $2$ 取模。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 200010int T,n,a[maxn];
long long k;
void work(int x){for(int i=1;i<=n;i++)a[i]=x-a[i];}int main()
{scanf("%d",&T);while(T--){scanf("%d %lld",&n,&k);int ma=-2147483647,mi=2147483647;for(int i=1;i<=n;i++){scanf("%d",&a[i]);ma=max(ma,a[i]);mi=min(mi,a[i]);}if(ma==mi){for(int i=1;i<=n;i++)printf("0 ");printf("\n");}else{k--;work(ma);if(k%2)ma=ma-mi,work(ma);for(int i=1;i<=n;i++)printf("%d ",a[i]);printf("\n");}}
}

C

显然每次肯定操作形如 $[i, n]$ 的一个区间，如果操作 $[i, j]$ 可能会使它们比 $[j + 1, n]$ 大。

那么对于每个 $i∈(1,n]i\in(1,n]$ ，假如满足 $a [i - 1] > a [i]$ ，那么就需要让 $[i, n]$ 增大 $a [i - 1] - a [i]$ 次，加起来就是答案。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 200010int T,n,last;
long long ans;int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);ans=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);if(i>1)if(x<last)ans+=last-x;last=x;}printf("%lld\n",ans);}
}

D

思考一下就可以知道，最后这 $n$ 个人肯定可以分成若干个小组，两两小组之间互不干扰。

而一个小组内的攻击情况有三种：RL，R_L，RRLL，于是dp一下就好了。

但是还要考虑环，即需要考虑 $1$ 和 $n$ 一组的情况，这个做 $4$ 次dp就可以了（因为最大的一组大小是 $4$ ），每次做完dp后旋转一下整个环。

代码如下;

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 200010
#define inf 999999999int T,n;
char s[maxn];
int f[maxn],ans;
int cost(int x,int y){return (s[x]!='R')+(s[y]!='L');}
int cost(int x){return (s[x]!='R')+(s[x+1]!='R')+(s[x+2]!='L')+(s[x+3]!='L');}
void dp()
{f[0]=0;f[1]=inf;for(int i=2;i<=n;i++){f[i]=inf;if(i>=2)f[i]=min(f[i],f[i-2]+cost(i-1,i));if(i>=3)f[i]=min(f[i],f[i-3]+cost(i-2,i));if(i>=4)f[i]=min(f[i],f[i-4]+cost(i-3));}ans=min(ans,f[n]);
}
void move()
{char p=s[1];for(int i=1;i<n;i++)s[i]=s[i+1];s[n]=p;
}int main()
{scanf("%d",&T);while(T--){scanf("%d %s",&n,s+1);ans=inf;dp();move();dp();move();dp();move();dp();printf("%d\n",ans);}
}
/*
RL
R_L
RRLL
*/

E

我们需要让每个和对应的路径唯一，那么我们需要能够从和倒推出那条唯一的路径。

事实上，当鸭子走完第 $i$ 步时，一定在第 $i + 1$ 条从右上到左下的对角线上，那么第 $i$ 条对角线上，我们考虑依次放 $2^i$ 和 $0$ 。

容易发现，这样放的话，对于第 $i$ 条对角线上的任何一个位置，向下和向右能到达的两个点，权值一定分别为 $2^{i+1}$ 和 $0$ 。

那么我们只需要看和的第 $i$ 位上是 $2^i$ 还是 $0$ ，就可以确定这一步走向了哪个位置。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 110
#define ll long longint n,q;
ll a[maxn][maxn];int main()
{scanf("%d",&n);for(int i=2;i<=2*n;i++)for(int j=min(i-1,n);j>=1&&i-j<=n;j--)a[i-j][j]=j&1?(1ll<<(i-2)):0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%lld ",a[i][j]);printf("\n");}fflush(stdout);scanf("%d",&q);while(q--){ll z;scanf("%lld",&z);int x=1,y=1;printf("%d %d\n",x,y);for(int i=1;i<=2*n-2;i++){ll c=(1ll<<i)&z;if(x==n)y++;else if(y==n)x++;else if(a[x+1][y]==c)x++;else y++;printf("%d %d\n",x,y);}fflush(stdout);}
}

F

先在这个山上想象一个阶梯，从左到右高度依次为 $a_1,a_1+1,a_1+2,...,a_1+n-1$ 。

容易发现，这个阶梯内的泥是不可能流动的，而阶梯上的泥一定可以往下流（假如有位置流的话）。那么接下来的问题等价于，将多出来的泥一滴一滴地滴到第 $n$ 级阶梯上，问最后每个位置有多高的泥。

这个手玩一下就可以发现，假如你滴了 $i(i≤n)i(i\leq n)$ 滴泥，那么这 $i$ 滴泥一定依次排布在 $1, 2, . . ., i$ 级阶梯上，那么代码就很简单了：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000010
#define ll long longint n;
ll a[maxn],sum=0,p;int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum+=a[i]-(a[1]+i-1);//sum记录每一级阶梯上多出来的泥p=sum/n;sum%=n;for(int i=1;i<=n;i++)printf("%lld ",a[1]+i-1+p+(sum>0)),sum--;
}

G

令 $f (A, B)$ 表示 $A, B$ 两个序列有多少个位置上的数相同。

容易发现，假如两个序列 $A, B$ 同时进行了一段相同的交换序列，那么得到的序列 $A^{'}, B^{'}$ 满足 $f (A, B) = f (A^{'}, B^{'})$ 。

定义，让序列 $s$ 逆序进行区间 $[l, r]$ 内的交换，表示依次交换 $s_{a_r},s_{b_r}),(s_{a_{r-1}},s_{b_{r-1}}),...,(s_{a_l},s_{b_l})$ 。

那么，设一次操作后，即让 $s$ 进行区间 $[l, r]$ 内的交换，得到的序列为 $s^{'}$ 。设 $s^{''}$ 为 $s^{'}$ 逆序进行 $[1, r]$ 内的交换， $t^{''}$ 为 $t$ 逆序进行 $[1, r]$ 内的交换。容易发现， $s^{''}$ 等价于 $s$ 逆序进行 $[1, l - 1]$ 内的交换。

要想知道 $f (s^{'}, t)$ ，就相当于求 $f (s^{''}, t^{''})$ 。

设 $fs_i$ 表示 $s$ 逆序进行 $[1, i]$ 内的交换， $ft_i$ 表示 $t$ 逆序进行 $[1, i]$ 内的交换，那么选择让 $s$ 进行 $[l, r]$ 内的交换，然后求 $f (s^{'}, t)$ ，等价于 $f(fs_{l-1},ft_r)$ 。

也就是说，我们只需要求出一组 $i, j$ ，使 $f(fs_i,ft_j)$ 最大即可。

对于两个长度为 $k$ 的 $01$ 序列 $A, B$ ，令 $u$ 表示 $A$ 中 $1$ 的数量， $v$ 表示 $B$ 中 $1$ 的数量， $d$ 表示两个序列中同为 $1$ 的位置数，那么这两个序列中位置上数字相同的位置数等于 $k−(u−d)−(v−d)=2×d+k−u−vk-(u-d)-(v-d)=2\times d+k-u-v$ 。

对于这题， $u, v, k$ 是不变的，也就是说我们要让 $fs_i$ 和 $ft_j$ 的 $d$ 尽可能大，这个可以用dp实现，设 $L_i$ 分别表示序列 $i$ 是 $fs_{L_i}$ 的子集，且 $L_i$ 是最小的，即不存在更小的 $L_i$ 满足 $i$ 是 $fs_{L_i}$ 的子集， $R_i$ 则表示 $i$ 是 $ft_{R_i}$ 的子集，且 $R_i$ 是最大的。

假如 $Ri−Li≥mR_i-L_i\geq m$ ，那么 $i$ 序列中 $1$ 的个数就是 $fs_{L_i}$ 和 $ft_{R_i}$ 的 $d$ ，更新一下答案即可。

以及还有一个细节，就是怎么求 $f s$ 和 $f t$ ，注意到这里需要逆序进行 $[1, i]$ 的操作，所以需要一些技巧来求。

设 $p_i$ 表示序列 $s$ 正序进行区间 $[1, j]$ 的交换后，原来位置 $i$ 上的数现在在 $p_i$ 位置。

可以发现，正序进行 $[1, j]$ 的交换后，假如再逆序进行区间 $[1, j]$ 的交换，那么所有数都会变回原来的位置，令 $c_i$ 表示 $s$ 逆序进行区间 $[1, j]$ 的交换后，原来位置 $i$ 上的数现在在 $c_i$ 位置，那么就是满足 $c_{p_i}=i$ 。

这样我们就可以通过 $p$ 求出 $c$ ，进而求出 $f s$ 和 $f t$ 了。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 21
#define inf 999999999int n,m,k,p[maxn];
char s1[maxn],s2[maxn],a[maxn],b[maxn];
int f[2][1<<maxn],ans=0,ansl,ansr;
int turn(char *s){int re=0;for(int i=0;i<k;i++)re|=((s[i]=='1')<<i);return re;
}
int count(int x){int re=0;for(int i=0;i<k;i++)if(x>>i&1)re++;return re;
}int main()
{scanf("%d %d %d",&n,&m,&k);scanf("%s %s",s1,s2);for(int i=0;i<k;i++)p[i]=i;for(int i=0;i<(1<<k);i++)f[0][i]=inf,f[1][i]=-inf;f[0][turn(s1)]=f[1][turn(s2)]=0;for(int i=1,x,y;i<=n;i++){scanf("%d %d",&x,&y);x--;y--;swap(p[x],p[y]);for(int j=0;j<k;j++){a[p[j]]=s1[j];b[p[j]]=s2[j];}f[0][turn(a)]=min(f[0][turn(a)],i);f[1][turn(b)]=i;}for(int i=(1<<k)-1;i>=0;i--){if(f[1][i]-f[0][i]>=m&&count(i)>ans)ans=count(i),ansl=f[0][i]+1,ansr=f[1][i];for(int j=0;j<k;j++)if(i>>j&1){f[0][i^(1<<j)]=min(f[0][i^(1<<j)],f[0][i]);f[1][i^(1<<j)]=max(f[1][i^(1<<j)],f[1][i]);}}printf("%d\n%d %d",k+2*ans-count(turn(s1))-count(turn(s2)),ansl,ansr);
}