\(A\)
过太慢了 QAQ 。看来得多练（可能是因为刚上完数模，脑子一团浆糊）
#include<bits/stdc++.h>
using namespace std;
char ans[105];
int cnt[28];
int main(){
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
string s;cin>>s;
for(int i=0;i<27;++i)cnt[i]=0;
for(int i=0;i<k;++i)ans[i]='a';
for(int i=0;i<n;++i)cnt[s[i]-'a']++;
for(int i=0;i<26;++i){
for(int j=0;j<k;++j){
if(cnt[i]<=0)break;
if(ans[j]-'a'==n/k)continue;
if(ans[j]-'a'==i){
--cnt[i];++ans[j];
}
}
}
for(int i=0;i<k;++i){
ans[i]=max(ans[i],'a');
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
\(B\)
好题！
很好想，公式很自然，但就是卡了 30min，甚至我都想弃赛了。
注意大数开 \(sqrt\) 精度损失严重！！ （其实小的数也一样）所以能不用 double 就不用。
#include<bits/stdc++.h>
using namespace std;
long long work(long long r){
if(r==0)return 0;
long long sq=sqrt(r),ans,now;
if((sq+1)*(sq+1)<=r)++sq;
if(sq*sq>r)--sq;
ans=3*(sq-1);
now=sq;
if(sq*(sq+1)<=r)++now;
if(sq*(sq+2)<=r)++now;
ans+=now-sq+1;
return ans;
}
int main(){
int t;
cin>>t;
while(t--){
long long l,r;
cin>>l>>r;
cout<<work(r)-work(l-1)<<endl;
}
return 0;
}
\(C\)
我觉得样例提示得已经够明显了。。。最小操作单元就是平移 2 个单位。
但这样可能会出错，但样例也十分良心地提醒了：
当 \(L\) 形中间点在棋盘四个角落时，无法整体平移，只能单独一行或一列。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;c=getchar();
}
return x*f;
}
int main(){
int t;cin>>t;
while(t--){
int n,fl=0;cin>>n;
int r1=read(),c1=read(),r2=read(),c2=read(),r3=read(),c3=read();
int x=read(),y=read();
int xx=r1,yy=c1;
if(r2==r3)xx=r2;if(c2==c3)yy=c2;
if((xx==1||xx==n)&&(yy==1||yy==n)){
if(x==xx||y==yy)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
continue;
}
if((x-r1)%2==0&&(y-c1)%2==0)fl=1;
if((x-r2)%2==0&&(y-c2)%2==0)fl=1;
if((x-r3)%2==0&&(y-c3)%2==0)fl=1;
if(fl)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
\(D\)
（比赛时太困了，想了 5 分钟直接弃疗。
这道题关键在于转化题意：即一步操作相当于用 \(w_i\) 的代价把第 \(i\) 条边的一个端点沿着已有的边转移。若是形成自环，就相当于合并端点。
这时我们考虑最后从 \(1\) 到 \(n\) 的最短路径，容易（完全想不到）发现，若是由 2 条边组成，那么可以只用 \(w\) 最小的边来连，最终代价更小。所以最后的答案路径一定是单独一条边。
这时，又有新的疑问了：如何移动呢？是通过初始边还是某条已经移动过的边呢？
还是考虑最简单的情况：假设有 \(i\) 和 \(j\) 两条边，目标是移动 \(i\) 来作为最终答案，但途中先移动了 \(j\) ，然后再让 \(i\) 通过 \(j\) 来移动。这个假设的前提是 \(j\) 移动比不移动更优，即 \(w_i>w_j\) 。
那么容易发现，因为 \(w_j<w_i\) ，那么完全可以让 \(j\) 走 \(i\) 走过的路，最终答案还更小。
所以构造方法呼之欲出：预处理出 \(1、n\) 到所有点的最短距离 \(dis[i][j]\)，枚举所有边，计算即可。
但自环有什么用？
那当然是先移动一个端点到某个点，然后让另一个端点 “飞” 过来，之后再分开走。这样就节省了一段距离！至于为什么只合并一次，就留给读者了（
（虽然但是，为什么 弗洛伊德 都能写错 QAQ
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';c=getchar();
}
return x*f;
}
#define N 505
#define inf 100000000000
long long dis[N][N],w[250005];
int u[250005][2];
int main(){
int t=read();
while(t--){
int n=read(),m=read();
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)dis[i][j]=inf;
for(int i=1;i<=n;++i)dis[i][i]=0;
for(int i=1;i<=m;++i){
u[i][0]=read(),u[i][1]=read(),w[i]=read();
dis[u[i][0]][u[i][1]]=min(dis[u[i][0]][u[i][1]],1ll);
dis[u[i][1]][u[i][0]]=min(dis[u[i][1]][u[i][0]],1ll);
}
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
long long ans=10000000000000000;
int fl=0;
for(int i=1;i<=m;++i){
for(int xo=0;xo<2;++xo){
int x=u[i][xo],y=u[i][xo^1];
if(dis[1][x]!=inf&&dis[y][n]!=inf){
ans=min(ans,1ll*(dis[1][x]+dis[y][n]+1)*w[i]);
fl=1;
}
for(int mi=1;mi<=n;++mi){
if(dis[x][mi]!=inf&&dis[mi][1]!=inf&&dis[mi][n]!=inf){
fl=1;
ans=min(ans,1ll*(dis[x][mi]+dis[mi][1]+dis[mi][n]+2)*w[i]);
}
}
}
}
if(fl==0)cout<<dis[1][n]<<endl;
printf("%lld\n",ans);
}
return 0;
}