2020牛客暑期多校训练营(第三场)

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