CF906 div2
A.Doremy's Paint 3
题意
给出一个序列，可以随意打乱顺序，问最后能否使得所有相邻两个元素的和相等。
数据范围
多组数据，\(2 <= n <= 100 , 1 <= a_i <= 10^5\)
样例输入
5
2
8 9
3
1 1 2
4
1 1 4 5
5
2 3 3 3 3
4
100000 100000 100000 100000
样例输出
Yes
Yes
No
No
Yes
题解
有两种情况，一种是所有元素均相等；另一种是有两种元素交替出现，这就要求n为偶数时，两种元素个数相等，n为奇数时，两种元素的个数只差1.
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 120;
int n;
int A[N];
void Solve()
{
int val1 , val2 , cnt1 , cnt2 , flag;
cin >> n;
for(int i = 1 ; i <= n ; ++i)
cin >> A[i];
flag = 1;
val1 = val2 = -1; cnt1 = cnt2 = 0;
for(int i = 1 ; i <= n ; ++i)
{
if(val1 == -1)
{
val1 = A[i];
cnt1 = 1;
}
else
if(A[i] != val1)
{
if(val2 == -1)
{
val2 = A[i];
cnt2 = 1;
}
else
if(A[i] != val2)
{
flag = 0;
break;
}
else
cnt2++;
}
else
cnt1++;
}
if(flag == 0)
cout << "NO" << '\n';
else
if(val2 == -1 || max(cnt1 - cnt2 , cnt2 - cnt1) <= 1)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) Solve();
return 0;
}
B.Qingshan Loves Strings
题意
给出一个大串和一个小串，均只含0或者1。
可以将小串插入到大串的任意位置任意多次（可以不操作）。
问能否使大串最终不会出现连续两个相同的元素。
数据范围
多组数据，\(1 <= T <= 2000 , 1 <= n , m <= 50\)
输入样例
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10
输出样例
Yes
Yes
No
No
No
题解
先看大串是否本身已经满足要求，若是则结束，输出Yes。
再看小串是否满足要求，若不满足则结束，输出No。
然后看小串首尾是否相同，不同则结束，输出No。
小串满足要求且首尾相同时才能起到作用，假设小串首尾都是1,那么只能分开连续的0。
判断有无连续的1，若有则输出No，没有则输出Yes。
小串首尾是0,则同理。
#include<iostream>
using namespace std;
const int N = 66;
int n , m;
char s[N] , t[N];
void Solve()
{
int flag;
cin >> n >> m;
cin >> (s + 1); cin >> (t + 1);
flag = 1;
for(int i = 1 ; i < n ; ++i)
if(s[i] == s[i+1]) { flag = 0; break; }
if(flag) { cout << "YES" << '\n'; return ; }
flag = 1;
for(int i = 1 ; i < m ; ++i)
if(t[i] == t[i+1]) { flag = 0; break; }
if((!flag) || (t[1] != t[m])) { cout << "NO" << '\n'; return ; }
flag = 1;
for(int i = 1 ; i < n ; ++i)
{
if(s[i] == s[i+1])
{
if(s[i] == t[1])
{
flag = 0;
break;
}
}
}
if(flag) cout << "YES" << '\n'; else cout << "NO" << '\n';
return ;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) Solve();
return 0;
}
C.Qingshan Loves Strings 2
题意
给出一个字符串，可以任意插入“01”，是否可以若干次操作之后使得\(a_i != a_{k - i + 1}\)对所有的i成立，k是字符串长度。
数据范围
多组数据，\(1 <= T <= 100 , 1 <= n <= 100\)
输入样例
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
输出样例
0
-1
-1
2
6 7
1
10
-1
题解
如果0的个数不等于1的个数则无解。
因为0总是需要1去抵消，1总是需要0去抵消，而且操作插入的是"01"并不能改变01的个数之差。
对于\(a_l != a_r , l++ , r++\)
对于\(a_l == a_r \And a_l == 0\)则在r后插入01
对于\(a_l == a_r \And a_l == 1\)则在l前插入01
最坏的情况就是对于所有的<l,r>都需要操作，那就需要操作\(n / 2\)次，远不及300.
而且无解时，会不停增加新的操作，陷入死循环。
所以可以直接按照上述流程进行，如果操作数大于了300,那么一定是无解，如果没有死循环进而小于300,那么就一定是有解。
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
int n;
string s;
void Solve()
{
string tmp;
vector<int> V;
cin >> n;
cin >> s;
if(n & 1) { cout << -1 << '\n'; return ; }
for(int i = 0 ; i < s.length() - i - 1 ; ++i)
{
if(s[i] == s[s.length() - i - 1])
{
if(s[i] == '0')
{
V.push_back(s.length() - i);
tmp = s.substr(0 , s.length() - i) + "01" + s.substr(s.length() - i , i);
s = tmp;
}
else
{
tmp = s.substr(0 , i) + "01" + s.substr(i , s.length() - i);
s = tmp;
V.push_back(i);
}
if(V.size() > 300) break;
}
}
if(V.size() <= 300)
{
cout << V.size() << '\n';
for(auto x:V)
cout << x << ' '; cout << '\n';
}
else
cout << -1 << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) Solve();
return 0;
}
/*
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
1010
*/
D.Doremy's Connecting Plan
题意
有n个城市，城市i中有居民\(a_i\)个，现在想要将这n个城市连成一个联通块。
对于<i , j>如果满足\(\sum_{k\in S} a_i >= i*j*c\)则可以连边。
数据范围
多组数据，\(2 <= n <= 2*10^5 , 1 <= c <= 10 ^6,0 <= a_i <= 10^{12}\)
样例输入
7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2
样例输出
Yes
Yes
Yes
No
No
Yes
No
题解
要比较的代价是编号，那么编号1就是出去连边的最优选择。
那可考虑是不是有这么一种情况，第一条边不能连接1和其它，因为1号点的值太小，只能连接两个非1号点？
其实是不存在的。
如果第一条边不能链接1和else，那么对于所有的\(2 <= i <= n\)
满足\(a_1 + a_i <= i * c\),也就是\(a_i <= i*c - a_1\)
这样的话，就更不可能有\(x \neq 1,y \neq 1,a_x+a_y>=x*y*c\)
所以将2到n号点按照\(i * c - a_i\)从小到大排序，判断现有的联通块内的值是不是大于等于\(i * c - a_i\)，是的话则加上\(a_i\)，不是的话则不可行。
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N = 2e5+10;
int n , c;
int p[N];
long long A[N];
bool cmp(const int &x , const int &y) { return 1ll * x * c - A[x] < 1ll * y * c - A[y]; }
void Solve()
{
long long res = 0ll;
cin >> n >> c;
for(int i = 1 ; i <= n ; ++i)
cin >> A[i] , p[i] = i;
sort(p + 2 , p + 1 + n , cmp);
res = A[1];
for(int i = 2 ; i <= n ; ++i)
{
if(res >= 1ll * p[i] * c - A[p[i]])
res += A[p[i]];
else
{
cout << "NO" << '\n';
return ;
}
}
cout << "YES" << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) Solve();
return 0;
}
/*
7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2
*/
E.Doremy's Drying Plan
题意
给出m个区间，范围都在1~n上，最多可以删去k个区间。
问1~n上最多能有多少个点没有被任何一个区间覆盖。
数据范围
多组数据，\(1 <= n <= 2*10^5 , 2 <= m <= 2*10^5,\)
简单版k=2,困难版\(2 <= k <= min(m , 10)\)
样例输入
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 4
1 5
6 10
2 2
3 7
5 8
1 4
100 6 5
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 3
9 20
3 3
10 11
11 13
6 18
样例输出
1
2
6
0
1000
17
题解
简单版
两种情况，一种选择的区间没有交集，另一种有交集。
先算出每个点被多少个区间覆盖。
如果选择没有交集的，那么就找两个区间，区间中只被覆盖一次的点的个数最多（也就是只被所找的区间覆盖的点）。
如果选择有交集，那么交集部分统计被覆盖两次的点的个数，不交的部分还是统计覆盖一次的部分。
如果有交集的话，则有用的区间对至多有n个。讲区间按照左端点升序，右端点降序排列，对于区间i找到第一个右端点超出它的第一个区间j，那么<i,j>就是有用的，对于j之后的区间是相对i区间无用的。
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 2e5+10;
int n , m , k;
int Sum[N] , Sum1[N] , Sum2[N];
struct Node{
int l , r , val1 , val2;
}p[N];
bool cmp_val1(const Node &A , const Node &B) { return A.val1 > B.val1; }
bool cmp_pos (const Node &A , const Node &B) { return A.l == B.l ? A.r > B.r : A.l < B.l; }
void Solve()
{
int res = 0 , Answer = 0;
cin >> n >> m >> k;
for(int i = 1 ; i <= m ; ++i)
cin >> p[i].l >> p[i].r;
for(int i = 0 ; i <= n + 1 ; ++i) Sum[i] = Sum1[i] = Sum2[i] = 0;
for(int i = 1 ; i <= m ; ++i) Sum[p[i].l]++ , Sum[p[i].r+1]--;
for(int i = 1 ; i <= n ; ++i) Sum[i] += Sum[i-1];
for(int i = 1 ; i <= n ; ++i) if(Sum[i] == 0) res++;
for(int i = 1 ; i <= n ; ++i) if(Sum[i] == 1) Sum1[i] = Sum1[i-1] + 1; else Sum1[i] = Sum1[i-1];
for(int i = 1 ; i <= n ; ++i) if(Sum[i] == 2) Sum2[i] = Sum2[i-1] + 1; else Sum2[i] = Sum2[i-1];
for(int i = 1 ; i <= m ; ++i)
p[i].val1 = Sum1[p[i].r] - Sum1[p[i].l-1] ,
p[i].val2 = Sum2[p[i].r] - Sum2[p[i].l-1] ;
sort(p + 1 , p + 1 + m , cmp_val1);
Answer = max(Answer , res + p[1].val1 + p[2].val1);
sort(p + 1 , p + 1 + m , cmp_pos);
for(int i = 1 ; i <= m ; ++i)
{
int j = i , l , r;
while(j <= m && p[j].l >= p[i].l && p[j].r <= p[i].r) j++;
for(int k = i + 1 ; k <= min(j , m) ; ++k)
{
l = max(p[i].l , p[k].l);
r = min(p[i].r , p[k].r);
Answer = max(Answer , res + p[i].val1 + p[k].val1 + max(Sum2[r] - Sum2[l-1] , 0));
}
i = j - 1;
}
cout << Answer << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) Solve();
return 0;
}
困难版
动态规划求解，设\(dp[i][j]\)表示到i为止，消除了j个区间，并且第i个位置目前没有区间覆盖的最大无覆盖的点的个数。
转移方程\(dp[i][j] = max\{1 + dp[t][j - d_t]\}\)
其中\(d_t\)表示\(t < l <= i <= r\)的区间个数。
\(d_t\)最多只有k种取值，每种取值对应一个第一维区间，所以就可以用O(k)的复杂度求出一个状态。
总的复杂度为O(n*k^2)
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 2e5+10 , inf = 1e8;
int n , m , k;
int St[11][N][18] , Visit[N];
vector<int> Add[N] , Dec[N];
struct Interval{ int l , r; }Inter[N];
inline void Update(int d , int p , int val)
{
St[d][p][0] = max(St[d][p][0] , val);
for(int i = 1 ; p - (1 << i) + 1 >= 0 ; ++i)
St[d][p-(1<<i)+1][i] =
max(St[d][p-(1<<(i-1))+1][i-1] , St[d][p-(1<<i)+1][i-1]);
}
inline int Query(int d , int l , int r)
{
int k = ceil(log2((r - l) / 2.0 + 1));
return max(St[d][l][k] , St[d][r - (1 << k) + 1][k]);
}
void Init()
{
for(int i = 0 ; i <= k ; ++i)
for(int j = 0 ; j <= n ; ++j)
for(int t = 0 ; t < 18 ; ++t)
St[i][j][t] = -inf;
for(int i = 0 ; i <= n + 1 ; ++i)
Add[i].clear() , Dec[i].clear();
for(int i = 0 ; i <= m ; ++i) Visit[i] = 0;
}
bool cmp(int x , int y) { return Inter[x].l > Inter[y].l; }
int Solve()
{
int cover , uncover , Answer , lst , pre;
vector<int> tmp , cur;
cin >> n >> m >> k;
for(int i = 1 ; i <= m ; ++i)
cin >> Inter[i].l >> Inter[i].r;
Init();
for(int i = 1 ; i <= m ; ++i)
Add[Inter[i].l].push_back(i) ,
Dec[Inter[i].r + 1].push_back(i);
Update(0 , 0 , 0);
cover = uncover = Answer = 0;
for(int i = 1 ; i <= n ; ++i)
{
for(auto x:Add[i])
{
cover++;
cur.push_back(x);
}
for(auto x:Dec[i])
{
cover--;
Visit[x] = 1;
}
if(cover > k)
{
for(int j = 0 ; j <= k ; ++j)
Update(j , i , -inf);
continue;
}
tmp.clear();
for(auto x:cur)
if(!Visit[x]) tmp.push_back(x);
cur = tmp;
if(cur.empty())
{
for(int j = 0 ; j <= k ; ++j)
Update(j , i , -inf);
uncover++;
continue;
}
sort(cur.begin() , cur.end() , cmp);
if(Inter[cur[0]].l < i)
{
for(int j = 0 ; j <= k ; ++j)
{
int val = Query(j , Inter[cur[0]].l , i - 1);
Answer = max(Answer , val + 1);
Update(j , i , val + 1);
}
}
else
{
for(int j = 0 ; j <= k ; ++j)
Update(j , i , -inf);
}
lst = Inter[cur[0]].l - 1;
for(int j = 0 ; j < min((int)cur.size() , k) ; ++j)
{
if(j + 1 != (int)cur.size() && Inter[cur[j]].l == Inter[cur[j+1]].l)
continue;
if(j + 1 == (int)cur.size())
pre = 0;
else
pre = Inter[cur[j+1]].l;
for(int g = j + 1 ; g <= k ; ++g)
{
int val = Query(g - (j + 1) , pre , lst);
Answer = max(Answer , val + 1);
Update(g , i , val + 1);
}
lst = pre - 1;
}
}
cout << Answer + uncover << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T; while(T--) Solve();
return 0;
}