首页 > 其他分享 >AT_abc 复盘合集（2024）

AT_abc 复盘合集（2024）

时间：2024-03-09 13:11:22浏览次数：27  
标签：abc int namespace cin 2024 code include 复盘 dp

AT_abc217 复盘

A

非常水

AC code:

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

string s1, s2;

int main(){
	cin >> s1 >> s2;
	if (s1 < s2) cout << "Yes";
	else cout << "No";
	return 0;
}

B

还是非常水，随便拿 map 搞搞

AC code:

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

string s1, s2, s3;
map<string, int> mp;

int main(){
	cin >> s1 >> s2 >> s3;
	mp[s1] = 1, mp[s2] = 1, mp[s3] = 1;
	string a = "ABC", b = "ARC", c = "AGC", d = "AHC";
	if (mp[a] == 0) cout << a;
	else if (mp[b] == 0) cout << b;
	else if (mp[c] == 0) cout << c;
	else if (mp[d] == 0) cout << d;
	return 0;
}

C

依旧很水，直接映射一下，甚至不用离散化

AC code:

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

int n;
int a[200005], b[200005];

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		b[a[i]] = i;
	}
	for (int i = 1; i <= n; i++) cout << b[i] << " ";
	return 0;
}

D

有点难度，但不多。很容易想到二分一下找上界和下界，所以要维护一个数组使它插入的时候自动排好序，用 set

注意：用 set 的时候一定要用自带的二分 st.lower_bound 不然会 TLE

警钟敲烂！！！！

AC code:

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

int n, q;
set<int> st;

signed main(){
    cin >> n >> q;
    st.insert(0), st.insert(n);
    for (int i = 1, opt, x; i <= q; i++){
        cin >> opt >> x;
        if (opt == 1) st.insert(x); 
        else{
            auto it = st.lower_bound(x);
            cout << *it - *(--it) << endl;
        }
    }
    return 0;
}

E

比 D 水，直接拿一个优先队列和普通队列处理一下就好了

AC code:

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

int n;
queue<int> q;
priority_queue<int, vector<int>, greater<int>> q1;

int main(){
	cin >> n;
	for (int i = 1, opt, x; i <= n; i++){
		cin >> opt;
		if (opt == 1){
			cin >> x;
			q.push(x);
		}
		else if (opt == 2){
			if (q1.empty()) cout << q.front() << endl, q.pop();
			else cout << q1.top() << endl, q1.pop();
		}
		else{
			while (!q.empty()) q1.push(q.front()), q.pop();
		}
	}
	return 0;
}

F

”遇到组合计数的题要么是数学，要么是 dp。“

一开始见到这题感觉是数学，但是这是区间 dp。定义 \(dp_{i,j}\) 表示把 \([i,j]\) 完全消掉的方案数。

不难想到转移，如果 \(l\) 和 \(r\) 是好朋友，那么 \(dp_{l,r}=dp_{l + 1, r - 1}\)。考虑一般情况，枚举断点 \(k\)，如果 \(k\) 和 \(r\) 也是朋友关系，就可以做到先把 \([l,k-1]\) 的消掉，再消 \([k + 1,r-1]\) 最后再把 \(k,r\) 消掉，也就是 \(dp_{l,r}=dp_{l, k-1} \times dp_{k + 1,r - 1}\)，但是这种没考虑删的顺序，所以还要乘上一个 \(C_{\frac{r - l + 1}{2}}^{\frac{r-k+1}{2}}\)。注意不是阶乘，因为这两个区间内的先后顺序是确定的，只是在两个区间混起来消除的时候考虑这一次消左边还是消右边。

注意在 \(dp\) 初始化时要 \(dp_{u,v}=dp_{v,u}=1\)，不然在后面枚举断点的时候可能会出现 \(k=r-1\) 的情况，然后计算的时候就 \(k+1>r-1\) 了，但是还是算方案数的，所以反向也要记录一下。

AC code:

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

const int mod = 998244353;
int n, m;
int dp[405][405], vis[405][405], c[405][405];

signed main(){
    for (int i = 0; i <= 400; i++){
        for (int j = 0;  j <= i; j++){
            if (i == 0) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        if ((v - u + 1) % 2) continue;
        vis[u][v] = 1;
        if (u + 1 == v) dp[u][v] = dp[v][u] = 1;
    }
    for (int len = 2; len <= 2 * n; len += 2){
        for (int l = 1; l + len - 1 <= 2 * n; l++){
            int r = l + len - 1;
            if (vis[l][r]) dp[l][r] = dp[l + 1][r - 1];
            for (int k = l + 2; k < r; k += 2){
                if (vis[k][r]) dp[l][r] = (dp[l][r] + dp[l][k - 1] * dp[k + 1][r - 1] % mod * c[len / 2][(r - k + 1) / 2] % mod) % mod;
            }
        }
    }
    cout << dp[1][2 * n];
    return 0;
}

G

比 F 简单一些。前置知识：斯特林数。

先来考虑简单情况，把 \(n\) 个数分成 \(m\) 组有多少种情况？

可以定义 \(dp_{i,j}\) 表示第 \(i\) 个数之前分了 \(j\) 组有多少种情况。

转移分两种讨论：

  • \(i\) 单独开一组新的：\(dp_{i,j}=dp_{i-1,j-1}\)。

  • 把 \(i\) 放到前面的几组中：\(dp_{i,j}=dp_{i-1,j} \times j\)。乘上 \(j\) 表示可以放到前 \(j\) 组，每组 \(dp_{i-1,j}\) 种情况。

回到原题，因为有了模数的限制，问题肯定出在放到前 \(j\) 组的地方，那么要乘上多少呢？就是除了放了模数相同的数的组里。而我们已经知道前 \(i-1\) 个数中与 \(i\) 同余的数肯定不在一个格子内，而有 \(\lfloor \frac{i-1}{m}\rfloor\) 个与 \(i\) 同余的数，所以有 \(j-\lfloor \frac{i-1}{m}\rfloor\) 组是合法的，可得最后式子为：

\[dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j} \times (j-\lfloor \frac{i-1}{m}\rfloor) \]

还有一点，在转移的时候记得将合法组数和 \(0\) 取一个 \(\max\)，肯定不能取负的组数嘛。

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

const int mod = 998244353;
int n, m;
int dp[5005][5005];

signed main(){
    cin >> n >> m;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * max((j - (i - 1) / m), 0ll)) % mod;
        }
    }
    for (int i = 1; i <= n; i++) cout << dp[n][i] << endl;
    return 0;
}

AT_abc219 复盘

A

直接上 if 大法

AC code:

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

int x;

int main(){
	cin >> x;
	if (x < 40) cout << 40 - x;
	else if (x >= 40 && x < 70) cout << 70 - x;
	else if (x >= 70 && x < 90) cout << 90 - x;
	else cout << "expert";
	return 0;
}

B

暴力字符串拼接

AC code:

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

string s[5], t, ans;

int main(){
	cin >> s[1] >> s[2] >> s[3] >> t;
	for (int i = 0; i < t.size(); i++) ans += s[t[i] - '0'];
	cout << ans;
	return 0;
}

C

好像直接写一个 \(cmp\) 也可以

拿一个 map 映射新字符对应着哪一个旧字符。询问的时候转换一下新旧字符，再拿个 map 映射一下，最后输出

AC code:

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

int n;
string s, t;
map<char, char> mp;
map<string, string> pre;
vector<string> v;

int main(){
	cin >> s;
	for (int i = 0; i < s.size(); i++) mp[s[i]] = i + 'a';
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> t;
		string tmp = t;
		for (int i = 0; i < t.size(); i++) tmp[i] = mp[t[i]];
		v.push_back(tmp);
		pre[tmp] = t;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) cout << pre[v[i]] << endl;
	return 0;
}

D

很明显是一个 dp 题。

按照朴素的想法，\(dp_{i,j,k}\) 表示前 \(i\) 个盒饭 \(j\) 个 a 种， \(k\) 个 b 种，很明显这样会 RE。

转换一下 \(dp_{i,j,k}\) 表示前 \(i\) 个盒饭大于等于 \(j\) 个 a 种，大于等于 \(k\) 个 b 种，这样子只用开到 \(300 \times 300 \times 300\) 就够了。

转移分两种：

  • 取 \(i - 1\) 个盒饭就已经满足要求，\(dp_{i,j,k}=dp_{i-1,j,k}\)
  • 取第 \(i\) 个盒饭，\(dp_{i,j,k}=\min(dp_{i,j,k}, dp_{i-1,j-a[i],k-b[i]}+1)\)

basecase 很好想，肯定就是 \(dp_{0,0,0}=0\)。ans 就是 \(dp_{n,x,y}\)

AC code:

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

int n, x, y;
int a[305], b[305], dp[305][305][305];

int main(){
	cin >> n >> x >> y;
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0][0] = 0;//basecase
	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= x; j++){
			for (int k = 0; k <= y; k++){
				if (dp[i - 1][j][k] != 0x3f3f3f3f) dp[i][j][k] = dp[i - 1][j][k];//直接满足条件
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][max(j - a[i], 0)][max(k - b[i], 0)] + 1);//转移，记得特判一下边界
			}
		}
	}
	cout << (dp[n][x][y] == 0x3f3f3f3f ? -1 : dp[n][x][y]);
	return 0;
}

E

数据范围很容易想到状压，但又很容易误导成状压 dp。

只需要枚举那个点在护城河内，在去判断不合法的情况。第 4、5 种情况已经被排除了，只需要判断前三种情况。

第一种很好判断，第二种也只需要去判一下连通块是否只有一个，而第三种就有点难度了。我们发现，如果状压出来的护城河由两条的话肯定是围成了一个类似于大圆套小圆的结构，护城河包裹的是圆环，而中间那部分在状压中是没有被包裹的，这就只需要判断是否有一块没有选中的点是走不到边缘的，如果有，那一定是被圆环包裹住了，也就是不合法的情况。

最后统计答案。

第二种：335053c01a13eb99e55767a3dc02eb38.png (800×711) (atcoder.jp)

第三种：

AC code:

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

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int n = 4, ans;
int a[5][5], b[5][5], vis[5][5];

int dfs1(int x, int y){//找被护城河围起来了但不是城内的区域
    if (x <= 0 || x > n || y <= 0 || y > n) return 1;
    if (b[x][y]) return 0;
    vis[x][y] = 1;
    int flag = 0;
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if (vis[nx][ny]) continue;
        flag |= dfs1(nx, ny);
    }
    return flag;
}

void dfs(int x, int y){//找连通块
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if (nx > 0 && nx <= n && ny > 0 && ny <= n && vis[nx][ny] == 0 && b[nx][ny] == 1) dfs(nx, ny);
    }
}

int main(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    }
    for (int k = 1; k < (1 << (n * n)); k++){
        for (int i = 0; i < n * n; i++) b[i / n + 1][i % n + 1] = 1 & (k >> i);
        memset(vis, 0, sizeof(vis));
        int flag = 1, cnt = 0;
        for (int i = 1; i <= n && flag; i++){
            for (int j = 1; j <= n && flag; j++){
                if (a[i][j] == 1 && b[i][j] == 0) flag = 0;
                else if (b[i][j] == 0 && !vis[i][j]) flag = dfs1(i, j);
                else if (b[i][j] == 1){
                    if (cnt && !vis[i][j]) flag = 0;
                    else dfs(i, j), cnt++;
                }
            }
        }
        if (flag) ans++;
    }
    cout << ans;
    return 0;
}

F

updating...

AC code:

G

根号分治，简单来说就是小于某一个值和大于某个值分开来做。

这题如果用暴力就是 \(n^2\) 级别的，会炸。在想优化的过程中，我们发现如果把所有要修改的点都打上标记的话，还是在 \(n^2\) 级别的，但是变成了修改 \(O(1)\)，查询 \(O(n)\) 的东西，这种跟分块有点类似——就是根号分治。我们的目的就是平摊复杂度，修改 \(\sqrt n\)，查询 \(\sqrt{n}\)。

如何分块？只要把点分成两类，重点和轻点——重点代表所连边数大于 \(\sqrt{m}\)，轻点则相反。

轻点就可以直接在操作的时候暴力修改，而重点就可以打一个类似于线段树的 lazytag，包含一个当前颜色 color 和修改时间 time。注意，这里的 tag 是指这个重点放出的颜色的 color 和 time，而不是这个点最终颜色。

还需要预处理一下，再建一个图，只由轻点和所连接的重点构成。

具体操作时，先把要修改的那个点还原出来，也就是把与它邻接的重点的 tag 扒出来，找到修改时间最晚并且晚于当前节点修改时间的重点，覆盖掉当前节点。

并更新当前节点覆盖别的节点的 time。然后分治重点和轻点，轻点直接更新，重点打上一个 tag，等到下次要用到这个重点的时候再按上一个步骤中的操作还原到需要的节点上。

对于复杂度的证明，重点不超过 \(\sqrt{m}\) 个，于是还原节点最多 \(O(\sqrt{m})\)；打上 tag 的复杂度为 \(O(1)\)；轻点所连的边不超过 \(\sqrt{m}\)，更新一次复杂度也不超过 \(\sqrt{m}\)。

预处理阶段，只连接轻点的重点，不超过 \(n \sqrt{n}\)；最后输出操作也不超过 \(n \sqrt{m}\)。总复杂度在 \(n\sqrt{n}\) 级别，可以过。

AC code:

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

int n, m, q, len;
int col[200005], tim[200005];//最终答案和标记时间
int col1[200005], tim1[200005];//重点放出的color和放出时间
vector<int> g[200005], e[200005];//完整的图和每一个轻点连向重点的图

int find(int x){//找到更新时间最晚的重点
    int mxt = tim[x], tmp = col[x];//先记录当前节点更新时间，便于后面判断是否晚于当前节点
    for (int i = 0; i < e[x].size(); i++){
        int v = e[x][i];
        if (mxt < tim1[v]) mxt = tim1[v], tmp = col1[v];
    }
    return tmp;
}

int main(){
    cin >> n >> m >> q;
    len = sqrt(m);
    for (int i = 1; i <= n; i++) col[i] = i;
    for (int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++){
        if (g[i].size() < len) continue;
        for (int j = 0; j < g[i].size(); j++) e[g[i][j]].push_back(i);//只记录轻点连向重点的边，达到 根号 m 的复杂度
    }
    for (int _ = 1, x; _ <= q; _++){
        cin >> x;
        col[x] = find(x), tim[x] = _;
        if (g[x].size() >= len) col1[x] = col[x], tim1[x] = _;//重点打上lazytag
        else{
            for (int i = 0; i < g[x].size(); i++) col[g[x][i]] = col[x], tim[g[x][i]] = _;//轻点直接更新
        }
    }
    for (int i = 1; i <= n; i++) cout << find(i) << " ";//跟上面还原 col[x] 一个道理
    return 0;
}

AT_abc238 复盘

A

挺简单的，简单画个图或者枚举一下

AC code:

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

int n;

int main(){
	cin >> n;
	if (n >= 2 && n <= 4) cout << "No";
	else cout << "Yes";
	return 0;
}

B

把每个切点丢到数组里或优先队列，然后一个一个出队看最大的块

注意要把 0 和 360 也放进去

AC code:

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

int n, a, lst, ans;
priority_queue<int> q;

int main(){
	cin >> n;
	q.push(0);
	for (int i = 1; i <= n; i++){
		cin >> a;
		lst = (lst + a) % 360;
		q.push(lst);
	}
	q.push(360);
	while (q.size() > 1){
		int x = q.top(); q.pop();
		int y = q.top();
		ans = max(ans, x - y);
	}
	cout << ans;
	return 0;
}

C

简简单单一个公式，稍微在草稿纸上推一下每一位的公式

but 在写完之后公式错了。。。加上有一个地方没有模调了 1h。。。

AC code:

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

const int mod = 998244353;
int n, ans;

signed main(){
	cin >> n;
	int lst = 0;
	for (; pow(10, lst + 1) <= n; lst++){
		ans = (ans + (1 + (int)pow(10, lst + 1) - (int)pow(10, lst)) % mod * (((int)pow(10, lst + 1) - (int)pow(10, lst)) % mod) / 2) % mod;
	}
	ans = (ans + (1 + n - (int)pow(10, lst) + 1) % mod * ((n - (int)pow(10, lst) + 1) % mod) / 2) % mod;
	cout << ans;
	return 0;
}

D

D 有点抽象，但不多

首先考虑结论，容易得到如果 \(a \ge s\) 时肯定不行

之后举几个例子发现 \(s\) 减去了 \(x,y\) 中的两个 \(a\) 之后剩下的数合法情况与 \(a\) 是为 \(0\) 的，而且这个剩下的数大于 \(0\)。

很简单，如果剩下的数那几位还是 \(1\)，就说明 \(x\) 和 \(y\) 中有一位是 \(1\) (不可能是进位上来的，前面都是最多一位为 \(1\))，那么加上 \(a\) 再与会发现这一位与出来是 \(0\)。

AC code:

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

int t, a, b;

signed main(){
    cin >> t;
    while (t--){
        cin >> a >> b;
        int s = b - 2 * a;
        if (s < 0 || (s & a) != 0) cout << "No\n";
        else cout << "Yes\n";
    }
    return 0;
}

E

很难想到可以用并查集。

在输入每一个数据的时候建一条 \((u-1,v)\) 的边，并放入并查集。最后判断 \(0\) 和 \(n\) 是否联通。

非常神奇，模拟一下发现这就等同于要求有好几个区间连续拼成一整个区间。

AC code:

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

int n, q;
int fa[200005];

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y){
    fa[find(y)] = find(x);
}

signed main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, u, v; i <= q; i++){
        cin >> u >> v;
        merge(u - 1, v);
    }
    cout << ((find(0) == find(n)) ? "Yes" : "No");
    return 0;
}

F

贪心+dp

先按 \(a\) 排一边序，定义 \(dp_{i,j,k}\) 表示前 \(i\) 位取了 \(j\) 位未选最小值为 \(k\)。

考虑转移，我们发现枚举到 \(i\) 时通过 \(i-1\) 转移不好转，考虑从 \(i\) 转到 \(i + 1\)。

分两种情况讨论：

  • 取这个数，因为 \(a_i\) 肯定大于前面的，只能是 \(b_i < k\) 才能转，\(dp_{i + 1,j + 1,k}+=dp_{i,j,k}\)。
  • 不取这个数，那么就要转移到 \(min(k,b_i)\) 上，\(dp_{i+1,j,\min{b_i},k}+=dp_{i,j,k}\)。

最后答案就是 \(\sum_{i=1}^{n+1}{dp_{n,m,i}}\)，这里 \(n\) 可能等于 \(k\)，所以要枚举到 \(n+1\)。

AC code:

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

const int mod = 998244353;
int n, m, ans;
int dp[305][305][305];
struct node{
    int p, q;
}a[305];

bool cmp(node x, node y){
    return x.p < y.p;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].p;
    for (int i = 1; i <= n; i++) cin >> a[i].q;
    sort(a + 1, a + n + 1, cmp);
    dp[0][0][n + 1] = 1;
    for (int i = 0; i < n; i++){
        for (int j = 0; j <= m; j++){
            for (int k = 1; k <= n + 1; k++){
                if (a[i + 1].q < k && j != m) dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k]) % mod;
                dp[i + 1][j][min(k, a[i + 1].q)] = (dp[i + 1][j][min(k, a[i + 1].q)] + dp[i][j][k]) % mod;
            }
        }
    }
    for (int i = 1; i <= n + 1; i++) ans = (ans + dp[n][m][i]) % mod;
    cout << ans;
    return 0;
}

标签：abc,int,namespace,cin,2024,code,include,复盘,dp
From： https://www.cnblogs.com/ccf-ioi/p/18062554

相关文章

  • P10217 [省选联考 2024] 季风题解
    考场上没写出来，火大，实际上这题放校内%你赛我肯定写的出来，可惜这是省选。实际上这题不难，主要是观察性质，接着拆柿子，然后就是有点难写，要写得好看有点考验代码构建能力和数学能力。我们考虑原题的每对\((x,y)\)都要满足\(|x|+|y|\lek\)而我们可以知道后面应该填的\((x,y)\)如......
  • [ABC297F] Minimum Bounding Box 2 题解
    容斥真有趣。有一个性质：两个相同的子矩阵，对答案的贡献一定相同。所以就只需要枚举矩阵大小即可。我们设当前矩阵长\(i\)宽\(j\)（对应的，\(H\)为长，\(W\)为宽），假如要给答案做出贡献，矩阵的四条边一定都有点，发现可以容斥了。至少\(0\)条边上有点的方案数为\(a=C_{i\times......
  • 2024省选游记
    \(Day\1\)按着不爆\(0\)的目标打省选（反正我才初二）。\(8:20\)拿到试题，\(T1\)不会，\(T2\)不会，\(T3\)不会。之后的两个小时尝试写\(T1\)正解（事实证明我想的离正解不远），一直调调调，没条出来，\(10:30\)时还一分没得。没办法，只能打特殊性质，\(40\)分。此时\(11:20......
  • 2024省选游记
    我来自ZJ,非常菜，别人在考省选，而我却像在考CSP。Day-1稍微补了点题，然后复习了下板子和之前写的博客。总结了下思路来源1.因为是序列上的问题，不难想到是一道数据结构题。2.在构造题中看到相等，我们就能想到各种-1和1相抵消。3.二进制想到拆位4.在图中的约束条件想到并查集5.......
  • 2024.3.9 笔记
    2024.3.9笔记P1948题目大意为在无向图上求出从\(1\)到\(N\)的路径，使路径上第\(k+1\)大的边权尽量少。第一种是DP用\(f[i][j]\)表示从\(1\)到点\(i\)，用了\(j\)条免费线的最小花费。对于一条\(u->v\)的边\(e\)有转移：不用免费线\(f_{v,k}=min(f_{v,k},max......
  • abc230E n/i分数求和
    题面：给定n，计算$\sum_{i=1}^{n}\frac{n}{i}$范围：1<=n<=1E12思路：分块，假设区间[l,r]的结果都相同，即n/l=n/r，根据l可以推算出r，那么这个区间对结果的贡献就是区间长度乘以结果，时间复杂度为O(sqrtn)。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#define......
  • abc342D 乘积为完全平方数的对数
    题面：给定长为n的数组A，问有多少对下标(i,j)满足A[i]*A[j]为完全平方数？范围：n<=2E5;A[i]<=2E5思路：完全平方数即质因子的个数为偶数，因此对元素进行化简，把偶次质因子都去掉，再统计即可。另外，0乘任何数都为0，需要单独处理。#include<bits/stdc++.h>usingnamespacestd;#defineint......
  • abc323D 合并泥巴
    题面：有n种泥巴，第i种有c[i]块，大小为s[i]。每次操作可以选择2块大小同为x的泥巴，将其合并成1块大小为2x的泥巴。操作次数不限，问最终至少有多少块泥巴？范围：n<=1E5;s[i],c[i]<=1E9思路：贪心，从小到大，能合并就合并，结果肯定是最少的。注意map的使用，如何实现边遍历边删除。#include<bits......
  • abc317D 选举总统
    题面：有n个区，第i个区有x[i]+y[i]个选民，其中x[i]支持A，y[i]支持B，支持人数多的一方获得该区的全部票数z[i]，全部区的票数之和多者获胜，问至少还要多少选民从支持B改为支持A，才能让A胜出？范围：1<=n<=100;0<=x[i],y[i]<=1E9;x[i]+y[i]为奇数,z[i]>=1，z[i]之和为奇数且不超过1E5。思路：将各......
  • abc325E 火车+班车的最短路
    题面：有n座城市，从城市i到城市j可以坐班车，需要A*D[i][j]时间，也可以坐火车，需要B*D[i][j]+C时间。可以从班车换到火车，但反过来不行。换乘时间不计，求从城市1到城市n的最短时间。范围：n<1000;A,B,C<1E6;D[i]][j]<1E6并且D[i][i]=0。思路：先预处理出任意两城市之间的耗时，包括班车D[i][j......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99