A. Permutation

题意

给定一个质数p，找到一个1~p-1的排列，使得xi₊1 ≡ 2x_i(mod p) 或者 x_i+1 ≡ 3x_i (mod p)。

题解

打表找规律，可以发现 2x_i(mod p) 会形成若干个环， 3x_i (mod p) 也会形成若干个环。如果在x*2中的某个环里有一个数变成了x*3那么就会形成另一个环。所以要优先考虑每次*2，下一个*2形成环了就变成*3。优先*3也是可以的，但是要考虑到如果p是3，会有取余等于0的情况，所以要判断的时候加一个取模不得零的条件。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 bool vis[1001000];
 5 vector<int>v;
 6  
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     while(t--){
12         v.clear();
13         memset(vis,0,sizeof(vis));
14         int n;
15         scanf("%d",&n);
16         int flag=0;
17         v.push_back(1);
18         vis[1]=1;
19         int res=1;
20         for(int i=2;i<n;i++){
21             if(vis[(res*2)%n]) res*=3;
22             else res*=2;
23             res%=n;
24             if(vis[res]) {flag=1;break;}
25             v.push_back(res);
26             vis[res]++;
27         }
28         if(flag) printf("-1
");
29         else {
30             for(int i=0;i<v.size();i++) printf("%d ",v[i]);
31             printf("
");
32         }
33     }
34     return 0;
35 }

E. Game

题意

有n列小方块，每列小方块有a[i]个，你可以选择一个位置从右往左推动小方块，当然如果此位置左边和上边也有小方块，它们会跟着一起移动，如果某个小方块移动后悬空，他就会落到下面的小方块上。如果跟着移动的最左边的小方块列为1，则不能移动这个位置。问若干次操作之后小方块的高度最大值的最小值是多少。（看题目的图就很清楚了

题解

二分答案，每次check的时候如果出现了当前位置移动后最大高度大于mid，则此mid不可行，否则可行。实际上就是在找当前位置的前缀和的平均值是否大于mid，大于就不可行，否则可行。

代码

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4  
 5 ll a[100100];
 6 ll b[100100];
 7  
 8 bool check(int mid,int n)
 9 {
10     for(int i=0;i<n;i++) b[i]=a[i];
11     ll res=0;
12     for(int i=0;i<n;i++){
13         if(b[i]>mid) res-=b[i]-mid;
14         else res+=mid-b[i];
15         if(res<0) return false;
16     }
17     return true;
18 }
19  
20 int main()
21 {
22     int t;
23     scanf("%d",&t);
24     while(t--){
25         int n;
26         scanf("%d",&n);
27         for(int i=0;i<n;i++) scanf("%lld",&a[i]);
28         int l=0,r=1e9,ans=0;
29         while(l<=r){
30             int mid=l+r>>1;
31             if(check(mid,n)){
32                 ans=mid;
33                 r=mid-1;
34             }
35             else l=mid+1;
36         }
37         printf("%d
",ans);
38     }
39     return 0;
40 }javascript:void(0);

I. Tournament

题意

有n个队伍要进行比赛，每两个队伍之间要比一场，每个队伍在他们比赛的第一天来，比赛完的那天走，问怎么安排比赛可以使得所有队伍在赛场待的天数总和最少。

题解

纠结于H题，一直没写这个题，直播的时候dls：你们真的以为自己能冲的过去吗 : )

看着样例构造的话，第一想法：这不就是双for吗，然后就会愉快的wa。那么怎样能够更优呢？

按照上边的做***发现队伍的编号越大等的时间就会越长，那么可以把他们折中一下，让大家等的时间尽量一样。按照出题人的思路：

• 有n个人的日子，至少一天，有至少n-1个人的日子，至少四天。依次类推，可以得到个下界。

• 同时还有另外一个下界，有3个人的日子，至少n(n-1)/2-2天，依次类推。

• 为了达到这个下界，构造的方法就是首先将人分成两个部分。

• 前后分别内部对打，然后中间将先离场的和最后进场的排在中间。

• 依次往外扩

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 int main()
 5 {
 6     int t;
 7     scanf("%d",&t);
 8     while(t--){
 9         int n;
10         scanf("%d",&n);
11         for(int i=2;i<=n/2;i++){
12             for(int j=1;j<i;j++){
13                 printf("%d %d
",j,i);
14             }
15         }
16         for(int i=n/2+1;i<=n;i++){
17             for(int j=1;j<=n-i;j++){
18                 printf("%d %d
",j,i);
19             }
20         }
21         for(int i=1;i<=n/2;i++){
22             for(int j=n-i+1;j<=n;j++){
23                 printf("%d %d
",j,i);
24             }
25         }
26         for(int i=n/2+1;i<=n;i++){
27             for(int j=i+1;j<=n;j++){
28                 printf("%d %d
",j,i);
29             }
30         }
31     }
32     return 0;
33 }

J. Identical Trees

题意

有两棵形状一样的有根树，分别给出了当前编号的父结点是谁，如果父结点为0，则是根结点。现在要求两棵树根的编号得一样，每个结点父亲的编号得一样，每棵树编号得是1~n的排列，每次操作可以改变一个结点的编号，问最少需要操作几次。

题解

首先肯定要使编号一样的最多，这样需要改的才最少，然后就可以用树形dp，转移的时候用费用流转移。dp[x][y]表示把第一颗树的x子树变成跟第二棵树的y子树一样需要更换的个数。然后转移到x的父亲p跟y的父亲q的时候就是他的p跟q的儿子们匹配一下。

代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef pair<int,int> pii;
  5 typedef pair<ll,ll> pll;
  6 typedef pair<double,double> pdd;
  7 typedef unsigned long long ull;
  8 typedef set<int>::iterator sit;
  9 #define st first
 10 #define sd second
 11 #define mkp make_pair
 12 #define pb push_back
 13 const int inf = 0x3f3f3f3f;
 14 const ll INF = 0x3f3f3f3f3f3f3f3f;
 15 const ll mod = 1000000007;
 16 const int maxn = 2000+10;
 17 const int M = 2e6 + 10;
 18  
 19 int head[maxn];
 20 struct Edge
 21 {
 22     int id,nex;
 23     int w,f;// w 花费 f 流
 24 }edge[M<<2];
 25 int cnt;
 26 void add(int x,int y,int f,int w)
 27 {
 28     edge[cnt].id = y;
 29     edge[cnt].f = f;
 30     edge[cnt].w = w;
 31     edge[cnt].nex = head[x];
 32     head[x] = cnt ++ ;
 33 }
 34 int n;
 35  
 36 int vis[maxn];
 37 int dis[maxn];
 38 int mflow[maxn];
 39 int per[maxn];
 40 queue<int> qq;
 41  
 42 int spfa(int s,int t)
 43 {
 44     for (int i = 0; i<= n ; i++ )
 45     {
 46         vis[i] = 0;
 47         dis[i] = inf;
 48     }
 49     mflow[s] = inf;
 50     qq.push(s);
 51     dis[s] = 0;
 52     vis[s] = 1;
 53     while(!qq.empty())
 54     {
 55         int x=  qq.front();
 56         qq.pop();
 57         vis[x] = 0;
 58         for (int i = head[x]; ~i; i = edge[i].nex)
 59         {
 60             int v = edge[i].id;
 61             if(dis[v] > dis[x] + edge[i].w && edge[i].f)
 62             {
 63                 // printf("111
");
 64                 dis[v] = dis[x] + edge[i].w;
 65                 per[v] = i;
 66                 mflow[v] = min(mflow[x],edge[i].f);
 67                 if(vis[v])
 68                     continue;
 69                 vis[v] = 1;
 70                 qq.push(v);
 71             }
 72         }
 73     }
 74     if(dis[t] != inf)
 75         return 1;
 76     return 0;
 77 }
 78 void update(int s,int t, int& flow)//flow 流  ans 花费
 79 {
 80     int minn = mflow[t];
 81     for (int i = t; i != s; i = edge[per[i] ^ 1].id)
 82     {
 83         int x = per[i];
 84         edge[x].f -= minn;
 85         edge[x^1].f += minn;
 86     }
 87     flow += minn;
 88 }
 89  
 90 int solve(int s,int t, int& flow)
 91 {
 92     int ans = 0;
 93     while(spfa(s,t))
 94     {
 95         ans += dis[t] * mflow[t];
 96         update(s,t,flow);
 97     }
 98     return ans;
 99 }
100  
101 std::vector<int> vv[2][maxn];
102  
103 string zxbs[2][maxn];
104 void getzxbs(int x,int f)
105 {
106     std::vector<string> vt;
107     zxbs[f][x] += '(';
108     for (int i =0 ; i < vv[f][x].size(); i ++ )
109     {
110         int v = vv[f][x][i];
111         getzxbs(v,f);
112         vt.pb(zxbs[f][v]);
113     }
114     sort(vt.begin(),vt.end());
115     for (int i = 0; i < vt.size(); i ++ )
116     {
117         zxbs[f][x] += vt[i];
118     }
119     zxbs[f][x] += ')';
120 }
121 int dp[maxn][maxn];
122 int N;
123 int bj[maxn];
124 void dfs(int x,int y)
125 {
126     for(int i= 0; i < vv[0][x].size(); i ++ )
127     {
128         int v = vv[0][x][i];
129         for (int j =0 ; j < vv[1][y].size(); j ++ )
130         {
131  
132             int p = vv[1][y][j];
133             if(zxbs[0][v] == zxbs[1][p])
134             {
135                 dfs(v,p);
136             }
137         }
138     }
139     if(vv[0][x].size() == 0)
140     {
141         if(x == y)
142             dp[x][y] = 0;
143         else
144             dp[x][y] = 1;
145         return;
146     }
147  
148     int s =0 , t = 1;
149     int pos = 1;
150     for (int i = 0; i < vv[0][x].size(); i ++ )
151     {
152         int v = vv[0][x][i];
153         bj[v] = ++pos;
154     }
155     for (int i =0 ; i < vv[1][y].size(); i ++ )
156     {
157         int v = vv[1][y][i];
158         bj[v + N] = ++ pos;
159     }
160     n = pos;
161     for (int i = 0; i<= n; i ++ )
162     {
163         head[i] = -1;
164     }
165     cnt = 0;
166     for(int i= 0; i < vv[0][x].size(); i ++ )
167     {
168         int v = vv[0][x][i];
169         for (int j =0 ; j < vv[1][y].size(); j ++ )
170         {
171             int p = vv[1][y][j];
172             if(zxbs[0][v] == zxbs[1][p])
173             {
174                 add(bj[v],bj[p + N],1,dp[v][p]);
175                 add(bj[p + N], bj[v],0,-dp[v][p]);
176             }
177         }
178     }
179     for (int i =0 ; i < vv[0][x].size(); i ++ )
180     {
181         int v= bj[vv[0][x][i]];
182         add(s,v,1,0);
183         add(v,s,0,0);
184     }
185     for (int i =0 ; i < vv[1][y].size(); i ++ )
186     {
187         int v= bj[vv[1][y][i] + N];
188         add(v,t,1,0);
189         add(t,v,0,0);
190     }
191     int p;
192     dp[x][y] = solve(s,t,p);
193     if(x != y)
194         dp[x][y] ++ ;
195 }
196  
197 int main()
198 {
199     int n;
200     scanf("%d",&n);
201     N=  n;
202     int r1,r2;
203     for (int i =1 ; i <= n; i ++ )
204     {
205         int x;
206         scanf("%d",&x);
207         if(x != 0)
208             vv[0][x].pb(i);
209         else
210             r1 = i;
211     }
212     for (int i =1 ; i <= n; i ++ )
213     {
214         int x;
215         scanf("%d",&x);
216         if(x != 0)
217             vv[1][x].pb(i);
218         else
219             r2 = i;
220     }
221     getzxbs(r1,0);
222     getzxbs(r2,1);
223     dfs(r1,r2);
224     printf("%d
",dp[r1][r2]);
225  
226 }