「模拟赛」暑期集训CSP提高模拟17(8.10)
虽然赛时打的并不好,但喜欢这次学长出的题。
总结写前面:
-
签到题就是拉开排名的,签到题一般不难,就看想没想到那一步了,确定哪个是签到题之后留出时间来打正解;
-
每道题想了过长时间没有正解思路赶紧打上暴力跳,留时间给签到题,签到题打出来了再去考虑别的题的优化或正解;
-
注意二维背包的写法
-
T4 思路多复习,DP 由于维数过大(但答案很小),于是拿出一维和答案互换,即答案作一维,DP 数组维护原来的一维。
A.符号化方法初探 55pts
因为这个题被拉开分了,构造题,开始先想了 40min,没想到正解,先跳了。后来回来时间不多了,又想了 10min,太着急(当时才打了 T2 、T4 暴力),没再想,直接打了 \(55pts\) 暴力溜了。
部分分:
- \(5pts\):样例 1;
- \(25pts\): 所有数为正数时,维护一个最大值,从 1 到 \(n\) 遍历让所有小于前一个数的数都加上最大值,并更新最大值;
- \(25pts\): \(|a_i| \le 1\) 时,没有 1 则全置为 0,有 1 则全置为 1。
正解:
第二个部分分引导正解。显然,当序列的数全为非负数或全为非正数时每个数最多需要 1 次操作就能满足条件,所以考虑把所有数变为同号。
维护一个最大值 \(max\) 和最小值 \(min\)(记住每次操作之后要更新):
- 当 \(max > -min\) 时,把所有负数都加上 \(max\) 可以使所有数都为非负数;之后按照第二个部分分操作即可;
- 否则,把所有正数加上 \(min\) (肯定为负数)可以使所有书都为非正数,之后从 \(n\) 到 1 让所有大于后一个数的数都加上最小值即可。
code:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, axid, inid, l[N], r[N];
ll a[N], amx, imn = 2e9;
void output(int e){
cout<<e<<"\n";
for(int i=1; i<=e; i++){
cout<<l[i]<<" "<<r[i]<<"\n";
}
}
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
if(amx < a[i]){
amx = a[i], axid = i;
}
if(imn > a[i]){
imn = a[i], inid = i;
}
}
int cnt = 0;
if(amx > -imn){
for(int i=1; i<=n; i++){
if(a[i] >= 0) continue;
a[i] += amx, l[++cnt] = axid, r[cnt] = i;
}
for(int i=1; i<=n; i++){
if(a[i] >= a[i-1]) continue;
a[i] += amx, l[++cnt] = axid, r[cnt] = i;
if(amx < a[i]) amx = a[i], axid = i;
}
output(cnt);
}
else{
for(int i=1; i<=n; i++){
if(a[i] <= 0) continue;
a[i] += imn;
l[++cnt] = inid, r[cnt] = i;
}
a[n+1] = 2e9;
for(int i=n; i>=1; i--){
if(a[i] <= a[i+1]) continue;
a[i] += imn, l[++cnt] = inid, r[cnt] = i;
if(imn > a[i]) imn = a[i], inid = i;
}
output(cnt);
}
return 0;
}
B.无标号 Sequence 构造 50pts
矩阵我刚学一周,对于矩阵的一些性质什么的不是很熟练,导致这个没那么难想的题没想出来,不过情有可原,至少暴力分没挂,不像不争气的 T4(好吧其实是我太菜了)。
部分分:
- \(50pts\) 矩阵乘法 \(n^3\) 暴力。
正解:
我们知道对于矩阵 \(A、B、C、ra\),若 \(A\times B=C\),那么 \(ra\times A\times B=ra\times C\);且 \(1\times n\) 的矩阵与 \(n\times n\) 的矩阵相乘得到 \(1\times n\) 的矩阵。
所以我们构造一个 \(1\times n\) 的矩阵 \(ra\),这样矩阵乘法的时间复杂度就变成了 \(O(1\times n^2)\),可做了。
code:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3005;
const int mod = 998244353;
int T, n, a[N][N], b[N][N], c[N][N];ll ra[N], temp[N];
ll ans1[N], ans2[N];
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<long long> dist(1, 998244353);
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>b[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>c[i][j];
bool f = 1;
for(int i=1; i<=n; i++) ra[i] = dist(rand_num);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
temp[i] = (temp[i] + ra[j] * a[j][i] % mod) % mod;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
ans1[i] = (ans1[i] + temp[j] * b[j][i] % mod) % mod;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
ans2[i] = (ans2[i] + ra[j] * c[j][i] % mod) % mod;
for(int i=1; i<=n; i++){
if(ans1[i] != ans2[i]){f = false; break;}
}
for(int i=1; i<=n; i++) temp[i] = ans1[i] = ans2[i] = 0;
cout<< ( f ? "Yes\n" : "No\n" ) ;
}
return 0;
}
C.无标号 Multiset 构造 5 pts
还未改。
D.有限制的构造 20 pts
赛时打的 \(5+15+20=40 pts\) 暴力,结果二维背包还打锅了,导致得分 \(5+15+0=20pts\)。
部分分:
-
\(5 pts\):样例 1;
-
\(15pts\):对于 \(n=8\) 的数据, 爆搜即可;
-
\(20pts\):对于 \(v\le 100\) 的数据,二维背包 DP。
暴力代码(40pts)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 85;
int n, A, B, a[N], b[N];
namespace case3
{
int f[85][605][605];
int main(){
for(int i=1; i<=n; i++) {
for(int j=0; j<=A; j++){
for(int k=0; k<=B; k++){
f[i][j][k] = f[i-1][j][k];
}
}
for(int j=a[i]; j<=A; j++){
for(int k=b[i]; k<=B; k++){
f[i][j][k] = max({f[i][j][k], f[i-1][j-a[i]][k-b[i]]+1, f[i-1][j][k]});
}
}
}
cout<<( (f[n][A][B]==n) ? n : (f[n][A][B]+1) );
return 0;
}
}
bool vis[N];
int dfs(int x, int cnt, int Aa, int Bb){
if(Aa > A or Bb > B) return cnt;
if(cnt == n) return n;
int ans = 0;
for(int i=1; i<=n; i++){
if(vis[i]) continue;
vis[i] = true;
ans = max(ans, dfs(i, cnt+1, Aa+a[i], Bb+b[i]));
vis[i] = false;
}
return ans;
}
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>A>>B; int v = max(A, B);
for(int i=1; i<=n; i++){
cin>>a[i]>>b[i];
v = max({v, a[i], b[i]});
}
if(n < 12){
cout<<dfs(0, 0, 0, 0);
return 0;
}
if(v <= 600){
return case3::main();
}
return 0;
}
注意二维背包 DP 写法:
因为二维背包的两个条件会存在一个满足另一个不满足的情况,所以看代码。
for(int i=1; i<=n; i++) {
for(int j=0; j<=A; j++){ //注意这一层 j 和 k 的循环范围
for(int k=0; k<=B; k++){
f[i][j][k] = f[i-1][j][k];
}
}
for(int j=a[i]; j<=A; j++){
for(int k=b[i]; k<=B; k++){
f[i][j][k] = max({f[i][j][k], f[i-1][j-a[i]][k-b[i]]+1, f[i-1][j][k]});
}
}
}
正解:
由于答案较小(最多只有 80)而 DP 数组开得过大,考虑把我们二维背包 DP 数组中一维与答案互换位置。
设 \(f_{i,j,k}\) 表示在前 \(i\) 个游戏里选 \(j\) 个,画面质量之和为 \(k\) 时最小的不可玩度之和,接下来怎么做显然了。
DP 状态转移部分的代码:
memset(f, 0x3f, sizeof f);
int ans = 0;
for(int i=0; i<=n; i++) f[i][0][0] = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
for(int k=A; k>=0; k--){
f[i][j][k] = f[i-1][j][k];
// if(f[i][j][k] <= B) ans = max(ans, j);
}
for(int k=A; k>=a[i]; k--){
f[i][j][k] = min(f[i-1][j][k], f[i-1][j-1][k-a[i]]+b[i]);
if(f[i][j][k] <= B) ans = max(ans, j);
}
}
}
code:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 85;
int n, A, B, a[N], b[N];
int f[81][81][10001];
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>A>>B;
for(int i=1; i<=n; i++){
cin>>a[i]>>b[i];
}
memset(f, 0x3f, sizeof f);
int ans = 0;
for(int i=0; i<=n; i++) f[i][0][0] = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
for(int k=A; k>=0; k--){
f[i][j][k] = f[i-1][j][k];
// if(f[i][j][k] <= B) ans = max(ans, j);
}
for(int k=A; k>=a[i]; k--){
f[i][j][k] = min(f[i-1][j][k], f[i-1][j-1][k-a[i]]+b[i]);
if(f[i][j][k] <= B) ans = max(ans, j);
}
}
}
cout<<((ans == n) ? n : ans + 1);
return 0;
}
标签:cnt,int,ll,long,times,amx,表扬,学长
From: https://www.cnblogs.com/YuenYouth/p/18353048