A.Who is better?
题意：
给定组
和
，
。两个人互相拿这个
个数，先手第一次不能拿完，每次后手只能拿
到前一次拿的数量
之间的数量，不能拿时则输
题解：
可由中国剩余定理求出，算出前几个数可以猜测
为斐波那契数列时先手必败
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
ll b[maxn], a[maxn], f[maxn];
int n;
ll Ex_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = Ex_gcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
return d;
}
ll Ex_Crt()
{
ll aa = b[1], rr = a[1], x, y;
for (int i = 2; i <= n; ++i)
{
ll bb = b[i], c = a[i] - rr;
ll d = Ex_gcd(aa, bb, x, y);
if (c % d)
return -1; //c不能整除d，不存在整数解
c = c / d;
bb = bb / d;
x = (x * c % bb + bb) % bb;
ll lcm = aa * bb;
rr = (x * aa % lcm + rr) % lcm;
aa = lcm;
}
if (rr == 0 || rr == 1)
rr += aa;
return rr;
}
int main()
{
scanf("%d",&n);
f[1] = f[2] = 1;
for (int i = 3; i < 80; ++i)
f[i] = f[i - 1] + f[i - 2];
for (int i = 1; i <= n; ++i)
scanf("%lld%lld",&b[i],&a[i]);
ll x = Ex_Crt();
if (x == -1)
puts("Tankernb!");
else
{
bool flag = false;
for (int i = 3; i < 80; ++i)
{
if (f[i] == x)
{
flag = true;
break;
}
}
if (flag)
puts("Lbnb!");
else
puts("Zgxnb!");
}
return 0;
} B.so easy
题意：
给定一个的序列，给出
次操作
1 将
点标为不可用
2 询问
从
开始第一个可用的数
原先所有数均可用
题解：
用set把所有不可用的数存下来，每次都往后找第一个可用的数即可或者用并查集算出每个开始的第一个可用数
set
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int> s;
int main()
{
int n, q;
scanf("%d%d", &n, &q);
while (q--)
{
int op, x;
scanf("%d%d", &op, &x);
if (op == 1)
s.insert(x);
else
{
while (s.count(x))
x++;
printf("%d\n", x);
}
}
return 0;
} 并查集
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int find(int x)
{
return mp[x] ? mp[x] = find(mp[x]) : x;
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
while (q--)
{
int op, x;
scanf("%d%d", &op, &x);
if (op == 1)
mp[x] = find(x + 1);
else
printf("%lld\n", find(x));
}
return 0;
} C.Buy Watermelon
题意：
判断一个西瓜能否均分为两份，并且每一份的重量至少是
题解：
为偶数，且不为
即可
#include <bits/stdc++.h>
using namespace std;
int main()
{
int w;
scanf("%d", &w);
if (!(w & 1) && (w != 2))
puts("YES");
else
puts("NO");
return 0;
} D.Carneginon
题意：
给定两个字符串和
，判断
和
的长度关系和是否为字串
题解：
根据题意模拟即可，判断字串可以用strstr()函数也可以用算法
strstr()函数
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char s1[100005],s2[100005];
int main(){
cin >> s1;
int len1=strlen(s1);
int t;
scanf("%d",&t);
while(t--){
cin >> s2;
int len2=strlen(s2);
if(len1==len2){
if(strcmp(s1,s2)==0)printf("jntm!\n");
else printf("friend!\n");
}
else if(len1<len2){
if(strstr(s2,s1)==NULL)printf("senior!\n");
else printf("my teacher!\n");
}
else if(len1>len2){
if(strstr(s1,s2)==NULL)printf("oh, child!\n");
else printf("my child!\n");
}
}
} 算法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int s[N], p[N], ne[N];
int n, m, sum, ans;
void getNext(const char P[], int ne[])
{
int i = 0, j;
j = ne[0] = -1;
while (i < m)
{
while (-1 != j && P[i] != P[j])
j = ne[j];
ne[++i] = ++j;
}
}
void kmp(const char S[], const char P[], int ne[])
{
int i, j;
getNext(P, ne);
i = j = 0;
while (i < n)
{
while (-1 != j && S[i] != P[j])
j = ne[j];
i++;
j++;
if (j >= m)
{
if (ans == -1)
ans = i - m + 1;
j = ne[j];
}
}
}
char T[N], S[N];
int main()
{
int t;
scanf("%s%d", T, &t);
while (t--)
{
getchar();
scanf("%s", S);
int lent = strlen(T), lens = strlen(S);
if (lent == lens)
{
if (strcmp(S, T) == 0)
puts("jntm!");
else
puts("friend!");
}
else if (lent > lens)
{
ans = -1;
memset(ne, 0, sizeof(ne));
n = lent, m = lens;
kmp(T, S, ne);
if (ans != -1)
puts("my child!");
else
puts("oh, child!");
}
else
{
ans = -1;
memset(ne, 0, sizeof(ne));
n = lens, m = lent;
kmp(S, T, ne);
if (ans != -1)
puts("my teacher!");
else
puts("senior!");
}
}
return 0;
} E.XKC's basketball team
题意：
给定个数
和一个数
，对每个
求出最大的
，满足
，输出两者之间间隔多少数
题解：
可以用单调队列从后往前记录，对于每个都对单调队列进行一次二分即可。
也可以用线段树维护区间最大值，每次只要找最大、最靠右的那个数即可，这个可以在query()函数中，先判断右结点再判断左结点来实现。
单调队列+二分
#include<bits/stdc++.h>
using namespace std;
int a[N], q[N], pos[N];
const int N = 5e5 + 5;
int main()
{
int n, m, top = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = n; i; i--)
{
if (q[top] < a[i])
q[++top] = a[i], pos[top] = i;
}
for (int i = 1; i <= n; i++)
{
int index = lower_bound(q + 1, q + top + 1, a[i] + m) - q;
printf("%d%c", (pos[index] - i - 1 >= 0) ? pos[index] - i - 1 : -1, i == n ? '\n' : ' ');
}
} 线段树
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, a[maxn], ans[maxn], MAX[maxn << 2];
void build(int l, int r, int x)
{
if (l == r)
{
MAX[x] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, x << 1);
build(mid + 1, r, x << 1 | 1);
MAX[x] = max(MAX[x << 1], MAX[x << 1 | 1]);
}
void query(int l, int r, int L, int R, int x, int val, int &ans)
{
if (l > R || r < L || ans != -1)
return;
if (l == r)
{
ans = l;
return;
}
int mid = (l + r) >> 1;
if (MAX[x << 1 | 1] >= val)
query(mid + 1, r, L, R, x << 1 | 1, val, ans);
if (MAX[x << 1] >= val)
query(l, mid, L, R, x << 1, val, ans);
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
build(1, n, 1);
for (int i = 1; i <= n; ++i)
{
ans[i] = -1;
query(1, n, i + 1, n, 1, a[i] + m, ans[i]);
if (ans[i] != -1)
ans[i] = ans[i] - i - 1;
}
for (int i = 1; i <= n; i++)
printf("%d%c", ans[i], i == n ? '\n' : ' ');
return 0;
} G.Colorful String
题意：
给定一个字符串，求所有回文子串中不同字符种数之和
题解：
先用Manacher预处理一波，然后找出每一个位置的26个字母下一个位置，存在一个vector里面，然后最后找的时候就是差值对应的个数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
char S[N], T[N << 1];
int Len[N << 1];
int nxt[N][27];
vector<int> V[N];
void Manacher(char *s)
{
int L = strlen(s);
int po = 0, mx = 0;
for (int i = 1; i <= L * 2; i++)
T[i] = i & 1 ? '#' : s[i / 2 - 1];
T[0] = '@';
T[2 * L + 1] = '#';
T[2 * L + 2] = '\0';
ll tmp = 0;
for (int i = 1; i <= 2 * L; i++)
{
if (i < mx)
Len[i] = min(mx - i, Len[2 * po - i]);
else
Len[i] = 1;
while (T[i + Len[i]] == T[i - Len[i]])
Len[i]++;
if (i + Len[i] > mx)
{
po = i;
mx = i + Len[i];
}
}
}
int main()
{
scanf("%s", S);
Manacher(S);
int len1 = strlen(S);
int len2 = strlen(T);
for (int j = 0; j < 26; j++)
{
int pos = INT_MAX;
for (int i = len1 - 1; i >= 0; i--)
{
if (S[i] == j + 'a')
pos = i;
nxt[i][j] = pos;
}
}
for (int i = 0; i < len1; i++)
{
for (int j = 0; j < 26; j++)
V[i].push_back(nxt[i][j]);
sort(V[i].begin(), V[i].end());
}
ll ans = 0;
for (int i = 2; i < len2; i++)
{
int L = Len[i] / 2;
if (L == 0)
continue;
int pos = i / 2 - 1;
if (i & 1)
pos++;
int R = pos + L - 1;
int Last = V[pos][0];
int cnt = 0;
for (auto x : V[pos])
{
if (x > R)
break;
int r = x - 1;
ans = ans + (ll)(cnt++) * (ll)(r - Last + 1);
Last = x;
}
if (R >= Last)
ans = ans + (ll)cnt * (ll)(R - Last + 1);
}
printf("%lld\n", ans);
return 0;
} I.query
题意：
给定一个长度为的排列
，给出
组询问，每种询问给定
，求
中询问多少组
满足
题解：
就是倍数关系，因此对于每个数将它的倍数都作为一对数记录下来，那么问题就是求
之间对数的个数，每次都去查找肯定会超时，发现这是道二位偏序问题。因此将每个问题都离线处理，将
从打到小排序，那么对于每个问题，肯定满足
，那么只需要用树状数组维护
，每次调用
即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define lowbit(x) x &(-x)
struct Query
{
int l, r, k, f;
Query(){};
Query(int l0, int r0, int k0, int f0) : l(l0), r(r0), k(k0), f(f0){};
bool operator<(const Query &C) const
{
if (l != C.l)
return l > C.l;
return f > C.f;
}
} q[maxn << 6];
int n, m;
int pos[maxn], cnt;
int a[maxn], bit[maxn], ans[maxn];
void update(int x, int ad)
{
for (; x <= n; x += lowbit(x))
bit[x] += ad;
}
int query(int x)
{
int res = 0;
for (; x; x -= lowbit(x))
res += bit[x];
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
pos[a[i]] = i;
}
for (int i = 1; i <= m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
q[cnt++] = Query(l, r, i, 0);
}
for (int i = 1; i <= n; i++)
for (int j = a[i] * 2; j <= n; j += a[i])
q[cnt++] = Query(min(i, pos[j]), max(i, pos[j]), 0, 1);
sort(q, q + cnt);
for (int i = 0; i < cnt; i++)
{
if (q[i].f)
update(q[i].r, 1);
else
ans[q[i].k] = query(q[i].r);
}
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
} J.Random Access Iterator
题意：
给定一棵以号节点为根节点的树，从根节点出发，在节点
有
次等概率进入儿子节点，求能够到达最深深度的概率。
题解：
第一次求出每个点的深度，
和最深的深度
树形,定义
为从
开始能到达最深节点的概率，每次不能到达最深节点的概率为
，那么
，因此最终结果为
，这个过程再跑一次
即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
int head[maxn], nxt[maxn << 1], to[maxn << 1], cnt;
int dep[maxn], siz[maxn], mxd[maxn];
ll dp[maxn];
ll ksm(ll a, ll b, ll mod)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void init()
{
memset(head, -1, sizeof(head));
cnt = 0;
}
void addedge(int u, int v)
{
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt++;
}
void dfs(int u, int fa)
{
mxd[u] = dep[u];
for (int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if (v == fa)
continue;
dep[v] = dep[u] + 1;
siz[u]++;
dfs(v, u);
mxd[u] = max(mxd[u], mxd[v]);
}
}
void dfs1(int u, int fa)
{
ll sum = 0;
for (int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if (v == fa)
continue;
if (mxd[v] == mxd[1])
{
dfs1(v, u);
sum = (sum + dp[v]) % mod;
}
}
if (siz[u] == 0)
dp[u] = 1;
else
{
ll p = sum * ksm(siz[u], mod - 2, mod) % mod;
p = (1 - p + mod) % mod;
dp[u] = (1 - ksm(p, siz[u], mod) + mod) % mod;
}
}
int main()
{
init();
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1, 0);
dfs1(1, 0);
printf("%lld\n", dp[1]);
return 0;
} K.Center
题意：
给定个点，要求添加尽可能少的点使得存在一个点，满足对每个点都能找到一个点以该点为中心
题解：
记录下每个点与这个点的中心，统计每个点出现的次数，次数最多的那个就作为中心，要添加的点数量就是
减去这个最大值
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1005;
pii p[maxn];
map<pii, int> mp;
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &p[i].first, &p[i].second);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mp[{p[i].first + p[j].first, p[i].second + p[j].second}]++;
int ans = 0;
for (auto i : mp)
ans = max(ans, i.second);
printf("%d\n", n - ans);
return 0;
} M.Longest subsequence
题意：
给定一个长度为的字符串
和一个长度为
的字符串
，要求在
中找到一个最长的字典序大于
的字序列
题解：
字典序大于只有两种情况，当前位置和
相等和当前位置
，当前位置和
相等那么只需要每次都选取尽可能靠前的那个位置，再对
考虑两种情况，对当前位置
那么也只需要取尽可能靠前那个，从当前位置开始后面的都可以取过来使得长度尽可能长。模拟即可，只需要考虑到前面几位都与
都相同，那么可以把后面的所有字符都取过来，单独判断一下即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
char s[maxn], t[maxn];
int dp[maxn][30];
int main()
{
int n, m;
cin >> n >> m;
scanf("%s%s", s + 1, t + 1);
for (int i = n - 1; i >= 0; i--)
for (int j = 0; j < 26; j++)
{
if (s[i + 1] - 'a' == j)
dp[i][j] = i + 1;
else
dp[i][j] = dp[i + 1][j];
}
int ans = 0, pos = 0, flag = 1;
for (int i = 1; i <= m; i++)
{
for (int j = t[i] - 'a' + 1; j < 26; j++)
if (dp[pos][j] > 0)
ans = max(ans, i + n - dp[pos][j]);
pos = dp[pos][t[i] - 'a'];
if (pos == 0)
{
flag = 0;
break;
}
}
if (flag && pos != n)
ans = max(ans, m + n - pos);
printf("%d\n", ans ? ans : -1);
return 0;
} 
京公网安备 11010502036488号