CodeforcesRound#590(Div.3)E(暴力/差分)+F(状压dp)

思路来源

https://www.cnblogs.com/carcar/p/11618099.html

https://blog.csdn.net/BeNoble_/article/details/101985236

https://codeforces.com/blog/entry/70233

E. Special Permutations&＃xff08;暴力/差分&＃xff09;

对于长度为n(n<&＃61;2e5)的近有序排列&＃xff0c;n个数在第i个近有序排列中是这样的

给定m(m<&＃61;2e5)个数&＃xff0c;第j个数为aj(1<&＃61;aj<&＃61;n)&＃xff0c;

对于一个给定的排列&＃xff0c;将m个数的贡献和函数f计算如下&＃xff1a;

取两个相邻位置的数aj和aj&＃43;1&＃xff0c;其对答案贡献为abs(pos[aj]-pos[aj&＃43;1])&＃xff0c;

即在原近有序排列中距离的差的绝对值&＃xff0c;

依序输出对于i从1到n&＃xff0c;在第i个近有序排列中&＃xff0c;f函数的值

题解

两种做法&＃xff0c;

①考虑第i个排列向第i&＃43;1个排列转移的时候&＃xff0c;有哪些位置的贡献会发生变化

预处理第一个排列&＃xff0c;然后转移的时候&＃xff0c;先分别减去受u/v影响的数的贡献&＃xff0c;交换位置后&＃xff0c;再加上对应贡献

注意到&＃xff0c;如果u和v正好在此轮互换&＃xff0c;则(u,v)的贡献只能被统计一次

②差分&＃xff0c;考虑相邻数在哪些时间段时&＃xff0c;距离不变&＃xff0c;贡献固定

不妨记相邻一对数值为l和r&＃xff0c;且l

(1)i

(2)i&＃61;&＃61;l时&＃xff0c;l在首&＃xff0c;且r在r处&＃xff0c;距离为r-1

(3)l

(4)i&＃61;&＃61;r时&＃xff0c;r在首&＃xff0c;且r右侧有数[1,l-1]&＃xff0c;距离为l

(5)i>r时&＃xff0c;l和r相对距离不变&＃xff0c;为r-l

代码1&＃xff08;暴力&＃xff09;

#include
using namespace std;
typedef long long ll;
const int N&＃61;2e5&＃43;10;
int a[N],now[N],to[N];
int n,m,x,y;
ll ans[N];
vectorpos[N];
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i){scanf("%d",&a[i]);pos[a[i]].push_back(i);}for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){now[i]&＃61;i;to[i]&＃61;i;}for(int i&＃61;1;i}

代码2&＃xff08;差分&＃xff09;

#include
using namespace std;
typedef long long ll;
const int N&＃61;2e5&＃43;10;
int n,m,l,r;
int a[N];
ll f[N];//f[]:差分数组
//考虑每一对值的贡献
void add(int l,int r,int v)//[l,r]&＃43;&＃61;v
{f[l]&＃43;&＃61;v;f[r&＃43;1]-&＃61;v;
}
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i)scanf("%d",&a[i]);for(int i&＃61;1;ir)swap(l,r);add(1,l-1,r-l);add(l,l,r-1);add(l&＃43;1,r-1,r-l-1);add(r,r,l);add(r&＃43;1,n,r-l); }for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){f[i]&＃43;&＃61;f[i-1];printf("%I64d%c",f[i]," \n"[i&＃61;&＃61;n]);}return 0;
}

F. Yet Another Substring Reverse&＃xff08;状压dp&＃xff09;

给你一个只由字母表前20个字母组成的字符串s&＃xff0c;|s|<&＃61;1e6

要求你最多翻转一个区间[l,r]&＃xff0c;使得存在一个子串[L,R]

[L,R]内没有相同字母&＃xff0c;且长度最大&＃xff0c;输出这个长度

题解

肯定是一个区间不变&＃xff0c;另一个区间翻过去接在一旁

问题等价于求两个串上不相交且字符集不相交的区间&＃xff0c;使区间长度和最大

状压&＃xff0c;一位代表一种字符是否出现&＃xff0c;

若令dp[mask]为mask中字符的个数&＃xff0c;

则问题等价于求两个不相交mask的和最大&＃xff0c;

那么从子集转移而来时&＃xff0c;取子集个数最多的那个子集转移即可

最终答案是最优的两个不相交集合的长度之和&＃xff0c;mask和mask的补集

代码

#include
using namespace std;
typedef long long ll;
const int N&＃61;1e6&＃43;10;
char s[N];
int dp[1<<20],ans;
int main()
{scanf("%s",s);int len&＃61;strlen(s);for(int i&＃61;0;i}