ShanDong Multi-University Training ＃3

目录

C - Easy Problem

G - Optimal Biking Strategy（DP + 二分）

E - Prefix Equality

D - Maximum Value

C - Easy Problem

值得学习的点：

1、数据范围很小，暴力走起来

2、vis开四层vis[][][][]

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 60;
char g[N][N];int n;
bool vis[N][N][N][N];
struct node
{
	int x1, y1;
	int x2, y2;
	int cnt;
};
int xa,xb,ya,yb;
void bfs()
{
	queue<node> q;

	int dx[] = {-1, 1, 0, 0};
	int dy[] = {0, 0, 1, -1};
	q.push({xa, ya, xb, yb, 0});
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		if(t.x1 == t.x2 && t.y1 == t.y2) {
			cout << t.cnt << '\n';
			return;
		}
		for (int i = 0; i < 4; i ++ ) {
			int nx1 = t.x1 + dx[i];
			int ny1 = t.y1 + dy[i];
			int nx2 = t.x2 + dx[i];
			int ny2 = t.y2 + dy[i];
			
			if(nx1 < 1 || nx1 > n)nx1 = t.x1;
			if(nx2 < 1 || nx2 > n)nx2 = t.x2;
			if(ny1 < 1 || ny1 > n)ny1 = t.y1;
			if(ny2 < 1 || ny2 > n)ny2 = t.y2;
			if(g[nx1][ny1] == '*')nx1 = t.x1, ny1 = t.y1;
			if(g[nx2][ny2] == '*')nx2 = t.x2, ny2 = t.y2;

			if(vis[nx1][ny1][nx2][ny2])continue;
			vis[nx1][ny1][nx2][ny2] = 1;
			q.push({nx1, ny1, nx2, ny2, t.cnt + 1});
		}
	}
	cout << "no solution\n";
}

int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 	cin >> n;
 	for (int i = 1; i <= n; i ++ ) {
 		for (int j = 1; j <= n; j ++ ) {
 			cin >> g[i][j];
 			if(g[i][j] == 'a') {
 				xa = i;
 				ya = j;
 			} else if(g[i][j] == 'b') {
 				xb = i;
 				yb = j;
 			}
 		}
 	}   

 	bfs();
	return 0;
}

G - Optimal Biking Strategy（DP + 二分）

 值得学习的点：

• 状态空间定义：花了多少钱，不关心怎么花的。所以brute force过来
• brute force利用了二分，因为有单调性
• 这个题的二分必须写从下标1开始的，直接选择用lowerbound

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int f[N][6];
int a[N];
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, p, s, t;
    cin >> n >> p >> s;
   	for (int i = 1; i <= n; i ++ ) cin >> a[i];
   	cin >> t;

   	for (int i = 0; i < t; i ++ ) f[0][i] = 0;

   	for (int i = 1; i <= n; i ++ )
   		for (int j = 0; j <= t; j ++ ) {
   			f[i][j] = f[i - 1][j] + a[i] - a[i - 1];
   		for (int k = 1; k <= j; k ++ ) {
   				int mx = k * s;
   				int ans = -1;
   				int l = 1, r = i;//下标从1开始不好写
   				while(l <= r) {
   					int mid = (l + r)>>1;
   					if(a[i] - a[mid] < mx) {
   						r = mid - 1;
   						ans = mid;
   					}
   					else if(a[i] - a[mid] == mx) {
   						ans = mid;
   						break;
   					}
   					else l = mid + 1;
   				}
   				if(ans == -1)continue;
   				f[i][j] = min(f[i][j], f[ans][j - k]);
/*

for (int l = 1; l <= j; l ++ ) {
   				int nx = lower_bound(a + 1, a + i, a[i] - l * s) - a;
   				if(nx == i) continue;
   				f[i][j] = min(f[i][j], f[i - nx][j - l]);
   			}*/

   			}
   		}
   	int ans = 0x3f3f3f3f;
   	for (int i = 1; i <= n; i ++ ) {
   		ans = min(ans, f[i][t] + p - a[i]);
   	}
   	cout << ans << '\n';
	return 0;
}

法二：

以后还是用lower_bound和upper_bound。下标可以随时改，红色部分为使用精髓

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int f[N][6];
表示在前i个选择，不超过j元所能骑行的最大长度
int a[N];
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, p, s, t;
    cin >> n >> p >> s;
   	for (int i = 1; i <= n; i ++ ) cin >> a[i];
   	cin >> t;
   	memset(f, 0, sizeof f);
   	for (int i = 1; i <= n; i ++ )
   		for (int j = 0; j <= t; j ++ ) {
   			得有个更新过来的啊，如果下面都不满足等于啥呢？
   			f[i][j] = max(f[i][j], f[i - 1][j]);不花钱
   			for (int l= 1; l <= j; l ++ ) {花点钱
   				int nx = lower_bound(a + 1, a + i, a[i] - l * s) - a;
   				if(nx == i) continue;
   				f[i][j] = max(f[i][j], f[nx][j - l] + a[i] - a[nx]);
   			}
   		}
   	int ans = 0;
   	for (int i = 0; i <= t; i ++ ) {
   		ans = max(ans, f[n][i]);
   	}
   	cout << p - ans << '\n';
	return 0;
}

E - Prefix Equality

题意：给出两段整数序列a,b，接着是q次询问，询问给出两个整数x,y，问a的前x位数字和b的前y位数字种类是否完全相同。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
int a[200010], b[200010];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    std::map<int, int> prea,preb;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if(!prea.count(a[i]))prea[a[i]] = i;
    }
    for (int i = 1; i <= n; i ++ ) {
        cin >> b[i];
        if(!preb.count(b[i]))preb[b[i]] = i;
    }
    std::vector<int> ansa(n + 1, 0), ansb(n + 1, 0);
    for (int i = 1; i <= n; i ++ ) {
        ansa[i] = max(ansa[i - 1], preb.count(a[i]) ? preb[a[i]] : inf);
        ansb[i] = max(ansb[i - 1], prea.count(b[i]) ? prea[b[i]] : inf);   
    }

    int t;
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        cout << ((ansb[y] <= x && ansa[x] <= y) ? "Yes" : "No") << '\n';
    }   
    return 0;
}

哈希。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll a[200010], b[200010];
set<ll> se;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    ll s = 0;
    for (int i = 1; i <= n; i ++ ) {
        ll x;
        cin >> x;
        if(se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        a[i] = s;
        se.insert(x);
    }
    se.clear();
    s = 0;
    for (int i = 1; i <= n; i ++ ) {
        ll x;
        cin >> x;
        if(se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        b[i] = s;
        se.insert(x);
    }
    int t;
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        if(a[x] == b[y]) {
            cout << "Yes\n";
        }
        else cout << "No\n";
    }   
    return 0;
}

 数量数组，前缀积，前缀和。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 250000;
const int mod = 1E9 + 7;
int x,n;
ll mul1[N], mul2[N];
ll sum1[N], sum2[N];
ll num1[N], num2[N];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    cin >> n;
    set<ll> s;
    mul1[0] = mul2[0] = 1;

    for (int i = 1; i <= n; i ++ ) {
        cin >> x;
        mul1[i] = mul1[i - 1];
        sum1[i] = sum1[i - 1];
        num1[i] = num1[i - 1];
        if(s.find(x) == s.end()) {
            s.insert(x);
            sum1[i] += x;
            mul1[i] = (mul1[i] * x) % mod;
            num1[i] ++;
        }
    }
    s.clear();
    for (int i = 1; i <= n; i ++ ) {
        cin >> x;
        mul2[i] = mul2[i - 1];
        sum2[i] = sum2[i - 1];
        num2[i] = num2[i - 1];
        if(s.find(x) == s.end()) {
            s.insert(x);
            sum2[i] += x;
            mul2[i] = (mul2[i] * x) % mod;
            num2[i] ++;
        }
        
    }
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        if(mul1[x] == mul2[y] && sum1[x] == sum2[y] && num1[x] == num2[y])
            cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

D - Maximum Value

题意就是求ai%aj的最大值，其中ai要大于等于aj，那先保证序列有序的情况下，如果直接遍历会TLE，这里考虑二分找最大可能值，可知ai大于等于aj，那么ai=n*aj+mod，因此，最大可能值一定出现在n倍和n+1倍之间最后一个值，直接lower_bound二分得到n+1倍的第一个值，它的前一个就是要找的最大可能值

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int a[2000100];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    n = unique(a, a + n) - a;
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
            int x = lower_bound(a, a + n, 2 * a[i]) - a;
            for (int j = 2; j * a[i] <= a[n - 1]; j++) {
                x = lower_bound(a, a + n, j * a[i]) - a;
                ans = max(ans, a[x - 1] % a[i]);
            }
            ans = max(ans, a[n - 1] % a[i]);
            ans = max(ans, a[x - 1] % a[i]);
    }
    cout << ans << '\n';
    
    return 0;
}