考试中：
发题以后，大致看了一下题目的难度：
- T1 感觉不太会做，应该是一道推公式或者找规律的题目。
- T2 感觉很原，但是有点忘了怎么写。
- T3 明显是 DP，感觉状转还需要想一下。
- T4 直接写暴力就可以跑了。
T1 上来就用草稿纸推公式，但是推了 20 分钟以后感觉没有什么出路，于是就果断选择先把暴力代码写出来。
写完以后就开始想有没有方式优化，但是没有办法。脑子灵光一现就输入了几组数据：
\[7,100 \]\[8,100 \]\[15,100 \]并且顺便把项数 \(i\) 和答案 \(y\) 打印了出来，然后就惊奇地发现了项数 \(i\) 变大到一定程度以后 \(y\) 构成的数列就成了等差数列。
一开始想着先找规律把 \(y\) 之间的公差求出来（大概就是按照 \(6\) 的倍数来划分了公差），但是在和暴力代码对拍的时候就发现错了很多。
于是干脆就直接不提前求出公差，当找到 \(y\) 序列中的 \(3\) 个数以后就可以直接输出答案，否则就一直暴力地跑下去，自己也预估了一下，发现要暴力跑的部分其实并不是很多。
在考试考了 1.5h 以后，我终于写好了这道题目。
T2 我是先跳过了的，直接去看 T3。
状态很简单，一眼就可以看出来：\(f_{i,j}\) 表示对于字符串 \(a\) 中前 \(i\) 个字符和对于 \(b\) 中前 \(j\) 个字符的最小贡献。
然后题目中的性质就是不用管相同字符中间出现的那些，只用在意开头和结尾。判断是不是开头和结尾都很简单，用 \(2\) 个前缀字符串数组优化一下就可以了。如果出现了第一个就减去 \(i+j\)，如果出现了最后一个就加上 \(i+j\)。
但是由于没有初始化 \(f_{0,j}\) 和 \(f_{i,0}\) 因此输出的数都是负数。
T4 我写的是 \(O((n-1)!)\) 的时间复杂度进行暴力，所以只得了 \(30\) 分。
T2 考试中写二分的时候忘记要先将 \(mid\) 提前减去，因此就写错了。
总结：
新年第一赛暴露了自己在 DP 转移和知识点扩展不充分的问题。
题解：
T1:【2015年7月的月赛】Ciocio的数学高考
跟考试中想的一样，代码实现很简单。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int Ts;
ll x,y,k,lst,now;
int main(){
*cin.tie(nullptr)<<fixed<<setprecision(20);
cout.tie(nullptr)->ios_base::sync_with_stdio(false);
cin>>Ts;
while(Ts--){
cin>>x>>y;
lst=x,now=x;
bool flag=false;
for(int i=2;i<=y;i++){
if(now%i) now=now+i-now%i;
if(lst/(i-1)==now/i){
cout<<(ll)y*(now/i)<<'\n';
flag=true;
break;
}
lst=now;
}
if(!flag) cout<<now<<'\n';
}
return 0;
}
T2:【思维挑战】帮忙
推完式子以后发现减去 \(mid\) 以后就没有很棘手的限制了，加上一个后缀最大值数组就过了。
const int N=1e6+5,eps=1e-4;
int n,k,a[N];
double s[N],Max[N];
bool check(double value){
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-value;
Max[n]=s[n];
for(int i=n-1;i;i--) Max[i]=max(Max[i+1],s[i]);
for(int i=1;i<=n-k+1;i++) if(Max[i+k-1]>=s[i-1]) return true;
return false;
}
signed main(){
*cin.tie(nullptr)<<fixed<<setprecision(20);
cout.tie(nullptr)->ios_base::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
double l=0.0000,r=2e9+5;
for(int cnt=1;cnt<=500;cnt++){
double mid=(l+r)/2.000000;
if(check(mid)) l=mid;
else r=mid;
}
cout<<(int)(l*1000)<<'\n';
return 0;
}
T3:小车的颜色
感谢 pyj，感谢 pyj。
思路很简单但是细节比较多。
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int Ts,n,m,f[N][N],s1[27][N],s2[27][N];
string a,b;
inline int calc(char ch){return (int)(ch-'A'+1);}
int main(){
*cin.tie(nullptr)<<fixed<<setprecision(20);
cout.tie(nullptr)->ios_base::sync_with_stdio(false);
cin>>Ts;
while(Ts--){
cin>>a>>b;
n=a.size(),m=b.size();
a=" "+a,b=" "+b;
memset(s1,0,sizeof s1),memset(s2,0,sizeof s2);
for(int i=1;i<=n;i++){
for(int j=1;j<=26;j++) s1[j][i]=s1[j][i-1];
s1[calc(a[i])][i]++;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=26;j++) s2[j][i]=s2[j][i-1];
s2[calc(b[i])][i]++;
}
// cout<<"a="<<a<<'\n'<<"b="<<b<<'\n';
// for(int i=1;i<=26;i++){
// cout<<(char)(i+'A'-1)<<":";
// for(int j=0;j<=n;j++){
// cout<<s1[i][j]<<'\t';
// }
// cout<<'\n';
// }
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// cout<<'\n';
// for(int i=1;i<=26;i++){
// cout<<(char)(i+'A'-1)<<":";
// for(int j=0;j<=m;j++){
// cout<<s2[i][j]<<'\t';
// }
// cout<<'\n';
// }
//
//
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
f[i][0]=f[i-1][0];
if(!s1[calc(a[i])][i-1]){
f[i][0]-=i;
}
if(s1[calc(a[i])][n]==s1[calc(a[i])][i]&&!s2[calc(a[i])][m]){
f[i][0]+=i;
}
}
for(int i=1;i<=m;i++){
f[0][i]=f[0][i-1];
if(!s2[calc(b[i])][i-1]){
f[0][i]-=i;
}
if(s2[calc(b[i])][m]==s2[calc(b[i])][i]&&!s1[calc(b[i])][n]){
f[0][i]+=i;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x=f[i-1][j],y=f[i][j-1];
if(!s1[calc(a[i])][i-1]&&!s2[calc(a[i])][j]) x-=(i+j);
if(s1[calc(a[i])][i]==s1[calc(a[i])][n]&&s2[calc(a[i])][j]==s2[calc(a[i])][m]) x+=(i+j);
if(!s1[calc(b[j])][i]&&!s2[calc(b[j])][j-1]) y-=(i+j);
if(s1[calc(b[j])][i]==s1[calc(b[j])][n]&&s2[calc(b[j])][j]==s2[calc(b[j])][m]) y+=(i+j);
f[i][j]=min(x,y);
}
}
// for(int i=0;i<=n;i++)
// {
// for(int j=0;j<=m;j++)
// {
// cout<<f[i][j]<<"\t";
// }
// cout<<endl;
// }
cout<<f[n][m]<<'\n';
}
return 0;
}
/*
1
GBBY
YRRGB
*/
T4:交作业
还未过
标签：false,新年,第一,int,T2,Ts,cin,2025,暴力 From： https://www.cnblogs.com/Dark-Figure/p/18665437