A.Permutation
题意：
给定一个质数，要求给出一段
的排列，使得
或
题解：
暴力枚举或者
的情况即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
bool vis[maxn];
int main()
{
int t;
cin >> t;
while (t--)
{
int p;
cin >> p;
for (int i = 0; i <= p; i++)
vis[i] = false;
vis[0] = true;
vector<int> ans;
ans.push_back(1);
vis[1] = true;
bool flag = true;
int cnt = 1;
ll tmp = 1;
while (cnt < p - 1 && flag)
{
if (!vis[(tmp * 2) % p])
{
tmp = (tmp * 2) % p;
ans.push_back(tmp);
cnt++;
vis[tmp] = true;
continue;
}
if (!vis[(tmp * 3) % p])
{
tmp = (tmp * 3) % p;
ans.push_back(tmp);
cnt++;
vis[tmp] = true;
continue;
}
flag = false;
break;
}
if (!flag)
printf("%d", -1);
else
for (auto i : ans)
printf("%d ", i);
puts("");
}
return 0;
} C.Decrement on the Tree
题意：
给定一棵个节点的带权树，每次操作可以选择两个节点，使得该节点之间的路径上每条边的权值
，询问最少多少次操作可以使得所有权值为
。同时给定
次操作，每次操作都会改变一条边的权值，每次求最少操作次数
题解：
如果一条边的权值，那么必然要访问两个端点各一次，因此可以把问题转化为求访问端点的次数上来。对于每个端点计算有多少条路径从该端点出发，最终答案就是各端点之和除
（因为两个端点才会形成一条路径）。可以发现当其中一条边的权值大于其他所有边的权值时，令最大的权值为
，和该点相连的所有边权之和为
，当
即
时，就需要从该节点连出
条边，否则当
时，当
为偶数时不需要以该点为端点连边，为奇数时只需要连出一条边即可。每次更新只需要更新和该边相连的两个节点的信息即可。附上一张别的博主的图。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int x[maxn], y[maxn];
ll w[maxn], sum[maxn];
multiset<ll, greater<ll>> s[maxn];
ll cal(int x)
{
ll mx = *s[x].begin();
if (mx * 2 > sum[x])
return mx * 2 - sum[x];
return sum[x] % 2;
}
void add(int p)
{
sum[x[p]] += w[p];
sum[y[p]] += w[p];
s[x[p]].insert(w[p]);
s[y[p]].insert(w[p]);
}
void update(int p, ll pw)
{
sum[x[p]] -= w[p];
sum[y[p]] -= w[p];
s[x[p]].erase(s[x[p]].find(w[p]));
s[y[p]].erase(s[y[p]].find(w[p]));
w[p] = pw;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++)
{
scanf("%d%d%lld", &x[i], &y[i], &w[i]);
add(i);
}
ll ans = 0;
for (int i = 1; i <= n; i++)
ans += cal(i);
printf("%lld\n", ans / 2);
while (m--)
{
int p;
ll pw;
scanf("%d%lld", &p, &pw);
ans -= cal(x[p]) + cal(y[p]);
update(p, pw);
add(p);
ans += cal(x[p]) + cal(y[p]);
printf("%lld\n", ans / 2);
}
return 0;
} E.Game
题意：
给定列的俄罗斯方块，每次可以选定一列的某一行开始往左推，过程种遇到和不比它矮的部分可以一起往左，可以推到最左端停止，途中遇到缺口会往下补。询问经过若干次操作最终最长的一列长度为多少
题解：
因为只能往左推，所以只要右边比左边高都能移过来，想一想可以知道就是求最大的前缀和
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll pre[maxn];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
pre[i] = 0;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ll x;
scanf("%lld", &x);
pre[i] = pre[i - 1] + x;
ll res = pre[i] / i + (bool)(pre[i] % i);
ans = max(res, ans);
}
printf("%lld\n", ans);
}
return 0;
} I.Tournament
题意：
有支队伍，要两两进行比赛，要求使得所有队伍停留的时间之和最短（离开时间-到达时间），要求给出一个构造方案
题解：
一开始想的时候先满足，再满足
这样，但是发现这样虽然能使
最快完成，但是最后的就慢了，因此想的使将每个点的时间平均一下。因此对于
支队伍，先让
的队伍进行比赛，再让
和
的队伍比赛，最终
队伍两两比赛。以
等于
为例，首先进行
，对于中间的点因为要
最晚进，但是要
最早走，因此
要放在中间，确定
的位置以后，在
中，
应该是最晚走的，因此
前面为
；而
走了以后
要走，因此
后面为
因此可以得出策略为
for(i=2;i<=n/2;++i)
for(j=1;j<i;++j)
printf("%d %d\n",j,i);
for(i=n/2+1;i<n;++i)
for(j=1;j<=n-i;++j)
printf("%d %d\n",j,i);
for(i=1;i<=n/2;++i)
for(j=n-i+1;j<=n;++j)
printf("%d %d\n",i,j);
for(i=n/2+1;i<n;++i)
for(j=i+1;j<=n;++j)
printf("%d %d\n",i,j); 发现可以前两部分和后两部分可以合并
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
for (int j = 1; j <= min(i - 1, n - i); j++)
printf("%d %d\n", j, i);
printf("1 %d\n", n);
for (int i = 2; i < n; i++)
for (int j = max(n - i + 1, i + 1); j <= n; j++)
printf("%d %d\n", i, j);
}
} J.Identical Trees
题意：
给定两棵有根树，计算第一棵树最少经过多少次节点编号变化可以变成和第二棵一样
题解：
可以想到大体方向上是树形dp，最难的是状态转移，对于若干个父节点和子节点，如果将它们一一对应，其实就有点感觉到想二分图，那么对于当前节点，肯定是要找二分图最小权，而最大权可以求出来，最小权则可以全部取负号，因此状态转移用KN算法即可
#include <bits/stdc++.h>
#define ll long long
#define inf 1 << 30
using namespace std;
const int MAXN = 510;
int mat[MAXN], lx[MAXN], ly[MAXN], slk[MAXN], pre[MAXN];
int nx, ny, ans, mp[MAXN][MAXN];
bool vis[MAXN];
void bfs(int k, int n)
{
int x, y = 0, yy = 0, dlt;
memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; i++)
slk[i] = inf;
mat[y] = k;
while (1)
{
x = mat[y], dlt = inf, vis[y] = 1;
for (int i = 1; i <= n; i++)
if (!vis[i])
{
if (slk[i] > lx[x] + ly[i] - mp[x][i])
slk[i] = lx[x] + ly[i] - mp[x][i], pre[i] = y;
if (slk[i] < dlt)
dlt = slk[i], yy = i;
}
for (int i = 0; i <= n; i++)
{
if (vis[i])
lx[mat[i]] -= dlt, ly[i] += dlt;
else
slk[i] -= dlt;
}
y = yy;
if (mat[y] == -1)
break;
}
while (y)
mat[y] = mat[pre[y]], y = pre[y];
}
int KM(int n)
{
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
memset(mat, -1, sizeof(mat));
for (int i = 1; i <= n; i++)
memset(vis, 0, sizeof(vis)), bfs(i, n);
int ans = 0;
for (int i = 1; i <= n; i++)
if (mat[i] != -1)
ans += -mp[mat[i]][i];
return ans;
} //KM板子
int dp[MAXN][MAXN];
vector<int> T1[MAXN], T2[MAXN]; //存两棵树
void dfs(int p1, int p2)
{
if (p1 != p2)
dp[p1][p2] = 1; //如果当前节点不相等，那么就要修改一次
int sz1 = T1[p1].size(), sz2 = T2[p2].size();
if (sz1 != sz2)//
{
dp[p1][p2] = 1000;
return;
} //如果子树大小都不一样，那么说明是无法变成那样的，赋为INF
if (!sz1)
return; //如果叶节点
for (int i = 0; i < sz1; i++)
for (int j = 0; j < sz2; j++)
dfs(T1[p1][i], T2[p2][j]); //继续递归
for (int i = 0; i < sz1; i++)
for (int j = 0; j < sz2; j++)
mp[i + 1][j + 1] = -dp[T1[p1][i]][T2[p2][j]]; //构建二分图
dp[p1][p2] += KM(sz1); //跑KM
}
int main()
{
int n, pa, rt1, rt2;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &pa);
if (pa)
T1[pa].push_back(i);
else
rt1 = i; //父亲为0即为根
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &pa);
if (pa)
T2[pa].push_back(i);
else
rt2 = i;
}
dfs(rt1, rt2);
printf("%d\n", dp[rt1][rt2]);
} 
京公网安备 11010502036488号