A.Game with Board
算法本质
思维
题目大意
初始存在n个数字1，Alice和Bob轮流执行操作：
- 选择多个相同数字组合为他们的和
若无法执行操作，则获胜。
给定n判断谁会获胜。
思路推演
通常来说，这种博弈论问题，通常将当前情况转化为更容易求得的情况来求解。
但是考虑到是A题，我们直接从小模拟n的情况。
当n较大时，可以发现Alice存在一个必胜法是：先组合n-2个数字1，Bob不得已组合剩下2个数字1，则Alice赢。
通过计算各种条件，这需要n>=5才行。
则n=2~4手动模拟，发现都是Bob胜利。
B.Keep it Beautiful
算法本质
思维
题目大意
对于数组a[]，定义美丽的满足以下：
- 选择
a[]前缀若干元素顺序添加至末尾，保证不降序排列
现给定空数组a[]，接下来挨个给定n个数字，若当前数组放入a[]末尾后a[]是美丽的，则必须放入。
最后输出01字符串s[]，s[i]表示第i个数字是否放入。
思路推演
通过手动模拟可以发现，若数字一直不降序，则必然美丽。
当发生第一次降序后，若其值小于第一个数字，并且大于前一个数字，则任然可以保持美丽。
当发生第二次降序后，则不添加数字。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
string ans;
int cnt=0, a1, ax; // a1 ax表示数组中的未降序前的最小、最大元素值， cnt表示降序次数
cin>>n>>a1; // 第一个元素手动初始化
ax = a1;
ans.push_back('1');
for (int i=2; i<=n; i++)
{
int x, nw_cnt;
cin>>x;
nw_cnt = cnt + (x<ax); // 降序次数预测
if (nw_cnt==0 || (nw_cnt==1 && x<=a1)) // 若当前还没有降序 或者 当前降序了1次但是当前值小于a1
cnt=nw_cnt, ax=x, ans.push_back('1'); // 加入数组，更新答案
else
ans.push_back('0'); // 不加入数组，更新答案
}
cout<<ans<<endl;
return;
}C.Ranom Numbers
算法本质
思维
题目大意
现在给定一由ABCDE组成的字符串s[]，其中每个字符分别表示的值绝对值为1 10 100 1000 10000，当s[i]右侧不存在大于其的字符，其值为正数，反之为负数。s[]的值为字符之和。
现在可以任意改变某个下标的字符，输出最大化的s[]的值。
思路推演-朴素做法
改变字符有2个思路：
小改大，当前下标表示的值更多了，但是会使得部分字符符号由正变负
大改小，当前下标的值减少了，单部分字符符号由负变正
一个容易想到的朴素做法是，我们暴力枚举每个下标的改变，通过预处理O(1)获取改变的值。
当我们目前这个下标绝对值变化时，我们需要知道2个东西：
- 右侧的最大字符——用于判断当前绝对值的值
- 左侧的正值、负值（因为谁而负）情况——判断左侧值的改变
预处理：
右侧最大字符相对容易，我们使用前缀和或者从右往左遍历即可获取。
左侧的值情况，负值我们可以详细分成：不可改变负值（存在>=2个大于其的字符）和可改变负值（有且仅有一个大于它的字符，并保存他们的下标）
思路推演-字符单位
当我们以字符为单位的思考的时候，其实其中存在规律的。
- 小改大：修改最前的字符是最优解
对于任意2个相等的字符、不同位置，设为a1 a2，当中间不存在大于字符a的字符时，显然正确。
现在考虑a1 b a2，其中b是大于a的字符。
当a1修改为x值且大于等于b时，一定优于a2修改为x，同时也优于a2修改为小于b的值 - 大改小：修改最后的字符是最优解
显然，不证明
ac核心代码-朴素做法
头文件、宏定义、快读模板、常见变量、常见变量等略。
const int pow10[] = {1, 10, 100, 1000, 10000};
int fu[maxn];
char maxc_right[maxn];
inline void solve()
{
//init
cin>>s;
map<char, pair<int, int>> now; // 存那些符号为负，但是可能转正的信息
map<int, map<char, int>> mp; // 存放因为当前点阻拦而取负值的字符、数目
maxc_right[s.length()] = 'A'; // 相当于情况maxc_right[]
for (int i=s.length()-1; i>=0; i--)
{
maxc_right[i] = max(maxc_right[i+1], s[i]); // 更新右侧的最大字符
if (now.count(s[i])==0) now[s[i]]={0,0};
now[s[i]].first++; // 数目+1
now[s[i]].second=i; // 最近下标更新
int num=0, p;
for (char c=s[i]+1; c<='E'; c++) // 找到右侧大于其的数目
if (now.count(c))
num += now[c].first, p=now[c].second;
if (num==0)
fu[i]=1;
else
fu[i]=-1;
if (num==1) // 说明是可能由负转正的
mp[p][s[i]]++;
}
//cal
int ans=0;
for (int i=0; i<s.length(); i++) // 不做改变的值
ans += pow10[s[i]-'A']*fu[i];
int yans=ans;
map<char, int> left; // 仅存符号为正的信息
for (int i=0; i<s.length(); i++)
{
// 小改大
for (char c=s[i]+1; c<='E'; c++)
{
if (maxc_right[i+1]>c) continue; // 右侧有更大的
int more=0;
more += pow10[c-'A']-pow10[s[i]-'A']*fu[i]; // 当前值的增加
for (char c2=s[i]; c2<c; c2++) // 左侧原本正值元素变为负值
more -= 2*pow10[c2-'A']*left[c2];
ans = max(ans, yans+more);
}
// 大改小
for (char c='A'; c<s[i]; c++)
{
int more=0;
more -= pow10[s[i]-'A']*fu[i];
if (maxc_right[i+1]>c) // 说明改了之后是负号
more -= pow10[c-'A'];
else
more += pow10[c-'A'];
for (char c2=c; c2<s[i]; c2++)
more += 2*mp[i][c2]*pow10[c2-'A']; // 由负转正的值
ans = max(ans, yans+more);
}
// 信息更新
if (fu[i]==1)
left[s[i]]++;
}
cout<<ans<<endl;
return;
}ac核心做法-字符单位
头文件、宏定义、快读模板、常见变量、常见变量等略。
const int pow10[] = {1, 10, 100, 1000, 10000};
int f(const string &x)
{
int res=0;
char c='A';
for (int i=x.length(); i--; i>=0)
{
if (c>x[i])
res -= pow10[x[i]-'A'];
else
res += pow10[x[i]-'A'];
c = max(c, x[i]);
}
return res;
}
inline void solve()
{
//init
cin>>s;
map<char, pair<int, int>> mp; // 记录每个字符的首下标和末下标
for (int i=0; i<s.length(); i++)
{
if (!mp.count(s[i]))
mp[s[i]] = {i, i};
else
mp[s[i]].second = i;
}
int ans=f(s);
for (char c='A'; c<='E'; c++)
{
if (!mp.count(c)) continue;
for (char c2='A'; c2<='E'; c2++)
{
string ns = s;
ns[mp[c].first] = c2;
ans = max(ans, f(ns));
ns = s;
ns[mp[c].second] = c2;
ans = max(ans, f(ns));
}
}
cout<<ans<<endl;
return;
}D.Pairs of Segments
算法本质
思维
题目大意
给定n个（一维）线段区间，现在要求你删去任意条线段，使得剩下的线段满足：
- 可两两分组
- 同组线段必定相交（点相交也算相交）
- 不同组线段必定不相交
输出最小化的删除条数。
n <= 2e3思路推演
难点是抽象题意：
我们任选2条相交线段，假定他们组成一组，可以用并集来表示他们的“管辖范围”，不能有其他任意的线段进入这个范围。
如何对任意2条线段如法炮制，这就变成了一个会议问题：
有4e6条一维线段，选则若干条线段出来，使其不相交同时保证数目最多。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<pair<int, int>> p1, p2; // p1用于存放线段 p2存放线段的并集
m = n;
while (m--)
{
pair<int, int> tmp;
cin>>tmp.first>>tmp.second;
p1.push_back(tmp);
}
for (int i=0; i<p1.size(); i++)
{
for (int j=i+1; j<p1.size(); j++) // 任意两条线段
{
auto [l1, r1] = p1[i];
auto [l2, r2] = p1[j];
if (max(l1, l2) <= min(r1, r2)) // 说明相交了
p2.push_back({min(l1,l2), max(r1,r2)});
}
}
sort(p2.begin(), p2.end(), [](const pair<int, int> &a, const pair<int, int> &b) // 排序，右端点升序，伴随左端点升序
{
if (a.second==b.second)
return a.first<b.first;
return a.second < b.second;
});
int ans=0, last=-1; // ans表示最多可以保留的线段并集数，last表示上次线段的左端点位置
for (auto it:p2)
{
if (it.first > last)
{
last = it.second;
ans++;
}
}
cout<<n-ans*2<<endl; // 删除条数 = 所有条数 - 2*最多保留的线段并集数
return;
}E.Fill the Matrix
算法本质
思维、st表
题目大意
给定n a[] m
表示一个n*n的棋盘，第i行的前a[i]格子不能填写数字。
目前拥有1~m数字，给其他格子填写，当j+1在j同行的下一列，贡献值+1。
输出最大化后的贡献值。
思路推演
本质是找同行的连续线段，收益为线段长度-1。
因为同列不可填的格子，都在最上方，所以可以用dfs分段来处理。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
// 忽略了st表模板（返回最大值下标）
map<int, int> mp; // mp[线段长度] = 数目
void dfs(int l=1, int r=n, int h=n) // 分类
{
int mid = find_st(l, r); // 最大值的下标
int nh = a[mid]; // 最大值
mp[r-l+1] += h-nh; // 记录
if (l<=mid-1 && nh>0) // 左边
dfs(l, mid-1, nh);
if (mid+1<=r && nh>0) // 右边
dfs(mid+1, r, nh);
}
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>a[i];
cin>>m;
init_st();
//cal
int ans=0;
mp.clear();
dfs();
for (auto it=mp.rbegin(); it!=mp.rend(); it++) // 从大到小遍历
{
if (m==0) break;
int num = min(m/it->first, it->second);
ans += num*(it->first-1);
it->second -= num;
m -= num*it->first;
if (it->second>0 && m>0)
{
ans += m-1;
it->second--;
m = 0;
}
}
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)