admin管理员组文章数量:1594655
A - Bad Triangle
最小的两边和小于等于最大的边，那么就一定不会存在这个三角形。否则，一定存在。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 5e4 + 10;
int T, n;
int a[N];
int main() {
T = read();
while (T--) {
n = read();
upd(i, 1, n)a[i] = read();
if (a[1] + a[2] <= a[n]) {
printf("%d %d %d\n", 1, 2, n);
}
else {
puts("-1");
}
}
return 0;
}
B - Substring Removal Game
看着是博弈论，实际就是统计全1段的长度和个数。然后排序后贪心的从最大的开始取即可。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e2 + 10;
int T;
char s[N];
int cnt[N];
int main() {
T = read();
while (T--) {
scanf("%s", s+1);
int len = strlen(s + 1);
upd(i, 0, len)cnt[i] = 0;
stack<int >st;
vector<int>vec;
upd(i, 1, len) {
if (st.empty()) {
st.push(s[i]);
cnt[1] = 1;
}
else {
if (st.top() != s[i]) {
st.push(s[i]);
cnt[st.size()]++;
}
else cnt[st.size()]++;
}
}
while (!st.empty()) {
if (st.top() == '1')vec.push_back(cnt[st.size()]);
st.pop();
}
int ans = 0;
sort(vec.begin(), vec.end());
int num = 1;
for (int i = vec.size()-1; i>=0; i--,num++) {
if (num & 1)ans += vec[i];
}
cout << ans << endl;
}
return 0;
}
C - Good Subarrays
连续子段的和是该子段的长度，我们就可以想到，把所有数字全部剪掉1，那么等价于子段和是零。
问题转化成求前缀和后，找有多少个前缀相等的即可。
注意单独计算前缀和是0的前缀。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e5 + 10;
int T, n;
char a[N];
int aa[N];
ll sum[N];
map<int, ll>mp;
int main() {
T = read();
while (T--) {
n = read();
upd(i, 0, n)aa[i] = sum[i] = 0;
mp.clear();
scanf("%s", a + 1);
upd(i, 1, n)
aa[i] = a[i] - 1 - '0';
ll ans = 0;
upd(i, 1, n){
sum[i] = sum[i - 1] + aa[i];
}
upd(i, 1, n) {
if (sum[i] == 0)ans++;
mp[sum[i]]++;
ans += mp[sum[i]] - 1;
}
printf("%lld\n", ans);
}
return 0;
}
D - Colored Rectangles
可以看见的是，我们肯定会想到优先将数字更大的进行匹配，所以我们先进行排序，分别对三种颜色。那么现在就是，从大到小的取，该怎么取。
我们利用一个简单的
d
p
dp
dp即可。
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k]表示三种颜色分别取
i
,
j
,
k
i,j,k
i,j,k个的时候的最大值。
就很容易想到，进行简单的转移即可。
d
p
[
i
+
1
]
[
j
]
[
k
+
1
]
=
m
a
x
(
d
p
[
i
]
[
j
]
[
k
]
+
r
r
[
i
]
∗
b
b
[
k
]
,
d
p
[
i
+
1
]
[
j
]
[
k
+
1
]
)
;
d
p
[
i
]
[
j
+
1
]
[
k
+
1
]
=
m
a
x
(
d
p
[
i
]
[
j
]
[
k
]
+
g
g
[
j
]
∗
b
b
[
k
]
,
d
p
[
i
]
[
j
+
1
]
[
k
+
1
]
)
;
d
p
[
i
+
1
]
[
j
+
1
]
[
k
]
=
m
a
x
(
d
p
[
i
]
[
j
]
[
k
]
+
r
r
[
i
]
∗
g
g
[
j
]
,
d
p
[
i
+
1
]
[
j
+
1
]
[
k
]
)
;
dp[i + 1][j][k + 1] = max(dp[i][j][k] + rr[i] * bb[k], dp[i + 1][j][k + 1]); dp[i][j + 1][k + 1] = max(dp[i][j][k] + gg[j] * bb[k], dp[i][j + 1][k + 1]); dp[i + 1][j + 1][k] = max(dp[i][j][k] + rr[i] * gg[j], dp[i + 1][j + 1][k]);
dp[i+1][j][k+1]=max(dp[i][j][k]+rr[i]∗bb[k],dp[i+1][j][k+1]);dp[i][j+1][k+1]=max(dp[i][j][k]+gg[j]∗bb[k],dp[i][j+1][k+1]);dp[i+1][j+1][k]=max(dp[i][j][k]+rr[i]∗gg[j],dp[i+1][j+1][k]);
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 210;
int R, G, B;
int r[N], g[N], b[N];
int dp[N][N][N];
vector<int>rr, gg, bb;
bool cmp(int a, int b) {
return a > b;
}
int ans = 0;
int main() {
R = read(), G = read(), B = read();
upd(i, 1, R)r[i] = read(), rr.push_back(r[i]);
upd(i, 1, G)g[i] = read(), gg.push_back(g[i]);
upd(i, 1, B)b[i] = read(), bb.push_back(b[i]);
rr.push_back(0); gg.push_back(0), bb.push_back(0);
sort(rr.begin(), rr.end(), cmp); sort(gg.begin(), gg.end(), cmp); sort(bb.begin(), bb.end(), cmp);
upd(i, 0, R) {
upd(j, 0, G) {
upd(k, 0, B) {
dp[i + 1][j][k + 1] = max(dp[i][j][k] + rr[i] * bb[k], dp[i + 1][j][k + 1]);
dp[i][j + 1][k + 1] = max(dp[i][j][k] + gg[j] * bb[k], dp[i][j + 1][k + 1]);
dp[i + 1][j + 1][k] = max(dp[i][j][k] + rr[i] * gg[j], dp[i + 1][j + 1][k]);
ans = max(dp[i + 1][j][k + 1], ans);
ans = max(dp[i][j + 1][k + 1], ans);
ans = max(dp[i + 1][j + 1][k], ans);
}
}
}
cout << ans << endl;
}
E - Two Types of Spells
问题的本质就是，找k个数字，乘以两倍，其他的数字乘以一倍。（k是闪电的个数）
我们利用两个集合进行操作。一个集合放两倍数，一个集合放置一倍数。
当插入的时候，我们优先判断是否能进行两倍，即当前数字大于一倍数集合的最大值的时候。
删除的时候直接进行集合之间的删除。
除此之外，我们继续维护一个k，表示当前闪电的个数，即集合-两倍数的大小。
所以我们每一次再统计答案的时候，先判断集合-两倍数是否是大小是k，如果不是，添加或者删除，从集合-一倍数中。
另外需要排除一种特殊情况，即集合-两倍数中，全是闪电，那么这个时候集合两倍数就需要将最小的闪电，和最大的火进行互换（如果可以的话，否则相当于从两倍数-集合中删除该数字）。
可以方便进行，我们直接维护所有数字的和-ans，然后再ans+=sum[两倍数集合]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 2e5 + 10;
int n;
set<int >s1, s2, F;
int main() {
n = read();
int cnt_l = 0;
int tp, d;
ll ans = 0;
upd(i, 1, n) {
tp = read(), d = read();
ans += d;
if (d > 0) {
if (tp == 0) {
F.insert(d);
if (s2.size() && *s2.begin() <= d)s2.insert(d), ans += d;
else s1.insert(d);
}
else {
cnt_l++;
if (s2.size() && *s2.begin() <= d)s2.insert(d), ans += d;
else s1.insert(d);
}
}
else {
if (tp == 0) {
F.erase(-d);
if (s1.count(-d))s1.erase(-d);
else s2.erase(-d),ans += d;
}
else {
cnt_l--;
if (s1.count(-d))s1.erase(-d);
else s2.erase(-d), ans += d;
}
}
while (s2.size() > cnt_l) {
ans -= *s2.begin();
s1.insert(*s2.begin());
s2.erase(s2.begin());
}
while (s2.size() < cnt_l) {
ans += *s1.rbegin();
s2.insert(*s1.rbegin());
s1.erase(--s1.end());
}
int x = 0;
if (s2.size()) {
if (F.size())x = min(x, *F.rbegin() - *s2.begin());
else x = -*s2.begin();
}
printf("%lld\n", ans + x);
}
return 0;
}
F - Controversial Rounds
题目的本质就是，给出一个长度len，判断最多有少个，不重叠的，长度是len的全
0
0
0，或者全
1
1
1字串。
我们进一步思考可以发现一个贪心的策略。当0，1串重叠的时候，当且仅当出现’?'的时候，我们如果将‘？’归入当前前面的数字中，情况不会变差，所以基于该贪心，我们可以：
维护一个后缀长度，
n
x
t
[
0
]
[
p
o
s
]
,
n
x
t
[
1
]
[
p
o
s
]
nxt[0][pos],nxt[1][pos]
nxt[0][pos],nxt[1][pos],以
p
o
s
pos
pos结尾的，全
0
0
0，全
1
1
1串的长度。继续维护两个vector,
v
e
c
[
0
]
[
l
e
n
]
,
v
e
c
[
1
]
[
l
e
n
]
vec[0][len],vec[1][len]
vec[0][len],vec[1][len]存储，全
0
0
0，全
1
1
1的长度是
l
e
n
len
len的所有左端点。
继而我们可以利用调和级数
n
+
n
/
2
+
n
/
3
+
n
/
4
+
.
.
.
+
1
=
n
∗
log
(
n
)
n+n/2+n/3+n/4+...+1=n*\log(n)
n+n/2+n/3+n/4+...+1=n∗log(n)进行暴力判断。其中还有一个二分的
l
o
g
log
log，当每次找不到的时候，我们二分一个最小的左端点
>
=
n
o
w
p
o
s
>=nowpos
>=nowpos即可，没有的话，直接退出。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e6 + 1l;
char s[N];
int nxt[2][N];
vector<int> len[2][N];
int n;
bool check(int pos,int ter) {
if (s[pos] != '?'&&s[pos] != (ter + '0'))return 0;
else return 1;
}
int main() {
n = read();
scanf("%s", s + 1);
dwd(i, n, 1) {
if (s[i] == '1' || s[i] == '?')nxt[1][i] = 1 + nxt[1][i + 1];
if (s[i] == '0' || s[i] == '?')nxt[0][i] = 1 + nxt[0][i + 1];
}
upd(bit, 0, 1) {
for (int l = 1; l <= n;) {
if (!check(l,bit))l++;
else {
int r = l;
for (r = l; r <= n;) {
if (check(r, bit))
{
len[bit][r - l + 1].push_back(l);
r++;
}
else break;
}
l = r + 1;
}
}
}
upd(x, 1, n) {
int pos = 1;
int ans = 0;
while (pos <= n) {
if (nxt[0][pos] >= x || nxt[1][pos] >= x)pos += x, ans++;
else {
int temp1 = lower_bound(len[0][x].begin(), len[0][x].end(), pos) - len[0][x].begin();
int temp2 = lower_bound(len[1][x].begin(), len[1][x].end(), pos) - len[1][x].begin();
int pos1 = INF, pos2 = INF;
if (temp1 != len[0][x].size())pos1 = len[0][x][temp1];
if (temp2 != len[1][x].size())pos2 = len[1][x][temp2];
if (pos1 == INF && pos2 == INF)break;
pos = min(pos1, pos2);
}
}
printf("%d ", ans);
}
return 0;
}
本文标签： codeforcesEducationalDivRated
版权声明：本文标题：Educational Codeforces Round 93 (Rated for Div. 2) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1728180302a1148307.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论