DP

DP是将一个大问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

用DP一定要满足两个条件：

1：无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响

2：最优子结构：大问题的最优解可以由小问题的最优解推出

数学知识

算180的约数个数：首先将180分解为质因数的乘积：180=2^2×3^2×5^1，再每个质因数的指数加1后相乘，得到约数的总数：(2+1)×(2+1)×(1+1)=3×3×2=18

各种算法模板

dfs 弱项！！多复习！！！

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

int n, m; 
int g[110][110], vis[110][110], dist[110][110];
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};

bool check(int nx, int ny) 
{
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) return true;
  return false;
}

void dfs(int x, int y)
{
	if (x == n && y == m)
	{
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (check(nx, ny) && dist[x][y] + 1 < dist[nx][ny])
		{
			vis[nx][ny] = 1;
			dist[nx][ny] = dist[x][y] + 1;
			dfs(nx, ny);
			vis[nx][ny] = 0;
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> g[i][j];
	vis[1][1] = 1;
	dist[1][1] = 0;
	dfs(1,1); 
	cout << dist[n][m];
	return 0;
}

bfs

用处：搜寻最短路

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

int n, m; 
int g[110][110], vis[110][110], dist[110][110];
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};

bool check(int nx, int ny) 
{
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) 
    return true;
  return false;
}

void bfs()
{
	queue<pair<int,int>> q;
	q.push({1,1});
	vis[1][1] = 1;
	dist[1][1] = 0;
	while (q.size())
	{
		auto t = q.front(); q.pop();
		int x = t.first, y = t.second;
		if (x == n && y == m) return;
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (check(nx, ny))
			{
				vis[nx][ny] = 1;
				q.push({nx, ny});
				dist[nx][ny] = dist[x][y] + 1;
			}
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> g[i][j];
	bfs(); 
	cout << dist[n][m];
	return 0;
}

二分

用处：快速查找一个量

bool c1(int mid)
{
	return a[mid] < t;
}

bool c2(int mid)
{
	return a[mid] <= t;
}

int bs1(int l, int r)
{
	while (l < r)
	{
		int mid = l + r >> 1;
		if (c1(mid)) l = mid + 1;
		else r = mid;
	}
	return l;
}

int bs2(int l, int r)
{
	while(l < r)
	{
		int mid = l + r + 1 >> 1;
		if (c2(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}

快速幂

用处：可以在o(logn)的时间里快速计算一个数的多次方

using ll = long long;

ll f(ll a,ll b,ll p)
{
	ll ans = 1;
	a %= p;
	while (b > 0)
	{
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}

龟速乘

用处：计算两个大数的乘积，不过有点慢

using ll = long long;

ll qmi(ll a,ll b,ll p)
{
	ll ans = 0;
	a %= p;
	while (b)
	{
		if (b & 1) ans = (ans + a) % p;
		a = (a + a) % p;
		b >>= 1;
	}
	return ans;
}

最大公约数

int gcd(int a, int b)
{
	while (b != 0)
	{
		int t = b;
		b = a % b;
		a = t;
	}
	return a;
}

这是辗转相除法，基于定理：gcd(a, b) = gcd(b, a % b) 执行步骤（举例gcd(48, 18)） 48 / 18 = 2 余 12 → 转为gcd(18, 12) 18 / 12 = 1 余 6 → 转为gcd(12, 6) 12 / 6 = 2 余 0 → 余数为0，‌GCD = 6‌ 数学证明 设d = gcd(a, b)，则： d能整除a和b → 必然能整除(a - kb)（即余数） 反之，任何整除b和余数的数也必然能整除a

DAY 1

T1 矩阵转置

题意：把题目里给的数组转置

思路：可以用动态数组存数组，然后转置

代码：

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<int>> A(H, vector<int>(W));
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
             cin >> A[i][j];
        }
    }
    for (int j = 0; j < W; ++j)
    {
        for (int i = 0; i < H; ++i)
        {
            if (i != 0) cout << " ";
            cout << A[i][j];
        }
        cout << endl;
    }
    return 0;
}

T2 chess960

题意：判断两个b的位置是否相同，k是否在两个R之间，是则输出yes，否则输出no

代码：

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

char a[10];

int main()
{
  int b1 = 0, b2, k, r1 = 0, r2;	
  for (int i = 1; i <= 8; i++)
  {
    cin >> a[i];	
    if (a[i] == 'K') k = i;
    else if (a[i] == 'B' && b1 == 0) b1 = i;
    else if (a[i] == 'B') b2 = i;
    else if (a[i] == 'R' && r1 == 0) r1 = i;
    else if (a[i] == 'R') r2 = i;
	}
  if (b1 % 2 == b2 % 2)
  {
    cout << "No" << endl;
    return 0;
	}
  else if (k < r1 || k > r2)
  {
    cout << "No" << endl;	
    return 0;
	}
  cout << "Yes" << endl;
  return 0;
}

T3 暑假打工

题意：一天可以完成一份工作，完成后a[i]天得b[i]元，求在m天后最多有几元？

思路：用贪心算法，能做的都做，算出，输出最后最多有几元

代码：

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

priority_queue<int> q1;
vector <pair<int,int>> jobs;

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int ai, bi; cin >> ai >> bi;
		jobs.push_back({ai, bi});
	}
	sort(jobs.begin(), jobs.end());
	int idx = 0, ans = 0;
	for (int day = 1; day <= m; day++)
	{
		while (idx < n && jobs[idx].first <= day)
		{
			q1.push(jobs[idx].second);
			idx++;
		}
		if (q1.size() != 0)
		{
			ans += q1.top();
			q1.pop();
		}
	}
	cout << ans << endl;
	return 0;
}

T4 我喜欢因式分解

错误原因：没有好好想该用什么解， 觉得暴力枚举拿不到分

题意：给定x，找出一组a，b让a^5-b^5=x

思路：数学题，可以求出a，b的最大范围：-200 ~ 200，所以可以枚举一下a, b的每一种可能

代码：

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

int main()
{
	int x;
	cin >> x;
	for (double i = 200; i >= -200; i--)
	{
		for (double j = 200; j >= -200; j--)
		{
			if (i * i * i * i * i - j * j * j * j * j == x)
			{
				cout << i << " " << j << endl;
				return 0;
			}
		}
	}
	return 0;
}

DAY 2

T4 统计区间

错误原因：没有想到二分，觉得没有单调性， 没有想到可以利用前缀和数组的单调性

题意：求数组a中有几串连续的和为k

思路：用前缀和和二分求

注：数组上面的为坐标，里面的为值

前缀和数组可用于快速求区间和：a[l] + a[l + 1] + a[l + 2] + ... + a[r] = s[r] - s[l - 1]

代码：

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

ll a[200005], s[200005], n, k;

int main()
{
	freopen("tjqj.in", "r", stdin);
	freopen("tjqj.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	unordered_map<ll, ll> mp;
	ll ans = 0;
	for (int i = 0; i <= n; i++)
	{
		ll x = s[i] - k;
		ans += mp[x];
		mp[s[i]]++;
	}
	cout << ans << endl;
	return 0;
}

T5 旅行

题意：给定几个城市和几条路，求旅行的终点和起点共有几种可能

思路：循环遍历所有的点作为起点，把能走到的点都标记，以i为起点进行路径标记，遍历当前点u能够到达的所有节点j，并以j为新的起点继续出发

代码：

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

using ll = long long;
int n;

vector<int> adj[2010];
bool vis[2010];

void dfs(int u)
{
	if (vis[u]) return;
	vis[u] = 1;
	for (int i = 0; i < adj[u].size(); i++)
	{
		int j = adj[u][i];
		dfs(j);
	}
}

int main()
{
	freopen("lx.in", "r", stdin);
	freopen("lx.out", "w", stdout);
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}
	for (int i = 1; i <= n; i++)
	{
		memset(vis, 0, sizeof vis);
		dfs(i);
		for (int j = 1; j <= n; j++) if (vis[j]) ans++;
	}
	cout << ans << endl;
	return 0;
}

DAY 3

T1 最小贪吃量

错误原因：因为粗心没有用sort函数

题意：给定一些菜品以及它们的甜度和咸度，当小k吃的总甜度超过x或总咸度超过y，小k就会停止进食， 求小k最少吃几盘菜

思路：先按甜度，咸度从大到小排序，再求小k最早何时停止进食

代码：

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

const int N = 2e5 + 10;
int a[N], b[N];

bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	freopen("eat.in", "r", stdin);
	freopen("eat.out", "w", stdout);
	int n;
	ll x, y;
	cin >> n >> x >> y;
	int ans = n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	sort(a + 1, a + n + 1, cmp);
	sort(b + 1, b + n + 1, cmp);
	for (int i = 1; i <= n; i++)
	{
		x -= a[i];
		if (x < 0)
		{
			ans = i;
			break;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		y -= b[i];
		if (y < 0)
		{
			ans = min(ans, i);
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

T2 三连纯一数

错误原因：用了一种歪思路，让我所能想到的样例都对，结果数据大一点就不对了

题意：十进制表示中所有数字均为1的整数被称为纯一数，三连纯一数是指三个纯一数相加，求第n小的三连纯一数

思路：把所有纯一数列举出来，枚举所有三连纯一数，输出第n个

代码：

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

long long  a[20] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111};

int main()
{
	freopen("three.in", "r", stdin);
	freopen("three.out", "w", stdout);
	int n, s = 0;
	cin >> n;
	for (int i = 1; i <= 13; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			for (int k = 1; k <= j; k++)
			{
				s++;
				if (s == n)
				{
					cout << a[i] + a[j] + a[k] << endl;
					return 0;
				}
			}
		}
	}
	return 0;
}

T3 倒立数对

错误原因：思路想歪了

题意：倒立数对是指整数a的首位和整数b的末位一样，a的末位和b的首位一样， 求n以内有几个这样的数对

思路：求n以内的数的首位和末位，如果a的首位是i，末位是j，那么a[i][j]++，最后把每个a[i][j]和a[j][i]相乘

代码：

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

int a[15][15];

int main()
{
	freopen("number.in", "r", stdin);
	freopen("number.out", "w", stdout);
	int n;
	long long ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int h, t = i % 10;
		if (i >= 100000) h = i / 100000;
		else if (i >= 10000) h = i / 10000;
		else if (i >= 1000) h = i / 1000;
		else if (i >= 100) h = i / 100;
		else if (i >= 10) h = i / 10;
		else h = i;
		a[h][t]++;
	}
	for (int i = 1; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			ans += a[i][j] * a[j][i];
		}
	}
	cout << ans << endl;
	return 0;
}

T5 区间合并

题意：合并多个区间并输出

知识点：区间合并分三种情况，包含，相交，不相交这里分类讨论

包含：不需要管

相交：拓展右区间，左区间不变

不相交：原区间已经是合并完成的独立区间，从下一个新区间重新合并下一个区间

代码：

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

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
	vector<PII> res;
	sort(segs.begin(), segs.end());
	int st = -2e9, ed = -2e9;
	for (auto seg : segs) 
	{
		if (ed < seg.first)
		{
			if (st != -2e9) res.push_back({st, ed});
			st = seg.first, ed = seg.second;
		}
		else ed = max(ed, seg.second);
	}
	if (st != -2e9) res.push_back({st, ed});
	segs = res;
}

int main()
{
	freopen("merge.in", "r", stdin);
	freopen("merge.out", "w", stdout);
	int n;
	scanf("%d", &n);
	vector<PII> segs;
	for (int i = 0; i < n; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		segs.push_back({l, r});
	}
	merge(segs);
	for (auto seg : segs)
	{
		cout << seg.first << " " << seg.second << endl;
	}
	return 0;
}

DAY 5

T1 单次交换

错误原因：“如果有无效的交换那么结果加1” 我没有T_T

题意：给定一串字符串s，可以交换任意两位，求一共可以交换出几串字符串

思路：用高斯求和算出一共可以交换几次，再减去无效的交换，如果有无效的交换那么结果加1

代码：

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

int a[130];

int main()
{
	freopen("swap.in", "r", stdin);
	freopen("swap.out", "w", stdout);
	string s;
	cin >> s;
	ll n = s.size();
	for (int i = 0; i < n; i++) a[s[i]]++;
	ll ans = n * (n - 1) / 2;
	bool f = 0;
	for (int i = 'a'; i <= 'z'; i++)
	{
		ans -= (ll)a[i] * (a[i] - 1) / 2;
		if (a[i] > 1) f = 1;
	}
	cout << ans + f << endl;
	return 0;
}

T2 开关

错误原因：枚举写错了

题意：有至多10个开关和10个灯炮，灯泡i连接到ki​个开关：开关si1,si2,...,ski。当这些开关中处于开状态的开关数量%2等于p[i]时，灯泡i会被点亮，求有多少种开关的开和关状态的组合能够点亮所有灯泡

思路：枚举所有可能的组合，算算是否满足条件

代码：

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

int n, m;
vector<int> a[15];
int p[15], ans, sw[15];

bool check()
{
	for (int i = 1; i <= m; i++)
	{
		int cur = 0;
		for (int k = 0; k < a[i].size(); k++) cur ^= sw[a[i][k]];
		if (cur != p[i]) return false;
	}
	return true;
}
void dfs(int u)
{
	if (u == n + 1)
	{
		if (check())
			ans++;
		return;
	}
	dfs(u + 1);
	sw[u] = 1;
	dfs(u + 1);
	sw[u] = 0;
}

int main()
{
	freopen("switch.in", "r", stdin);
	freopen("switch.out", "w", stdout);
	int k, t;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> k;
		while (k--)
		{
			cin >> t;
			a[i].push_back(t);
		}
	}
	for (int i = 1; i <= m; i++) cin >> p[i];
	dfs(1);
	cout << ans << endl;
	return 0;
}

T3 不可表示的数

错误原因：枚举的范围太大，超时了

题意：给定n，求n以内有多少个不能表示为a^b的形式（a和b都<=2）

思路：直接用暴力枚举，a从2到sqrt(n)，b从2到34

代码：

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

set <ll> s;

ll solve(ll a, ll b)
{
	ll sum = 1;
	for (int i = 1; i <= b; i++) sum *= a;
	return sum;
}

int main()
{
	freopen("num.in", "r", stdin);
	freopen("num.out", "w", stdout);
	ll n, ans = 0;
	cin >> n;
	for (ll i = 2; i <= sqrt(n); i++)
	{
		for (ll j = 2; j <= 34; j++)
		{
			ll sum = solve(i, j);
			if (sum <= n)
			{
				ans++;
				s.insert(sum);
			}
			else if (sum > n) break;
		}
	}
	cout << n - s.size() << endl;
	return 0;
}

T4 幸运数

错误原因：质数筛的方法，范围都错了

题意：k幸运数，k可以表示为p * q^3，求n以内一共有几个k（p，q均为质数）

思路：先用质数筛筛出所有质数，再暴力枚举

知识点：

埃氏筛

const int N = 1e6+5;
int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
	for (int i=2; i<=n; i++)
  {
		if (!st[i])
    {
			primes[++cnt] = i;
			for (int j=i+i; j<=n; j+=i) st[j] = 1;
		}
	}
}

欧拉筛(线性筛)

void get_primes(int n)
{
	for (int i=2; i<=n; i++) {
		if (!st[i]) primes[++cnt] = i;
			for (int j=1; primes[j]<=n/i; j++)
      {
				st[primes[j]*i] = 1;
				if (i%primes[j] == 0) break;
			}
	}
}

代码：

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

const int N = 1e6+5;
int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i]) primes[++cnt] = i;
		for (int j = i + i; j <= n; j += i) st[j] = 1;
	}
}

int main()
{
	freopen("lucky.in", "r", stdin);
	freopen("lucky.out", "w", stdout);
	ll n;
	cin >> n;
	get_primes(N);
	ll ans = 0;
	for (int i = 1; i <= cnt; i++)
	{
		ll p = primes[i];
		if (p * p * p * p >= n) break;
		for (int j = i + 1; j <= cnt; j++)
		{
			ll q = primes[j];
			q = q * q * q;
			if (q * p > n) break;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

T5 逻辑表达式

错误原因：题目没看懂

题意：给定N个字符串s[1]…,s[n]，每个字符串是AND或OR。 求满足以下条件的N+1元组(x[0],…,x[n])的数量，其中每个元素为true或false，使得以下计算过程最终y[n]为true:

y[0]=x[0]；

对于i≥1，如果s[i]​是and，则y[i]=y[i−1]∧x[i]；如果s[i]是or，则y[i]=y[i−1]∨x[i]。 这里，a∧b和a∨b是逻辑运算符。

代码：

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

int n;
ll ans = 1;
string op[67];

int main()
{
	freopen("expr.in", "r", stdin);
	freopen("expr.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> op[i];
	for (int i = n; i >= 1; i--) if (op[i][0] == 'O') ans += (1ll << i);
	cout << ans << endl;
	return 0;
}

DAY 8

T2 金字塔

错误原因：没有用方程的思路反推

题意：给定金字塔的周围的坐标，高度，求中间的坐标，高度，(x, y)的高度 = max(h−(x−c[x])−(y−c[y]),0)

思路：用方程的思路反推，再暴力枚举，找到对的就输出，return 0

代码：

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

int x[105], y[105], h[105];

int main()
{
	freopen("tower.in","r",stdin);
	freopen("tower.out","w",stdout);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i] >> h[i];
		if (h[i] > 0)
		{
			swap(x[i], x[1]);
			swap(y[i], y[1]);
			swap(h[i], h[1]);
		}
	}
	for (int cx = 0; cx <= 100; cx++)
	{
		for (int cy = 0; cy <= 100; cy++)
		{
			int ch = h[1] + abs(cx - x[1]) + abs(cy - y[1]);
			bool flag = true;
			for (int i = 2; i <= n; i++)
			{
				if (max(ch - abs(x[i] - cx) - abs(y[i] - cy), 0) != h[i]) flag = false;
			}
			if (flag)
			{
				cout << cx << " " << cy << " " << ch << endl;
				return 0;
			}
		}
	}
	return 0;
}

T3 走迷宫

错误原因：bfs写错了，没背牢

这题没写对，只有70多分，很可惜，以后一定要细心，bfs和dfs的模板也要背牢，有空多复习

题意：给定一个迷宫，求从任意的起点到任意终点的最短路的最大步数 <- 题目里这句话让我理解了半天

思路：用暴力枚举各个起点，终点，再用广搜查找最短路，再用ans记录最大步数

代码：

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

const int N = 110;
int n, m, a[N][N], dist[N][N], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(int nx, int ny)
{
	memset(dist, -1, sizeof(dist));
	queue <pair <int,int>> q;
	q.push({nx, ny});
	dist[nx][ny] = 0;
	int ma = 0;
	while (!q.empty())
	{
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x = t.first + dx[i], y = t.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 0 && dist[x][y] == -1)
			{
				dist[x][y] = dist[t.first][t.second] + 1;
				ma = max(ma, dist[x][y]);
				q.push({x, y});
			}
		}
	}
	return ma;
}

int main()
{
	freopen("maze.in", "r", stdin);
	freopen("maze.out", "w", stdout);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char x;
			cin >> x;
			if (x == '.') a[i][j] = 0;
			else a[i][j] = 1;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (a[i][j] == 0) ans = max(ans, bfs(i, j));
	cout << ans << endl;
	return 0;
}

T5 序列查询

我都想到用multiset了，结果还是只有4分

题意：有一个空序列a和三种查询，求每个查询的结果查询如下

1：将x插入a

2：在a中小于等于x的元素中，输出第k大的值。（k不超过5）如果a中小于等于x的元素不足k个，则输出−1

3：在a中大于等于x的元素中，输出第k小的值。（k不超过5）如果a中大于等于x的元素不足k个，则输出−1

思路：用multiset排序后，分类求结果

知识点： multiset s;

(1)插入一个数x到多重集合中：s.insert(x)

(2)删除多重集合中的所有x：s.erase(x)

(3)删除多重集合中的一个x：s.erase(s.find(x))

(4)s.lower_bound(x) 返回 >= x的第一个元素迭代器，相当于二分中的bs1

(5)s.upper_bound(x) 返回 > x的第一个元素迭代器，和bs2差不多，但不是bs2，需要加一次特判

(6)s.begin() 指向第一个元素的迭代器

(7)s.end() 指向最后一个元素后一位的迭代器

multiset中用二分查找很方便，因为它会自动排序， 它还可以用来维护一个有序序列

迭代器可以理解为数组下标，但实际上它是一个地址，所以要取得迭代器对应的值，需要用 * 解除引用

代码：

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

const int N = 2e5 + 10;
long long n;

int main()
{
	freopen("list.in","r",stdin);
	freopen("list.out","w",stdout);
	multiset<ll> s;
	int n;
	cin >> n;
	while (n--)
	{
		ll opt, x, k;
		cin >> opt >> x;
		if (opt == 1) s.insert(x);
		else if (opt == 2)
		{
			cin >> k;
			auto it = s.upper_bound(x);
			bool flag = true;
			while (k-- && it != s.begin()) it--;
			if(k >= 0 || it == s.end()) flag = false;
			cout << (flag ?*it : -1) << endl;
		}
		else
		{
			cin >> k;
			auto it = s.lower_bound(x);
			while (--k && it != s.end()) it++;
			if (it == s.end()) cout << -1 << endl;
			else cout << *it << endl;
		}
	}
	return 0;
}

DAY 12

T1 给我一张凳子

错误原因：太粗心了，ans没有开long long

题意：有n个人，可以给每人一把凳子，后面人不能低于前面人，求凳子的最小总高度

思路：用一个for循环和一个zd，如果a[i]大于zd，zd等于a[i]，否则答案加上zd-a[i]

代码：

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

int a[200005];

int main()
{
	freopen("step.in", "r", stdin);
	freopen("step.out", "w", stdout);
	int n, zd = INT_MIN;
	long long ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++)
	{
		if (a[i] >= zd)
		{
			zd = a[i];
		}
		else
		{
			ans += zd - a[i];
		}
	}
	cout << ans << endl;
	return 0;
}

T3 起遇质数

错误原因：用上了质数筛，却没看出来可以用前缀和优化，所以超时了

题意：如果一个数是质数，且（这个数 + 1）/ 2也是质数，则我们称之为起遇质数，问从l到r有几个这样的数

思路：先用质数筛找出100000以内的质数，再用前缀和求出答案

代码：

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

const int N = 1e5 + 10;

int main()
{
	freopen("qy.in","r",stdin);
	freopen("qy.out","w",stdout);
	vector <bool> ok(N, 1);
	vector <int> sum(N, 0);
	ok[0] = ok[1] = 0;
	for (int i = 2; i < N; i++)
	{
		if (ok[i])
		{
			for (int j = i * 2; j < N; j += i)
			{
				ok[j] = 0;
			}
		}
	}
	sum[0] = 0;
	for (int x = 1; x < N; x++)
	{
		sum[x] = sum[x - 1];
		if (x % 2 == 1)
		{
			if (ok[x])
			{
				if (ok[(x + 1) / 2])
				{
					sum[x]++;
				}
			}
		}
	}
	int q;
	cin >> q;
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		cout << sum[r] - sum[l - 1] << endl;
	}
	return 0;
}

T4 魔法咒语

错误原因：调试时把freopen注释了，交的时候……也注释了

T5 简单路径统计

错误原因：对存图不是太熟练，存的图竟然是错的！看来以后得多练

题意：给定一个有n个顶点，m条边的简单无向图，设k为从顶点1出发的简单路径的数量，输出min(K,1000000)

思路：先用邻接表存图，再遍历所有路，然后注意最大只能输出1000000

代码：

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

const int N = 2e5 + 10;
int n, m, vis[N], cnt = 0;
vector <int> adj[N];

void dfs (int u)
{
	if (cnt > (int)1e6) return;
	cnt++;
	for (int i = 0; i < adj[u].size(); i++)
	{
		int j = adj[u][i];
		if (vis[j]) continue;
		vis[j] = 1;
		dfs(j);
		vis[j] = 0;
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vis[1] = 1;
	dfs(1);
	if (cnt > int(1e6)) cout << int(1e6) << endl;
	else cout << cnt << endl;
	return 0;
}

T6 自助餐

题意：自助餐有n道菜，给定吃每道菜的时间，相应的美味度和总时间，求吃完后小k的幸福感有多少

思路：先按时间排序，再套01背包

代码：

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

int n, t;
pair <int, int> w[3010];
int dp[3010];

int main()
{
	freopen("free.in", "r", stdin);
	freopen("free.out", "w", stdout);
	cin >> n >> t;
	for (int i = 0; i < n; i++)
	{
		cin >> w[i].first >> w[i].second;
	}
	sort(w, w + n);
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		int a = w[i].first, b = w[i].second;
		if (t - 1 >= 0)
		{
			ans = max(ans, dp[t - 1] + b);
		}
		for (int j = t - 1; j >= a; j--)
		{
			dp[j] = max(dp[j], dp[j - a] + b);
		}
	}
	ans = max(ans, dp[t - 1]);
	cout << ans << endl;
	return 0;
}

DAY 13

T3 重复重复重复...重复重复

错误原因：没有想到重复数的表示方法：长度为k的重复数可以表示为d × (10^k − 1) / 9，所以也没有想到可以枚举d和k，结果可想而知：超时了

题意：给定n，m，x是一个小于10^n的正整数，且x的十进制表示中的所有数字都相同，x是m的倍数，求最大的x，若x不存在，输出-1

思路：因为重复数的表示方法是长度为k的重复数可以表示为d × (10^k − 1) / 9，所以可以枚举d，k，在这之前，要预处理10^k % 9m的值，避免重复计算

代码：

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

int main()
{
	freopen("repeat.in", "r", stdin);
	freopen("repeat.out", "w", stdout);
	int n;
	ll m;
	cin >> n >> m;
	string ans = "-1";
	ll N = 9 * m;
	vector<ll> a(n+1);
	a[0] = 1 % N;
	for(int i = 1; i <= n; ++i) a[i] = (a[i-1] * 10) % N;
	for(int k = n; k >= 1; --k)
	{
		ll t = (a[k] - 1) % N;
		for(int d = 9; d >= 1; --d)
		{
			if((d * t) % N == 0)
			{
				string s(k, '0' + d);
				if (ans == "-1" || k > (int)ans.size() || (k == (int)ans.size() && s > ans)) ans = s;
				break;
			}
		}
		if (ans != "-1") break;
	}
	cout << ans << endl;
	return 0;
}

T4 灯

题意：有一个由h行w列组成的网格和一个不会斜着照射的灯，求灯最大照射范围

代码：

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

int main()
{
	freopen("deng.in", "r", stdin);
	freopen("deng.out", "w", stdout);
	int h, w;
	cin >> h >> w;
	vector<string> a(h);
	for (int i = 0; i < h; ++i) cin >> a[i];
	vector <vector <int>> left (h, vector <int>(w));
	vector <vector <int>> right (h, vector <int>(w));
	vector <vector <int>> up (h, vector <int>(w));
	vector <vector <int>> down (h, vector <int>(w));
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			if (a[i][j] == '#') left[i][j] = 0;
			else left[i][j] = (j == 0) ? 1 : left[i][j - 1] + 1;
		}
	}
	for (int i = 0; i < h; ++i)
	{
		for (int j = w - 1; j >= 0; --j)
		{
			if (a[i][j] == '#') right[i][j] = 0;
			else right[i][j] = (j == w - 1) ? 1 : right[i][j + 1] + 1;
		}
	}
	for (int j = 0; j < w; ++j)
	{
		for (int i = 0; i < h; ++i)
		{
			if (a[i][j] == '#') up[i][j] = 0;
			else up[i][j] = (i == 0) ? 1 : up[i - 1][j] + 1;
		}
	}
	for (int j = 0; j < w; ++j)
	{
		for (int i = h - 1; i >= 0; --i)
		{
			if (a[i][j] == '#') down[i][j] = 0;
			else down[i][j] = (i == h - 1) ? 1 : down[i + 1][j] + 1;
		}
	}
	int ans = 0;
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			if (a[i][j] == '.')
			{
				int sum = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3;
				ans = max(ans, sum);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

DAY 14

T3 最大MEX值

错误原因：以为0，1，2，2，2占5个数字，但它们只占3个，没有深度思考

题意：给定一个长度为N的非负整数序列a。当b是通过从a中选择k个元素并按原顺序连接而成的序列时，求MEX(b)的最大可能值。 这里，对于一个序列x，我们定义MEX(x)为满足以下条件的唯一非负整数m：

1，所有满足0 ≤ i < m的整数i都包含在X中。

2，m不包含在X中。

思路：先用桶数组，在查找

代码：

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

const int N = 3e5 + 10;
int a[N], cnt[N];

int main()
{
	freopen("C.in", "r", stdin);
	freopen("C.out", "w", stdout);
	int n, k, ans = 0;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] < N)
		{
			cnt[a[i]]++;
		}
	}
	if (cnt[0] == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	while (ans < N && cnt[ans] >= 1 && k > 0)
	{
		k--;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

T5 构成回文

题意：对于一个序列x，定义f(x)为（将x修改为回文序列所需改变的最小元素数量）。 给定一个长度为n的序列a，求a的所有连续子数组的f(x)之和。 这里，长度为m的序列x被称为回文序列，当且仅当对于所有1 ≤ i ≤ m，x的第i个元素与第(m + 1 − i)个元素相等。

思路：我们可以构造一种对称，当位置p[j]=r−dp[j]=r−d，那么对于某一个d，他们是对称的，d的取值可以是0到p[i]，那么正向就有 p[i]个贡献，反向有n−p[j]+1个贡献，对两个值取较小值就是当前可行的。而我们发现，求p[i]和p[j]是可以通过双指针枚举的。当p[i]小于p[j]时，p[i]到p[j]−1 之间的值都肯定小于p[j]，那么不需要修改的对数就是 (r−l)×p[i]，l，否则从p[j]到p[i]+1，这个区间的值都会小于p[i]，则贡献为(r−l)×p[i]，r。

代码：

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

const int N = 2e5 + 10;
vector <int> p[N];

int main()
{
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		p[x].push_back(i);
	}
	long long ans = 0;
	for (int k = 1; k <= n; k++)
		ans += 1LL * (n - k + 1) * (k / 2);
	for (int x = 1; x <= n; x++)
	{
		if (p[x].size() == 0) continue;
		int l = 0, r = p[x].size() - 1;
		while (l<r)
		{
			if (p[x][l] < n - p[x][r] + 1)
				ans -= 1LL * (r - l) * p[x][l], l++;
			else
				ans -= 1LL * (r - l) * (n - p[x][r] + 1), r--;
		}
	}
	cout << ans << endl;
	return 0;
}