C 回文自动机

  • 将原字符串复制一遍，防止重复，结尾大于 n nn 的才加入cnt中
  • 之后就是回文自动机的板子
    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
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    int ans = 0;
    /*
    ---------------回文自动机PAM---------------

    - 传入字符串下标从0开始
    - 本质不同的回文子串个数
    - 所有回文子串个数
    - 每种回文串出现的次数 cnt（需要get_cnt）
    - 每种回文串的长度 len
    - 以下标 i 为结尾的回文串的个数 sed
    - 每个回文串在原串中出现的起始位置 record
    */

    struct PAM {
    	string s;
    	int n;
    	int nxt[N][10];
    	int fail[N]; // 当前节点最长回文后缀的节点
    	int len[N]; // 当前节点表示的回文串的长度
    	int cnt[N]; // 当前节点回文串的个数， 在getcnt后可得到全部
    	// int sed[N]; // 以当前节点为后缀的回文串的个数
    	// int record[N]; // 每个回文串在原串中出现的位置
    	int tot; // 节点个数
    	int last; // 上一个节点
    	void init()
    	{
    		tot = 0;
    		for (int i = 0; i < N; i ++ )
    		{
    			fail[i] = cnt[i] = len[i] = 0;
    			for (int j = 0; j < 10; j ++ ) nxt[i][j] = 0;
    		}
    	}
    	int newnode(int lenx)
    	{
    		for (int i = 0; i < 26; i++)
    		nxt[tot][i] = 0;
    		cnt[tot] = 0;
    		len[tot] = lenx;
    		return tot;
    	}
    	void build(string ss)
    	{
    		tot = 0;
    		newnode(0);
    		tot = 1, last = 0;
    		newnode(-1);
    		fail[0] = 1;
    		n = ss.size();
    		s = " " + ss;
    	}
    	int getfail(int x, int n)
    	{
    		while (n - len[x] - 1 <= 0 || s[n - len[x] - 1] != s[n])
    			x = fail[x];
    		return x;
    	}
    	void insert(char cc, int pos, int op)
    	{
    		int c = cc - '0';
    		int p = getfail(last, pos);
    		if (!nxt[p][c])
    		{
    			tot++;
    			newnode(len[p] + 2);
    			fail[tot] = nxt[getfail(fail[p], pos)][c];
    			len[tot] = len[p] + 2;
    			// sed[tot] = sed[fail[tot]] + 1;
    			nxt[p][c] = tot;
    		}
    		last = nxt[p][c];
    		cnt[last] += op;
    		// record[last] = pos;
    	}
    	void insert()
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			if (i <= n / 2) insert(s[i], i, 0);
    			else insert(s[i], i, 1);
    		}
    	}
    	void get_cnt()
    	{
    		for (int i = tot; i > 0; i -- )
    		{
    			cnt[fail[i]] += cnt[i];
    			if (i >= 2 && len[i] <= n / 2)
    			{
    				ans = (ans + 1ll * cnt[i] * cnt[i] % mod * len[i] % mod) % mod;
    			}
    		}
    	}
    	int get_diff_cnt() // 本质不同的回文子串个数
    	{
    		return tot - 1;
    	}
    	int get_all_cnt() // 所有回文子串个数（本质相同的多次计算）
    	{
    		int sum = 0;
    		get_cnt();
    		for (int i = 2; i <= tot; i ++ ) sum += cnt[i];
    		return sum;
    	}
    } pam;
    //------------------------------------

    void solve()
    {
    	int n; cin >> n;
    	string s; cin >> s;
    	s = s + s;
    	pam.init();
    	pam.build(s);
    	pam.insert();
    	pam.get_cnt();
    	cout << ans << '\n';
    }

    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);

        int t = 1;
        // cin >> t;
        while (t--)
        {
            solve();
        }
        return 0;
    }

E

要用离散化去实现接着去横竖两遍去遍历数组,结构体有sum,cnt,a[x].sum += i(j), cnt += 1, ans += a[x].cnt * i(j) - a[x].sum;

F

签到

G

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void solve()
{
	int n, m, k; cin >> n >> m >> k;
	string s; cin >> s;
	s = " " + s;
	vector<int> pre(n + 1);
	for (int i = 1; i <= n; i ++ ) pre[i] = pre[i - 1] + (s[i] == '0');
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, INF)));
	auto check = [&](int x)
	{
		for (int i = 0; i <= n; i ++ )
		{
			for (int j = 0; j <= k; j ++ )
			{
				dp[i][j][0] = dp[i][j][1] = INF;
			}
		}
		dp[0][0][0] = dp[0][0][1] = 0;
		for (int i = 1; i <= n; i ++ )
		{
			for (int j = 0; j <= k; j ++ )
			{
				if (s[i] == '0')
				{
					dp[i][j][0] = min({dp[i][j][0], dp[i - 1][j][0], dp[i - 1][j][1]});
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1);
				}
				else
				{
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1]);
				}
				if (i >= x && j >= 1)
				{
					dp[i][j][1] = min(dp[i][j][1], dp[i - x][j - 1][0] + pre[i] - pre[i - x]);
				}
			}
		}
		return (min(dp[n][k][0], dp[n][k][1]) <= m);
	};
	int l = 0, r = n;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	if (r > 0) cout << r << '\n';
	else cout << -1 << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

J

Dijstra + 思维

分别枚举每一条边,把他当作最大值

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
struct edge {
	int a, b, c;
};

void solve()
{
	int n, m; cin >> n >> m;
	vector<vector<PII>> g(n + 1);
	vector<struct edge> e(m);
	for (int i = 0; i < m; i ++ )
	{
		int a, b, c; cin >> a >> b >> c;
		e[i] = {a, b, c};
		
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	vector<int> dist1(n + 1, INF), dist2(n + 1, INF);
	auto dijkstra = [&](int rt, vector<int>&dist)
	{
		vector<bool> st(n + 1);
		priority_queue<PII, vector<PII>, greater<PII>> pq;
		pq.push({0, rt});
		dist[rt] = 0;
		while (pq.size())
		{
			auto t = pq.top();
			pq.pop();

			int v = t.second, maxx = t.first;

			if (st[v]) continue;
			st[v] = true;

			for (int i = 0; i < g[v].size(); i ++ )
			{
				int j = g[v][i].first, w = g[v][i].second;
				if (st[j]) continue;
				if (dist[j] > max(dist[v], w))
				{
					dist[j] = max(dist[v], w);
					pq.push({dist[j], j});
				}
			}
		}
	};
	dijkstra(1, dist1);
	dijkstra(n, dist2);
	int ans = INF;
	for (int i = 0; i < m; i ++ )
	{
		auto [a, b, c] = e[i];
		int tmp = min(max(dist1[a], dist2[b]), max(dist1[b], dist2[a]));
		if (tmp <= c) ans = min(ans, tmp + c);
	}
	
	cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}