C
爆搜，这里不再多说，直接上代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20;
int n, m;
int a[N][N], ans;
map<int, bool> t;
void dfs(int x, int y) {
if (x == n && y == m) {
if (!t[a[x][y]]) ans++;
return;
}
if (t[a[x][y]]) return;
t[a[x][y]] = 1;
if (x < n) dfs(x + 1, y);
if (y < m) dfs(x, y + 1);
t[a[x][y]] = 0;
return;
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
dfs(1, 1);
cout << ans << endl;
return 0;
}
D
前置知识
- 并查集
思路
因为数据保证合法，所以其实绳子哪一端相连并不重要，故读入时直接 ignore， 我们只考虑每一次操作中是否产生了新环，而产生新环的条件即为，两条绳子在之前的操作中已经被绑在了一条绳子里，用并查集判断即可，同时，在每一次合并时，都有两条绳子变为一条，或者一条绳子变成了环，由此可得，只要有一次合并，没有形成环的绳子数就会减少一条，故最终未形成环的绳子数为
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, ans;
int f[N];
int find(int x) {
if (f[x] == x) return x;
return (f[x] = find(f[x]));
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1; i <= m; i++) {
int u, v;
char p;
scanf("%lld %c %lld %c", &u, &p, &v, &p);
int p1 = find(u), p2 = find(v);
if (p1 == p2) ans++;
f[p1] = p2;
}
cout << ans << " " << n - m << endl;
return 0;
}
E
前置知识
- 快速幂
思路
等比公式，初中数学，只需快速幂即可 具体公式为：
推导过程：
然而，在这一过程中，我们惊奇地发现，居然有取余这一操作，这样一来，我们的除法将直接寄飞，但是与此同时，题目中又并不保证 为质数，故非常悲惨，我们似乎进入了一种进退两难的处境
当然，笔者已经找到了一种无比神奇的做法，将 ， 这样以来，则在计算的过程中，我们必然保证了答案的整除性
注意
记得特判 和 取模后为 的情况
#include<bits/stdc++.h>
#define int __int128
using namespace std;
long long mod, a, x;
__int128 qpow(int a, int b){
if (b == 0) return 1;
int res = qpow(a, b / 2);
if (b % 2) return res * res % mod * a % mod;
return res * res % mod;
}
signed main(){
cin >> a >> x >> mod;
if (a == 1) {
cout << x % mod << endl;
return 0;
}
mod *= a - 1;
int p = qpow(a, x);
if (!p) p = mod;
cout << (long long)((p - 1) / (a - 1)) << endl;
return 0;
}
// 令 S = a^0 + a^1 + a^2 + ... + a^ (x - 1)
// S * a = a^1 + a^2 + a^3 + ... + a ^ x
// S * (a - 1) = a ^ x - a ^ 0
// S = (a ^ x - 1) / (a - 1)
// 1 ^ 0 + 1 ^ 1 = 2;
// 114514 114514 114514
F
题意
组数据，每组一个正整数 ，保证 ，对于每个 求满足条件的 的个数，使得 的 进制表示只包含 或
思路
对于这道题，我们可以从暴力出发，逐步优化
暴力枚举，对于这道题来讲并不难，无非就是枚举每种进制即可，复杂度
然而，我们发现，因为每种进制都有可能，所以我们似乎必然要进行每一个枚举，但由于这道题 ，我们只能望而却步，于是，我们将目光投向第二个条件：使得 的 进制表示只包含 或 ，故我们可以对 数列进行枚举，对于每一个数列，我们都用二分找到最接近的进制，使得其的十进制转换后为 , 复杂度取决于数列长度，因此，我们发现，其复杂度也相当炸裂
然而，我们可以考虑将二者结合，我们便可得到一个极优的时间复杂度，我们将进制数先枚举至 , 故绝大部分的数字都已被枚举，需要枚举的数列长度被极大缩短，至多为 , 这时，我们再进行枚举即可
代码
#include<bits/stdc++.h>
#define ll long long
#define int __int128
using namespace std;
ll T, n;
int ans;
int check(int x, int tot) {
int s = 0, p = 1;
for (int i = 0; i <= 5; i++) {
if ((1 << i) & tot) {
s += p;
// if (s < 0) return n + 1;
if (s > n) return 2e18;
}
if (p > 1e18 / x) p = 2e18;
else p *= x;
}
return s;
}
void Tmain() {
ans = 0;
scanf("%lld", &n);
for (int i = 2; i <= min(n, 1000ll); i++) {
int tot = n, flag = 1;
while (tot) {
if (tot % i > 1) {
flag = 0;
break;
}
tot /= i;
}
ans += flag;
}
if (n <= 1000) {
cout << (signed)ans << endl;
} else {
for (int i = 1; i <= (1 << 6) - 1; i++) {
int l = 0, r = 1e18;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid, i) >= n) r = mid;
else l = mid;
}
if (check(l, i) == n && l > 1000) ans++;
if (check(r, i) == n && r > 1000) ans++;
}
cout << (signed)ans << endl;
}
return;
}
signed main(){
cin >> T;
while (T--) Tmain();
return 0;
}
G
前置知识
- 莫队（不会可以看这里）
- 分块
思路
我们看到没有修改，且不强制在线，而且可以快速处理加点删点对答案的贡献，显然是莫队板子。
（哈哈，今天终于可以试一试自学的莫队了）
首先，我们要思考的就是怎样删点和增点，
当我们加入一个新点时，我们便可以对其进行判断，其是否在这个区间中有了同样的另外两个点，
若在操作过后，有 ， 则这个点对于其他点的贡献即为 因为这个点可任取另外两个点，同时两个点的相对位置可能出现重复，故要 ，最终的结果为
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 1000;
int n, Q, now;
struct Node {
int num, l, r;
}q[N];
int a[N], f[N], cnt[N], ans[N];
bool cmp(Node x, Node y) {
int t1 = f[x.l], t2 = f[y.l];
if (t1 != t2) return t1 < t2;
if (t1 % 2) return x.r > y.r;
return x.r < y.r;
}
void init() {
int size = sqrt(n); // 表示每块长度
int l = (n + size - 1) / size;
for (int i = 1; i <= l; i++)
for (int j = (i - 1) * size + 1; j <= i * size; j++)
f[j] = i;
}
void del(int x) {
if (cnt[a[x]] >= 3) now -= (cnt[a[x]] - 1) * (cnt[a[x]] - 2) / 2;
cnt[a[x]]--;
}
void add(int x) {
cnt[a[x]]++;
if (cnt[a[x]] >= 3) now += (cnt[a[x]] - 1) * (cnt[a[x]] - 2) / 2;
}
signed main(){
cin >> n >> Q;
init();
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= Q; i++) scanf("%lld %lld", &q[i].l, &q[i].r), q[i].num = i;
sort(q + 1, q + 1 + Q, cmp);
int l = 1, r = 0;
for (int i = 1; i <= Q; i++) {
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
while (l < q[i].l) del(l++);
while (r > q[i].r) del(r--);
ans[q[i].num] = now;
}
for (int i = 1; i <= Q; i++) cout << ans[i] << endl;
return 0;
}
共 1 条回复
不好意思，已补发