A. Dual Trigger
贪心
大概思路
如果是奇数个1,那么免谈;如果是偶数个1,只需要两边从最外侧往内一个个开就行
注意: 当1的个数等于2时,要注意这两个1是不是相邻的,是的话就没办法了,输出NO; 当1的个数大于2时,考虑个数为4的情况,这时候就算它们四个都挤在一起,也有解:按照13、24这样打开就行;当个数大于4时,显然可以多次操作,回到个数为4的情况,依然可解。
因此当1的个数为2时比较特殊,需要特判。
参考代码
void solve() {
cin(n);
scin(s);
ll cnt=0;
for(auto &c:s)cnt+=(c=='1');
bool NO=0;
if(cnt==2)rep(i,0,n-2){
if(s[i]=='1'&&s[i+1]=='1'){
NO=1;break;
}
}
if(NO){CN;return;}
cout<<ANS[cnt%2==0];
}
B. Battle Cows
贪心,模拟
大概思路
思路挺清晰的,就是分类讨论比较麻烦。
当前面没有牛比自己rating大时,直接和第一头牛swap。
当位置k的前面只有一头rating比自己大的牛存在时,显然一把都赢不了,所以这时候你有两个选择
- 让自己和从左到右第一头rating比自己大的牛换位置
- 让自己和第一头牛换位置
这时候就要权衡选哪个的收益会更高了,设那头牛位置为 $j$,这里我们直接比较 $j-1$ 和 $m-j$ 即可。
当位置k的前面有两头及以上的牛比自己rating大时,也有同样的两个选择,不过这时候权衡的式子要调整,设两头牛位置分别为 $i,j(i<j)$,只需要比较 $i-1$ 和 $j-i$ 即可。
参考代码
void solve() {
cin(n);cin(m);
vector<int> a(n+1);
rep(i,1,n)cin>>a[i];
int flag[2]={-1,-1};
rep(i,1,m-1){
if(flag[0]==-1&&a[i]>a[m]){
flag[0]=i;
}else if(flag[0]!=-1&&a[i]>a[m]){
flag[1]=i;
break;
}
}
if(flag[0]==-1){
swap(a[1],a[m]);
m=1;
}else if(flag[1]==-1){
if(flag[0]-1>m-flag[0]){
swap(a[1],a[m]);
m=1;
}else{
swap(a[flag[0]],a[m]);
m=flag[0];
}
}else{
if(flag[0]-1>flag[1]-flag[0]){
swap(a[1],a[m]);
m=1;
}else{
swap(a[flag[0]],a[m]);
m=flag[0];
}
}
ll cnt=0;
rep(i,max(1,m-1),n){
//cout<<i<<"]";
if(a[i]>a[m])break;
if(a[i]<a[m])cnt++;
}
cout<<cnt<<et;
}
C - Ticket Hoarding
排序,贪心,模拟
大概思路
从小到大分配每天购买的票数,然后跑模拟即可。
参考代码
struct P{
int v,i,rnk;
};
void solve() {
cin(n);cin(m);cin(k);
int have=0;
vector<P> a(n+1);
rep(i,1,n){cin>>a[i].v;a[i].i=i;}
sort(a.begin()+1,a.end(),[&](P a,P b){//按值大小排序
return a.v<b.v;
});
rep(i,1,n)a[i].rnk=i;//标记rank
sort(a.begin()+1,a.end(),[&](P a,P b){//按原下标排序回去
return a.i<b.i;
});
ll cost=0;//开始模拟
rep(i,1,n){
if(a[i].rnk<=k/m){
cost+=(a[i].v+have)*m;
have+=m;
}
if(k%m&&a[i].rnk==k/m+1){
cost+=(a[i].v+have)*(k%m);
have+=(k%m);
}
}
cout<<cost<<et;
}
D - Buying Jewels
贪心,数学,找规律
大概思路
你手画一个表格,穷举一下 $n,k\in(1,9)$ 的情况,结合一下常识就会发现结论:
- 当 $n=k$ 时,显然可行,设单价为 $1$ 就行了
- 当 $\lfloor \frac{n+1}{2} \rfloor \ge k$ 时,也可行,开两家商铺,第一家单价为 $n-k+1$,让她只买到一个,剩 $k-1$ 元,然后第二家单价为 $1$ 即可。
- 当 $k>n$ 时,显然不行,你单价设成 $1$ 都不够她买的。
- 当 $k<n$ 且 $k>\lfloor \frac{n+1}{2} \rfloor$ 时,不可行,因为如果第一家单价为 $1$,那么她显然会买超了;如果单价为 $2$,那么也不行,因为此时你的最大购买力就是 $\lfloor \frac{n+1}{2} \rfloor$,购买力赶不上 $k$ 值,显然不够买;如果单价为 $3$ 或者更多,显然也是不够买的(不用算都知道单价开的越高,同样的钱买到的东西数越少)
综上,只需要特判出 $n=k$ 和 $\lfloor \frac{n+1}{2} \rfloor \ge k$ 剩下的直接输出NO就行了
参考代码
void solve() {
cin(n);cin(k);
if(n==k){
CY;
cout<<1<<et<<1<<et;
return;
}
if(((n+1)>>1)>=k){
CY;
cout<<2<<et<<n-k+1<<" "<<1<<et;
return;
}
CN;
}
E - No Palindromes
马拉车,暴力
大概思路
直接上马拉车预处理出回文半径(用于快速判断字符串子串是否为回文串),如果其本身已经是回文,直接输出即可;如果不是,就暴力遍历该往哪切一刀,使得两个串均为非回文串即可。
(要被自己蠢si了,最后10分钟放弃debug了,赛后发现是子串判回文写笨了,果然只了解板子是没用的,还要多练,写熟了,下次比赛中才不会去调细节)
参考代码
vector<int> manacher(string s) {
string t = "#";
for (auto c : s) {
t += c;
t += '#';
}
int n = t.size();
vector<int> r(n);
for (int i = 0, j = 0; i < n; i++) {
if (2 * j - i >= 0 && j + r[j] > i) {
r[i] = min(r[2 * j - i], j + r[j] - i);
}
while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
r[i] += 1;
}
if (i + r[i] > j + r[j]) {
j = i;
}
}
return r;
}
vector<int> PR;
inline bool PAL(int l,int r){
return PR[r+l-1]-1==(r-l+1);//就这玩意让我调了半天没过
}
void solve() {
scin(s);
PR = manacher(s);
if(!PAL(1,s.length())){
CY;
cout<<1<<et<<s<<et;
return;
}
rep(i,2,s.length()-1){
if(!PAL(1,i)&&!PAL(i+1, s.length())) {
CY;
cout<<2<<et<<s.substr(0,i)<<" "<<s.substr(i)<<et;
return;
}
}
CN;
}
附录
这里放上用到的文件头和main函数
#include<iostream>
#include<vector>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
//不要用#define,使用using可以用ll格式转换,但是#define不行
#define et '\n'
//慎用register和inline
#define reg register
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rrep(i,a,b) for(int i=(a);i>=(b);i--)
#define cin(a) ll a;cin>>a
#define dcin(a) ld a;cin>>a
#define scin(a) string a;cin>>a
#define CA cout<<ans<<et
#define CY cout<<"YES"<<et
#define CN cout<<"NO"<<et
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};
int M=1e9+7;
//inline ll MO(ll x){return (x%M+M)%M;}
void solve(){
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//pre();
cin(t);while(t--)
solve();
return 0;
}