2020牛客暑期多校训练营（第三场）

w 本文总阅读量次

7.18 打一半电脑死机的牛客3

A-Clam and Fish

题意

共n天，每天共有四种状态

  1. 无鱼无蛤蜊
  2. 无鱼有蛤蜊
  3. 有鱼无蛤蜊
  4. 有鱼有蛤蜊

每天可进行的操作：

  1. 做鱼饵（当天有蛤蜊）
  2. 钓鱼（当天有鱼时不消耗鱼饵，无鱼时可用一个鱼饵换一条鱼）
  3. 啥也不做

求出最多可以抓多少鱼

思路

有鱼的时候抓鱼一定最优，没有鱼的时候先考虑有鱼饵的情况，如果当前鱼饵数小于之后没有鱼的天数，则收集鱼饵，否则就用鱼饵换鱼。这样既没鱼也没鱼饵的时候就可以直接用鱼饵换鱼。

B-Classical String Problem

题意

给定一个字符串 $s$，规定两种操作：

  • $A$ 操作：输出 $s$ 的第 $x$ 个字符；
  • $M$ 操作：将 $s$ 的最右边 $x$ 个字符串移到最左边或者将 $s$ 的最左边 $x$ 个字符串移到最右边

思路

设一个变量 $cur$ ，初始值为 $0$ ，题目本质就是 M 操作时改变 $cur$ 的值，左移右就是让 $cur$ 加上 $x$ 后对字符串长度 $len$ 取模，右移左就是让 $cur$ 减去 $x$ 后对字符串长度 $len$ 取模，$A$ 操作时以 $cur$ 为起点取第 $x$ 个字符，为了保证 $cur$ 的值不越过 $[0,len-1]$ 这个范围，先将 $x$ 对 $len$ 取模，再在计算 $cur$ 时多加一个 $len$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
using namespace std;
const int maxn = 2e6 + 5;
char s[maxn];
void solve(){
    scs(s); int len=strlen(s),cur(0);
    int q; sc(q); getchar(); while(q--){
        char c; int t; c=getchar(); sc(t); getchar();
        if(c=='A') pf("%c\n",s[(t+cur+len-1)%len]);
        else{ cur+=t; if(t<0) cur+=len; cur%=len; }
    } 
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

D-Points Construction Problem

题意

无限大的平面上全部为白点，选择刚好 $n$ 个涂黑，需要有恰好 $m$ 对相邻点颜色不同。求出其中一种方案。

思路

呜呜气死了场上没开这题血亏。就是个简单构造题。

已知有 $n$ 个黑点的情况下，最多有 $4*n$ 对相邻点颜色不同，即分散开来的每个点的四周；而最少的情况是补成方块（或者最接近方块）的形状。同时能发现不可能有奇数点对。非法情况就只有 $m$ 为奇数、$m$ 过小、$m$ 过大，而区间内的任意偶数都能通过固定形状变化而得。

最大情况判掉，反正好写。

只有一列的情况也选择特判，好写一点。因为 $n\leq 50$ ，所以先排出一列间隔 $100$ 的点。之后根据 $m$ 的值合并点。最少的情况为 $n$ 个点排成连续的直线，此时有 $2*n+2$ 个点对。

因为 $n\leq 50$ ，所以最多只有 $7$ 种排列情况。逐一判断。

对于每个排列情况：设每列最多有 $x$ 个。最少情况是所有点排成矩形（或者最接近矩形）；最多情况是先排一个 $x*x$ 的方块，剩下的点排成一列，大概是个小旗的形状。

$m$ 在当前排列合法时就可以从最多的情况一个一个点合并。

代码

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 scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#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;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e4 + 5;
const int mod = 1e9 + 7;
pii ans[maxn];
int slove(int x,int n,int m){
    int t1=2*(x+n/x)+2*(n%x>0),t2=4*x+2*(n-x*x);
    if(t1>m) return 0;
    int r=n-x*x,d=t2-m,u=1,cnt(0);
    rep(i,1,x+1) rep(j,1,x+1) ans[cnt++]=pii(i,j);
    rep(i,1,r+1) ans[cnt++]=pii(x+i,1);
    // 根据差值调整
    int v=cnt-1; 
    while(v>=cnt-d/2){
        rep(j,2,x+1){
            if(i<cnt-d/2) break;
            ans[i]=pii(x+u,j),v--;
        } u++;
    }
    rep(i,0,cnt) pf("%d %d\n",ans[i].first,ans[i].second);
    return 1;
}
int solve(){
    int n,m; sc(n); sc(m);
    int q=1; while(q*q<=n) q++; q--;
    int u=4*q,e=n-q*q; u+=e?n<=q*(q+1)?2:4:0;
    if(m<u||m&1||m>4*n) return pf("No\n"); 
    if(m==4*n){
        pf("Yes\n");
        rep(i,1,n+1)  pf("%d %d\n",i,i);
        return 0;
    }
    int t=4*n,d=t-m; 
    if(m>=2*n+2){
        rep(i,0,n) ans[i]=pii(100*i,100*i);
        pf("Yes\n"); int qaq=1;
        dep(i,n-1,n-d/2) ans[i]=pii(qaq,0),qaq++;
        rep(i,0,n) pf("%d %d\n",ans[i].first,ans[i].second);
        return 0;
    }
    pf("Yes\n");
    rep(i,2,8) if(slove(i,n,m)) return 0;
    // 只用讨论1-7列的情况
}
int main(){
    int _; sc(_); while(_--) solve();
}

F-Fraction Construction Problem

题意

给定 $a$ 、$b$，求满足$\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$的 $c$ 、$d$ 、$e$ 、$f$ ，其中 $d$ 和 $f$ 需小于 $b$

思路

首先考虑 $a$ 和 $b$ 不互质的情况（题目没有保证互质）。可以想到直接让 $c/d$ 为整数，$e$ 和 $f$ 相减一下就得到了。

通分后有 $\frac{c * f-e * d}{d * f}=\frac{a}{b}$（此时 $a$ 、$b$ 互质）。则必须有 $d*f\equiv 0$ $(mod$ $b)$ ，此题需要 $d$ 、$f$ 尽量小即直接考虑 $d * f=b$。

可以初步判掉一部分无解的情况：$b$ 为 $1$ 时和 $b$ 为质数显然无解。

当 $d$ 、$f$ 互质时有 $c * f-e * d=1$ 即 $a * c * f-a * e * d=a$ 。故求 $c$ 、$e$ 可以通过 $exgcd$（最后再乘上 $a$ ）。

还要注意的就是当 $b$ 只有一个质因数时，不存在互质且积为 $b$ 的 $d$ 、$f$，此时无解。

代码

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
57
58
59
60
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){ x=1; y=0; return a; }
    else{
        ll ans=exgcd(b,a%b,y,x);
        y-=(a/b)*x; return ans;
    }
}
int p[maxn],vis[maxn],pn;
void init(){
    rep(i,2,maxn){
        if(!vis[i]) p[pn++]=i;
        for(int j=0;j<pn&&i*p[j]<maxn;j++) vis[i*p[j]]=1;
    } mst(vis,0); rep(i,0,pn) vis[p[i]]++; 
}
int solve(){
    ll a,b; scl(a); scl(b);
    ll g=__gcd(a,b),c,d,e,f;
    if(g>1){
        c=a/b+1; // 不能取上整 参考样例2 2
        d=1; a/=g; b/=g; e=c*b-a; f=b;
        return pf("%lld %lld %lld %lld\n",c,d,e,f);
    } 
    if(b==1||vis[b]) return pf("-1 -1 -1 -1\n");
    // 先约分再判质数是a%b==0的情况是有解的
    // 为1时没有比1小的正数 为质数时无法分解
    vector<int>vv; ll tb=b;
    for(int i=0;1ll*p[i]*p[i]<=tb;++i){
        if(tb%p[i]==0){
            ll res=1;
            while(tb%p[i]==0) tb/=p[i],res*=p[i];
            // 这么计算res可以在后一步枚举的时候保证b/res和res是互质的
            vv.push_back(res);
        }
    } if(tb>1) vv.push_back(tb); // 剩下的大质数也记得要存
    if(vv.size()==1) return pf("-1 -1 -1 -1\n");
    // 只有一个质因数的情况也无解 可以感性理解一下=。=
    for(int x:vv){
        ll d=x,f=b/x,q=exgcd(f,-d,c,e);
        // d和f相乘为b且互质
        ll tt=(ll)(max((1.*c-1)/d,(1.*e-1)/f))+1;
        if(c<=0||e<=0) c+=tt*d,e+=tt*f;
        // 小于0时加到大于0
        if(c*f<e*d) swap(c,e),swap(d,f);
        // 保证结果是正数
        c*=a; e*=a; // 别忘了
        return pf("%lld %lld %lld %lld\n",c,d,e,f);
    }
}
int main(){
    init(); int _; sc(_); while(_--) solve();
}
w