loj 有原题。别问为什么没 T4,问就是不会,等以后来补。
T1-两台机器
设两台机子分别为 \(a,b\),分 \(4\) 种情况:只用 \(a\),只用 \(b\),先 \(a\) 后 \(b\),先 \(b\) 后 \(a\),判断时间上是否满足,取最大值。
int main()
{
ll k,a,b,c,d;
read(k);read(a);read(b);read(c);read(d);
// if(a>c)swap(a,c),swap(b,d);
ll ans=0;
if(k-a-c>=0)cout<<max((k-a)*b+(k-a-c)*d,(k-c)*d+(k-a-c)*b);
else{
if(k>=a)ans=(k-a)*b;
if(k>=c)ans=max(ans,(k-c)*d);
cout<<ans;
}
return 0;
}
T2-分割数表
观察 \(a_{i,j}\),其实就是123456...一直往下排。
直接来推柿子:对于总和:\(sum=mn(mn+1)/2\),很明显是吧。
然后题目要求我们切一刀分成和不同的两块。
对于竖着切,设切了 \(k\) 列,左边那块的和为:
对于横着切,一样的,设切了 \(k\) 行,上面的那块和是等差数列,末项为 \(mk\),那么和为:
\[\frac {mk(mk+1)}2 \]然后我们可以 \(O(1)\) 求和,那么枚举行列就可以得出 \(O(n+m)\) 的算法。
考虑优化,希望最小化 \(\max(\sum x,\sum y)\),那肯定越接近 \(sum/2\) 越好,这个时候有两个办法:
- 二分,枚举行列显然有单调性,二分到 \(sum/2\),注意 \(\pm1\) 的误差,都要算一遍。
- 直接解方程解出 \(k\),也要注意 \(\pm1\) 的误差。
代码写成屎山了,细节有亿点点多,上 loj 贺代码。
T3 基因突变
队测的时候摆烂了暴力都没打。。。基因只因鸡~~~
注意 \(1,3\) 操作,如果一个字符可以换,那它肯定可以删,且删肯定比换更优,所以 \(3\) 操作没卵用。
将所有的相同字母看作一个块,记录这些块方便使用。
首先考虑最小化,显然只能用操作 \(2\),如果在长度大于二的块内删,那对答案贡献最多是 \(1\),甚至没有贡献:如 3AC4A
到 2AC4A
。
对于上面的例子,最好方法肯定删 C
,贡献也很容易计算。
接下来考虑最大化,最坏办法是插一个字符产生 \(1\) 的贡献,最优的肯定是在大于 \(2\) 的块内添字符,如 6A
到 3AC3A
,也就是我们要将前面的数字拆开,使位数最大化,这时很容易产生一个错误:操作的数字越大会使答案更优。但其实不是,举出反例:6A
到 3AC3A
,产生 \(3\) 的贡献;11A
到 10ACA
或 5AC6A
,产生 \(2\) 的贡献。但 \(3>2\),所以说我们每个数字都要枚举。
接下来要考虑怎么分,手模几组数据可以知道,只会有两种分发,一种折半分,如 \(8,100,1000=500+500\),另一种分成小于它的最大的 \(10\) 的幂,如 \(13,12=10+2\)。所以我们对一个数分成两种情况取最大值。
mdsb分类讨论题,一个小时真的写吐了,感谢 loj 一位老哥的代码:
#include<bits/stdc++.h>
#define fi first
#define se second
#define is(ch) isdigit(ch)
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using ull=unsigned long long;
void read(int &x){
char ch=getchar();
int r=0,w=1;
while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
while(isdigit(ch))r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
x=r*w;
}
const int N=2e5+7;
char t[N];
int n,cnt;
struct node{
char c;
int len;
}a[N];
int get(int x){
if(x==1)return 0;
int sum=0;
while(x){
sum++;
x/=10;
}
return sum;
}
void getmin(){
int pos=0,s=0;
int val=0;
for(int i=1;i<=cnt;i++)if(a[i-1].c==a[i+1].c&&a[i].len==1)
{
int x=a[i-1].len+a[i+1].len;
if(get(a[i-1].len)+get(a[i+1].len)-get(x)>=val)
{
pos=i;
val=get(a[i-1].len)+get(a[i+1].len)-get(x);
}
}
if(!pos)
for(int i=1;i<=cnt;i++)if(a[i].len<=2){pos=i;break;}
for(int i=1;i<=pos-1;i++)s+=a[i].len;
printf("2 %d\n",s+1);
}
char cc[]={'A','G','C','T'};
int get2(int x)
{
int t=1;
while(t*10<x)t*=10;
return t;
}
void getmax(){
int pos;
int val=0,tval;
for(int i=1;i<=cnt;i++){
int ttt=get2(a[i].len),ttx;
if(get(ttt)+get(a[i].len-ttt)>get(a[i].len>>1)*2)ttx=ttt;
else ttx=a[i].len>>1;
if(get(ttx)+get(a[i].len-ttx)+2-get(a[i].len)>=val&&a[i].len>=4){
val=get(ttx)+get(a[i].len-ttx)-get(a[i].len)+2;
pos=i;
tval=ttx;
}
//3A AC2A
else if(a[i].len==3&&val<2){
val=2;
pos=i;
tval=ttx;
}
//2A ACA A AC
else if(a[i].len<3&&val<1){
val=1;
pos=i;
tval=ttx;
}
}
int s=0;
char ans;
for(int i=0;i<=3;i++)if(cc[i]!=a[pos].c&&cc[i]!=a[pos+1].c)ans=cc[i];
for(int i=1;i<=pos-1;i++)s+=a[i].len;
printf("1 %d %c\n",s+tval,ans);
}
int main(){
scanf("%s",t+1);
n=strlen(t+1);
int now=0;
for(int i=1;i<=n;i++){
if(is(t[i]))now=now*10+t[i]-'0';
else{
a[++cnt].c=t[i];
a[cnt].len=now==0?1:now;
now=0;
}
}
getmin();
getmax();
return 0;
}
标签:ttx,get,read,题解,sum,len,ROIR,ch,2021
From: https://www.cnblogs.com/LAK666/p/16754150.html