题解 P6254 【[ICPC2019 WF]Circular DNA】
题目:
一个长度为 n 的环形 DNA 序列，以顺时针顺序给出，其中每个基因有类型和编号两个属性，类型是 s（头）或 e（尾）中的一种，而编号是 1 到 106 中的整数。 你需要在某个地方切断，按照顺时针顺序拉成链后，最大化能够完美匹配的基因编号个数。
一个基因编号 i 是能够完美匹配的，当且仅当它在链中对应的所有基因，将 s 看作左括号，e 看作右括号，可以匹配成非空的合法括号序列。
如果有多个位置满足最大化的条件，输出最小的位置。
输入第一行一个整数 n (1≤n≤106)，表示DNA序列的长度，第二行是DNA序列，包含 nn 个元素，每个元素有一个字符 c∈{s,e}（s 表示切割时以这个元素为开始还是结束，s 表示开始,e 表示结束）和一个整数 i (1 \le i \le 10^6) 表示基因类型。可以通过在任意位置切割，从环状DNA获得给定的DNA序列。
输出一行包含两个整数 p 和 m , p是切割位置，可最大化能够完美匹配的基因编号个数，m 是能够完美匹配基因类型的最大数量如果多个切割位置产生相同的最大值 m，输出最小的 p。
题目大意:
将环状序列抽出一条长度为n的链,使其完美匹配的个数尽可能多
首先对有环状的问题一般来说就是将长度为n的环变成一个长度为2n,3n的一条链,然后求解
或者向类似于这道题的
首先算出来1~n这条链的符合题意的答案,这个是可以O(n)求解的,然后每次O(1)转移算出来对于每个i~(i+n)%n的结果
首先我们可以计算出每一个e和s之间的绑定关系,0表示没有绑定,非0表示绑定的那个位置坐标,
对于一个s我们可以将其放到对应的set中,遇到一个对应的e我们可以取出对应的set中的最后一个元素相互绑定
当然我是提前判断了一下对于某些元素是有可能匹配成功的和没有可能匹配成功的,
考虑对于每一个s,要放到最后肯定只有两种情况,一种是本身绑定了一个e,一种是没有绑定e,
然后如果绑定的那个放到最后一定是成为一个未绑定e的存在,因此如果之前绑定的那个e寻找一些对应的set中的首元素是否满足情况如果有的话,这部对答案的操作是没有任何影响的
对应e的话,本身一定不是一个绑定的存在,因此向后方一定会遇到和在set里面未绑定对应e的s绑定,或者不影响任何存在
//下列代码若为声明的话出现s和e表示的是对应值相同改的s和e
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define eps 1e-9
#define endl '\n'
#define gcd __gcd
#define pi acos(-1)
#define ll long long
#define LL long long
#define IDX(x) x - 'A'
#define idx(x) x - 'a'
#define idz(x) x - '0'
#define ld long double
#define lowebit(x) x&(-x)
#define rint register int
#define Len(x) (int)(x).size()
#define all(s) (s).begin(), (s).end()
using namespace std;
inline int read()
{
register int x = 0, f = 1, ch = getchar();
while( !isdigit(ch) ){if(ch == '-') f = -1; ch = getchar();}
while( isdigit(ch) ){x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
set <int> a[3000005]; // a[i]表示编号i中未能完成配对的s(左括号)的存在
int p[3000005]; // p中记录任意一个数对应被绑定的另一个数的位置,未被绑定值未0
pair<int, bool> //c[3000005]; c[i]中记录第i个读取值的信息
bool kt[3000005]; //记录i是否可能存在完美匹配的情况
set<int> k[3000005]; // 计算最开始的序列答案
int ff[3000005]; // 记录e和s是否相等
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
clock_t c1ockck = clock();
int n; cin >> n;
int ans = 0, res = 1;// 记录最后答案
int mmm = -1;
for(int i = 1 ; i <= n ; i ++)
{
string s; cin >> s;
rint t = 0;
for(int j = 1 ; j < Len(s) ; j ++) t = t * 10 + idz(s[j]); // 读入信息
kt[t] = true; // 在这个时候表示t是出现过的值
mmm = max(t, mmm); // 求一下给出的最大值
if(s[0] == 'e')
{
ff[t] --; // 会抵消一个s,可以是未出现的s,值可以为负
if(Len(a[t])) // 如果集合a[t]中有元素(表明有之前配对的s出现)
{
auto x = *(--a[t].end()); // 提取最后一个未出现的信息
p[i] = x;
p[x] = i; // 记录对应的绑定信息
a[t].erase(x); // 删除未绑定的s的信息
}
else
{
k[t].insert(i); /
}
}
else
{
ff[t] ++; // 会抵消一个e,可以是未出现的e,这个数组有用的信息只有0的值
a[t].insert(i); //新加入的s一定是未配对的s
}
c[i] = make_pair(t, s[0] != 'e'); // 记录值的信息
}
for(int i = 1 ; i <= mmm ; i ++)
{
if(kt[i] && !Len(a[i]) && !Len(k[i])) ans ++; // 记录1~n存在的答案
if(!ff[i] && kt[i]) kt[i] = false; // 将可以达成的信息标记未false,不能达成的标记为true
else kt[i] = true;
}
int t_ans = ans; //转移最多只会从ans改变一个
for(int i = 1 ; i <= n ; i ++) // i表示第i个是链的末尾,i+1为链首
{
if(c[i].second == 0) // 如果当前是e
{
if(Len(a[c[i].first])) // 并且存在未匹配的s, 因为当前的e是最后一个元素,因此对于存在的s一定会匹配上
{
auto x = *(--a[c[i].first].end()); // 为了方便取出来的是最后一个放进去的s
p[x] = i + n;
p[i + n] = x; //此时的s对应的恰好是相当于多了一圈的i,因此对应方式未i+n
a[c[i].first].erase(x); // 匹配成功的删除
if(!Len(a[c[i].first]) && !kt[c[i].first])t_ans ++; // 凑成新的完美匹配答案+1
}
}
else
{
if(p[i]) // 如果被配对的是
{
p[p[i]] = 0; // 对应的e会被解除配对关系
a[c[i].first].insert(i + n); // 一定是未被配对的存在
auto x = *a[c[i].first].begin();
if(p[i] > x && Len(a[c[i].first])) // 为了方便取出来对应的最小的值判断就ok
{
p[p[i]] = x;
p[x] = p[i];
a[c[i].first].erase(x); // 成立新的绑定关系,
}else
{
if(!kt[c[i].first] && Len(a[c[i].first]) == 1) t_ans --; // 上面的情况一定不会达成一个新的完美匹配和接触完美匹配的状态,只有这种情况才能解除完美匹配的状况
}
}
}
if(t_ans > ans) // 更新答案
{
res = i + 1;
ans = t_ans;
}
//cout << i + 1<< " : T_ans = " << t_ans << " ans = " << ans << " res = " << res << endl;
}
cout << res << " " << ans << endl;
cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
/**srO**/return 0;/**Orz**/
}