S+20250814测试
A. 交换序列
暴力秒了（
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int n,p[55];
signed main(){
Cios;
cin>>n;
for (int i=1;i<=n;i++) cin>>p[i];
bool bl=1;
for (int k=1;k<n;k++) {
if (p[k+1]<p[k]) {
bl=0;
break;
}
}
if (bl) {
cout<<"YES"<<endl;
return 0;
}
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
swap(p[i],p[j]);
bl=1;
for (int k=1;k<n;k++) {
if (p[k+1]<p[k]) {
bl=0;
break;
}
}
swap(p[i],p[j]);
if (bl) {
cout<<"YES"<<endl;
return 0;
}
}
}
cout<<"NO"<<endl;
return 0;
}B. 最小绝对值
枚举 $x$ ，计算出 $y_1=\lceil \sqrt{d-x^2}\rceil ,y_2=\lfloor \sqrt{d-x^2}\rfloor$ 算出最小值即可
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int d,mind=LONG_LONG_MAX;
signed main(){
Cios;
cin>>d;
int sqd=sqrtl(d);
for (int x=sqd;x>=0;x--) {
int y=sqrtl(d-x*x);
mind=min({mind,abs(d-x*x-y*y),abs(d-x*x-(y+1)*(y+1))});
if (mind==0) break;
}
cout<<mind<<endl;
return 0;
}C. 3色骨牌
事实上这是一道数学题…（证明我上数学强基课没认真听吗有点意思
我们要进行分类讨论：
1. 当这个组合是两个横放（即$a_{1,i} \not = a_{2,i}$）时，有三种情况：
这是开头的骨牌（$i=1$）：$ans\times 6$
它的前一个组合是两个横放（$a_{1,i-1} \not = a_{2,i-1}$）的：$ans\times 3$
否则（它的前一个组合是一个竖放的，$a_{1,i-1} = a_{2,i-1}$）：$ans\times 2$
然后这种情况要记得跳掉一个$i$防止重复计算~
2.当这个组合是一个竖放时（即$a_{1,i}=a_{2,i}$）时，也有三种情况：
这是开头的骨牌（$i=1$）：$ans\times 3$
它的前一个组合是两个横放（$a_{1,i-1} \not = a_{2,i-1}$）的：$ans$ 保持不变
否则（它的前一个组合是一个竖放的，$a_{1,i-1} = a_{2,i-1}$）：$ans\times 2$
然后记得取模~
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc mod=1e9+7;
int ans=1,n;
char a[4][60];
signed main(){
Cios;
cin>>n;
for (int i=1;i<=2;i++) {
for (int j=1;j<=n;j++) cin>>a[i][j];
}
for (int i=1;i<=n;i++) {
if (a[1][i]!=a[2][i]) {
if (i==1) (ans*=6)
else if (a[1][i-1]!=a[2][i-1]) (ans*=3)
else (ans*=2)
i++;
}
else {
if (i==1) (ans*=3)
else if (a[1][i-1]!=a[2][i-1]) ans
else (ans*=2)
}
}
cout<<ans
return 0;
}D. 翻转行列
赛时你会发现输出 0 可以得 49 分（
这道题需要用到组合计数的知识，记得预处理 $C_n^m$
枚举每行每列反转的个数，多的可以直接堆在一起反转掉，都要用到组合数
具体看代码~
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc mod=555555555,N=3000;
int h,w,rc,cc,s,ans,c[N][N];
signed main(){
Cios;
cin>>h>>w>>rc>>cc>>s;
for (int i=0;i<N;i++) {
c[i][0]=1;
for (int j=1;j<=i;j++) c[i][j]+=(c[i-1][j]+c[i-1][j-1])
}
for (int i=0;i<=min(h,rc);i++) {
if (rc
for (int j=0;j<=min(w,cc);j++) {
if (cc
if (i*w+j*h-2*i*j-s) continue;
ans+=(c[h][i]*c[w][j]
ans
}
}
cout<<ans<<endl;
return 0;
}E. 键帽
非常好的dp题，使我的大脑旋转
可以发现dp方程充斥着 $5$ 和 $21$，非常正常，因为元音有 5 个嘛（
记得不要用memset，用for循环清空（不然会被卡掉
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc mod=1e9+7,maxp=1e6+10;
intl pow5[maxp],s[maxp];
void init() {
pow5[0]=1;
for(int i=1;i<maxp;i++) pow5[i]=pow5[i-1]*5
}
signed main(){
Cios;
init();
int T;
cin>>T;
while (T--) {
int n,k;
cin>>n>>k;
for (int i=1;i<=n+2;i++) s[i]=0;
s[0]=1;
for (int i=1;i<=n;i++) {
if (i<=k) s[i]=26*s[i-1]
else if (i==k+1) s[i]=(26*s[i-1]
else s[i]=(26*s[i-1]
s[i]=(s[i]
}
cout<<s[n]<<endl;
}
return 0;
}
评论（0）
暂无评论