论坛 - CSPOJ
主页
问题
题单
比赛
状态
排名
讨论
常见问答
搜索
登录
注册
讨论
综合
2023CSP-J模拟赛-1-题解
2 条回复
新建讨论
CSPOJ
2023-10-02 18:24:15
## 比赛结束之后公布 ## 欢迎各位同学讨论
加载中...
回复
CSPOJ
2023-10-02 18:46:00
# T1.学习除法 分析: 我们可以把题目缩减一下: `给定一个数n,如果n为质数,输出0;反之,输出它被它因数除成质数的次数。` n是质数的情况,就不多说了,直接判就行。 如果n是合数: 我们如何找到它的因数,把它变成质数呢? 我们知道,一个数由若干个质因子相乘而得,如果提出 n 的一个质因数,那么剩下的质因数乘起来,不也是n的因数吗? 所以,我们用n除以剩下的数,n就会变成质数。 总而言之: 我们只需要判断 n 是不是个质数。 如果是,则输出0,不是,则输出1. ```c++ #include <iostream> using namespace std; int main(){ long long n; cin >> n; for(int i = 2; i <= n / i; i++){ if(n % i == 0){ cout << 1 << endl; return 0; } } cout << 0 << endl; } ``` # T2.拆分(题解一) # 分析: 我们可以拿一个桶来存每个数出现的次数。 如果我们想尽量让mex之和最大,那么我们必须满足不浪费每一个最大的mex 所以,我们每次可以从零开始,往后枚举,每次把当前枚举到的数减一,当枚举到一个为0的数时,跳出本次循环,把答案加上当前这个数。 ```c++ #include<bits/stdc++.h> using namespace std; #define MAXN 100005 int a[MAXN],t[MAXN],n,ans,mx; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*w; } int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(),t[a[i]]++,mx=max(mx,a[i]); while(t[0]){ int temp=1; t[0]--; for(int i=1;i<=mx;i++){ if(!t[i]) break; t[i]--,temp=i+1; } ans+=temp; } printf("%d",ans); return 0; } ``` ## T2 拆分(题解二) 考虑有多少个集合的 mex 可以至少为 1——这些集合必须有一个 0 所以假设 0 有 $x$ 个,那么就说明可以拆出来 $x$ 个集合 mex 至少为 1,此时答案增加 $x$(这一步是考虑这些集合对答案的贡献)。 再考虑有多少个集合的 mex 可以至少为 2——这些集合必须有一个 1,并且 mex 至少为 2 的集合的数量一定小于等于 mex 至少为 1 的集合,所以涉及到一个求 min 的操作。 ```C++ #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int a, cnt[maxn]; int main(){ int n; cin >> n; memset(cnt, 0, sizeof cnt); for(int i = 1; i <= n; i++){ cin >> a; cnt[a]++; } int now = cnt[0], ans = now; for(int i = 1; i <= 1000; i++){ now = min(now, cnt[i]); ans += now; } cout << ans << endl; } ``` ## T3.部落 ### 分析: 1~m: 读题后,我们可以发现: 如果当前i的战力大于i+1的战力,那么i或i+1就必须改变 m~n: 同理,如果i的战力小于i+1的战力,那么i或i+1就必须改变 所以,我们1~m我们需要跑最长不下降子序列,把最大的dp[i]存下来。 m~n,我们要跑最长不上升子序列,也把最大的dp[i]存下来。 最后判断一下m是否被取到两次,用n减去这两次跑出来的最大值,即为答案。 值得一提的是,由于本道题的数据范围较大,所以我们需要用O(nlogn)的做法。 ```c++ #include<bits/stdc++.h> using namespace std; #define MAXN 100005 int a[MAXN],n,m,dp1[MAXN],dp2[MAXN],ans1,ans2,b[MAXN]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*w; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); a[0]=a[n+1]=0x3f3f3f3f; int f[MAXN]={},len=1; f[1]=a[1],dp1[1]=1; for(int i=2;i<=m;i++){ if(f[len]<=a[i]) f[++len]=a[i]; else f[lower_bound(f+1,f+len+1,a[i])-f]=a[i]; dp1[i]=len; } bool fl=0; for(int i=1;i<=m;i++) ans1=max(ans1,dp1[i]); memset(f,0,sizeof(f)); int cnt=0; for(int i=n;i>=m;i--) b[++cnt+m]=a[i];//把a倒过来存 len=1,f[1]=b[m],dp2[m]=1; for(int i=m+1;i<=n;i++){ if(f[len]<=b[i]) f[++len]=b[i]; else f[lower_bound(f+1,f+len+1,b[i])-f]=b[i]; dp2[i]=len; } for(int i=m;i<=n;i++) ans2=max(ans2,dp2[i]); if(ans1==dp1[m]||ans2==dp2[n]) n++;//判断m是否被取两次 printf("%d",n-ans1-ans2); return 0; } ``` ## T4 传递 $dp[i][j][0/1]$ 表示目前 A 青蛙在第 $i$ 个石子,B 青蛙在第 $j$ 个石子,0/1 表示目前哪只青蛙拿跳跃器。 每次转移有 4 种情况,要么 A 青蛙跳跃,要么 B 青蛙跳跃,要么传递跳跃器。 如果这样写 $dp$ 的话,我们会发现 $dp[i][j][0]$ 可以转移到 $dp[i][j][1]$,而 $dp[i][j][1]$ 也可以转移到 $dp[i][j][0]$,不满足无后效性。但本题是一个求 min 的 $dp$,多次求 min 不会出错,所以可以在原地多转移几次,保证对于某一位置 $i,j$,无论第三维是 0 还是 1,都转移到了最优解。 每次跳跃都是跳跃到下一个石子就行,不必跨越多个石子跳跃。因为本题考虑的是最少传递次数,和跳跃次数无关。 ```c++ #include <bits/stdc++.h> using namespace std; const int maxn = 1005; int a[maxn], b[maxn], dp[maxn][maxn][2]; int main(){ int n, m, k, q; cin >> n >> m >> k >> q; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ cin >> b[i]; } a[n+1] = a[n]; b[n+1] = b[n]; memset(dp, 0x3f, sizeof dp); dp[0][0][0] = 0; dp[0][0][1] = 1; for(int step = 0; step <= 2 * n; step++){ for(int j = 0; j <= min(n, step); j++){ int i = step - j; if(i > n) continue; for(int k = 0, r = 0; r <= 3; k++, r++){ // 枚举第三维时,在原地转移 4 次,这样 0 1 都被互相求 min k = r % 2; if(dp[i][j][k] >= 1e9) continue; if(abs(a[i] - b[j]) <= q) dp[i][j][k^1] = min(dp[i][j][k^1], dp[i][j][k] + 1); if(k == 0){ dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]); if(b[j+1] - b[j] <= m){ dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]); } }else{ dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]); if(a[i+1] - a[i] <= m){ dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]); } } } } } cout << min(dp[n][n][0], dp[n][n][1])<< endl; } ```
加载中...
回复
加载中...
加载中...