| T1 | T2 | T3 | T4 |
|---|---|---|---|
| \(\color{#FFC116} 普及/提高-\) | < | \(\color{#52C41A} 普及+/提高\) | < |
参赛网址：https://oj.33dai.cn/d/TYOI/contest/68a45437c5d9c2f14c27494d
为数不多的普及组比赛，祝你 AK ，今年争取普及组人人高分
T1 钻石【CSPJ2025模拟赛T1】
题目传送门
题目难度：\(\color{#FFC116} 普及/提高-\)
算法标签：模拟
原题链接
对标CSP-J T3
思路
这题一眼就是一个大模拟。
枚举顶点，然后暴力确认。
AC Code
#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2005;
int n,m;
int cnt;
int mp[maxn][maxn];void bfs(int x,int y){int xx=x,i=0;int flag=0;while (xx<=n){flag=0;if (mp[xx][y-i]==0||mp[xx][y+i]==0) flag=1;for (int j=y-i+1;j<=y+i-1;j++)if (mp[xx][j]==1)flag=1;if (flag) break;xx++;i++;}if (xx>n&&flag==0) return ;xx--;i--;if (i==0) return ;while (xx<=n){if (mp[xx][y-i]==0||mp[xx][y+i]==0) return ;for (int j=y-i+1;j<=y+i-1;j++)if (mp[xx][j]==1)return ;xx++;i--;if (i==-1) break;}if (xx>n&&i!=-1) return ;cnt++;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);freopen("diamond.in","r",stdin);freopen("diamond.out","w",stdout);cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){char c;cin>>c;if (c=='#') mp[i][j]=1;else mp[i][j]=0;}}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (mp[i][j])bfs(i,j);cout<<cnt;return 0;
}T2 军训【CSPJ2025模拟赛T2】
题目传送门
题目难度：\(\color{#FFC116} 普及/提高-\)
算法标签：贪心，二分
思路
我们发现，他求的是最小值中的最大值，明显的二分答案，二分的枚举答案。
然后考虑验证，我们一定是将所有速度的大于等于 \(mid\) 的人背剩下的人，并且保证背后所有的人的速度都依旧大于等于 \(mid\)。
-
如果队员 \(i\) 背着队员 \(j\) 时，如果队员 \(i\) 的体重大于等于队员 \(j\)，则队员 \(i\) 的移动速度不会变化，仍然为 \(v_i\)
-
如果队员 \(i\) 的体重小于队员 \(j\)，则队员 \(i\) 的移动速度会减去两者的体重差值，即变为 \(v_i-(w_j-w_i)\)。
-
如果队员 \(i\) 的移动速度将变为负数，则队员
\(i\) 无法背起队员 \(j\)。
所以 队员 \(i\) 能背着队员 \(j\) 时，他的速度是 \(v_i-\max(w_j-w_i,0)\)，又因为我们刚才推出（我们一定是将所有速度的大于等于 \(mid\) 的人背剩下的人），\(v_i \ge mid\)，所以 如果 \(\max(w_j-w_i,0)=0\)，则 \(v_i\) 和 \(v_i-\max(w_j-w_i)\) 都大于等于 \(mid\)，对答案没有影响。
我们就把式子化为 \(v_i-(w_j-w_i) \ge mid\)。
对于每一次 \(\text {check}\)，维护一个数组 \(t\) 表示所有 \(v_i \ge mid\)，的 \(v_i+w_i\)，然后排序。
然后对于每一个 \(v_i < mid\)，二分找到最小的满足 \(v_i-(w_j-w_i) \ge mid\) 的位置。
那么从找到的位置到 \(t\) 数组的最后一个，都可以背 \(i\)，然后我们可以差分，对于任意一个 \(i\)，如果在 \(t\) 的末尾到 \(i\) 的这些人中，需要背的人数大于他的区间（\(t\) 的末尾到 \(i\)）的人数，则无法达到。
AC Code
#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=1e5+5;
int T;
int n;
int cnt,t[maxn];
int d[maxn];
struct node{int v,w;friend bool operator < (const node &x,const node &y){if (x.v==y.v) return x.w<y.w;return x.v<y.v;}
}a[maxn];int check(int mid){cnt=0;for (int i=1;i<=n;i++){d[i]=0;if (a[i].v<mid) continue;t[++cnt]=a[i].v+a[i].w;}sort(t+1,t+cnt+1);for (int i=1;i<=n;i++){if (a[i].v>=mid) break;int pos=lower_bound(t+1,t+cnt+1,a[i].w+mid)-t;if (pos>cnt) return 0;d[pos]++;}for (int i=cnt;i>=1;i--) d[i]+=d[i+1];for (int i=1;i<=cnt;i++){if (d[i]>cnt-i+1){return 0;}}return 1;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);freopen("training.in","r",stdin);freopen("training.out","w",stdout);cin>>T;while (T--){int l=1,r=0,ans=0;cin>>n;for (int i=1;i<=n;i++) cin>>a[i].v>>a[i].w,r=max(r,a[i].v);sort(a+1,a+n+1);while (l<=r){int mid=((l+r)>>1);if (check(mid)){ans=mid;l=mid+1;}else r=mid-1;}cout<<ans<<"\n";}return 0;
}/*
i a[i].v<mid
->
j a[j].v+a[j].w>=mid+a[i].w
j a[j].v>=mid
*/
T3 机器人捡硬币【CSPJ2025模拟赛T3】
题目传送门
题目难度：\(\color{#52C41A} 普及+/提高\)
算法标签：动态规划，LIS，其他，构造，SPJ
思路
AC Code
#include <bits/stdc++.h>
using namespace std;const int maxn=2e5+5;
int n,m,k;
int pre[maxn],id[maxn];
int len,dp[maxn];
struct pos{int x,y;int id;friend bool operator < (const pos &x,const pos &y){if (x.x==y.x) return x.y<y.y;return x.x<y.x;}
}a[maxn];void print(int x){if (x==1) return ;print(pre[x]);for (int i=1;i<=a[x].x-a[pre[x]].x;i++) cout<<"D";for (int i=1;i<=a[x].y-a[pre[x]].y;i++) cout<<"R";
}int main(){ios::sync_with_stdio(false);cin.tie(0);freopen("robot.in","r",stdin);freopen("robot.out","w",stdout);cin>>n>>m>>k;for (int i=1;i<=k;i++)cin>>a[i].x>>a[i].y;int op;cin>>op;a[k+1]={1,1,0};a[k+2]={n,m,k+1};k+=2;sort(a+1,a+k+1);for (int i=1;i<=k;i++){if (i==1||a[i].y>=dp[len]){dp[++len]=a[i].y;pre[i]=id[len-1];id[len]=i;}else {int p=upper_bound(dp+1,dp+len+1,a[i].y)-dp;pre[i]=id[p-1];id[p]=i;dp[p]=a[i].y;}}cout<<len-2<<"\n";if (op==2) print(k);return 0;
}
T4 相似字符串【CSPJ2025模拟赛T4】
题目传送门
题目难度：\(\color{#52C41A} 普及+/提高\)
算法标签：Dp，计数dp
思路
我们发现数据范围，\(1 \le n \le 2\times 10^3,0 \le k \le 2\times 10^3\)
一眼就是Dp
为什么我想不出来QAQ
考虑将每一次输入的字符串排序，将同样的字符归类，然后考虑 \(dp_{i,j}\)
AC Code
#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2e3+5;
const int mod=1e9+7;
int n,k;
int cnt;
int a[maxn];
int c[maxn][maxn];
int dp[maxn][maxn];
string s;
map<string,int> M;void add(int &x,int y){x=(x+y)%mod;}signed main(){ios::sync_with_stdio(false);cin.tie(0);freopen("string.in","r",stdin);freopen("string.out","w",stdout);cin>>n>>k;for (int i=1;i<=n;i++){cin>>s;sort(s.begin(),s.end());if (M[s]==0) M[s]=++cnt;a[M[s]]++;}c[0][0]=1;for (int i=1;i<=n;i++){c[i][0]=1;for (int j=1;j<=i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}dp[0][0]=1;for (int i=1;i<=cnt;i++){for (int j=0;j<=k;j++){for (int l=0;l<=a[i];l++){if (j+l*(l-1)/2>k) break;add(dp[i][j+l*(l-1)/2],dp[i-1][j]*c[a[i]][l]%mod);}}}cout<<dp[cnt][k];return 0;
}