ABCFL
A. Clam and Fish
题意
一个游戏有n次，每次有四种类型：
0：没有鱼也没有蛤蜊
1：没有鱼有一个蛤蜊
2：有一个鱼没有蛤蜊
3：有一个鱼和一个蛤蜊
游戏每次可以执行下面4中操作中的一种：
1：用蛤蜊换一报鱼饵
2：直接抓一条鱼
3：用鱼饵钓一条鱼
4：不做任何操作
问n次之后最多可以拥有鱼。
题解
如果有鱼的话肯定要优先选择2直接抓鱼，这样不需要鱼饵。如果没有鱼的话有蛤蜊的话，就先换鱼饵，因为如果遇到没有鱼也没有蛤蜊的时候就可以钓鱼了。如果鱼饵多出来了，可以在最后的时候两个鱼饵变成一条鱼，相当于换一次鱼饵钓一次鱼。如果没有蛤蜊也没有鱼，如果有鱼饵的话就钓鱼，否则就跳过。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
int n;
string s;
cin>>n>>s;
int p=0,q=0;
for(int i=0;i<n;i++){
if(s[i]=='0'){
if(p) p--,q++;
else continue;
}
else if(s[i]=='1'){
p++;
}
else q++;
}
q+=p/2;
cout<<q<<endl;
}
}B. Classical String Problem
题意
有n个操作，如果操作是A，输出第x个数字。如果操作是M，并且x是正数，那么就将前x个字符移到最后边，否则将后x个字符移到最前边。
题解
被队友一句话点醒，维护一个起点就好了，因为这个移动就相当于是起点在动，字符串是不动的。如果x>0 ，那么起点标志向后移动x位，否则向前移动x位，当然要记得对字符串长度取余。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
char s[2001000];
int main()
{
scanf("%s",s);
int n;
scanf("%d",&n);
int b=0;
int p=strlen(s);
while(n--){
char a[2];
scanf("%s",a);
int x;
scanf("%d",&x);
if(a[0]=='A'){
printf("%c\n",s[(b+x-1)%p]);
}
else{
b+=x;
b=(b+p)%p;
}
}
return 0;
}C. Openration Love
题意
t组测试，每次测试按顺时针或逆时针给20个点，是一个手的形状，题目给出的图是右手，判断给出的点组成的是左手还是右手。
题解
这个题是真的坑啊，可以用凸包解，板子求出凸包的所有点记录下来，然后求一下长度为6的边（即大拇指）的下一条边是不是底下长度为9的边。是的话就是右手，否则为左手。但是，这个题他卡精度，两个边长相等判断的时候要用fabs(d1,d2)<1e-5，比1e-5更大一些也可以，小的话会wa，wa到哭。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
struct node
{
double x,y;
}p[100],s[100];
double xx,yy;
double cross(node a,node b,node c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp1(node a,node b)
{
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int cmp2(node a,node b)
{
if(atan2(a.y-yy,a.x-xx)==atan2(b.y-yy,b.x-xx)) return a.x<b.x;
else return atan2(a.y-yy,a.x-xx)<atan2(b.y-yy,b.x-xx);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
int n=20;
for(int i=0;i<n;i++){
cin>>p[i].x>>p[i].y;
}
sort(p,p+n,cmp1);
xx=p[0].x,yy=p[0].y;
sort(p+1,p+n,cmp2);
s[0]=p[0],s[1]=p[1];
int top=1;
for(int i=2;i<n;i++){
while(cross(s[top-1],s[top],p[i])<0) top--;
//如果是向右转，这个中间点就不是我们要找的点
s[++top]=p[i];//如果是向左转，就加进来
}
double q=dis({1.0,0.0},{1.0,6.0});
double y=dis({1.0,0.0},{10.0,0.0});
for(int i=0;i<=top;i++){
double k=dis(s[i],s[(i+1)%(top+1)]);
if(fabs(q-k)<1e-1) {
double x=dis(s[(i+1)%(top+1)],s[(i+2)%(top+1)]);
if(fabs(x-y)<1e-1) cout<<"right"<<endl;
else cout<<"left"<<endl;
break;
}
}
}
return 0;
}F. Fonction Construction Problem
题意
给你a和b，求出一组解 c d e f 满足，并且d<b,f<b
没有解的话输出 “-1 -1 -1 -1” 。
题解
b是1的时候肯定是无解的，分母不能为0，所以直接输出四个-1。
令g=gcd(a,b)，如果g>1，说明分式不是最简的，那么可以给他化简成
，那么解就是d=f=b'，c=a'+1，e=1；
如果g==1，将分式通分得到
，将b分解成d * f，d和f互质，如果没有这样的d和f，就输出四个-1。用大雪菜老师的线性筛预处理2e6的所有数的最小质因子，就可以在O(logn)内求出d和f了。那么现在只需要求出cf-de=a就好了，这不就是拓展欧几里得吗，至于怎么求其他的几组解，可以看这个博客：https://www.cnblogs.com/Antigonae/p/10106068.html 。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const ll maxn=2e6+10;
ll st[maxn];
ll prime[maxn];
ll factor[maxn]; //记录最小质因数
ll cnt;
void Prime(ll n)
{
cnt=0;
for(ll i=2;i<=n;i++){
if(!st[i]) prime[cnt++]=i,factor[i]=i;
for(int j=0;prime[j]*i<=n;j++){
st[prime[j]*i]=1;
factor[prime[j]*i]=prime[j];
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a, ll b)
{
return b? gcd(b, a%b) : a;
}
void ex_gcd(ll a, ll b, ll &x, ll &y)
{
if(!b){
x = 1, y = 0;
return ;
}
ex_gcd(b, a%b, y, x);
y -= a/b * x;
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Prime(2000000);
int t;
cin>>t;
while(t--){
ll a,b;
cin>>a>>b;
if(b==1) {cout<<"-1 -1 -1 -1"<<endl;continue;}
ll g=gcd(a,b);
if(g>1){
cout<<a/g+1<<' '<<b/g<<' '<<1<<' '<<b/g<<endl;
}
else{
ll f=1,d=b,p=factor[b];
while(p>1&&d%p==0) d/=p,f*=p;
if(d==1){ //没有两个互质的质因子
cout<<"-1 -1 -1 -1"<<endl;
continue;
}
ll c,e;
ex_gcd(d,f,e,c);
e=-e;
if(c<=0||e<=0){
ll c1=(c%d+d)%d;
ll e1=(e%f+f)%f;
ll res=max(0ll,max((e1-e)/f,(c1-c)/d));
e+=f*res,c+=d*res;
}
e*=a,c*=a;
cout<<c<<' '<<d<<' '<<e<<' '<<f<<endl;
}
}
return 0;
}
L. Problem L is the Only Lovely Problem
题意
不管大小写，如果给出的字符串前6个字符是lovely，那么输出 "lovely "，否则输出 "ugly" 。
题解
先判断一下字符串的长度，如果小于6的话，就可以直接输出ugly，然后在去判断前6个字符是不是和lovely一样。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s="lovely";
string a;
cin>>a;
if(a.size()<6) cout<<"ugly"<<endl;
else{
for(int i=0;i<a.size();i++){
if(i>5){
cout<<s<<endl;
return 0;
}
if(a[i]==s[i]||a[i]==s[i]-'a'+'A') continue;
else break;
}
cout<<"ugly"<<endl;
}
return 0;
}
京公网安备 11010502036488号