2020 Multi-University Training Contest 7

8.11 差点没签上到的杭电7

1009-Increasing and Decreasing

题意

给定 $n$ 、$x$ 、$y$ ,需要构造一个 $1-n$ 的排列使得排列里 $LIS$ 的长度为 $x$ ,$LDS$ 的长度为 $y$ 。如果有多个满足要求的排列,选择其中字典序最小的。

思路

构造的思路是:由于有字典序的要求,考虑尽量把 $LIS$ 放在最前面。选择连续递增的小于 $x$ 的一部分(可能为 $0$ ),将长度设为 $f$ ,后面有长度为 $x-f$ 的分别递减的小块。设小块数量为 $t$ ,则可以列出 $t+n-t*y=x$ ,则 $t=\frac{n-x}{y-1}$ 。小块内不一定取满则 $t$ 需要取上整。

可以发现当 $x+y>n+1$ 时没有答案。同时根据分小块的结论可以发现在 $x*y<n$ 时也不存在解。

由于后面有对 $y-1$ 进行的除法操作,所以当 $x=n$ ,$y=1$ 时选择特判。代码里直接将所有 $x+y=n+1$ 的情况特判。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
const int maxn = 1e6 + 5;
int ans[maxn];
int solve(){
int n,x,y; sc(n); sc(x); sc(y);
if(x+y>n+1||1ll*x*y<n) return pf("NO\n");
if(x+y==n+1){
pf("YES\n");
rep(i,1,x) pf("%d ",i);
dep(i,n,x) pf("%d%c",i," \n"[i==x]);
return 0;
} pf("YES\n");
int t=(n-x+y-2)/(y-1),f=max(0,x-t);
rep(i,1,f+1) ans[i]=i;
int pos=n-y+1,cnt(0),tot(0); dep(i,n,f+1){
ans[pos]=i; pos++; cnt++; tot++;
if(cnt==y) cnt=0,pos-=2*y;
pos=max(pos,f+1);
} rep(i,1,n+1) pf("%d%c",ans[i]," \n"[i==n]);
return 0;
}
int main(){
int _; sc(_); while(_--) solve();
}

1010-Jogging

题意

一个点 $(x,y)$ 合法当且仅当满足 $gcd(x,y)>1$ 。设一个合法点周围八个点内的合法点数为 $z$ ,到达一个合法点后有 $\frac{1}{z+1}$ 的概率留在原地,$\frac{z}{z+1}$ 的概率到周围的合法点。给定点 $(x,y)$ ,问在时间趋于正无穷时回到此点的概率。

思路

首先可以想到,这样的点不会特别多,可以考虑直接暴搜。特别的,当周围的点对有横竖坐标相同的情况,这时点是无穷多的,加个标记判掉。结论是给定点对周围合法点数/所有能到的合法点周围的合法点总和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
int ff;
queue<pii>q;
map<pii,int>mp;
void dfs(ll x,ll y){
if(ff) return;
if(mp.count(pii(x,y))) return;
if(x==y){ ff++; return; }
if(__gcd(x,y)==1) return;
q.push(pii(x,y));
mp[pii(x,y)]=1;
dfs(x+1,y); dfs(x,y+1);
dfs(x-1,y); dfs(x,y-1);
dfs(x+1,y+1); dfs(x+1,y-1);
dfs(x-1,y+1); dfs(x-1,y-1);
}
int cal(ll x,ll y){
int ans(0);
if(mp.count(pii(x-1,y))) ans++;
if(mp.count(pii(x,y-1))) ans++;
if(mp.count(pii(x+1,y))) ans++;
if(mp.count(pii(x,y+1))) ans++;
if(mp.count(pii(x-1,y-1))) ans++;
if(mp.count(pii(x-1,y+1))) ans++;
if(mp.count(pii(x+1,y-1))) ans++;
if(mp.count(pii(x+1,y+1))) ans++;
return ans;
}
int solve(){
ll x,y; scl(x); scl(y);
mp.clear(); ff=0;
while(!q.empty()) q.pop();
dfs(x,y); if(ff) return pf("0/1\n");
ll sz=q.size(),ans=sz,cnt=1+cal(x,y);
while(!q.empty()){
ll x=q.front().first,y=q.front().second; q.pop();
if(mp.count(pii(x-1,y))) ans++;
if(mp.count(pii(x,y-1))) ans++;
if(mp.count(pii(x+1,y))) ans++;
if(mp.count(pii(x,y+1))) ans++;
if(mp.count(pii(x-1,y-1))) ans++;
if(mp.count(pii(x-1,y+1))) ans++;
if(mp.count(pii(x+1,y-1))) ans++;
if(mp.count(pii(x+1,y+1))) ans++;
} ll g=__gcd(ans,cnt); ans/=g; cnt/=g;
return pf("%lld/%lld\n",cnt,ans);
}
int main(){
int _; sc(_); while(_--) solve();
}