A.Permutation
题意
给一个质数$p$,构造一组长度为$p-1$的全排列,满足以下条件$\forall i(1 \leq i \leq p-2), x_{i+1} \equiv 2x_{i}$ $(mod$ $p)$ $or$ $x_{i+1} \equiv 3x_{i}$ $(mod$ $p)$.
若存在,输出任一组可行解;若不存在,输出-1.
$1 \leq T \leq 100, 2 \leq p \leq 10^{6}, \sum p \leq 10^{6}$
思路
从1开始构造,先乘2，若不满足，则再乘3，若还是不满足，则为-1.
瞎猜结论,不会证
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int t, n, ans[N], vis[N];
int st[N], p[N], tot;
void init(int n)
{
for (int i = 2; i <= n; i++)
{
if (!st[i]) p[++tot] = i;
for (int j = 1; j <= tot && p[j] * i <= n; j++)
{
st[p[j] * i] = 1;
if (i % p[j] == 0) break;
}
}
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int tot = 0;
for (int i = 1; i <= n; i++) vis[i] = 0;
int tmp = 1;
ans[++tot] = 1; vis[1] = 1;
for (int i = 1; i < n; i++)
{
int pre =tmp;
tmp = tmp * 2 % n;
if (tmp > 0 && tmp < n && !vis[tmp])
{
ans[++tot] = tmp;
vis[tmp] = 1;
continue;
}
tmp = pre;
tmp = tmp * 3 % n;
if (tmp > 0 && tmp < n && !vis[tmp])
{
ans[++tot] = tmp;
vis[tmp] = 1;
continue;
}
break;
}
if (tot < n - 1) printf("-1\n");
else
{
for (int i = 1; i <= tot; i++) printf("%d ", ans[i]);
printf("\n");
}
}
return 0;
}
C.Decrement on the Tree
题意
给一棵树，每次操作可以选择一条路径，将该路径上的边权减1，且边权不能为负.问最少多少次操作使得树的所有边权都为0.同时需要依次做m次操作,每次操作都将修改一条边权,问每次修改后的最少操作次数.
$1 \leq n,q \leq 10^{5}, 1 \leq u,v \leq n, 1 \leq w \leq 10^{9}$
思路
考虑路径端点的最少个数$cnt$,那么最少操作次数$ans=cnt/2$.
对于$\forall x \in V$,设$x$所连边权的最大值为$maxval$,$ $ $x$所连边权总和为$sumval$.
1. 若$maxval > sumval - maxval$,则说明$x$含有$2 * maxval - sumval$个端点.
2. 若$maxval <= sumval - maxval$,则$x$含有端点个数只与sumval的奇偶性有关.
此处端点个数的计算过程,类似于$x$的不同边之间边权相校过程,使得端点个数尽量少.
修改操作的维护可通过multiset实现
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, q, id, val;
int x[N], y[N], w[N], pre[N];
multiset<int>e[N];
ll sum[N];
int main()
{
scanf("%d %d", &n, &q);
for (int i = 1; i < n; i++)
scanf("%d %d %d", &x[i], &y[i], &w[i]);
for (int i = 1; i < n; i++)
{
e[x[i]].insert(w[i]);
e[y[i]].insert(w[i]);
sum[x[i]] += w[i];
sum[y[i]] += w[i];
}
ll ans = 0;
for (int i = 1; i <= n && n != 1; i++)
{
int cur = *e[i].rbegin();
if (cur >= sum[i] - cur) ans += (pre[i] = 2 * cur - sum[i]);
else ans += (pre[i] = sum[i] & 1);
}
printf("%lld\n", ans / 2);
while (q--)
{
scanf("%d %d", &id, &val);
ans -= pre[x[id]];
ans -= pre[y[id]];
sum[x[id]] -= w[id];
sum[y[id]] -= w[id];
auto it = e[x[id]].find(w[id]);
e[x[id]].erase(it);
it = e[y[id]].find(w[id]);
e[y[id]].erase(it);
w[id] = val;
e[x[id]].insert(val);
e[y[id]].insert(val);
sum[x[id]] += val;
sum[y[id]] += val;
int cur = *e[x[id]].rbegin();
if (cur >= sum[x[id]] - cur) ans += (pre[x[id]] = 2 * cur - sum[x[id]]);
else ans += (pre[x[id]] = sum[x[id]] & 1);
cur = *e[y[id]].rbegin();
if (cur >= sum[y[id]] - cur) ans += (pre[y[id]] = 2 * cur - sum[y[id]]);
else ans += (pre[y[id]] = sum[y[id]] & 1);
printf("%lld\n", ans / 2);
}
return 0;
}
D.Hearthstone Battlegrounds
题意
给一个游戏规则,xtq只要有可能获胜(平局不算),无论可能性有多小,他就可以赢得比赛.
游戏规则如下，现有四种鱼人($x/y$表示攻击力为x,血量为y):
1. $1/10^9$,带剧毒圣盾盲语
2. $1/10^9$,带剧毒圣盾
3. $1/10^9$,带剧毒盲语
4. $1/10^9$,带剧毒
攻击与各技能效果如下:
- 攻击效果：当一个$x1/y1$的随从攻击一个$x2/y2$的随从（假定两者都没有圣盾和剧毒）,则$y1$变为$y1−x2$,$y2$变为$y2−x1$.当任意一个随从的血量小于等于0,即视为死亡.
- 剧毒效果：当该随从攻击对方随从,对方被攻击随从立即死亡.
- 圣盾效果：免疫一次任何攻击效果,随后立即消失.
- 亡语效果：随从死亡时触发,召唤一个$1/1$的藤蔓.
每回合一个随从都会攻击敌方随从,直至某一方随从数为0.
只要xtq在游戏结束时仍有至少一个随从存活 或 双方均无随从存活且藤蔓数量大于对方藤蔓,xtq获胜.
现xtq有$a_i$个$i$种鱼人,对手有$b_i$个i种鱼人.若xtq可以赢得比赛,则输出”Yes”;否则,输出”No”.
$1 \leq T \leq 150000, 0 \leq a_i \leq 100000, 0 \leq b_i \leq 100000, \sum a_1 + a_2 + a_3 + a_4 + b_1 + b_2 + b_3 + b_4 \leq 5·10^6$
思路
“无论可能性有多小”,相当于xtq可以操纵对手,即可用贪心策略.
按以下顺序执行
1. 若xtq含有3和4,则先清理对方的藤蔓
2. 若xtq含有藤蔓,则利用藤蔓攻击对方的圣盾
3. 若xtq含有3,利用3攻击敌方
4. 若xtq含有1,利用1攻击敌方
4. 2和4的顺序无关
利用鱼人攻击敌方时,优先攻击3和4,因为尽量让藤蔓破坏对方的圣盾.
代码
#include <bits/stdc++.h>
using namespace std;
int t, val[2][10];
void fight()
{
if (val[1][3]) val[1][3]--, val[1][5]++;
else if (val[1][4]) val[1][4]--;
else if (val[1][1]) val[1][1]--, val[1][3]++;
else if (val[1][2]) val[1][2]--, val[1][4]++;
}
int main()
{
scanf("%d", &t);
while (t--)
{
for (int i = 1; i <= 4; i++) scanf("%d", &val[0][i]);
for (int i = 1; i <= 4; i++) scanf("%d", &val[1][i]);
val[0][0] = val[1][0] = 0;
val[0][5] = val[1][5] = 0;
int sum = 0;
for (int i = 1; i <= 4; i++)
val[0][0] += val[0][i], val[1][0] += val[1][i];
while (val[0][0] && val[1][0])
{
if (val[0][3] + val[0][4]) val[1][5] = 0;
if (val[0][5] && val[1][1] + val[1][2])
{
val[0][5]--;
if (val[1][1]) val[1][1]--, val[1][3]++;
else if (val[1][2]) val[1][2]--, val[1][4]++;
}
if (val[0][3])
{
val[0][3]--; val[0][5]++;
fight();
}
else if (val[0][1])
{
val[0][1]--; val[0][3]++;
fight();
}
else if (val[0][2])
{
val[0][2]--; val[0][4]++;
fight();
}
else if (val[0][4])
{
val[0][4]--;
fight();
}
val[0][0] = val[1][0] = 0;
for (int i = 1; i <= 4; i++)
val[0][0] += val[0][i], val[1][0] += val[1][i];
}
if (val[0][0] || (val[1][0] == 0 && val[0][5] > val[1][5])) printf("Yes\n");
else printf("No\n");
}
}
E.Game
题意
有n列小方块，每列小方块有a[i]个，你可以选择一个位置从右往左推动小方块，如果此位置左边和上边也有小方块，它们会跟着一起移动，如果某个小方块移动后悬空，他就会落到下面的小方块上.如果跟着移动的最左边的小方块列为1，则不能移动这个位置.问若干次操作之后小方块的高度最大值的最小值是多少.
$1 \leq T \leq 100000, 2 \leq p \leq 10^{5}, 1 \leq a_i \leq 10^{9}, \sum n \leq 2·10^{5}$
思路
最大值的最小值，二分的基本套路
二分最大的高度height，判断是否能构造所有列的高度小于等于height的情况即可
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t, n, a[N];
bool check(ll val)
{
ll res = 0;
for (int i = n; i >= 1; i--)
{
if (a[i] >= val) res += a[i] - val;
else res = res - min(res, val - a[i]);
}
return res == 0;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int l = 0, r = 1e9 + 10;
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
}
return 0;
}
G.Math Test
题意
给定a,n,求满足以下条件的$(x,y)$数量:
$gcd(x,y) = 1,$ $y|(x^2+a),$ $x|(y^2+a),$ $1 \leq x \leq y \leq n$
$1 \leq T \leq 10^6, 1 \leq a \leq 10^{5}, 1 \leq n \leq 10^{18}$
思路
$如果(x,y)是原方程的一个解那么(x,\frac{x^2+a}{y})和(y,\frac{y^2+a}{x})也是一个解$
$由于两者具有对称性,因此我们证明前者是个合法解$
- $首先\frac{x^2+a}{y}|(x^2+a)显然成立$
- $x|(\frac{x^2+a}{y})^2+a,两边乘y^2且x,y互质所以等价于x|((x^2+a)^2+ay^2),只需证明x|a(y^2+a),这显然成立$
- $接下来证明gcd(x,\frac{(x^2+a)}{y})=1$
$我们反证:假设d|x,d|\frac{x^2+a}{y},d>1,由于x,y互质那么d,y互质所以d|(x^2+a)$
$所以d|a,又由于x|(y^2+a)且d|x则d|y这和x,y互质矛盾$
至此,合法解证毕.
$接下来只需要找到所有的极小解即可,所谓的极小解是指(x,\frac{x^2+a}{y})不比原来的解更小.$
$这只能是\frac{x^2+a}{y}\ge x,a\ge x(y-x),可以枚举(y-x)和x.同时这也证明了极小解个数不超过n·H_n.$
$一通暴力可以发现解的个数很小,但是似乎可能出现一个极小解生成出很多解的情况$
不知道有没有大哥证明$\frac{x}{d}$的一个比较好的界
$如果将a视为x^2级别的随机变量,那么所有解的个数的一个界是n^{1.5}·H_n$
注:本题会被各种卡空间、时间
代码
#include<bits/stdc++.h>
using namespace std;
using pii=pair<long long,long long>;
const int N=1e5;
vector<pii> root[N+10];
vector<long long>R[N+10];
int mod_inv(int a, int m) {
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
void init(){
for(int i=1;i<=N;i++){
root[i].push_back({1,1});
}
for(int d=1;d<=N;d++){
for(int x=1;1ll*x*d<=N;x++){
if(__gcd(x,d)==1){
int y=x+d;
int i=1ll*x*x%y;i=(y-i)%y;
int j=1ll*y*y%x;j=(x-j)%x;
long long M=1ll*x*y;
long long a=(1ll*i*mod_inv(x,y)*x%M+1ll*j*mod_inv(y,x)*y%M)%M;
while(a<1ll*x*d)a+=M;
while(a<=N){
root[a].emplace_back(y,x);
a+=M;
}
}
}
}
int sz=0;
for(int i=1;i<=N;i++){
// if(i%1000==0){
// cout<<i<<endl;
// }
for(int j=0;j<root[i].size();j++){
__int128 x=root[i][j].second,y=root[i][j].first;
__int128 nx=y,ny=(y*y+i)/x;
if(ny>1e18)continue;
root[i].emplace_back(ny,nx);
}
sort(root[i].begin(), root[i].end());
int m=unique(root[i].begin(),root[i].end())-root[i].begin();
for(int j=0;j<m;j++){
R[i].push_back(root[i][j].first);
}
root[i].resize(0);
root[i].shrink_to_fit();
}
}
signed main(){
init();
int T;
scanf("%d",&T);
while(T--){
long long n;
int a;
scanf("%d%lld",&a,&n);
//cout<<root[a].size()<<endl;
//for(auto i:root[a])cout<<i.first<<':'<<i.second<<endl;
printf("%d\n",(int)(upper_bound(R[a].begin(),R[a].end(),n)-R[a].begin()));
}
}
I.Tournament
题意
有n个球队,每个球队都和其它球队有一场比赛,每天只能安排一场比赛,因此共有$\frac {n·(n-1)}{2}$ 场比赛,共需要$\frac{n·(n-1)}{2}$天.每个球队会在第一场比赛开始时到达，最后一场比赛结束后离开.求一个日程表，使所有球队停留的天数之和最小.
$1 \leq T \leq 30, 2 \leq n \leq 300$
思路
稍微打个小表，再加猜想
尽量使得每个队伍的停留时间平均,构造方法如下三部分:
1. 让前一半人打
2. 让前一半人和后一半人打
3. 让后一半人打
本题构造关键在于情况二的构造
假设$n$是最晚来的球队,那么$(1,n)$这场比赛应该处于中间位置,打完$(1,n)$球队$1$离开.
对于$(2,n)$而言,肯定位于$(1,n)$之后,而对于$(2, n-1)$而言,若放在$(1,n)$之前那么会导致球队$1$晚离开一天,若放在$(1,n)$之后所有球队的离开时间不受影响.
因此按照这种思路构造出情况二的后半段,即$(1,n), (2,n-1), (2,n), (3,n-2), (3,n-1), (3,n)…$
情况二的前半段类似
代码
#include <bits/stdc++.h>
using namespace std;
int t, n;
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 2; i <= n / 2; i++)
for (int j = 1; j < i; j++)
printf("%d %d\n", j, i);
for (int i = n / 2 + 1; i <= n; i++)
for (int j = 1; i + j <= n; j++)
printf("%d %d\n", j, i);
for (int i = 1; i <= n / 2; i++)
for (int j = n + 1 - i; j <= n; j++)
printf("%d %d\n", i, j);
for (int i = n / 2 + 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
printf("%d %d\n", i, j);
}
return 0;
}
J.Identical Trees
题意
给两棵有根节点的同构树,仅编号存在不同.每次都只能对第一颗树进行编号修改.问至少修改多少个节点的编号使得两棵树完全相同.
输入一个$p$数组,$p_i$代表$i$结点的父亲结点编号,若为0则为根节点.
$1 \leq n \leq 500$
思路
树hash + 最小费用最大流/KM
$dp[i][j]表示T1中以i为根的子树转化到T2中以j为根的子树最少的修改次数$
$对于每次比较的i,j，我们只需将这两个点的子节点逐个匹配(可用树hash判同构)$
$这些子节点匹配的代价之前已经得出，所以每次比较的时候，只需跑一遍费用流/KM即可$
注:树hash的p和mod取不好可能会被卡
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
//最小费用最大流
struct MCMF{
static const int N = 1010; //点数
static const int M = 250010; //边数
int INF = 0x7fffffff; //最大值
int tot, head[N];
struct node
{
int v, ne;
ll flow, cap, cost;
} edge[M << 1];
void init(int n) //初始化
{
tot = 1;
for (int i = 0; i <= n; i++) head[i] = 0;
}
void add(int x, int y, ll flow, ll cap, ll cost)
{
edge[++tot].v = y;
edge[tot].flow = flow;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].ne = head[x];
head[x] = tot;
}
void add_edge(int x, int y, ll cap, ll cost)
{
add(x, y, 0, cap, cost);
add(y, x, cap, cap, -cost);
}
bool aug[N];
ll dfs(int u, int S, int T, ll &ans, ll &sum, ll resflow)
{
if (!resflow) return 0;
if (u == T) return ans += resflow * sum, resflow;
ll addflow = 0;
aug[u] = true;
for (int i = head[u]; i; i = edge[i].ne)
{
int &v = edge[i].v;
if (!edge[i].cost && edge[i].cap - edge[i].flow && !aug[v])
{
ll delta = dfs(v, S, T, ans, sum, min(resflow - addflow, edge[i].cap - edge[i].flow));
addflow += delta;
edge[i].flow += delta;
edge[i ^ 1].flow -= delta;
if (addflow == resflow)
break;
}
}
if (addflow == resflow) aug[u] = false;
return addflow;
}
ll dist[N];
bool augment(int S, int T, int n, ll &sum)
{
priority_queue<PLL, vector<PLL>, greater<PLL> > qu;
fill(dist, dist + n + 1, INF);
qu.push({ dist[T] = 0, T });
while (!qu.empty())
{
PLL cur = qu.top();
qu.pop();
if (dist[cur.second] != cur.first)
continue;
int u = cur.second;
ll dt;
for (int i = head[u]; i; i = edge[i].ne)
{
int &v = edge[i].v;
if (edge[i ^ 1].cap - edge[i ^ 1].flow && (dt = dist[u] - edge[i].cost) < dist[v])
qu.push({ dist[v] = dt, v });
}
}
sum += dist[S];
for (int i = 0; i <= n; i++)
for (int j = head[i]; j; j = edge[j].ne) edge[j].cost += dist[edge[j].v] - dist[i];
return dist[S] != INF;
}
//S:源点; T汇点; n:点数; flow:最大流量; ans:对应的最小费用
void get_mcmf(int S, int T, int n, ll &flow, ll &ans)
{
flow = ans = 0;
ll res, sum = 0;
do{
do{
fill(aug, aug + n + 1, 0);
}while (flow += (res = dfs(S, S, T, ans, sum, INF)), res > 0);
}while (augment(S, T, n, sum));
}
}mcmf;
const int N = 510;
const int mod = 1e9 + 7;
struct node{
int v, ne;
}edge[N];
int tot, head[N];
void init(int n)
{
tot = 0;
for (int i = 0; i <= n; i++) head[i] = 0;
}
void add(int x, int y)
{
edge[++tot].v = y;
edge[tot].ne = head[x];
head[x] = tot;
}
//树hash
int root1, root2;
int siz[N], hash1[N], hash2[N];
void dfs(int son, int fa, int (&Hash)[N])
{
siz[son] = 1;
for (int i = head[son]; i; i = edge[i].ne)
{
if (edge[i].v == fa) continue;
dfs(edge[i].v, son, Hash);
Hash[son] = (Hash[son] + 1LL * siz[edge[i].v] * Hash[edge[i].v] % mod) % mod;
siz[son] += siz[edge[i].v];
}
Hash[son] ^= 1LL * siz[son] * 1331 % mod;
}
int n, a[N], b[N];
vector<int>v1[N], v2[N];
int dp[N][N]; //dp[i][j]:第1棵树的i子树 和 第2棵树的j子树 相同的最少修改次数
void solve(int x, int y)
{
if (x == y) dp[x][y] = 0;
else dp[x][y] = 1;
for (auto nx: v1[x])
{
for (auto ny: v2[y])
{
if (hash1[nx] != hash2[ny]) continue;
solve(nx, ny);
}
}
int sz1 = v1[x].size(), sz2 = v2[y].size();
int S = 1, T = 1 + sz1 + sz2 + 1;
mcmf.init(T);
for (int i = 1; i <= sz1; i++)
mcmf.add_edge(S, S + i, 1, 0);
for (int i = 1; i <= sz1; i++)
for (int j = 1; j <= sz2; j++)
if (dp[v1[x][i - 1]][v2[y][j - 1]] != 0x3f3f3f3f)
mcmf.add_edge(S + i, S + sz1 + j, 1, dp[v1[x][i - 1]][v2[y][j - 1]]);
for (int i = 1; i <= sz2; i++)
mcmf.add_edge(S + sz1 + i, T, 1, 0);
ll flow, fare;
mcmf.get_mcmf(S, T, T, flow, fare);
dp[x][y] += fare;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
init(n);
for (int i = 1; i <= n; i++)
{
if (a[i] == 0) root1 = i;
else add(a[i], i), v1[a[i]].push_back(i);
}
dfs(root1, 0, hash1);
init(n);
for (int i = 1; i <= n; i++)
{
if (b[i] == 0) root2 = i;
else add(b[i], i), v2[b[i]].push_back(i);
}
dfs(root2, 0, hash2);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = 0x3f3f3f3f;
solve(root1, root2);
// cout << hash1[1] << " " << hash2[1] << endl;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= n; j++)
// cout << dp[i][j] << " ";
// cout << endl;
// }
printf("%d\n", dp[root1][root2]);
return 0;
}
