\(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";
}