目录
946(div3)
A
每个屏幕3X5, 可放2个2X2, 其余可填7个1X1 先算2X2需要多少个屏幕,再算当前屏幕是否可放下所有1X1, 根据1X1的量加屏幕.
void func()
{
int a,b;
cin >> a >> b;
int ans = (b+1) / 2;
int stp = a - (ans*15 - 4*b);
if(stp > 0) ans += (stp + 14) / 15;
//当前屏幕是否可以放下所有a，不能则再加屏幕.
cout << ans << '\n';
}
B
s为原字符串,r为s中字字母去重排序后字符串串. 题目需要求将s中每个字符根据r替换为r中对称字符后的字符串的原字符串. 实际操作可逆, 从s'得到s和从s得到s'的操作是一样的.
用s将r处理出来,再把对称字符互相映射用二分硬找也行,也是O(nlogn),输出替换的串即可.
void func()
{
int n;
string st;
cin >> n >> st;
vector<char> a(n);
for(int i=0;i<n;++i) a[i] = st[i];
sort(a.begin(),a.end());//处理r
a.erase(unique(a.begin(),a.end()),a.end());//去重函数
int len = a.size();
map<char,char> mp;//对称串映射
for(int i=0;i<len;++i)
{
mp[a[i]] = a[len - 1 - i];
}
for(int i=0;i<n;++i)
{
st[i] = mp[st[i]];
}
cout << st << '\n';
}
C
数据最多可有1011, 要开longlong
解法1: 3map暴力O(nlogn)
找到连续三个字符的字符串中有一个不同的个数. 时间长且数据不大,开三个map分别存123号位不同的点即可. 统计其中两个位相同第三个位相同和不同的数目,相乘加入总数即可.
代码比较丑陋, 直接粘贴了三个for().
void func()
{
int n;
cin >> n;
vector<int> v(n);
map<pair<int,int>,vector<int>> mp1,mp2,mp3;//三个二元组映射vector, 根据其中两位映射第三位.
int a,b,c;
for(auto &i : v) cin >> i;
for(int i=0;i<n-2;++i)
{
mp1[{v[i],v[i+1]}].push_back(v[i+2]);// 存储
mp2[{v[i],v[i+2]}].push_back(v[i+1]);
mp3[{v[i+1],v[i+2]}].push_back(v[i]);
}
int cnt = 1,ans = 0;
for(auto &i : mp1)//每次处理一组两位置相同的元素
{
sort(i.y.begin(),i.y.end());//排序,方便根据前一位统计有几个相同
int size = i.y.size();
for(int j=1;j<size;++j)
{
if(i.y[j] == i.y[j-1]) cnt++;
else
{
ans += (size-cnt)*cnt;
cnt = 1;
}
}
ans += (size-cnt)*cnt;//可能最后一元素与前一个相同, 需单独处理
cnt = 1;
}
//后二for()操作相同
for(auto &i : mp2)
{
sort(i.y.begin(),i.y.end());
int size = i.y.size();
for(int j=1;j<size;++j)
{
if(i.y[j] == i.y[j-1]) cnt++;
else
{
ans += (size-cnt)*cnt;
cnt = 1;
}
}
ans += (size-cnt)*cnt;
cnt = 1;
}
for(auto &i : mp3)
{
sort(i.y.begin(),i.y.end());
int size = i.y.size();
for(int j=1;j<size;++j)
{
if(i.y[j] == i.y[j-1]) cnt++;
else
{
ans += (size-cnt)*cnt;
cnt = 1;
}
}
ans += (size-cnt)*cnt;
cnt = 1;
}
cout << ans/2 << '\n';
}
解法2: 容斥O(nlogn)
统计出12,13,23号位相同的可能性, 再减去123号位完全相同的可能.
注意: 在12,13,23三组,统计了三次123相同,所以最后结果需要减三个123.
容斥原理
void func()
{
int n,ans1 = 0,ans2 = 0;
cin >> n;
map<pair<int,int>,int> cnt1,cnt2,cnt3;//分别存12, 13, 23相同的元素数目
map<edge,int> cnt4;// 存三个元素完全相同的元素数目
vector<int> v(n);
for(int i=0;i<n;++i) cin >> v[i];
for(int i=0;i<n-2;++i)
{
cnt1[{v[i],v[i+1]}]++;
cnt2[{v[i],v[i+2]}]++;
cnt3[{v[i+1],v[i+2]}]++;
cnt4[{v[i],v[i+1],v[i+2]}]++;
}
for(auto &i : cnt1) ans1 += (i.y-1)*i.y/2;
for(auto &i : cnt2) ans1 += (i.y-1)*i.y/2;
for(auto &i : cnt3) ans1 += (i.y-1)*i.y/2;
for(auto &i : cnt4) ans2 += i.y*(i.y-1)/2;
int ans = (ans1 - 3*ans2);
cout << ans << '\n';
}
D
保证两者都进行过运动下直接暴力即可, 因为多个if太长了, 抄了会长的代码.
对于每种操作, 第一次给了H, 第二次就必须给R. 所以计算同类操作MOD2后是否相同来确定此方向下HR同位置. 另外, 将Y轴操作初试设为1, X轴操作设为0可以保证有解情况下两者一定进行了操作.
void func()
{
int n;
string st,ans;
cin >> n >> st;
int cnt = 0;// 确定都进行操作
map<char,int> mp;
mp['W'] = mp['E'] = 1;
mp['N'] = mp['S'] = 0;
for(int i=0;i<n;++i)
{
ans += (mp[st[i]] == 0 ? 'R' : 'H');
if(ans[i] == 'R') cnt |= 1;// R
if(ans[i] == 'H') cnt |= 2;// H
mp[st[i]] ^= 1;
}
/*
cnt | 1 | 2 == 3, 保证两者都进行操作
N == S, W == E, 保证位置相同
*/
if(cnt == 3 && mp['N'] == mp['S'] && mp['W'] == mp['E']) cout << ans << '\n';
else cout << "NO\n";
}
E
G
贪心, 如果当前金钱可以购买本月快乐, 则加入答案, 但是如果买本次快乐的钱足够买后面两次的, 那就不成立, 所以在遇到后续更便宜的快乐时替换掉, 总快乐不变但是余额变多.
其实是反悔贪心, 把每次加入的答案加入堆, 如果余额足够则加入, 不足则和堆最大值比较, 如果更小则替换最大值, 获得差值的金钱.
void func()
{
int m,x;
cin >> m >> x;
vector<int> a(m);
for(auto &i :a) cin >> i;
priority_queue<int> pq;// 大根堆
int money = 0,happy = 0;
for(int i=0;i<m;++i)
{
if(money >= a[i])
{
happy++;
money -= a[i];
pq.push(a[i]);
}
else if(pq.size() && pq.top() > a[i])// 注意堆为空时不能访问.
{
money += (pq.top()-a[i]);
pq.pop();
pq.push(a[i]);
}
money += x;
}
cout << happy << '\n';
}