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();
}