S+20250816测试
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)
string a,b;
int ans=0;
signed main(){
Cios;
cerr.tie(0);
cin>>a>>b;
for (int i=0;i<a.size();i++) {
string a1=a.substr(0,i),a2=a.substr(i,a.size()-i);
string s;
s.append(a1);
s.append(b);
s.append(a2);
cerr<<s<<endl;
bool re=1;
for (int j=0,k=(int)s.size()-1;j<k;j++,k--) {
if (s[j]!=s[k]) {
re=0;
break;
}
}
if (re) ans++;
}
a.append(b);
cerr<<a<<endl;
bool re=1;
for (int i=0,j=(int)a.size()-1;i<j;i++,j--) {
if (a[i]!=a[j]) {
re=0;
break;
}
}
cout<<ans+re<<endl;
return 0;
}B. 三角形
输入点，预处理所有不相同点之间的斜率，此时我们定义，斜率$slove_{a,b}$：
$$
slove_{a,b} = \frac{|x_a-x_b|}{|y_a-y_b|} (y_a \not = y_b)
$$
$y_a=y_b$ 时，我们将斜率定义成 $\infty$；
分析三角形存在条件，无论方向，当三条边的斜率在我们这样定义的情况下一定会有至少两条边斜率不同。所以当我们发现三条边的斜率在数值上都相同时，这个三角形不存在。
#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 N=400;
int n,ans=0;
struct point {
int x,y;
}p[N];
struct slope {
int p,q;
bool operator !=(const slope &s) {
return p!=s.p||q!=s.q;
}
}sl[N][N];
slope getsl(int p,int q) {
int gcd=__gcd(p,q);
return {p/gcd,q/gcd};
}
//define slope_{a,b} = |x_a-x_b|/|y_a-y_b|
signed main(){
Cios;
cin>>n;
for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (i!=j) {
sl[i][j]=getsl(abs(p[i].x-p[j].x),abs(p[i].y-p[j].y));
}
}
}
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
for (int k=j+1;k<=n;k++) {
slope s1=sl[i][j],s2=sl[i][k],s3=sl[k][j];
if (s1!=s2||s2!=s3||s1!=s3) ans++;
}
}
}
cout<<ans<<endl;
return 0;
}C. 幂次整除
设 $c$ 的质因数分解 $c=p_1^{k_1}\times p_2^{k_2}\times … \times p_n^{k_n}$ ，$a$ 的质因数分解 $a=q_1^{r_1}\times q_2^{r_2}\times … \times q_m^{r_m}$ ；
可以发现，$c^d | a^b$，当且仅当 $\forall 1\le i\le n , \exists 1\le j\le m , \to p_i=q_j \land k_i d \le r_j b$。
所以我们记录所有 $c$ 的质因数分解，并进行判断即可。
注意两个特判，当 $a=1$ 时，当且仅当 $c=1$ 时有解，否则一定无解；当 $c=1$ 时一定有解。
#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)
intl a,b,c,d;
int main() {
Cios;
cin>>a>>b>>c>>d;
if (c==1) {
cout<<"divisible"<<endl;
return 0;
}
if (a==1) {
cout<<"not divisible"<<endl;
return 0;
}
map<intl,int> fac;
intl temc=c;
for (intl i=2;i*i<=temc;i++) {
while (temc
fac[i]++;
temc/=i;
}
}
if (temc>1) fac[temc]++;
for (auto [p,cnt]:fac) {
intl tema=a;
int cnta=0;
while (tema
cnta++;
tema/=p;
}
if (cnta==0) {
cout<<"not divisible"<<endl;
return 0;
}
if ((intl)cnta*b<(intl)cnt*d) {
cout<<"not divisible"<<endl;
return 0;
}
}
cout<<"divisible"<<endl;
return 0;
}D. 完整正方形
dp求解即可~
设 $dp_{i,j}$ 表示以 $(i,j)$ 为左上角的正方形个数 ，容易得出当$(i,j)$ 不为洞时，$dp_{i,j}=\min(dp_{i+1,j},dp_{i,j+1},dp_{i+1,j+1})+1$ ,为洞时 $dp_{i,j} =0$。
#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 N=3e3+2;
int dp[N][N];
bool hole[N][N];
int main() {
Cios;
int h,w,n;
cin>>h>>w>>n;
for (int i=1;i<=n;i++) {
intl a,b;
cin>>a>>b;
hole[a][b]=1;
}
intl ans=0;
for (int i=h;i>=1;i--) {
for (int j=w;j>=1;j--) {
if (hole[i][j]) dp[i][j]=0;
else dp[i][j]=min({dp[i+1][j],dp[i][j+1],dp[i+1][j+1]})+1;
ans+=dp[i][j];
}
}
cout<<ans;
return 0;
}F. 小学数学
理解题目之后就知道是二分图最大匹配的板子(大概？
需要一点离散化xd
#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 N=2510,M=7510;
struct edge{
int to;
char oper;
};
vector<edge> g[N];
map<intl,int> disc;
intl val_arr[M];
int match_r[M];
char ans_op[N];
int res_node[N];
bool vis[M];
intl a_arr[N],b_arr[N];
bool dfs(int u){
for(auto &e:g[u]){
int v=e.to;
if(vis[v]) continue;
vis[v]=1;
if(!match_r[v]||dfs(match_r[v])){
match_r[v]=u;
ans_op[u]=e.oper;
res_node[u]=v;
return 1;
}
}
return 0;
}
signed main(){
Cios;
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a_arr[i]>>b_arr[i];
intl val1=a_arr[i]+b_arr[i];
intl val2=a_arr[i]-b_arr[i];
intl val3=a_arr[i]*b_arr[i];
if(!disc.count(val1)){
disc[val1]=++cnt;
val_arr[cnt]=val1;
}
if(!disc.count(val2)){
disc[val2]=++cnt;
val_arr[cnt]=val2;
}
if(!disc.count(val3)){
disc[val3]=++cnt;
val_arr[cnt]=val3;
}
g[i].push_back({disc[val1],'+'});
g[i].push_back({disc[val2],'-'});
g[i].push_back({disc[val3],'*'});
}
int matchc=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(bool)*(cnt+1));
if(dfs(i)) matchc++;
}
if(matchc!=n) cout<<"impossible";
else{
for(int i=1;i<=n;i++) cout<<a_arr[i]<<" "<<ans_op[i]<<" "<<b_arr[i]<<" = "<<val_arr[res_node[i]]<<'\n';
}
return 0;
}
评论（0）
暂无评论