论坛 - CSPOJ

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;
} 
```

加载中...