2020牛客多校第三场题解
A. Clam and Fish
签到。题意比较麻烦，注意桌子上只有饵料的时候也可以不拿，利用之前的饵料钓鱼
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n; scanf("%d",&n);
string s; cin >> s;
int ans = 0, er = 0;
for(int i=0;i<n;i++) {
if(s[i]=='0'&&er) ans++,er--;
if(s[i]=='1') er++;
if(s[i]=='2'|| s[i]=='3') ans++;
}
ans += er/2; //这一行是关键，把所有之前收饵料的环节的一半用来钓鱼，保证最大化
printf("%d\n",ans);
}
} B. Classical String Problem
题意
两种操作，A x 代表输出字符串第x个字符，M x代表将字符串左移位/右移位x个位置。
解题
签到，本质是下标取模。注意由于字符串长度和询问组数比较多，所以变化量delta需要取模防止溢出。同时cin/cout可能超时。
#include <bits/stdc++.h>
using namespace std;
int main() {
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
string s; cin >> s;
int len = s.length();
int t; cin >> t;
int d = 0;
while(t--) {
char a; cin >> a;
int b; cin >> b;
if(a=='A') cout<<s[(b-1+d)%len]<<endl;
else d+=len+b;
d = d%len+len;
}
} C. Operation Love
根据固定的几何图形判断左右手。比赛时由于精度过高一直WA。思路就是先判断好四个关键点，之后再根据左手和右手底边到下一条边叉积的正负不同来进行判断。注意，精度1e-4可以通过，但是更高的精度将无法通过。
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-4;
struct point {
double x,y;
}data[25];
double dis(point aa, point bb) {
return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}
double cross(point aa, point bb, point cc) {
return (bb.x-aa.x)*(cc.y-aa.y)-(cc.x-bb.x)*(bb.y-aa.y);
}
int same(double a, double b) {
if(fabs(a-b)<eps) return 1;
return 0;
}
int main() {
//freopen("in.txt","r",stdin);
int t;
scanf("%d", &t);
while(t--) {
for(int i=0;i<20;i++) {
scanf("%lf%lf", &data[i].x, &data[i].y);
}
int d1=0, d2=0, d3=0, flag=0;
for(int i=0;i<20;i++) {
d1=i,d2=(i+1)%20,d3=(i+2)%20;
if(same(dis(data[d1],data[d2]), 9)) {
if(cross(data[d1],data[d2],data[d3]) > 0 && same(dis(data[d2],data[d3]),6) ||
cross(data[d1],data[d2],data[d3]) < 0 && same(dis(data[d2],data[d3]),8)) {
puts("left"); flag=1; break;
}
}
}
if(!flag) puts("right");
}
} F. Fraction Construction Problem
题意
给定正整数 ，
求，满足
数据范围
解题
化简得
首先若ab不互质，则可以轻松构造出一组解d=b/gcd(a,b), f=1
ab互质，则将b分解为互质的两个数之积（不互质则ab不互质），之后根据exgcd求解方程，注意符号的正负，暴力卡过去。
要尽量把不必要的long long开成int防止超时
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}
inline ll exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a%b, x, y);
ll z = x;
x = y;
y = z - y * (a/b);
return d;
}
int a, b, d, f;
ll c, e;
int main() {
// freopen("in.txt", "r", stdin);
int t;
scanf("%d",&t);
while(t--) {
scanf("%lld%lld",&a,&b);
int g = gcd(a,b);
if(b == 1) printf("-1 -1 -1 -1\n");
else if(g!=1) {
printf("%d %d %d %d\n",(a+b)/g,b/g,1,1);
} else {
int flag = 0;
for(int i=2; i*i<b; i++) {
if(b%i==0 && gcd(i,b/i)==1) {
d = i;
f = b/i;
flag = 1;
break;
}
}
if(!flag) printf("-1 -1 -1 -1\n");
else {
exgcd(f, d, c, e);
c *= 1LL*a;
e *= 1LL*a;
if(c > 0 && e < 0)
printf("%lld %d %lld %d\n",c,d,-e,f);
else
printf("%lld %d %lld %d\n",e,f,-c,d);
}
}
}
} G. Operating on a Graph
题意
给一个 个点的 Graph，第 i 个点一刚开始是第
种颜色，接着有 k 次 操作，第 i 次操作有个参数
代表颜色
会侵略所有和自己相邻的颜色， 于是所有和
相邻的颜色全都变成
(若已没有颜色
已被侵略，则该次操作无效)，求最终每个点的颜色。
解题
并查集
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
vector <int> a[maxn], temp;
int fa[maxn];
void init(int n) {
for(int i = 0; i<=n; i++) fa[i]=i;
}
int find(int x) {
return (fa[x] == x)?x:fa[x] = find(fa[x]);
}
int n,m,x,y,q,o,t;
int main() {
// freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
init(n);
for(int i=0;i<=n;i++) a[i].clear();
while(m--) {
scanf("%d%d",&x,&y);
a[x].push_back(y),
a[y].push_back(x);
}
scanf("%d",&q);
while(q--) {
scanf("%d",&o);
if(fa[o]!=o) continue; // 不存在这种颜色，直接取消操作
temp = a[o];
a[o].clear();
for(int i=0;i<temp.size();i++) { // 遍历每个相邻的点
int f = find(temp[i]);
if(f != o) {
fa[f] = o;
// 本质上就是合并两个动态数组a[o]和a[f]
if(a[o].size()<a[f].size())
swap(a[o],a[f]);
for(int j=0; j<a[f].size(); j++)
a[o].push_back(a[f][j]);
}
}
}
for(int i=0;i<n;i++) {
printf("%d ", find(i));
}
printf("\n");
}
} L. Problem L is the Only Lovely Problem
签到。判断字符串首是否有lovely，用了个新学的函数。
string :: find(string substring) 返回字符串在母串中的起始下标位置（下标记录），如果没有找到，那么会返回s.npos
字节跳动公司氛围 560人发布
