2020牛客暑期多校训练营（第十场）
A. Permutation
题意
给定一个质数p，找到一个1~p-1的排列，使得xi+1 ≡ 2xi (mod p) 或者 xi+1 ≡ 3xi (mod p)。
题解
打表找规律，可以发现 2xi (mod p) 会形成若干个环， 3xi (mod p) 也会形成若干个环。如果在x*2中的某个环里有一个数变成了x*3那么就会形成另一个环。所以要优先考虑每次*2，下一个*2形成环了就变成*3。优先*3也是可以的，但是要考虑到如果p是3，会有取余等于0的情况，所以要判断的时候加一个取模不得零的条件。
代码
#include<bits/stdc++.h>
using namespace std;
bool vis[1001000];
vector<int>v;
int main()
{
int t;
scanf("%d",&t);
while(t--){
v.clear();
memset(vis,0,sizeof(vis));
int n;
scanf("%d",&n);
int flag=0;
v.push_back(1);
vis[1]=1;
int res=1;
for(int i=2;i<n;i++){
if(vis[(res*2)%n]) res*=3;
else res*=2;
res%=n;
if(vis[res]) {flag=1;break;}
v.push_back(res);
vis[res]++;
}
if(flag) printf("-1\n");
else {
for(int i=0;i<v.size();i++) printf("%d ",v[i]);
printf("\n");
}
}
return 0;
}
E. Game
题意
有n列小方块，每列小方块有a[i]个，你可以选择一个位置从右往左推动小方块，当然如果此位置左边和上边也有小方块，它们会跟着一起移动，如果某个小方块移动后悬空，他就会落到下面的小方块上。如果跟着移动的最左边的小方块列为1，则不能移动这个位置。问若干次操作之后小方块的高度最大值的最小值是多少。（看题目的图就很清楚了
题解
二分答案，每次check的时候如果出现了当前位置移动后最大高度大于mid，则此mid不可行，否则可行。实际上就是在找当前位置的前缀和的平均值是否大于mid，大于就不可行，否则可行。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100100];
ll b[100100];
bool check(int mid,int n)
{
for(int i=0;i<n;i++) b[i]=a[i];
ll res=0;
for(int i=0;i<n;i++){
if(b[i]>mid) res-=b[i]-mid;
else res+=mid-b[i];
if(res<0) return false;
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
int l=0,r=1e9,ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid,n)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}javascript:void(0);
I. Tournament
题意
有n个队伍要进行比赛，每两个队伍之间要比一场，每个队伍在他们比赛的第一天来，比赛完的那天走，问怎么安排比赛可以使得所有队伍在赛场待的天数总和最少。
题解
纠结于H题，一直没写这个题，直播的时候dls：你们真的以为自己能冲的过去吗 : )
看着样例构造的话，第一想法：这不就是双for吗，然后就会愉快的wa。那么怎样能够更优呢？
按照上边的做***发现队伍的编号越大等的时间就会越长，那么可以把他们折中一下，让大家等的时间尽量一样。按照出题人的思路：
• 有n个人的日子，至少一天，有至少n-1个人的日子，至少四天。依次类推，可以得到个下界。
• 同时还有另外一个下界，有3个人的日子，至少n(n-1)/2-2天，依次类推。
• 为了达到这个下界，构造的方法就是首先将人分成两个部分。
• 前后分别内部对打，然后中间将先离场的和最后进场的排在中间。
• 依次往外扩
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
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;j<=n-i;j++){
printf("%d %d\n",j,i);
}
}
for(int i=1;i<=n/2;i++){
for(int j=n-i+1;j<=n;j++){
printf("%d %d\n",j,i);
}
}
for(int i=n/2+1;i<=n;i++){
for(int j=i+1;j<=n;j++){
printf("%d %d\n",j,i);
}
}
}
return 0;
}
J. Identical Trees
题意
有两棵形状一样的有根树，分别给出了当前编号的父结点是谁，如果父结点为0，则是根结点。现在要求两棵树根的编号得一样，每个结点父亲的编号得一样，每棵树编号得是1~n的排列，每次操作可以改变一个结点的编号，问最少需要操作几次。
题解
首先肯定要使编号一样的最多，这样需要改的才最少，然后就可以用树形dp，转移的时候用费用流转移。dp[x][y]表示把第一颗树的x子树变成跟第二棵树的y子树一样需要更换的个数。然后转移到x的父亲p跟y的父亲q的时候就是他的p跟q的儿子们匹配一下。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000007;
const int maxn = 2000+10;
const int M = 2e6 + 10;
int head[maxn];
struct Edge
{
int id,nex;
int w,f;// w 花费 f 流
}edge[M<<2];
int cnt;
void add(int x,int y,int f,int w)
{
edge[cnt].id = y;
edge[cnt].f = f;
edge[cnt].w = w;
edge[cnt].nex = head[x];
head[x] = cnt ++ ;
}
int n;
int vis[maxn];
int dis[maxn];
int mflow[maxn];
int per[maxn];
queue<int> qq;
int spfa(int s,int t)
{
for (int i = 0; i<= n ; i++ )
{
vis[i] = 0;
dis[i] = inf;
}
mflow[s] = inf;
qq.push(s);
dis[s] = 0;
vis[s] = 1;
while(!qq.empty())
{
int x= qq.front();
qq.pop();
vis[x] = 0;
for (int i = head[x]; ~i; i = edge[i].nex)
{
int v = edge[i].id;
if(dis[v] > dis[x] + edge[i].w && edge[i].f)
{
// printf("111\n");
dis[v] = dis[x] + edge[i].w;
per[v] = i;
mflow[v] = min(mflow[x],edge[i].f);
if(vis[v])
continue;
vis[v] = 1;
qq.push(v);
}
}
}
if(dis[t] != inf)
return 1;
return 0;
}
void update(int s,int t, int& flow)//flow 流 ans 花费
{
int minn = mflow[t];
for (int i = t; i != s; i = edge[per[i] ^ 1].id)
{
int x = per[i];
edge[x].f -= minn;
edge[x^1].f += minn;
}
flow += minn;
}
int solve(int s,int t, int& flow)
{
int ans = 0;
while(spfa(s,t))
{
ans += dis[t] * mflow[t];
update(s,t,flow);
}
return ans;
}
std::vector<int> vv[2][maxn];
string zxbs[2][maxn];
void getzxbs(int x,int f)
{
std::vector<string> vt;
zxbs[f][x] += '(';
for (int i =0 ; i < vv[f][x].size(); i ++ )
{
int v = vv[f][x][i];
getzxbs(v,f);
vt.pb(zxbs[f][v]);
}
sort(vt.begin(),vt.end());
for (int i = 0; i < vt.size(); i ++ )
{
zxbs[f][x] += vt[i];
}
zxbs[f][x] += ')';
}
int dp[maxn][maxn];
int N;
int bj[maxn];
void dfs(int x,int y)
{
for(int i= 0; i < vv[0][x].size(); i ++ )
{
int v = vv[0][x][i];
for (int j =0 ; j < vv[1][y].size(); j ++ )
{
int p = vv[1][y][j];
if(zxbs[0][v] == zxbs[1][p])
{
dfs(v,p);
}
}
}
if(vv[0][x].size() == 0)
{
if(x == y)
dp[x][y] = 0;
else
dp[x][y] = 1;
return;
}
int s =0 , t = 1;
int pos = 1;
for (int i = 0; i < vv[0][x].size(); i ++ )
{
int v = vv[0][x][i];
bj[v] = ++pos;
}
for (int i =0 ; i < vv[1][y].size(); i ++ )
{
int v = vv[1][y][i];
bj[v + N] = ++ pos;
}
n = pos;
for (int i = 0; i<= n; i ++ )
{
head[i] = -1;
}
cnt = 0;
for(int i= 0; i < vv[0][x].size(); i ++ )
{
int v = vv[0][x][i];
for (int j =0 ; j < vv[1][y].size(); j ++ )
{
int p = vv[1][y][j];
if(zxbs[0][v] == zxbs[1][p])
{
add(bj[v],bj[p + N],1,dp[v][p]);
add(bj[p + N], bj[v],0,-dp[v][p]);
}
}
}
for (int i =0 ; i < vv[0][x].size(); i ++ )
{
int v= bj[vv[0][x][i]];
add(s,v,1,0);
add(v,s,0,0);
}
for (int i =0 ; i < vv[1][y].size(); i ++ )
{
int v= bj[vv[1][y][i] + N];
add(v,t,1,0);
add(t,v,0,0);
}
int p;
dp[x][y] = solve(s,t,p);
if(x != y)
dp[x][y] ++ ;
}
int main()
{
int n;
scanf("%d",&n);
N= n;
int r1,r2;
for (int i =1 ; i <= n; i ++ )
{
int x;
scanf("%d",&x);
if(x != 0)
vv[0][x].pb(i);
else
r1 = i;
}
for (int i =1 ; i <= n; i ++ )
{
int x;
scanf("%d",&x);
if(x != 0)
vv[1][x].pb(i);
else
r2 = i;
}
getzxbs(r1,0);
getzxbs(r2,1);
dfs(r1,r2);
printf("%d\n",dp[r1][r2]);
}
