\(1844E\)
题意:
定义一个矩形 \(a\) 是好的,当且仅当其满足以下条件:
- 矩形中每一个元素 \(x\) 都为 \(A,B,C\) 其中之一
- 每一个 \(2\times 2\) 的子矩形都必须包含三个不同的字符
- 共用一条边的两个元素不相等
给定 \(k\) 个限制条件,限制条件分为两类:
- \((x,x+1,y,y+1)\),限制 \(a[x,y]= a[x+1,y+1]\)
- \((x,x+1,y,y-1)\),限制 \(a[x,y]= a[x+1,y-1]\)
求满足所有条件的矩形是否存在。
题解:
考场上想半天差分约束,哎!
我们来推一推这个题的特殊性。
我们考虑用数字 \(1,2,3\) 代替字母 \(A,B,C\)
考虑设横差 \(d1[x,y]=a[x+1,y]-a[x,y]\in \lbrace 1,2\rbrace\)
则有 \(d1[x,y]=a[x+1,y]-a[x,y],d1[x,y+1]=a[x+1,y+1]-a[x,y+1]\)
由性质,有 \(a[x,y]=a[x+1,y+1]\) 或者 \(a[x+1,y]=a[x,y+1]\)
两个相等的元素与两个不等的元素做差后再对其中一个取个相反数,枚举一下几种可能,则有 \(d1[x,y]=d1[x,y+1]\)。
列设 \(d2[x,y]=a[x,y+1]-a[x,y]\) 同理可得 \(d2[x,y]=d2[x+1,y]\)
那么就一行的 \(d1\) 值与一列的 \(d2\) 值是一个数。
将这个视为该行/列的标签,那么对于限制条件 \((x,y,x+1,y+1)\) 而言,则是限制 \(x,y\) 的标签不同(分别取行列),\((x+1,y,x,y-1)\) 是限制标签相同。
我们使用并查集,就可以判断是否有矛盾,进而求解了。图论染色同样可以。
这里有几个重要的套路:
-
关于 “3” 的问题,可以往 “2” 的解决方案想。
-
具有轮换性的题目,可以令 \(0,1,2\) 来寻找规律。用数字替代字母,研究数字的和差关系
-
\(\bmod 3\) 运算的性质。异同的奇妙转化。
void dfs(int u){
for(int i=head[u];i;i=nxt[i]){
int v=ver[i],w=c[u]^cost[i];
if(c[v]==-1){
c[v]=w;dfs(v);
}
else if(c[v]!=w){
tag=1;
}
}
}
int main(){
int t;cin>>t;
while(t--){
cin>>n>>m;int k;cin>>k;
for(int i=1;i<=n+m;i++)c[i]=-1,head[i]=0;
tot=1,tag=0;
for(int i=1;i<=k;i++){
int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
int u=min(x1,x2),v=n+min(y1,y2),w=(x1+y1==x2+y2);
add(u,v,w);add(v,u,w);
}
for(int i=1;i<=n+m;i++){
if(c[i]==-1){
c[i]=1;dfs(i);
}
}
if(tag)cout<<"No\n";
else cout<<"Yes\n";
}
}
做题的启发:
- 用数字代替字母
- 从2*2开始对元素做差寻找性质,一定要手玩,由易到难,发现性质
- 欣赏轮换性与模运算的周期性结合的美
\(1844F\)
给定正整数数组 \(a\) 以及常数 \(c\) ,求
其中 \(b\) 是 \(a\) 的排列,在取得最小值的同时,要求字典序最小。
面对这种问题,我们分类讨论。
先从 \(c=0\) 开始。
显然将 \(a\) 升序排序即为所求。
证明:邻项交换法
设 \(b\) 为 \(a\) 升序排序后的序列,则:
邻项交换 \(x,x+1\) 两项,有:
所以这是不优的。
当 \(c\ge 0,c\le 0\)?
先来考虑 \(c\ge 0\) 的情况,运用类似的方法,不难证明在递增时取到最小值。
那么 \(c\le 0\) 时,我们将 \(b\) 进行翻转,同样化为了 \(c\ge 0\) 的情况,所以在递减时取到最小值
在 \(c\ge 0\) 时,显然有将原数组递增排列即可。
但 \(c\le 0\) 时,却不一定满足最小字典序的条件。
怎么办呢?不难想到找一个值一样字典序最小的值。
找什么呢?让我们先想想它的性质。
我们考虑一位一位地将后面的值提取到前面来。
那么此时后面单调不减一定是最优决策(之一),为什么?
因为如果不单调不减就会产生代价,进而没掉。
那什么样的点可以提到前面来呢?显然是不会增大最终代价的点。
设当前已经取了 \(i-1\) 位,现在在取 \(i\) 位,后面序列第 \(x\) 个数左右边下标分别是 \(l[x],r[x]\),设取数 \(k\)
那么必定要满足:
- \(a[k]-b[i-1]\ge c\) 因为这样不会破坏最终状态(最终状态即为负减负)
- \(a[r[k]]-a[l[k]]\ge c\) 因为拿走之后,这里的代价不能扩大
- \(k\) 是满足1,2的下标最小值。
当然,\(b[1]=a[1]\) 是显然的。
由此,我们可以枚举 \(k\),进而过掉F1(要特判1,n-1,n之类的情况)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 505050
int a[N],n,t,c;
signed main() {
ios::sync_with_stdio(false);cin>>t;
while (t--) {
cin>>n>>c;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
if(c>=0){
for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<"\n";continue;
}
reverse(a,a+n);
for(int i=0;i<n;i++){
for(int j=n-1;j>i;--j){
int tag=0;
if(j<n-1)tag+=abs(a[j+1]-a[j-1]-c)-abs(a[j+1]-a[j]-c);
if(i==0)tag+=abs(a[i]-a[j]-c);
else tag+=abs(a[i]-a[j]-c)+abs(a[j]-a[i-1]-c)-abs(a[i]-a[i-1]-c);
if(tag==abs(a[j]-a[j-1]-c)){
for(int &k=j;k>i;--k)swap(a[k],a[k-1]);
}
}
}
for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<"\n";
}
return 0;
}
算法优化:
考虑到限制条件1本质上与限制条件2脱钩,用分离限制条件原则来维护一个解的集合。
详细地说,我们维护一个集合 \(T\),包括所有满足限制条件2的点
然后注意到限制条件1和3 本质上是 \(b[i-1]+c\le a[k]\) 取最小值,也可以根据 \(b[i-1]+c\) 的值来寻找。
那,什么样的数据结构是可行的呢? set!
我们事先将满足条件2的点加入 \(T\),然后二分set,找到合适的值,再更改 \(l,r\),并将其在set中删去,最后判断是否可以重新加入即可。
注意set是不可重集合,我们可以用下标当第二维度。
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
#define pr pair<int,int>
#define mk make_pair
#define N 505050
int a[N],b[N],c,l[N],r[N],n,m;
set<pr >t;
int main(){
int T;cin>>T;
while(T--){
cin>>n>>c;
for(int i=0;i<n;i++)cin>>a[i];
if(c>=0){
sort(a,a+n);
for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<"\n";
continue;
}
for(int i=1;i<n;i++)l[i]=i-1;l[0]=n-1;
for(int i=0;i<n-1;i++)r[i]=i+1;r[n-1]=0;
sort(a,a+n);reverse(a,a+n);
for(int i=2;i<n-1;i++)if(a[r[i]]-a[l[i]]>=c)t.insert(mk(a[i],i));
b[0]=a[0];
for(int i=1;i<n;i++){
int u=0;auto it=t.lower_bound(mk(b[i-1]+c,0));
if(it==t.end())u=r[0];
else u=(*it).second,t.erase(it);
b[i]=a[u];
r[l[u]]=r[u];l[r[u]]=l[u];
t.erase(mk(a[r[u]],r[u]));
t.erase(mk(a[l[u]],l[u]));
if(l[u]!=0&&r[l[u]]!=0&&l[l[u]]!=0&&a[r[l[u]]]-a[l[l[u]]]>=c)t.insert(mk(a[l[u]],l[u]));
if(r[u]!=0&&r[r[u]]!=0&&l[r[u]]!=0&&a[r[r[u]]]-a[l[r[u]]]>=c)t.insert(mk(a[r[u]],r[u]));
}
for(int i=0;i<n;i++)cout<<b[i]<<" ";cout<<"\n";
}
}
由于各方面原因,这里没有详细的数学证明,感兴趣的读者可以看CF原题解(反正我是看懵了)。
\(ABC310F\)
看到n=10,考虑状态压缩动态规划。
设 \(f[i][s]\) 表示前 \(i\) 个骰子组成可选数为 \(s\) 的方案数。
注意到我们只关心十及其以下的数字,那么人为限制 \(s<2^10\)
考虑计算,我们来进行分类讨论。
- \(a[i]\le 10\)
首先枚举自己骰子这次取那些值,设为 \(k\),那么
s_new=(s|(1<<(k-1))|(s<<k))&((1<<10)-1)
f[i][(s|(1<<(k-1))|(s<<k))&((1<<10)-1)]+=f[i-1][s]*inv_ai
即可完成转移
- \(a[i]> 10\)
将 \(1\sim 10\) 的部分交给上一个处理,多出来的一定不会对新的集合产生影响,则直接有
f[i][j]+=(ai-10)*inv_ai*f[i-1][j]
挂点:没有往状压方向考虑,事实上看到状态这么小我应该思考状压的,尤其是当出现一个比较明显的常数在10的左右的时候
启发:概率DP,如果从时间轴上看,则必然每个时间的概率之和相等,否则挂
int f[505][1<<12],n;
signed main(){
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++){
int x,y,inv;cin>>x;inv=power(x,p-2);y=min(x,10ll);
for(int j=0;j<(1<<10);j++){
for(int k=1;k<=y;k++){
f[i][(j|(1<<(k-1))|(j<<k))&((1<<10)-1)]+=f[i-1][j]*inv%p;
f[i][(j|(1<<(k-1))|(j<<k))&((1<<10)-1)]%=p;
}
f[i][j]+=(x-y)*inv%p*f[i-1][j]%p;
f[i][j]%=p;
}
}
int ans=0;
for(int i=1<<9;i<(1<<10);i++){
ans+=f[n][i];ans%=p;
}
cout<<ans<<"\n";
}
\(Codeforces\) \(Round\) #\(885\) 数学专场
\(Atcoder\) \(Beginner\) \(Contest\) \(311\) \(A\sim G\)
\(Codeforces\) \(Round\) #\(887\) 规律/构造/转化/平面几何/数学
\(Educational\) \(Codeforces\) \(Round\) \(152\) Trie/异或/区间统计/转化
\(Codeforces\) \(Round\) \(889\) \(Div.2\) \(A\sim F\) 构造/DP专场
\(Atcoder\) \(Beginner\) \(Contest\) \(312\) \(A\sim Ex\)
- Codeforces Practice Atcoder July andcodeforces practice atcoder july codeforces practice atcoder august codeforces practice atcoder june codeforces practice atcoder may codeforces div and grimoire codeforces atcoder amp codeforces 1439e cheat and codeforces and round mocha july version july 2023 1.81