abc260_a
题目翻译
聊天聊过头晚开题我是什么品种的制杖。
有一个长度为 $3$ 的字符串 $s$，问 $s$ 中只出现一次的字符是什么，没有输出 $-1$。
题目思路
建一个数组存放每个小写字母出现次数，最后扫一遍。
AC 代码
#include<bits/stdc++.h>
using namespace std;
int a['z'+1];
int main()
{
string s;
cin>>s;
a[s[0]]++;
a[s[1]]++;
a[s[2]]++;
for(int i='a';i<='z';i++)
{
if(a[i]==1)
{
cout<<char(i)<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}abc260_b
题目翻译
忘了 greater<pair<int,int>>() 对 second 也从大到小排序我是什么品种的制杖。
有 $n$ 个学生，第 $i$ 个学生数学成绩 $a_i$，英语成绩 $b_i$。
选取数学成绩前 $x$ 个，英语成绩前 $y$ 个，总成绩前 $z$ 个学生录取，一位同学若录取多次，资格顺延。
问录取了哪些学生。
题目思路
结构体排序，存放数学、英语、总分、学号。
或者和我一样，写几个 pair 储存。
AC 代码
#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[1005];
pair<int,int>b[1005];
pair<int,int>c[1005];
set<int>ans;
bool f[1005];
bool cmp(pair<int,int>a,pair<int,int>b)
{
if(a.first!=b.first)return a.first>b.first;
return a.second<b.second;
}
int main()
{
int n,x,y,z;
cin>>n>>x>>y>>z;
for(int i=1;i<=n;i++)
{
cin>>a[i].first;
a[i].second=i;
}
for(int i=1;i<=n;i++)
{
cin>>b[i].first;
b[i].second=i;
c[i].first=a[i].first+b[i].first;
c[i].second=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
sort(c+1,c+n+1,cmp);
for(int i=1;i<=x;i++)
{
if(!f[a[i].second])
{
f[a[i].second]=1;
ans.insert(a[i].second);
}
else
{
x++;
}
}
for(int i=1;i<=y;i++)
{
if(!f[b[i].second])
{
f[b[i].second]=1;
ans.insert(b[i].second);
}
else
{
y++;
}
}
for(int i=1;i<=z;i++)
{
if(!f[c[i].second])
{
f[c[i].second]=1;
ans.insert(c[i].second);
}
else
{
z++;
}
}
for(int i:ans)cout<<i<<endl;
return 0;
}abc260_c
题目翻译
check 函数写错我是什么品种的制杖。
你一开始有一个红 Buff，可以减速敌人并且打出真伤。可以和队友交换能减 CD 回蓝量的蓝 Buff。
每个 $m$ 级红宝石，可兑换 $1$ 个 $m-1$ 级红宝石和 $x$ 个 $m$ 级蓝宝石。
每个 $m$ 级蓝宝石，可兑换 $1$ 个 $m-1$ 级红宝石和 $y$ 个 $m-1$ 级蓝宝石。
你有一个 $n$ 级红色宝石，问最多能换几个蓝宝石。
题目思路
换最多的蓝宝石，必定是 $1$ 级蓝宝石。
循环操作兑换过程即可。
AC 代码
#include<bits/stdc++.h>
using namespace std;
long long red[20];
long long blue[20];
int n,x,y;
bool check()
{
for(int i=2;i<=10;i++)
{
if(blue[i]||red[i])return 0;
}
return 1;
}
int main()
{
cin>>n>>x>>y;
red[n]++;
while(!check())
{
for(int i=n;i>=2;i--)
{
long long z=red[i];
red[i]-=z;
red[i-1]+=z;
blue[i]+=z*x;
}
for(int i=n;i>=2;i--)
{
long long z=blue[i];
blue[i]-=z;
blue[i-1]+=z*y;
red[i-1]+=z;
}
}
cout<<blue[1]<<endl;
return 0;
}abc260_d
题目翻译
看错输出 21:39 发现并交代码我是什么品种的制杖。
有 $n$ 张牌 $p_1,p_2,p_3,\dots,p_n$，$p$ 是 $n$ 的排列。
维护若干个牌堆，执行以下操作：
- 如果所有牌堆堆顶都比 $p_i$ 小，新开牌堆并把 $p_i$ 当堆顶。
- 如果有牌堆堆顶比 $p_i$ 大，$p_i$ 放在比它大的最小的牌堆堆顶那一个牌堆。
- 如果某个牌堆数量到了 $k$，永远不放牌了并且这个牌堆的牌的答案为 $i$。
题目思路
I love set.
用 STL 中的 set。
每次暴力找牌堆堆顶是不可取的，把这些牌堆存进 set 并二分这个牌堆。
其他的按题意说的操作即可。
AC 代码
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int fa[200005],id,c[200005],d[200005];
bool f[200005];
int ans[200005];
set<int>s;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(s.size()==0||a[i]>*s.rbegin())
{
s.insert(a[i]);
id++;
fa[a[i]]=id;
c[id]=a[i];
d[id]++;
if(d[id]==k)
{
f[id]=1;
ans[id]=i;
s.erase(a[i]);
}
}
else
{
auto it=s.upper_bound(a[i]);
int x=fa[*it];
if(f[x]==1)
{
continue;
}
c[x]=a[i];
d[x]++;
fa[a[i]]=x;
s.erase(it);
s.insert(a[i]);
if(d[x]==k)
{
f[x]=1;
ans[x]=i;
s.erase(a[i]);
}
}
}
for(int i=1;i<=n;i++)
{
cout<<(ans[fa[i]]==0?-1:ans[fa[i]])<<endl;
}
return 0;
}