给一个长度为偶数的字符串，第 个字符为 ，对于所有的 ，交换 与 。
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
for (int i = 0; i + 1 < s.length(); i += 2)
{
swap(s[i], s[i + 1]);
}
cout << s << "\n";
return 0;
}
有 个人，编号为 。每个人都有一张卡片，第 个人的卡片上写的是 。
现在从第一个人开始，如果这个人没有被喊过，就喊一下他卡片上写着的人。
问最终有多少个人从没被喊过。
#include <bits/stdc++.h>
using namespace std;
int n;
bool vis[212345];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
int ai;
cin >> ai;
if (!vis[i])
vis[ai] = true;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
cnt += (!vis[i]);
cout << cnt << "\n";
for (int i = 1; i <= n; i++)
if (!vis[i])
cout << i << " ";
return 0;
}
给定一个 行 列的矩阵，每次可以往右或往下走，问从 走到 有多少条路径满足下面的要求：“路径上的数没有重复的”
考虑到数据范围，暴力枚举所有路径即可。
#include <bits/stdc++.h>
using namespace std;
int h, w, ans;
int a[15][15];
int path[15];
void dfs(int x, int y, int step)
{
if (x > h)
return;
if (y > w)
return;
path[step] = a[x][y];
for (int i = 1; i < step; i++)
if (path[i] == path[step])
return;
if (x == h && y == w)
ans++;
dfs(x + 1, y, step + 1);
dfs(x, y + 1, step + 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> h >> w;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
cin >> a[i][j];
ans = 0;
dfs(1, 1, 1);
cout << ans << "\n";
return 0;
}
给 根绳子，每根绳子的两端分别为蓝色与红色。
有 次操作，第 次操作为：，表示把第 根绳子的 颜色端和第 根绳子的 颜色端连在一起。保证每根绳子的每个颜色端最多被连接一次。
问最终有多少个环，和多少个链。
建图，dfs 判断是环还是链
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a, c;
char b, d;
int tot;
int id[212345][2]; // id[i][col=='R'] 的点编号
pair<int, int> e[412345]; // i号点连接到的(线段，端点)
bool visL[212345]; // 第i条线段是否走过了
bool visP[412345]; // 第i条端点是否走过了
void dfs(int LineId, int PointId)
{
if (visP[PointId])
return;
//cout<<LineId<<" "<<PointId<<"\n";
visL[LineId] = true;
visP[PointId] = true;
int temp = id[LineId][0];
if (temp == PointId)
temp = id[LineId][1];
pair<int, int> nxt = e[temp];
if (nxt.first == 0)
return;
dfs(nxt.first, nxt.second);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tot = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 1; j++)
{
id[i][j] = ++tot;
//cout<<i<<":"<<j<<" = "<<tot<<endl;
}
for (int i = 1; i <= m; i++)
{
cin >> a >> b >> c >> d;
int u = id[a][b == 'R'];
int v = id[c][d == 'R'];
e[u] = make_pair(c, v);
//cout<<u<<" "<<c<<"~"<<v<<endl;
e[v] = make_pair(a, u);
//cout<<v<<" "<<a<<"~"<<u<<endl;
}
for (int i = 1; i <= n; i++)
visL[i] = false;
for (int i = 1; i <= tot; i++)
visP[i] = false;
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i++)
{
if (visL[i])
continue;
//cout<<"start"<<i<<" "<<id[i][0]<<"\n";
if (e[id[i][0]].first != 0)
dfs(e[id[i][0]].first, e[id[i][0]].second);
if (visP[id[i][1]])
ans1++;
else
ans2++;
//cout<<"start"<<i<<" "<<id[i][1]<<"\n";
if (e[id[i][1]].first != 0)
dfs(e[id[i][1]].first, e[id[i][1]].second);
}
cout << ans1 << " " << ans2 << endl;
return 0;
}
显然如果某两根绳子被连接之前已经联通了，就构成了环。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a, c;
char b, d;
int fa[200005];
int findFa(int x)
{
if (fa[x] == x)
return x;
return fa[x] = findFa(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
fa[i] = i;
int ans1 = 0; // 环的数量
int ans2 = n; // 非环联通块的数量
for (int i = 1; i <= m; i++)
{
cin >> a >> b >> c >> d;
if (findFa(a) == findFa(c))
{
ans1++;
ans2--;
}
else
{
ans2--;
fa[findFa(a)] = findFa(c);
}
}
cout << ans1 << " " << ans2 << "\n";
return 0;
}
给定 ，求
已经搬到了 33OJ：等比数列求和
考虑到有可能 ，不能直接等比数列求和。
.
可以转为为递推式：
然后矩阵快速幂加速递推即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXR = 3; // 矩阵最大行数
const int MAXC = 3; // 矩阵最大列数
int MOD;
struct Mat
{
int r, c; // 行数列数
int m[MAXR + 1][MAXC + 1];
Mat() { memset(m, 0, sizeof(m)); }
};
Mat operator*(const Mat &a, const Mat &b)
{
assert(a.c == b.r);
Mat res;
res.r = a.r, res.c = b.c;
for (int i = 1; i <= a.r; i++)
for (int k = 1; k <= a.c; k++)
{
int temp = a.m[i][k];
for (int j = 1; j <= b.c; j++)
res.m[i][j] = (res.m[i][j] + temp * b.m[k][j]) % MOD;
}
return res;
}
Mat quick_pow(Mat a, int b)
{
assert(a.r == a.c);
Mat res;
res.r = res.c = a.r;
for (int i = 1; i <= res.r; i++)
res.m[i][i] = 1;
while (b > 0)
{
if (b % 2)
res = res * a;
a = a * a;
b = b / 2;
}
return res;
}
signed main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int a, x;
cin >> a >> x >> MOD;
// 构造矩阵
Mat now;
now.r = 1, now.c = 3;
now.m[1][1] = 1, now.m[1][2] = a + 1, now.m[1][3] = 1;
Mat ans;
ans.r = ans.c = 3;
ans.m[1][1] = 0, ans.m[1][2] = 0, ans.m[1][3] = 0;
ans.m[2][1] = 1, ans.m[2][2] = a, ans.m[2][3] = 0;
ans.m[3][1] = 0, ans.m[3][2] = 1, ans.m[3][3] = 1;
// 计算答案
ans = quick_pow(ans, x - 1);
now = now * ans;
cout << now.m[1][1] % MOD << "\n";
return 0;
}
/*
((1*a+1)*a+1)*a+1 ...
f(0) = 1
f(x) = f(x-1)*a+1
[A11, A12, A13] * M
= [A11*M11+A12*M21+A13*M31,
A11*M12+A12*M22+A13*M32,
A11*M13+A12*M23+A13*M33]
[f0, f1, 1] * M
= [f1, f2, 1]
= [f1, f1 * a + 1, 1]
M = 0 0 0
1 a 0
0 1 1
*/
给定一个不小于 的整数 ，请找到有多少个 满足：
不小于
在 进制下每一位都是 或 。
：T 组询问
.
首先 肯定符合。然后我们发现 的上限可以达到 。这有点过大了，但是当 很大时， 进制下的 位数是不多的。
可以考虑枚举每个小范围的 。大范围内直接考虑 的所有可能的 进制下的构成。，所以当 时， 进制下的 位数最多只有 位，每一位都是 只有 种可能。可以考虑每一种可能能不能找到一个 来达成。
如果 在 进制下为：，即 ，那么显然可以二分查找是否存在 使得
最终时间复杂度：
然后 组数据，综合粗算一下，
#include <bits/stdc++.h>
#define int long long
using namespace std;
// 检查 A 在 B 进制下是否为全 0/1
bool check1(int A, int B)
{
while (A > 0)
{
if (A % B > 1)
return false;
A /= B;
}
return true;
}
// 返回 sta 这样的 01 对应的 B 进制
// 如果硬算，可能会爆 ll，加一个 A 的上限限制
int cal(int B, int sta, int A)
{
int res = 0;
int now = 1;
while (sta > 0)
{
if (sta % 2 == 1)
{
res += now;
if (res > A)
return A + 1;
}
sta /= 2;
if (now > A / B + 1 && sta > 0)
return A + 1;
now *= B;
}
return res;
}
//检查能否找到某个 B 使得 B 进制下“sta 的 01 构成”这个数为 A
bool check2(int A, int sta)
{
int l = 1001;
int r = A;
bool res = false;
while (l <= r)
{
int mid = (l + r) / 2; // 检查 mid 进制
int now = cal(mid, sta, A);
if (now == A)
return true;
if (now < A)
l = mid + 1;
if (now > A)
r = mid - 1;
}
return false;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T, A;
cin >> T;
while (T--)
{
cin >> A;
int ans = 1; // B==2 不检查
for (int B = 3; B <= min(1000LL, A); B++)
ans += check1(A, B);
if (A > 1000)
for (int sta = 1; sta <= (1 << 6) - 1; sta++)
ans += check2(A, sta);
cout << ans << "\n";
}
return 0;
}
给定一个长度为 的序列：。 次询问，第 次询问 ，求 区间有多少个三元组 使得：
一眼莫队
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200000;
const int MAXQ = 200000;
const int MAXAI = 200000;
int n, q;
int a[MAXN + 5];
int id[MAXN + 5]; // id[i]：a[i]所属的块编号
struct Q
{
int l, r, id;
} p[MAXQ + 5];
int ans[MAXQ + 5];
bool cmp(const Q &x, const Q &y)
{
if (id[x.l] == id[y.l])
{
if (id[x.l] % 2)
return x.r < y.r;
else
return x.r > y.r;
}
return x.l < y.l;
}
int now, cnt[MAXAI + 5];
int cal(int x)
{
if (x <= 2)
return 0;
return x * (x - 1) * (x - 2) / 6;
}
void add(int pos)
{
// cout << "add " << a[pos] << endl;
// 新增一个a[pos]
now -= cal(cnt[a[pos]]);
cnt[a[pos]]++;
now += cal(cnt[a[pos]]);
// cout << "=" << now << endl;
}
void del(int pos)
{
// cout << "del " << a[pos] << endl;
// 删去一个a[pos]
now -= cal(cnt[a[pos]]);
cnt[a[pos]]--;
now += cal(cnt[a[pos]]);
// cout << "=" << now << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
int nn = sqrt(n);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
id[i] = i / nn;
}
for (int i = 1; i <= q; i++)
{
cin >> p[i].l >> p[i].r;
p[i].id = i;
}
sort(p + 1, p + q + 1, cmp);
int L = 1, R = 0;
now = 0;
for (int i = 1; i <= q; i++)
{
// cout << L << "~" << R << " -> " << p[i].l << "~" << p[i].r << endl;
while (R < p[i].r)
add(++R);
while (L > p[i].l)
add(--L);
while (R > p[i].r)
del(R--);
while (L < p[i].l)
del(L++);
// cout << "====" << now << endl;
ans[p[i].id] = now;
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
return 0;
}