2020 Multi-University Training Contest 7

wenzhuan

发布于 2022-08-15 12:44:31

3220

发布于 2022-08-15 12:44:31

文章被收录于专栏：你会烧尽还是结冰你会烧尽还是结冰

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+1x*y<n

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

代码

#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)>1z ，到达一个合法点后有 \frac{1}{z+1} 的概率留在原地，\frac{z}{z+1} 的概率到周围的合法点。给定点 (x,y) ，问在时间趋于正无穷时回到此点的概率。

思路

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

代码

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度