2019 ICPC 徐州网络赛
solve ： 7/13
补题 ： 10/13
https://www.jisuanke.com/contest/3005?view=challenges
A. Who is better?
中国剩余定理+暴力算前10项猜结论。然后最后三分钟1A
#include <bits/stdc++.h>
#define ll long long//__int128
using namespace std;
const int MAXN = 2000;
int n;
ll a[MAXN], b[MAXN];///a为除数，b为余数
ll mul(ll a, ll b, ll mod)
{
ll res = 0;
while (b > 0)
{
if (b & 1)
res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}
ll exgcd(ll a, ll b, ll& x, ll& y) ///ax+by = gcd(a,b);
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - a / b * (y);
return gcd;
}
ll excrt() ///x == b(mod a)
{
ll m1, r1, m2, r2, x, y, c, t;
m1 = a[1], r1 = b[1];
for (int i = 2; i <= n; i++)
{
m2 = a[i], r2 = b[i];
ll d = exgcd(m1, m2, x, y);
c = r2 - r1;
if (c % d)
return -1;
t = m2 / d;
x = (c / d * x % t + t) % t;
r1 = m1 * x + r1;
m1 = m1 * m2 / d;
}
return r1;
}
ll qq[80], flag;
bool check(ll x)
{
for (int i = 1; i < 80; i++)
if (qq[i] == flag)
return true;
return false;
}
int main()
{
scanf("%d", &n);
qq[1] = 1;
qq[2] = 1;
for (int i = 3; i < 80; i++)
qq[i] = qq[i - 2] + qq[i - 1];
for (int i = 1; i <= n; i++)
scanf("%lld %lld", &a[i], &b[i]);
flag = excrt();//-1表示无解
if (flag == -1)
printf("Tankernb!");
else
{
if (check(flag))
printf("Lbnb!\n");
else
printf("Zgxnb!\n");
}
} B. so easy
出题人标称用unordered_map，嗯，牛逼，让我找找 cf 上怎么 hack 这玩意儿的。
赛时用map T到爆炸，最后还是用线段树离散化２ｅ６个数字，找区间最小值才过了，整场比赛自闭的开始，最后 I J K 三个水题没时间看都是这个题的锅。
unorderer_map+并查集
#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
unordered_map<int, int>mp;
int find(int k)
{
if (mp.count(k) == 0)
return k;
else
return mp[k] = find(mp[k]);
}
int main()
{
int n, m;
sc("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int op, num;
sc("%d%d", &op, &num);
if (op == 1)
{
mp[num] = find(num + 1);
}
else
{
int fa = find(num);
if (fa > n)
fa = -1;
pr("%d\n", fa);
}
}
} 线段树
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
struct note
{
int op;
int num;
}in[1000005];
int t[2000005];
const int MAXN = 2e6 + 5;
int ans;
struct node
{
int l;
int r;
int minn;
}que[MAXN * 4];
int n, m, ql, qr, all;
void up(int k)
{
que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void build(int left = 1, int right = all, int k = 1)
{
que[k].l = left;
que[k].r = right;
if (left == right)
{
que[k].minn = left;
return;
}
imid;
build(lson);
build(rson);
up(k);
}
void update(int left = 1, int right = all, int k = 1)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].minn = 9999999;
return;
}
imid;
update(lson);
update(rson);
up(k);
}
int query(int left = 1, int right = all, int k = 1)
{
if (qr < left || right < ql)
return 99999999;
if (ql <= left && right <= qr)
return que[k].minn;
imid;
return min(query(lson), query(rson));
}
int main()
{
sc("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
sc("%d%d", &in[i].op, &in[i].num);
t[2 * i] = in[i].num;
t[2 * i + 1] = in[i].num + 1;
}
all= m * 2;
sort(t, t + all);
all = unique(t, t + all) - t;
for (int i = 0; i < m; i++)
in[i].num = lower_bound(t, t + all, in[i].num) - t + 1;
build();
for (int i = 0; i < m; i++)
{
if (in[i].op == 1)
{
ql = qr = in[i].num;
update();
}
else
{
ql = in[i].num; qr = all;
int ans = query();
pr("%d\n", t[ans - 1]);
}
}
} C. Buy Watermelon
签到
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
int n;
sc("%d", &n);
if (n % 2 == 0 && n != 2)
pr("YES\n");
else
pr("NO\n");
} D. Carneginon
签到，上个KMP
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char t[100005],s[100005];
const int N = 1e6 + 10;
int nex[N], plen, slen;
void get_nex(char p[])
{
int i = 0, j = -1;
nex[0] = -1;
while (i < plen)
{
if (j == -1 || p[i] == p[j])
{
i++, j++;
nex[i] = j;
}
else
j = nex[j];
}
}
int query(char s[], char p[])
{
get_nex(p);
int i = 0, j = 0;
while (i < slen)
{
if (j == -1 || s[i] == p[j])
i++, j++;
else
j = nex[j];
if (j == plen)
{
return i - j + 1;
}
}
return -1;
}
//从0开始
int main()
{
sc("%s", t);
int lent = strlen(t);
int n;
sc("%d", &n);
while (n--)
{
sc("%s", s);
int lens = strlen(s);
if (lens == lent)
{
for (int i = 0; i < lens; i++)
{
if (t[i] != s[i])
{
puts("friend!");
goto qwe;
}
}
puts("jntm!");
}
else if (lens < lent)
{
slen = lent, plen = lens;
if (query(t, s) != -1)
puts("my child!");
else
puts("oh, child!");
}
else
{
slen = lens, plen = lent;
if (query(s, t) == -1)
puts("senior!");
else
puts("my teacher!");
}
qwe:;
}
} E. XKC's basketball team
找区间最右的大于某个数字的数字的位置
爆搜线段树，和CCPC 02有点像，用线段树来剪枝。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 5e5 + 5;
int n, m, ql, qr, val;
struct node
{
int l;
int r;
int maxn;
}que[MAXN * 4];
int a[MAXN], ans;
void build(int left = 1, int right = n, int k = 1)
{
que[k].l = left;
que[k].r = right;
if (left == right)
{
que[k].maxn = a[left];
return;
}
imid;
build(lson);
build(rson);
que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
bool query(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return false;
if (left == right)
{
if (que[k].maxn >= val)
{
ans = max(ans, left);
return true;
}
return false;
}
if (que[k].maxn < val)
return false;
imid;
if (qr > mid)
{
if (query(rson))
return true;
else
return query(lson);
}
else
return query(lson);
}
int main()
{
sc("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
sc("%d", &a[i]);
build();
for (int i = 1; i <= n; i++)
{
ql = i, qr = n;
val = a[i] + m;
ans = -1;
query();
if (ans != -1)
ans -= i + 1;
pr("%d%c", ans, i == n ? '\n' : ' ');
}
} G. Colorful String
回文自动机板子
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int MAXN = 26;
int nex[N][MAXN], fail[N];
ll cnt[N];
int num[N], len[N], s[N], q[N << 1]; /*s用来存放已经插入的字符*/
int vis[N][26];
char str[N]; /*cnt 以i结尾的回文串出现次数 num 以i结尾的回文串种类*/
int last, idx, length;
ll ans[N];
int id[N];
void newnode(int l)
{
len[idx] = l;
memset(nex[idx], 0, sizeof(nex[idx]));
}
void init()
{
idx = 1, last = 0;
len[0] = 0, len[1] = -1;
cnt[1] = cnt[0] = 0;
num[0] = num[1] = 0;
memset(nex[0], 0, sizeof(nex[0]));
memset(nex[1], 0, sizeof(nex[1]));
length = 0;
s[length] = -1;
fail[0] = 1;
}
int get_fail(int x)
{
while (s[length - len[x] - 1] != s[length])
x = fail[x];
return x;
}
void insert_pam(int c)
{
s[++length] = c;
int p = get_fail(last);
if (!nex[p][c])
{
++idx;
id[idx] = length;
newnode(len[p] + 2);
memcpy(vis[idx], vis[p], sizeof(vis[p]));
//ans[idx] = ans[p];
vis[idx][c] = 1;
for (int i = 0; i < 26; i++)
{
if (vis[idx][i])
ans[idx]++;
}
fail[idx] = nex[get_fail(fail[p])][c];
nex[p][c] = idx;
num[idx] = num[fail[idx]] + 1;
}
last = nex[p][c];
cnt[last]++;
}
void count()
{
for (int i = idx; i >= 2; i--)
cnt[fail[i]] += cnt[i];
}
int main()
{
init();
scanf("%s", str + 1);
memset(cnt, 0, sizeof(cnt));
int n = strlen(str + 1);
for (int i = 1; i <= n; i++)
insert_pam(str[i] - 'a');
ll ANS = 0;
count();
for (int i = idx; i >= 2; i--)
{
ANS += 1ll * ans[i] * cnt[i];
}
printf("%lld", ANS);
} I. query
一个全排列，每次问你一个区间内有倍数关系的数字对数
因为是全排列，所以可以在nlogn的时间可以求出所有对数，然后离线查询，按右端点从小到大排，边加入边查询就可以
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define Pair pair<int,int>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];
vector<Pair>v;
int ind[MAXN];//index[i]表示值 i 的所在的下标
struct node
{
int l;
int r;
int id;
}in[MAXN];
int ans[MAXN];
int c[MAXN];
int lowbit(int k)
{
return k & (-k);
}
void update(int k, int x)
{
while (k < MAXN)
{
c[k] += x;
k += lowbit(k);
}
}
int query(int k)
{
int ans = 0;
while (k)
{
ans += c[k];
k -= lowbit(k);
}
return ans;
}
int main()
{
int n, m;
sc("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
sc("%d", &a[i]);
ind[a[i]] = i;
}
for (int i = 1; i <= n; i++)
for (int j = i + i; j <= n; j += i)
if (ind[i] < ind[j])
v.push_back(Pair{ ind[i],ind[j] });
else
v.push_back(Pair{ ind[j],ind[i] });
for (int i = 0; i < m; i++)
{
sc("%d%d", &in[i].l, &in[i].r);
in[i].id = i;
}
sort(v.begin(), v.end(), [](Pair q, Pair w) {
if (q.second == w.second)
return q.first < w.first;
return q.second < w.second;
});
sort(in, in + m, [](node q, node w) {
if (q.r == w.r)
return q.l < w.l;
return q.r < w.r;
});
int posv = 0, posq = 0;
int len = v.size();
for (int i = 1; i <= n; i++)
{
//update
while (posv < len && v[posv].second == i)
{
update(v[posv].first, 1);
posv++;
}
//query
while (posq < m && in[posq].r == i)
{
ans[in[posq].id] = query(in[posq].r) - query(in[posq].l - 1);
posq++;
}
}
for (int i = 0; i < m; i++)
pr("%d\n", ans[i]);
} J. Random Access Iterator
有一个函数，大概意思是执行他的儿子个数次随机选一个儿子，问他这样能正确求出树的高度的概率是多少。
树形DP，假设所有最高的节点为1，其他都是0，然后递归从下向上转移，只要求出一次成功的概率，然后1-K次不成功的概率就可以。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e6 + 5;
struct edge
{
int to;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
}
void add(int a, int b)
{
e[tot] = edge{ b,head[a] };
head[a] = tot++;
}
int deep[MAXN], maxn;
void dfs1(int u, int fa, int dep)
{
deep[u] = dep;
maxn = max(maxn, dep);
for (int i = head[u]; i + 1; i = e[i].nex)
{
int to = e[i].to;
if (to == fa)
continue;
dfs1(to, u, dep + 1);
}
}
const ll mod = 1e9 + 7;
ll power(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll inv[MAXN];
void init1()
{
inv[1] = 1;
for (int i = 2; i < MAXN; i++)
inv[i] = inv[mod % i] * (ll)(mod - mod / i) % mod;
}
ll dp[MAXN];
void dfs(int u, int fa)
{
ll cnt = 0;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int to = e[i].to;
if (to == fa)
continue;
dfs(to, u);
dp[u] += dp[to];
cnt++;
}
if (cnt == 0)
return;
ll may = dp[u] * inv[cnt] % mod;
dp[u] = (1 - power((1 - may + mod) % mod, cnt) + mod) % mod;
}
int main()
{
init(), init1();
int n, a, b;
sc("%d", &n);
for (int i = 0; i < n - 1; i++)
{
sc("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs1(1, 0, 1);
for (int i = 1; i <= n; i++)
if (deep[i] == maxn)
dp[i] = 1;
dfs(1, 0);
pr("%lld\n", dp[1]);
} K. Center
先枚举一个点，第二层枚举所有点，然后求出这两个点的中心点，若选择的中心点是他们的中心点的话，那么第二层枚举到的点的对称点就是第一个点，就不需要额外加入一个新的点到点集中，所以这个中心点的贡献+1。
然后枚举每个点作为中心点还需要的点数。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
#define Pair pair<int,int>
map<Pair, int>mp;
Pair book[1005];
int main()
{
int n, a, b;
sc("%d", &n);
for (int i = 0; i < n; i++)
sc("%d%d", &book[i].first, &book[i].second);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mp[Pair{ book[i].first + book[j].first,book[i].second + book[j].second }]++;
int ans = n;
for (auto it = mp.begin(); it != mp.end(); it++)
ans = min(ans, n - it->second);
pr("%d\n", ans);
} M. Longest subsequence
预处理每个位置后的每个字母最先出现的位置，在位置 i 的最长长度就是第一个串的当前位置大于当前第二个串位置字母的字母的首位置，然后考虑有相同的肯定先匹配相同的才最优，然后用求子串的方法暴力匹配一下
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e6 + 5;
char s[MAXN], s1[MAXN];
int a[MAXN][30];
int main()
{
int n, m;
sc("%d%d", &n, &m);
sc("%s%s", s + 1, s1 + 1);
for (int i = 0; i < 26; i++)
a[n + 1][i] = 1e9;
for (int i = n; i >= 0; i--)
{
for (int j = 0; j < 26; j++)
a[i][j] = a[i + 1][j];
if (i != 0)
a[i][s[i] - 'a'] = i;
}
int ans = -1;
for (int i = s1[1] - 'a' + 1; i < 26; i++)
ans = max(ans, n - a[0][i] + 1);
int pos = 1;
for (int i = 1; i <= n;)
{
if (s[i] == s1[pos])
{
pos++;
i++;
if (pos == m + 1)//end
{
if (i != n + 1)//还有
ans = max(ans, m + n - i + 1);
break;
}
else
{
for (int j = s1[pos] - 'a' + 1; j < 26; j++)
ans = max(ans, pos - 1 + n - a[i][j] + 1);
}
}
else
i++;
}
pr("%d\n", ans);
}
投递上海莱迪思半导体等公司10个岗位 >
华为成长空间 480人发布
