2020牛客暑期多校训练营（第三场）
2020牛客暑期多校训练营（第三场）
7.18 打一半电脑死机的牛客3
A-Clam and Fish
题意
共n天，每天共有四种状态
- 无鱼无蛤蜊
- 无鱼有蛤蜊
- 有鱼无蛤蜊
- 有鱼有蛤蜊
每天可进行的操作：
- 做鱼饵（当天有蛤蜊）
- 钓鱼（当天有鱼时不消耗鱼饵，无鱼时可用一个鱼饵换一条鱼）
- 啥也不做
求出最多可以抓多少鱼
思路
有鱼的时候抓鱼一定最优，没有鱼的时候先考虑有鱼饵的情况，如果当前鱼饵数小于之后没有鱼的天数，则收集鱼饵，否则就用鱼饵换鱼。这样既没鱼也没鱼饵的时候就可以直接用鱼饵换鱼。
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
代码
#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 在当前排列合法时就可以从最多的情况一个一个点合并。
代码
#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，此时无解。
代码
#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();
}腾讯云开发者
