主頁 >  其他 > 【比賽】2021牛客寒假演算法基礎集訓營4 題解 【C題不肝了T^T】

【比賽】2021牛客寒假演算法基礎集訓營4 題解 【C題不肝了T^T】

2021-02-21 16:38:54 其他

比賽鏈接

點擊此處進入比賽

A 九峰與簽到題

簽到題
不多說，直接上代碼

AC代碼

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % 1000000007
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 20 + 10;
bool vis[N];
int st[N];

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	
	int n, m;
	cin >> m >> n;

	while (m--)
	{
		int t;
		string op;
		cin >> t >> op;
		if (op == "AC") st[t]++;
		else st[t]--;

		if (st[t] < 0) vis[t] = true;
	}

	_rep(i, 1, n) if (!vis[i]) cout << i << " ";
	cout << endl;
	
	return 0;
}

B 武辰延的字串

這個題目在比賽的時候做了我好久，就是那種感覺可以做出來，但是就是做不出來的那種感覺，
實際上還差很遠，錯因： 模擬的時候沒有經過嚴格的證明，資料點沒找出來，隨意的給運行剪枝，導致答案不對，
對于資料點沒找出來這個問題，需要在看題的時候將所有限制條件列出來，然后給自己出各種情況的資料點，這個能力有待提高！

這個題目考點就是字串哈希 + 二分，
對于匹配字串好用的就是字串哈希或者KMP了，這個題目范圍有點大，所以個人偏向于哈希，感覺快一些，
對于公式 ： s i + s j = t i + j s_i + s_j = t_{i + j} si?+sj?=ti+j? 如果兩邊的前綴 s i s_i si?相同的話，那么可以同時減去 s i s_i si?，那么剩下來的就是我們需要的答案了，有多長就代表在以 s i s_i si?為前綴的情況下的所有結果，
接下來就是求最大匹配長度的問題了，看到最大，然可以根據字串哈希值比較大小條件可以劃分為兩個不同的部分，這時候我們就要想到二分了，
如果兩邊的字串哈希值是一樣的，那么就說明還可以往右邊取，如果不一樣就說明要往左邊移動，

			主要是沒有想到將公式變形一下找到相同的，就直接模擬了，模擬前也沒有好好分析題目， 這個毛病要改！！！

AC代碼

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % 1000000007
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;

const int N = 100000 + 10, P = 131;
ull ha[N], hb[N], p[N];
char a[N], b[N];
int sza, szb;
unordered_map<ll, bool> vis;

ull get(int l, int r, ull h[])
{
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> a + 1 >> b + 1;
	sza = strlen(a + 1), szb = strlen(b + 1);

	p[0] = 1;
	int n = max(sza, szb), m = min(sza, szb);
	_rep(i, 1, n)
	{
		if (sza <= n) ha[i] = ha[i - 1] * P + a[i];
		if (szb <= n) hb[i] = hb[i - 1] * P + b[i];
		p[i] = p[i - 1] * P;
	}

	ll ans = 0;
	_rep(i, 1, m) if (get(1, i, ha) == get(1, i, hb))
	{
		int l = 0, r = min(sza, szb - i);
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (get(1, mid, ha) == get(i + 1, mid + i, hb)) l = mid;
			else r = mid - 1;
		}
		ans += l;
	}
	cout << ans << endl;
	return 0;
}

D 溫澈瀅的狗狗

這個題目看了我好久，，（主要是太菜了）
做題的時候想到了用二分，但是不知道怎么去定義它的性質，
兩兩不同顏色的狗之間會產生親密度，對每一對有親密度的狗按照關鍵詞進行排序，求第k對狗的下標，
如果模擬的話肯定會超時，所以要往快速找到第k對狗的方向想，會想到使用二分思想，
想到用二分思想就要想能不能找到一個能夠二分的條件，
第一關鍵詞是按照親密度去的，所以想想能不能以親密度去劃分，
我們假設第k對的親密度為x，那么就說明 > x > x >x 的部分是不需要的，所以就有明顯的二分性，

知道了以親密度作為判斷條件，那么接下來的步驟就是完善細節，計算每個 ≤ x \leq x ≤x親密度的個數，
只有顏色不同才會有親密度，直接求有點麻煩，時間復雜度也會比較高，直接求不行，那么就試試間接的求法：
異 色 點 對 數 = 總 點 對 數 ? 同 色 點 對 數 （ O ( n ) ） 異色點對數=總點對數-同色點對數 （O(n)） 異色點對數=總點對數?同色點對數（O(n)）

設x為親密度，我們將同色點都放到同一個下標的陣列中，
總點對數 ： ( n ? x ) ? x + x ? ( x ? 1 ) / 2 (n - x) * x + x * (x - 1) / 2 (n?x)?x+x?(x?1)/2
我們知道親密度了，（親密度是下標距離）那么從下標1開始到(n - x) 分別做區間，每個區間都可以取x個數與區間第一個點形成對，有（n - x ）個區間，所以就為 ( n ? x ) ? x (n - x) * x (n?x)?x, 后部磁區間不能延長了，到達總下標的末端了，所以可取值分別為 x ? 1 、 x ? 2 、 x ? 3 … … x ? ( x ? 1 ) x - 1、x - 2、x - 3……x - (x - 1) x?1、x?2、x?3……x?(x?1),等引數列求和就得出了 x ? ( x ? 1 ) / 2 x * (x - 1) / 2 x?(x?1)/2 ，
同色點數利用雙指標求解即可（這個不知道怎么用語言講，待會看代碼吧，）

二分具體條件出來了，那么就可以求出來最大親密度為 l l l 總對數小于 k k k 的 l l l值，
所以第k對狗的親密度為 l + 1 l + 1 l+1，
親密度知道了，直接for回圈找即可，

AC 代碼

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
int c[N], n;
ll k;
vi same[N];

ll cal(ll x)
{
	ll tot = (n - x) * x + x * (x - 1) / 2;
	_rep(i, 1, n)
	{
		int r = 0, sz = same[i].size();
		_for (j, 0, sz)
		{
			while (r < sz && same[i][r] - same[i][j] <= x) ++r;
			tot -= r - j - 1;
		}
	}
	return tot;
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	
	cin >> n >> k;
	_rep(i, 1, n)
	{
		cin >> c[i];
		same[c[i]].push_back(i);
	}

	if (cal(n) < k) return puts("-1"), 0;

	int l = 0, r = n;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (cal(mid) < k) l = mid;
		else r = mid - 1;
	}

	int dist = l + 1;
	ll cnt = cal(l);
	_rep(i, 1, n - dist) if (c[i] != c[i + dist])
	{
		cnt++;
		if (cnt == k)
		{
			cout << i << " " << i + dist << endl;
			break;
		}
	}
	
	return 0;
}

E 九峰與子序列

很明顯的動態規劃題目，但是我就是想不到，我想到以子序列為dp的目標，但是沒有想到以字串k為dp目標，

							多嘗試不同的條件，說不定就能碰出火花，不能懶！

記住，動態規劃不是一步就達到答案的，是一步一步轉化之后才到達答案的，
f [ i ] [ j ] f[i][j] f[i][j]表示前i個定序列匹配到字串k第j位的所有合法方案， 所以分為取和不取兩種選擇，這就類似于01背包了，但是比01背包多了一個點就是取之前需要判斷它是否能拼接成字串k，

所以狀態轉移方程為 ：
f [ i ] [ j ] = f [ i ? 1 ] [ j ? l e n [ i ] ] ? c h e c k ( h a [ j ] , j ? l e n [ i ] + 1 , j ) + f [ i ? 1 ] [ j ] f[i][j] = f[i - 1][j - len[i]] * check(ha[j], j - len[i] +1, j) + f[i - 1][j] f[i][j]=f[i?1][j?len[i]]?check(ha[j],j?len[i]+1,j)+f[i?1][j]
利用滾動陣列，將狀態轉移方程進一步轉化為 ：
f [ j ] = f [ j ? l e n [ i ] ] ? c h e c k ( h a [ i ] , j ? l e n [ i ] + 1 , j ) + f [ j ] f[j] = f[j - len[i]] * check(ha[i], j - len[i] +1, j) + f[j] f[j]=f[j?len[i]]?check(ha[i],j?len[i]+1,j)+f[j]
使用之前的值，所以別忘記了是逆序遍歷，

AC代碼

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % 1000000007
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 5000000 + 10, P = 131, M = 50;
ull p[N], h[N], ha[M];
ll f[N];
int n, len[M];
char k[N], a[M][N];

bool check(ull hash, int l, int r)
{
	return hash == h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> n >> k + 1;

	int sz = strlen(k + 1);
	p[0] = 1;
	_rep(i, 1, 5e6) {
		p[i] = p[i - 1] * P;
		if (i <= sz) h[i] = h[i - 1] * P + k[i];
	}

	_rep(i, 1, n)
	{
		cin >> a[i] + 1;
		len[i] = strlen(a[i] + 1);
		_rep(j, 1, len[i]) ha[i] = ha[i] * P + a[i][j];
	}

	f[0] = 1;
	_rep(i, 1, n) For(j, sz, len[i]) f[j] += f[j - len[i]] * check(ha[i], j - len[i] + 1, j);
	cout << f[sz] << endl;
	return 0;
}

F 魏遲燕的自走棋

這個題目就差一點點就做出來了，太遺憾了，我只是將權值排序了，但是沒有將他的下標所連接的點做出改變，
對匈牙利演算法還不夠熟練！

										審題很重要，重視！

AC 代碼

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % 1000000007
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
int match[N];
int n, m;
int st[N];

struct Node
{
	int k, a[3], w;

	bool operator < (const Node& t) const
	{
		return w > t.w;
	}
}alls[N];

bool find(int x)
{
	_for (i, 0, alls[x].k)
	{
		int j = alls[x].a[i];
		if (!st[j])
		{
			st[j] = true;
			if (match[j] == 0 || find(match[j]))
			{
				match[j] = x;
				st[j] = false;
				return true;
			}
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	
	cin >> n >> m;
	_rep(i, 1, m)
	{
		cin >> alls[i].k;
		_for(j, 0, alls[i].k) cin >> alls[i].a[j];
		cin >> alls[i].w;
	}

	sort(alls + 1, alls + m + 1);
	_rep(i, 1, m) find(i);

	ll ans = 0;
	_rep(i, 1, n) if (match[i]) ans += alls[match[i]].w;
		
	cout << ans << endl;
	return 0;
}

G 九峰與蛇形填數

這個題目直接暴力就可以了，不需要用啥線段樹，
每個點每次取值肯定是最后一個覆寫到它區域的值，所以直接取那個數即可，
然后還有一個細節就是剪枝，預處理區域的大小，如果這個點不在這個區域直接break，不用賦值了，

AC代碼 （有bug）

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 3000 + 10, M = 2010, INF = 0x3f3f3f3f;
int n, m;
int x[N], y[N], k[N],g[M][M];

bool inside(int t, int a, int b)
{
	return a <= t && t <= b;
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> n >> m;
	int x1 = INF, y1 = INF, x2 = 0, y2 = 0;
	_rep(i, 1, m)
	{
		cin >> x[i] >> y[i] >> k[i];
		x1 = min(x1, x[i]);
		y1 = min(y1, y[i]);
		x2 = max(x2, x[i] + k[i] - 1);
		y2 = max(y2, y[i] + k[i] - 1);
	}
		
	_rep(i, 1, n) _rep(j, 1, n) For(l, m, 1)
	{
		if (!inside(i, x1, x2) || !inside(j, y1, y2)) break;
		if (inside(i, x[l], x[l] + k[l] - 1) && inside(j, y[l], y[l] + k[l] - 1))
		{
			g[i][j] = k[l] * (i - x[l]);
			if (i - x[l] & 1) g[i][j] += y[l] + k[l] - j;
			else g[i][j] += j - y[l] + 1;
			break;
		}
	}

	_rep(i, 1, n) _rep(j, 1, n) printf("%d%s", g[i][j], j == n ? "\n" : " ");
	
	return 0;
}

----------------------------------------------------------2020、2、20---------------------------------------------------------------------
慘遭hack！還是老老實實用正規做法做吧！后面補上正規做法，感謝榜一大佬及時提醒！
在這里插入圖片描述
看完線段樹的題解之后感覺并沒有想象中的那么難，都是圍繞著取某個點最后一次覆寫做優化，
這里建議使用線段樹求解，雖然雨巨說這個寫法有點毛病，但是標算就是用線段樹，出題人的意思就是讓我們鞏固一下線段樹知識，寫的每一個題總得有反思和提高，如果投機取巧，使用的還是以前會的東西，那這個題目對于你來說意義不大，

核心：找到每個點最后一次被覆寫的矩陣下標，
對于需要快速的對區間或者點的修改查詢的題，我們就要想到線段樹之類的知識點，
因為是矩陣，所以要用二維去維護，

維護的是每個點最后一次被覆寫的矩陣下標，每次都修改肯定是超時的，所以需要使用懶標記，

線段樹的變形感覺有好多，現在又看到一種，，

AC代碼 （標算）

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2000 + 10, M = 3010;
int n, m;

struct Node
{
	struct point
	{
		int l, r, lz;
	}tr[N << 2];

	void push_down(int u){
		auto& t = tr[u];
		if (t.lz)
		{
			tr[u << 1].lz = t.lz;
			tr[u << 1 | 1].lz = t.lz;
			t.lz = 0;
		}
	}

	void build(int u, int l, int r)  
	{
		tr[u] = { l, r, 0 };
		if (l != r)
		{
			int mid = l + r >> 1;
			build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		}
	}

	void modify(int u, int l, int r, int k)
	{
		auto& t = tr[u];
		if (l <= t.l && t.r <= r) t.lz = k;
		else
		{
			int mid = t.l + t.r >> 1;
			push_down(u);
			if (r <= mid) modify(u << 1, l, r, k);
			else if (l > mid) modify(u << 1 | 1, l, r, k);
			else modify(u << 1, l, mid, k), modify(u << 1 | 1, mid + 1, r, k);
		}
	}

	int query(int u, int l)
	{
		auto& t = tr[u];
		if (t.l == t.r) return t.lz;
		int mid = t.l + t.r >> 1;
		push_down(u);
		if (l <= mid) return query(u << 1, l);
		return query(u << 1 | 1, l);
	}
}g[N];

struct Mat
{
	int x, y, k;
}mat[M];

int cal(int x, int y, int k, int i, int j)
{
	if (i - x & 1) return k * (i - x) + y + k - j;
	return k * (i - x) + j - y + 1;
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	
	cin >> n >> m;
	_rep(i, 1, n) g[i].build(1, 1, n);
	_rep(i, 1, m) {
		cin >> mat[i].x >> mat[i].y >> mat[i].k;
		_rep(j, mat[i].x, mat[i].x + mat[i].k - 1)
			g[j].modify(1, mat[i].y, mat[i].y + mat[i].k - 1, i);
	}
	
	_rep(i, 1, n) _rep(j, 1, n)
	{
		int v = g[i].query(1, j);
		if (!v) cout << 0;
		else
		{
			auto& t = mat[v];
			cout << cal(t.x, t.y, t.k, i, j);
		}
		cout << (j == n ? "\n" : " ");
	}
	
	return 0;
}

H 吳楚月的運算式

這個題目只要把dfs的引數搞清楚了，就差不多了，

我們對運算進行分析可以發現，只要對前一個數進行優先級運算就可以了：

  • + : ( a + b ) + w [ j ] +: ( a + b) + w[j] +:(a+b)+w[j]
  • ? : ( a + b ) ? w [ j ] -: ( a + b) - w[j] ?:(a+b)?w[j]
  • ? : a + b ? w [ j ] * : a + b * w[j] ?:a+b?w[j]
  • / : a + b ? w [ j ] ? 1 /: a + b * w[j]^{-1} /:a+b?w[j]?1

因為是從根節點出發，所以只需要三個變數 a 、 b 、 v a、b、v a、b、v就可以了， v v v記錄當前位置，

AC代碼

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10, MOD = 1e9 + 7;
int n, w[N], fa[N], h[N], ne[N], e[N], idx;
ll ans[N];
char op[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

ll qmi(int a, int b)
{
	ll res = 1, t = a;	
	while (b)
	{
		if (b & 1) res = mod(res * t);
		t = mod(t * t);
		b >>= 1;
	}
	return res;
}

void dfs(ll a, ll b, int v)
{
	ans[v] = mod(a + b);
	for (int i = h[v]; ~i; i = ne[i])
	{
		int j = e[i];
		switch (op[j])
		{
		case '+':
			dfs(a + b, w[j], j);
			break;
		case '-':
			dfs(a + b, MOD - w[j], j);
			break;
		case '*':
			dfs(a, mod(b * w[j]), j);
			break;
		default:
			dfs(a, mod(b * qmi(w[j], MOD - 2)), j);
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	memset(h, -1, sizeof h);
	cin >> n;
	_rep(i, 1, n) cin >> w[i];
	add(0, 1);
	_rep(i, 2, n) cin >> fa[i], add(fa[i], i);
	cin >> op + 2;
	op[1] = '+';

	dfs(0, 0, 0);

	_rep(i, 1, n) cout << ans[i] << " ";
	cout << endl;
	
	return 0;
}

I 九峰與分割序列

這個題目也太難了吧😭😭😭
感謝溢流眼淚大佬寫的博客，看了好久終于看懂了，

真沒想到DP還可以這么玩，學到了學到了，，，
求一種分割方法使得所有子區間的貢獻之和最大，我們設 d p [ i ] dp[i] dp[i]為到 i i i為止所有子區間的最大貢獻和， f [ i ] f[i] f[i]為到 i i i為止最后最后一段區間長度大于k的所有貢獻之和，

那么就會有動態轉移方程：
d p ( i ) = m a x { d p ( i ? 1 ) + a i 2 ? S ( j , i ) + f ( j ? 1 ) ( i ? j + 1 ≤ k ) dp(i) = max \begin{cases} dp(i - 1) + a_i \\ 2 * S(j, i) + f(j - 1) & (i - j +1 \leq k) \end{cases} dp(i)=max{dp(i?1)+ai?2?S(j,i)+f(j?1)?(i?j+1≤k)?
上部分為不分割，因為只是加一倍的原來的那段區間和，那么它的值也就是相當于當前的值加上前面那一段，下部分為符合分割條件可以分割，就是取可以分割的區間乘以2加上前面那一段，
f [ i ] f[i] f[i]的狀態轉移好理解，就是讓后面k + 1個數取一倍，剩下的數取最大即可，
f ( i ) = d p ( i ? k ? 1 ) + S ( i ? k , i ) f(i) = dp(i - k - 1) + S(i - k, i) f(i)=dp(i?k?1)+S(i?k,i)

繼續優化，看能不能將dp的轉移方程的第二個條件的 j j j給優化一下，
因為它的長度永遠都是只能小于等于 k k k的，所以可以想到滑動視窗，也就是單調佇列，
讓單調佇列維護 2 ? S ( j , i ) + f ( j ? 1 ) 2 * S(j, i) + f(j - 1) 2?S(j,i)+f(j?1)的最大值，每次取隊首就是最大值，
單調佇列基礎知識就不講了，代碼中有一個彈出佇列的細節在這里講一下，

while (hh <= tt && 2 * S(q[tt] + 1, i) + f[q[tt]] < f[i]) --tt; 為什么是小于 f [ i ] f[i] f[i]？
因為如果把i放入佇列 2 ? S ( j , i ) + f ( j ? 1 ) 2 * S(j, i) + f(j - 1) 2?S(j,i)+f(j?1)的值就會變成2 * S(i+ 1, i) + f[i] 也就是 f [ i ] f[i] f[i]，

代碼中維護的是 k + 1 k + 1 k+1個下標，

AC代碼

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
int n, k;
ll dp[N], f[N], c[N];
int a[N], q[N];

ll S(int l, int r)
{
	return c[r] - c[l - 1];
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> n >> k;
	_rep(i, 1, n)
	{
		cin >> a[i];
		dp[i] = f[i] = c[i] = c[i - 1] + a[i];
	}

	int hh = 0, tt = -1;
	q[++tt] = k + 1;
	_rep(i, k + 2, n)
	{
		while (hh <= tt && i - q[hh] > k) ++hh;
		dp[i] = max(2 * S(q[hh] + 1, i) + f[q[hh]], dp[i - 1] + a[i]);
		f[i] = dp[i - k - 1] + S(i - k, i);
		while (hh <= tt && 2 * S(q[tt] + 1, i) + f[q[tt]] < f[i]) --tt;
		q[++tt] = i;
	}

	cout << dp[n] << endl;
    return 0;
}

J 鄔澄瑤的公約數

這個題目氣死我了，WA了幾發，看錯題了，把他按照最大公倍數去算了，暈死，
這個題目只要找到所有數字中都出現的質數的最小冪相乘就得出結果了，

看題要仔細，做題前的 “ 靜 ” 要做到！

AC代碼

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % 1000000007
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 10000 + 10;
ll a[N], t[N];
unordered_map<ll, ll> ansMap;
int cnt[N];

void dive(ll x, ll p)
{
	for (int i = 2; 1ll * i * i <= x; ++i)
		if (x % i == 0)
		{
			ll s = 0;
			while (x % i == 0) x /= i, s++;
			if (!cnt[i]) ansMap[i] = s * p, cnt[i]++;
			else {
				ll o =  min(ansMap[i], s * p);
				ansMap[i] = o;
				cnt[i]++;
			}
		}
	if (x > 1) {
		if (!cnt[x]) ansMap[x] = p, cnt[x]++;
		else {
			ll o = min(ansMap[x], p);
			ansMap[x] = o;
			cnt[x]++;
		}
	}
}

ll qmi(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}

int main()
{
#ifdef LOCAL
	freopen("data.in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	int n;
	cin >> n;
	_for(i, 0, n) cin >> a[i];
	_for(i, 0, n) cin >> t[i];
	_for(i, 0, n) dive(a[i], t[i]);
	if (n == 1) {
		cout << qmi(a[0], t[0]) << endl;
		return 0;
	}
	
	ll ans = 1;
	for (const auto& p : ansMap)
		if (cnt[p.first] == n) ans = mod(ans * qmi(p.first, p.second));
	cout << ans << endl;
	return 0;
}

總結

學會轉換公式，減少沒有必要運行的東西，
仔細分析題目，給定的條件要運用到位，
沒有思路的時候就造各種奇葩的資料點，根據資料點去找思路，
猜測題目考點，

遇到認為是二分的題目，就瘋狂尋找有沒有能夠使得題目二分的性質，
認為是動態規劃的題目，就要以迭代的思想去考慮，動態規劃不是一步就找到答案的，可以想象為優化版的dfs，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261877.html

標籤：其他

上一篇：推薦一條高效的Python爬蟲學習路徑！

下一篇：JVM筆記-6Java虛擬機堆疊（Java虛擬機堆疊基本認識）

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂