Preface
重点策略：
\[\large\textbf{\underline{先写简单好写的算法，再逐步修改优化}} \]十分有效，百试百灵，屡试不爽。
A. Binary Imbalance
当有相邻两字符不相等时，就可以不断向中间插入 0。
所以输出 NO 当且字符串全为 1。
点击查看代码
#include<cstdio>
using namespace std;
const int N=105;
int n;
char str[N];
bool check()
{
for(int i=1;i<n;i++)
if((str[i]-'0')^(str[i+1]-'0'))
return true;
if(str[1]=='0') return true;
else return false;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,str+1);
printf("%s\n",check()?"YES":"NO");
}
}
B. Getting Points
究极橙题。
做法有点像这篇题解，用的是 \(O(1)\) 的数学做法。但是如果让我再来一次，我宁愿用二分。
因为数学做法太容易挂了，而且脑子要烧烂，看下代码就知道了。
下次遇到这种题先打最不容易错的，再逐步优化（这题甚至不用优化）。
点击查看代码
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,p,l,t;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld",&n,&p,&l,&t);
long long week=ceil(n/7.0);
if((week+1)/2*l+week*t>=p) printf("%lld\n",n-min((long long)ceil(1.0*p/(l+t*2)),week));
else printf("%lld\n",n-(week+1)/2-(long long)ceil(1.0*(p-(week+1)/2*l+week*t)/l));
}
return 0;
}
C. Insert and Equalize
所选 \(x\) 为 \(\gcd(a_1,a_2,\dots,a_n)\)，排序后如果原序列是等差数列就把 \(a_{n+1}\) 放在开头或末尾，否则在中间找一个值最大的空插进去。
最后序列要全部变为最大值，用最大值减每一个数再除以最大公约数就是每一次的操作次数，全部加起来即可。
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n;
long long a[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
if(n==1)
{
printf("1\n");
continue;
}
sort(a+1,a+n+1);
int d=a[2]-a[1];
for(int i=2;i<n;i++)
d=gcd(d,a[i+1]-a[i]);
long long ans=0;
for(int i=1;i<=n;i++)
ans+=(a[n]-a[i])/d;
bool is_full=true;
for(int i=n;i>=2;i--)
if(a[i]-a[i-1]!=d)
{
ans+=(a[n]-(a[i]-d))/d;
is_full=false;
break;
}
if(is_full) ans+=min((long long)(a[n]-(a[1]-d))/d,1ll*n*d);
printf("%lld\n",ans);
}
return 0;
}
D. Robot Queries
这题做的挺顺的，就是连着被卡空间又被卡时间有点不爽。
但是做这道题就是“先写简单好写的写法，再逐步优化”策略的典范，以后要多多按照这个策略做题。
E. Collapsing Strings
看出来是字典树，也有一些做法，但是实现比较复杂还容易错，所以我用的是这篇题解的处理方法。
久了没打字典树都快忘了，这次正好复习一下。
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+5;
int n;
string str[N];
long long ans,sumlen;
namespace Trie{
int trie[N][30],idx;
int cnt[N],end[N];
void insert(string &s)
{
int p=0;
for(int i=0;i<(int)s.length();i++)
{
int num=s[i]-'a'+1;
if(!trie[p][num]) trie[p][num]=++idx;
p=trie[p][num];
cnt[p]++;
}
end[p]++;
return;
}
long long query(string &s)
{
int p=0;
long long res=1ll*s.length()*n+sumlen;
for(int i=0;i<(int)s.length();i++)
{
int num=s[i]-'a'+1;
if(trie[p][num])
{
p=trie[p][num];
res-=2*cnt[p];
}
else break;
}
return res;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>str[i];
sumlen+=str[i].length();
Trie::insert(str[i]);
}
for(int i=1;i<=n;i++)
{
reverse(str[i].begin(),str[i].end());
ans+=Trie::query(str[i]);
}
printf("%lld\n",ans);
return 0;
}