官方題解
A . 串
考察點：動態規劃
這一題用到的是動態規劃，對于
d
p
[
i
]
dp[i]
dp[i]表示的是成都為
i
i
i的字串方案數是多少，現在考慮前一個狀態對于后一個狀態的影響，
- 第一種情況 i i i這個長度的字串里有"us"，那第 i + 1 i+1 i+1個位置就隨便填，方案數就是 d p [ i ] ? 26 dp[i]*26 dp[i]?26，
- 第二種情況前
i
i
i的字串里只有"s"沒有“us”，那第
i
i
i位置就只填"s"，方案數就是，
2
6
i
?
d
p
[
i
]
?
2
5
i
26^i-dp[i]-25^i
26i?dp[i]?25i，其中
d
p
[
i
]
dp[i]
dp[i]表示有"us"的方案數，
2
5
i
25^i
25i表示不填"u"的情況，
還有一點就是要注意取模，下面是遞推代碼，
ll d[N];
int main() {
int n;
cin >> n;
d[2] = 1ll;
for (int i = 3; i <= n; i++)
d[i] = (d[i - 1] * 26 % mod + qpow(26, i - 1, mod) - d[i - 1] - qpow(25, i - 1, mod) + mod) % mod;
ll ans = 0ll;
for (int i = 2; i <= n; i++)
ans = (ans + d[i]) % mod;
cout << ans << endl;
return 0;
}
經典中的經典演算法:動態規劃
kuangbin動態規劃入門專題
B . 括號
考察點：構造
簡單的構造題，構造方法有很多，
C . 紅和藍
考察點：dfs，圖論
這題還是比較有難度的，對于這個題最主要的是找到性質，一共有兩種寫法，在這里參考一下別人的一份題解，
上面的講解都很詳細，我在這題不過多贅述，下面是代碼，
第一種解法
const int N = 1e5 + 10;
vector<int>G[N];
int ji[N], cnt, col[N];
bool flag = 0;
void dfs(int x, int fa) {
int son = 0;
for (auto v : G[x]) {
if (v == fa)continue;
dfs(v, x); //先遍歷子樹這樣才能保證每個節點被標記
son++;
}
if (son == 0 || ji[x] == 0) { //如果這個點沒被標記但是他不是葉子說明他和他的子節點不一樣只能和父親節點一樣
if (ji[fa] != 0) {
flag = 1;
return;
}
ji[fa] = ji[x] = ++cnt;
}
}
void dfs2(int x, int fa) {
for (auto v : G[x]) {
if (v == fa)continue;
if (ji[x] == ji[v])col[v] = col[x];
else col[v] = col[x] ^ 1;
dfs2(v, x);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
if (flag || ji[0]) { //如果根節點和0被標記了說明根節點與他的子節點都不相同，這是不可能的
puts("-1");
return 0;
}
col[1] = 0; //0/1都一樣
dfs2(1,0);
for (int i = 1; i <= n; i++) {
if (col[i] == 1)cout << 'R';
else cout << 'B';
}
cout << endl;
return 0;
}
出題人解法
const int N = 1e5 + 10;
vector<int>G[N];
int sizen[N];
void dfs(int x, int fa) { //找每個子樹的大小
sizen[x] = 1;
for (auto v : G[x]) {
if (v == fa)
continue;
dfs(v, x);
sizen[x] += sizen[v];
}
}
int ji[N], cnt;
int flag = 0;
void dfs2(int x, int fa) {
if (ji[x] == 0) {
int odd = 0, id = 0;;
for (auto v : G[x]) {
if (v == fa)continue;
if (sizen[v] % 2) {
odd++, id = v;
}
if (odd > 1) {
flag = 1;
return;
}
}
if (!odd) {
flag = 1;
return;
}
ji[x] = ji[id] = ++cnt;
}
for (auto v : G[x]) {
if (v == fa)continue;
dfs2(v, x);
}
}
int clo[N];
void dfs3(int x, int fa) {
for (auto v : G[x]) {
if (v == fa)continue;
if (ji[x] == ji[v])clo[v] = clo[x];
else clo[v] = clo[x] ^ 1;
dfs3(v, x);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 0);
if (flag) {
cout << -1 << endl;
return 0;
}
clo[1] = 1;
dfs3(1, 0);
for (int i = 1; i <= n; i++) {
if (clo[i] == 1)cout << 'R';
else cout << 'B';
}
cout << endl;
return 0;
}
D . 點一成零
考察點：并查集
這題主要考的是并查集維護連通塊大小和數量，不要被題目嚇到，這題雖然代碼量大，但是很好想，
這里提供一個并查集經典例題的講解
這題主要思路是，我們對于這個二維圖，把他們的坐標轉化成一維即
(
x
,
y
)
?
>
x
?
n
+
y
(x,y)->x*n+y
(x,y)?>x?n+y，把坐標轉化為一維以后我們用并查集，來維護每個連通塊的大小，還有連通塊的數量，初始化我們把每個點當成一個單獨的連通塊（大小為1），然后對于沒個為1的點，我們遍歷他的相鄰點，如果也為1，就合并，同時因為每次合并的操作對連通塊數量的改變最多為1，答案很好維護，
下面是代碼，
ll qpow(ll a, ll b, ll mod) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
inline ll inv(ll a, ll p) { return qpow(a, p - 2, p); } //這里是求逆元的操作
const int N = 250015;
char s[505][505];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int pre[N];
int sizen[N];
int n;
int get_id(int i, int j) {
return i * n + j;
}
int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
ll ans = 1ll; //記錄答案
int cnt = 0; //記錄連通塊的數量
void unioun(int x, int y) {
int xx = find(x), yy = find(y);
if (xx == yy)return;
ans = ans * inv(cnt, mod) % mod;
cnt--;
ans = ans * inv(sizen[xx], mod) % mod * inv(sizen[yy], mod) % mod;
ans = ans * (sizen[xx] + sizen[yy]) % mod;
sizen[xx] += sizen[yy];
pre[yy] = xx;
}
int main() {
#ifdef MPDFDFL
freopen("D:/input.txt", "r", stdin);
//freopen("D:/output.txt", "w", stdout);
#endif
cin >> n;
for (int i = 0; i < n; i++)
scanf("%s", s[i]);
for (int i = 0; i <= n * n + 10; i++)
pre[i] = i;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (s[i][j] == '1')
ans = (ans * ++cnt) % mod, sizen[get_id(i, j)] = 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (s[i][j] == '1') {
for (int k = 0; k < 4; k++) {
int sx = dx[k] + i, sy = j + dy[k];
if (s[sx][sy] == '1')
unioun(get_id(i, j), get_id(sx, sy));
}
}
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (s[x][y] == '1') {
cout << ans << endl;
continue;
}
s[x][y] = '1';
sizen[get_id(x, y)] = 1;
cnt++;
ans = ans * cnt % mod;
int flag = 0;
for (int i = 0; i < 4; i++) {
int sx = dx[i] + x, sy = y + dy[i];
if (s[sx][sy] == '1') {
flag = 1;
unioun(get_id(sx, sy), get_id(x, y));
}
}
cout << ans << endl;
}
return TIME;
}
E . 三棱錐之刻
考察點：計算幾何
高中立體幾何知識，自己推公式即可，
F . 對答案一時爽
考察點：貪心
簽到題，
G . 好玩的數字游戲
考察點：模擬
按照題意模擬即可
H . 冪塔個位數的計算
考察點：歐拉降冪，找規律
這題官方題解里給的是找規律，這里不在多講，主要講一下歐拉降冪的解法，
這是一個歐拉降冪的演算法講解
這一題其實是歐拉降冪的一個經典例題的延申，
如果懂了上面哪一題以后這題就非常好理解，很明顯這題雖然不是無限的，但是模數是固定的，就是10，所以根據歐拉函式，他最多迭代四層，之后答案就不會在改變了，這里我們控制一下迭代層數，還有每次次迭代處理的模數，這題就解決了，
ll qpow(ll a, ll b, ll mod) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
const int mod = 1e9 + 7;
int phi[15];
int mo(string x,int MOD) {
int len = SZ(x);
int res = 0;
for (int i = 0; i < len; i++)
res = (res*10 + x[i] - '0') % MOD;
return res;
}
int f(string x, int MOD,int cnt) {
if (MOD == 1)return 0;
if (cnt == 1)return mo(x, MOD);
return (qpow(mo(x, MOD) , f(x, phi[MOD], cnt - 1) + phi[MOD], MOD) + MOD) % MOD;
}
int main() {
phi[10] = 4, phi[4] = 2, phi[2] = 1;
string a, b;
cin >> a >> b;
int cnt = 0;
if (SZ(b) > 1)cnt = 10;
else cnt = min(10, b[0] - '0');
cout << (f(a, 10, cnt) % 10 + 10) % 10 << endl;
return 0;
}
I . 限制不互素對的排列
考察點：構造
這題同樣是一個簡單的構造，構造方法很多這里不在多講，
J . 一群小青蛙呱蹦呱蹦呱
考察點：素數篩
這里參考一下別人的一個題解講的很好，
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 2e8 + 10;
ll Pow(ll x, ll y)
{
ll res = 1;
while (y)
{
if (y & 1)
res = res*x%mod;
y >>= 1;
x = x*x%mod;
}
return res;
}
bool vis[N]; int p[12000000];
int tot;
void init()
{
for (int i = 2; i < N; i++)
{
if (!vis[i])
p[++tot] = i;
for (int j = 1; j <= tot&&i*p[j] < N; j++)
{
vis[i*p[j]] = 1;
if (i%p[j] == 0) break;
}
}
}
int main()
{
init();
int n;
scanf("%d", &n);
if (n <= 5)
{
puts("empty");
exit(0);
}
ll ans = 1;
int x = n / 3;
int cnt = 0;
while (x > 1) x /= 2, cnt++;
ans = ans*Pow(2, cnt) % mod;
int pp = sqrt(n);
for (int i = 2; i <= tot&&p[i]<=n; i++)
{
if (p[i] > pp)
{
if (n / p[i] > 1)
ans = ans*p[i] % mod;
}
else
{
cnt = 0;
x = n / 2;
while (x >= p[i]) x /= p[i], cnt++;
ans = ans*Pow(p[i], cnt) % mod;
}
}
printf("%lld\n", ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255967.html
標籤：其他