题目描述
解法
首先可以观察出必要条件，也就是对于所有 \((i,j)\) 要求 \((i+1,j)\) 和 \((i,j+1)\) 的颜色相等，这样才能保证无论用什么方法走到 \((i+1,j+1)\) 经过红色格子的数量都是一样的。
这也是充分条件，因为任意时候路径经过红色格子数都是全相等的。
所以对于每一个 \(i+j\) 统计颜色分布，如果全是.答案乘 \(2\)，如果既有B又有W答案为 \(0\)，否则答案不变。
#include <cstdio>
const int M = 505;
const int MOD = 998244353;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,ans=1;char s[M][M];
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=2;i<=n+m;i++)
{
int c1=0,c2=0;
for(int j=1;j<=n;j++)
{
if(i-j<=0 || i-j>m) continue;
if(s[j][i-j]==‘R‘) c1++;
if(s[j][i-j]==‘B‘) c2++;
}
if(c1 && c2) ans=0;
if(!c1 && !c2) ans=2*ans%MOD;
}
printf("%d\n",ans);
}
题目描述
有长度为 \(n\) 的两个序列 \(a,b\)，要求通过最少的操作数把 \(a\) 变成 \(b\)
操作定义如下：选择 \(1\leq i<n\)，交换 \(a_i,a_{i+1}\)，把 \(a_i\) 加上 \(1\)，\(a_{i+1}\) 减去 \(1\)
\(2\leq n\leq 2\cdot 10^5,0\leq a_i,b_i\leq 10^9\)
解法
首先观察：无论怎么操作数列的总和是不会变的，一次操作相当于把某个数左移，并给它加 \(1\)
要从变化中找不变量，我们对于每个数可以定义一个势能 \(a_i+i\)，势能相等的两个位置才可能匹配。
然后依次考虑 \(b\) 的每一个位置，找到初始位置最小并且还未匹配的 \(a\)，由于匹配会带来他前面数位置的移动，所以用一个树状数组维护每个数已经被迫移动的距离即可，时间复杂度 \(O(n\log n)\)
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
#define pii pair<int,int>
#define make make_pair
#define int long long
const int M = 200005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,bit[M];set<pii> s;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int f)
{
for(int i=x;i<=n;i+=lowbit(i))
bit[i]+=f;
}
int ask(int x)
{
int r=0;
for(int i=x;i>0;i-=lowbit(i))
r+=bit[i];
return r;
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
s.insert(make(read()+i,i));
for(int i=1;i<=n;i++)
{
int x=read();
set<pii>::iterator it=s.lower_bound(make(x+i,0));
if(it==s.end() || (*it).first!=x+i)
{
puts("-1");
return 0;
}
int t=ask((*it).second);
add(1,1);add((*it).second,-1);
ans+=(*it).second+t-i;
s.erase(it);
}
printf("%lld\n",ans);
}
题目描述
对于一个长为 \(2n\) 的括号序列 \(s\)，如果对于 \(i<j\) 有 \(s_i=\)(\(,s_j=\))，并且 \(i,j\) 中间的括号序列恰好能匹配，那么可以产生 \(|a_i-a_j|\) 的贡献。
给定 \(n,a\)，试构造 \(s\) 使得贡献和最大。
\(1\leq n\leq 2\cdot 10^5,1\leq a_i\leq 10^9\)
解法
先考虑贡献产生的条件，对于最两边的元素只有 (()()) 才能产生贡献而 ()() 则不行，所以右括号只能和它匹配的左括号产生贡献，贡献的对数最多是 \(n\)
现在考虑最大化答案，\(dp\) 是不容易的，我们考虑构造答案上界。由于是绝对值相减的形式那么一定有 \(n\) 个数字前面符号是正，\(n\) 个数字前面符号是负，那么我们让最大的 \(n\) 个符号为正，其它符号为负。
也就是我们要让最大的 \(n\) 个数和最小的 \(n\) 个数匹配，那么线性扫一遍不难构造。
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int M = 400005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,a[M],c[M];char t[M];stack<int> s[2];
struct node
{
int x,id;
bool operator < (const node &r) const
{
return x<r.x;
}
}b[M];
signed main()
{
n=2*read();
for(int i=1;i<=n;i++)
{
a[i]=read();
b[i]=node{a[i],i};
}
sort(b+1,b+1+n);
for(int i=1;i<=n/2;i++)
c[b[i].id]=1;
for(int i=1;i<=n;i++)
{
if(!s[c[i]^1].empty())
{
t[s[c[i]^1].top()]=‘(‘;
t[i]=‘)‘;s[c[i]^1].pop();
}
else
s[c[i]].push(i);
}
printf("%s\n",t+1);
}
题目描述
有 \(n\) 个人，一开始第 \(i\) 个人在 \(a_i\) 处，每秒每个人可以移动一格，或者不动，问所有 \(1\leq i<n\) 满足 \(i\) 和 \(i+1\) 相遇过的最小时间。
\(2\leq n\leq 2\cdot 10^5,0\leq a_i\leq 10^9\)，\(a_i\) 全为偶数并且以升序给出
解法
首先可以有如下观察：每个人时时刻刻都是在动的，\(i\) 一开始会一直往右边走直接碰到 \(i+1\)，然后一直往左走，反之亦然。
然后我们考虑如果 \(i\) 和 \(i+1\) 是相向而行的，他们碰面了之后不反向，而是照着原来的方向继续行进，只是他们需要交换各自的任务。
如上图，我们可以转化题意：横轴代表现在每个人的坐标，纵轴代表时间。那么我们钦定两个人同向走就能让中间的点都能满足条件（注意端点还是不满足条件的），我们称这个过程为配对，配对的过程中有如下限制：
那么可以用 \(dp\) 来配对，设 \(f[i]\) 表示前 \(i\) 个点均合法的方案数，转移我们让 \(i+1\) 和 \(j-1\) 配对就可以得到区间 \([j,i]\) 的合法，但是注意 \(i=j\) 的转移会出问题，因为连续四个点让它们两两配对会导致不满足性质三，所以转移如下：
看上去是 \(O(n^2)\) 的，其实 \(j\) 的取值范围很有限因为根本不可能配对得那么远，所以循环到 \(j=i-3\) 即可。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 200005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,a[M],f[M];
signed main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
a[0]=a[1];a[n+1]=a[n];
for(int i=2;i<=n;i++)
{
f[i]=a[i+1]-a[1];
for(int j=max(i-3,1);j<=i-1;j++)
f[i]=min(f[i],max(f[j-1],a[i+1]-a[j-1]));
}
printf("%d\n",f[n]/2);
}
题目描述
有 \(n\) 个钻石排成一排，第 \(i\) 个钻石的价值是 \(a_i\)，阿七要拿走 \(m\) 个钻石来救大保，但是如果相邻两个钻石都被拿走神医就会发现。在不让神医发现的情况下，阿七想知道每种情况
原文：https://www.cnblogs.com/C202044zxy/p/14825837.html