cf815 div2 (A题fst的一场)
下述题目中默认n为10^5级别，n*m为10^5-10^6级别，整数范围10^9级别。
A
题意：有两个分数a/b,c/d,我们一次操作可以给a,b,c,d乘上任意数(b,d不可以乘0),问最少多少次操作两个分数相等。
思路：两个分数相等即a*d=b*c，同时可以注意到我们可以给a和c都乘0，因此必然操作数最多为2。接下来只需要判断什么时候为0，1，2即可。
- 0：显然a*d=b*c时就是0
- 1：只需要1次操作，说明我们只能乘1次，便使得a*d=b*c。假如乘的数是k,那么最开始就有a*d = k*b*c或者b*c=k*a*d。
- 2：剩余的情况显然就是2次
碎碎念：A题判断1次的时候我写的是a*d/b%c==0||b*c/a%d==0，蠢蠢牛马了属于是。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=100005;
void solve(){
ll a,b,c,d;
cin >> a >> b >> c >> d;
a*=d;b*=c;
if(a==b) puts("0");
else if(a==0||b==0||a%b==0||b%a==0) puts("1");
else puts("2");
}
int main(){
int tt;
cin >> tt;
while (tt--){
solve();
}
return 0;
}
|
B
题意：给定有n个数的a数组，计算a数组的所有子串(连续的一段)中的最大beauty值。beauty值的定义为：max(a1,a2,…,al−1,ar+1,ar+2,…,an)−min(a1,a2,…,al−1,ar+1,ar+2,…,an)+max(al,…,ar)−min(al,…,ar).
其中al-ar为a数组的子串。
思路：读完题意第一反应就是选出数组中的第一大和第二大，还有第一小和第二小，这样一定是最优的，但是能不能保证一定能选到呢，经过分析可知，这四个数是一定可以选到的。
由上述思路，我们设这四个数的位置是i,j,m,n。无论他们相对位置如何，我们总可以选出一个子串包含一个大的(第一大或者第二大)，和一个小的(第一小或者第二小)。因为我们可以先选一个大的(两个中选一个)，再将范围向左或者向右延申，由于只剩下另外一个大的，所以两边一定有一边可以延申到小的，然后就停在这，这即为选出的子串。
考虑子串中的大小，显然我们为子串选的那个大的和小的，分别是这个子串的极大值和极小值。(因为就算有更大的和更小的也在子串外)。对于子串外的那部分同理，所以这四个数是一定可以选到的。
综上beauty值就是a数组从小到大排序后的a[n]+a[n-1]-a[1]-a[2]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=100005;
int a[maxn];
void solve(){
int n;
cin >> n;
rep(i,1,n){
cin >> a[i];
}
sort(a+1,a+n+1);
cout << a[n]+a[n-1]-a[1]-a[2] << '\n';
}
int main(){
int tt;
cin >> tt;
while (tt--){
solve();
}
return 0;
}
|
C
题意：给定n*m的矩阵，每个格子是1或者0。每次操作可以选定一个L型区域(2*2矩阵去掉一个格子)，并且要求里面要有1，那么我们这次操作会将里面的1全部变成0，问最多我们能操作多少次。
思路：这题问的是最多，那么显然每个1都要倾尽其力(警觉×)，一般这种矩阵题思路要么就dfs或者从小的块入手。dfs的话我们没有什么入手点，因为从开头dfs不一定最优，所以我们考虑从一些小的格子找入手点。
我们注意到当两个0能出现在一个L型中时(即相邻或者对角)，选中一个包含这两个0和一个1的L型，会使得这个1最大化的利用了，同时这个1会在这次操作中变成0。因此我们又得到了新的满足条件的两个0。显然这个过程是不会中断的，因此只要我们初始化有两个相邻或对角的0，便可以使得这里面的1都被最大化的利用。即操作数opt=cnt1(矩阵中1的个数)。而开局这样的0的时候，我们大概率要开一组两个1的L型，即浪费了一次，因此opt=cnt1-1。
另外注意特判全是1的情况:这个开局会直接3个1的L型，浪费两个1，opt=cnt1-2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=100005;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
void solve(){
int n,m,cnt0=0,ok=0;
string s[505];
cin >> n >> m;
rep(i,0,n-1){
cin >> s[i];
}
rep(i,0,n-1){
rep(j,0,m-1){
if(s[i][j]=='0'){
cnt0++;
if(ok==0){
rep(k,0,7){
int ii=i+dir[k][0];
int jj=j+dir[k][1];
if(ii>=0&&ii<=n-1&&jj>=0&&jj<=m-1){
if(s[ii][jj]=='0') ok=1;
}
}
}
}
}
}
if(cnt0==n*m) cout << 0 << '\n';
else if(ok==0&&cnt0!=0) cout << n*m-cnt0-1 << '\n';
else if(ok==0&&cnt0==0) cout << n*m-cnt0-2 << '\n';
else cout << n*m-cnt0 << '\n';
}
int main(){
int tt;
cin >> tt;
while (tt--){
solve();
}
return 0;
}
|
D1
题意：给定有n个数的a数组，从中选出一个子序列b，这里b中的数是下标数，如选出a1,a2,a4，则b中为[1,2,4]。设b数组有m个数，若对于任意0<=i<m-1，有a[b[i]]^b[i+1]<a[b[i+1]]^b[i]，则该序列叫做美丽的。求最长的美丽子序列的长度。
a[i]<=200
思路：求最长子序列，显然是dp。但是显然dp的复杂度是n^2。主要时间浪费在为每个i寻找匹配的j的地方，因此我们结合给定条件考虑可不可以缩小范围选j。
D1给定的特殊条件为a[i]<=200，这就保证了每次b[i+1](其实是一个下标)和a[b[i]](这才是a数组中的数)异或时，我们对b[i+1]的改变不会超过256。因为a[i]<=200，即它最多只有8位，因此异或最多只会改变b[i+1]的后八位。因此当b[i+1]-b[i]>256的时候，这个条件显然不成立(因为不管异或的怎么样，后8位之前的那些数b[i+1]要大于b[i])。因此我们每次为i找匹配的j时，从max(0,i-256)开始匹配就可以。剩下就是标准的最长子序列dp做法了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=300005;
int a[maxn];
void solve(){
int n;
cin >> n;
rep(i,0,n-1){
scanf("%d",&a[i]);
}
vi dp(n+5,1);
rep(i,1,n-1){
rep(j,max(0,i-256),i-1){
if((a[j]^i)<(a[i]^j)){
dp[i]=max(dp[j]+1,dp[i]);
}
}
}
int ans=0;
rep(i,1,n){
ans=max(ans,dp[i]);
}
cout << ans << '\n';
}
int main(){
int tt;
cin >> tt;
while (tt--){
solve();
}
return 0;
}
|
