章魚圖的判斷

題意：

對于無向圖\(G = (V, E)\)，我們將有且只有一個環的、大于2個頂點的無向連通圖稱之為章魚圖，因為其形狀像是一個環（身體）帶著若干個樹（觸手），故得名。
給定一個無向圖，請你判斷是不是只有一個章魚子圖存在。

注意：這里的章魚子圖指的是滿足章魚圖性質的極大連通子圖

思路：

①有幾個聯通快？dfs一遍即可
②如何判斷是不是“章魚圖”？對于一個合法的章魚圖，\(點數=\frac{出度數 + 入度數}{4}\)
③如何求環上的點數？dfs，保留前驅，更新深度

代碼

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
using namespace std;

const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;
const int N = 1e5 + 10;

//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;
int head[N];
int ne[N * 2];
int idx;
int w[N * 2];
int group[N];
int cnt = 0;
int num = 0;
int dep[N];

bool flag = false;
void add (int x, int y) {
	 ne[idx] = head[x];
	 w[idx] = y;
	 head[x] = idx ++;
}
void dfs (int u, int father) {
	 group[u] = cnt;
	 for (int i = head[u]; i != -1; i = ne[i]) {
	 	 int ww = w[i];
	 	 if (ww != father && !group[ww]) {
	 	 	 dfs (ww, u);
	 	 }
	 }
}

void dfs2 (int u, int deep, int pre) {
	 dep[u] = deep;
	 for (int i = head[u]; i != -1; i = ne[i]) {
	 	 int ww = w[i];
	 	 if (ww == pre) continue;
	 	 if (ww != pre && dep[ww]) {
	 	 	 num = abs(dep[u] - dep[ww]) + 1;
	 	 	 flag = 1;
	 	 	 return ;
	 	 }
	 	 dfs2 (ww, deep + 1, u);
	 	 if (flag) return ;
	 }
}

void solve() {
	 int n, m;
	 cin >> n >> m;
	 idx = 0;
	 cnt = 0;
	 memset (head, -1, sizeof (head));
	 for (int i = 1; i <= n; ++i) {
	 	 group[i] = 0;
	 }
	 vector<int> Size (n + 1, 0);
	 vector<int> In (n + 1, 0);
	 vector<int> Out (n + 1, 0);
	 vector<int> groupIn (n + 1, 0);
	 vector<int> groupOut (n + 1, 0);
	 for (int i = 1; i <= m; ++i) {
	 	 int x, y;
	 	 cin >> x >> y;
	 	 add (x, y);
	 	 add (y, x);
	 	 In[x] ++;
	 	 In[y] ++;
	 	 Out[x] ++;
	 	 Out[y] ++;
	 }
	 for (int i = 1; i <= n; ++i) {
	 	 if (!group[i]) {
	 	 	 cnt ++;
	 	 	 dfs (i, 0);
	 	 }
	 }
	 for (int i = 1; i <= n; ++i) {
	 	 Size[group[i]] ++;
	 	 groupIn[group[i]] += In[i];
	 	 groupOut[group[i]] += Out[i];
	 }
	 int res = 0;
	 int resid = 0;
	 for (int i = 1; i <= cnt; ++i) {
	 	 if (Size[i] >= 3 && Size[i] == (groupIn[i] + groupOut[i]) / 4) {
	 	 	 res ++;
	 	 	 resid = i;
	 	 }
	 }
	 if (res >= 2 || res == 0) {
	 	 cout << "No" << " " << res << "\n";
	 }else{
	 	 flag = false;
	 	 for (int i = 1; i <= n; ++i) {
	 	 	 dep[i] = 0;
	 	 }
	 	 for (int i = 1; i <= n; ++i) {
	 	 	 if (group[i] == resid) {
	 	 	 	 dfs2 (i, 1, -1);
	 	 	     break;
	 	 	 }
	 	 }
	 	 cout << "Yes" << " " << num << "\n";
	 }
}
int main() {
	 ios::sync_with_stdio (false);
	 cin.tie(NULL);
	 cout.tie(NULL);
	 t = 1;
	 cin >> t;
	 while (t --) {
	 	 solve();
	 }
	 return 0;
}

工作安排

題意：

小\(K\)有\(N\)項工作等待完成，第\(i\)項工作需要花\(t_i\)單位時間，必須在\(d_i\)時刻或之前完成，報酬為\(p_i\)。假設小\(K\)工作時刻從\(0\)開始，且同一時刻只能做一項工作、工作一旦開始則不可中斷或切換至其他工作，請你幫小\(K\)規劃一下如何選擇合適的工作，使小\(K\)可以獲得最多的報酬。

思路：

按截止時間排序 + 倒序背包
假設你沒有按截止時間排序，而是隨機順序，結果你把一個截止時間很晚的任務放進去了，占據了一段時間。然后你遇到一個截止時間早、時間短、收益高的任務，結果你卻安排不進去了 → 損失最優解。
而如果你按截止時間升序處理，就能保證：每次你在當前時刻前安排能做的任務，不會沖突掉未來那些“必須早做”的任務

TLE代碼

void solve() {
	 int n;
	 cin >> n;
	 for (int i = 1; i <= n; ++i) {
	 	 cin >> nd[i].x >> nd[i].y >> nd[i].z;
	 }
	 sort (nd + 1, nd + 1 + n, cmp);
	 vector<int> dp (N, 0);
	 for (int i = 1; i <= n; ++i) {
	 	 for (int j = nd[i].y; j >= 0; --j) {
	 	 	 if (j - nd[i].x >= 0) dp[j] = max (dp[j], dp[j - nd[i].x] + nd[i].z);
	 	 }
	 }
	 int res = 0;
	 for (int i = 0; i < N; ++i) {
	 	res = max (res, dp[i]);
	 }
	 cout << res << "\n";
}

問題

1、每組數據進 solve() 都會重新構造一個 vector dp(N, 0)，底層走了一次堆上分配＋初始化＋析構。雖然 N 只有 5010，看似很小，但反復 5 次 malloc/free＋5000 次寫零，常數開銷就被放大了。
2、把 int j、int i、int n 全抬升成 long long 以后，編譯器可以直接在 R 系列（64?bit）寄存器上循環，省掉每次從 32→64 的零擴展或者 64→32 的截斷資源沖刺

代碼

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
using namespace std;
#define int long long 
const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;
const int N = 5010;
//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;

struct node {
	 int x, y, z;
};

node nd[N];
int dp[N];

bool cmp (node a, node b) {
	 return a.y < b.y;
}

void solve() {
	 int n;
	 cin >> n;
	 for (int i = 1; i <= n; ++i) {
	 	 cin >> nd[i].x >> nd[i].y >> nd[i].z;
	 }
	 sort (nd + 1, nd + 1 + n, cmp);
	 memset (dp, 0, sizeof (dp));
	 for (int i = 1; i <= n; ++i) {
	 	 for (int j = nd[i].y; j >= nd[i].x; --j) {
	 	    dp[j] = max (dp[j], dp[j - nd[i].x] + nd[i].z);
	 	 }
	 }
	 int res = 0;
	 for (int i = 0; i < N; ++i) {
	 	res = max (res, dp[i]);
	 }
	 cout << res << "\n";
}

signed main() {
	 ios::sync_with_stdio (false);
	 cin.tie(NULL);
	 cout.tie(NULL);
	 t = 1;
	 cin >> t;
	 while (t --) {
	 	 solve();
	 }
	 return 0;
}