A ：Clam and Fish
简要题意 •
小月有 n 单位的时间都在钓鱼，每个单位时间有四种状态，
。蛤蜊 鱼
0:0 // 0
1:0 //1
2:1//0
3: 1//1
小月事先知道这 n 个时间点的状态。每个时间点有四种可能 的动作：
- 若该时间点有鱼，则可以直接钓鱼。
- 若该时间点有蛤蜊，则可以用该蛤蛎制作一个鱼饵。
- 若该时间点身上有至少一个鱼饵，则可以用一个鱼饵钓一条鱼，钓完后就少 了一个鱼饵。
-
什么事都不做。
请问小月最多可以钓多少条鱼。
输入
2
4
0103
1
1
输出
2
备注:
One possible scenario you can catch two fishes is as follow:
stage 1: Do nothing.
stage 2: Make a pack of fish bait.
stage 3: Catch a fish by a pack of fish bait.
stage 4: Catch the fish that appears in the stage.
状态2，3 有鱼直接钓鱼，状态1，0顺序配合钓鱼，状态1，1顺序配合钓鱼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
int yi;
int main()
{
ios::sync_with_stdio(false);
int t,n,m,yu=0;
cin>>t;
while(t--)
{
yu=0;yi=0;
cin>>n;
cin>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='2'||s[i]=='3') yu++;
else if(s[i]=='1') yi++;
else
{
if(yi)
{
yi--;yu++;
}
}
}
yu+=yi/2;
cout<<yu<<endl;
}
return 0;
}
B：Classical String Problem
简要题意：
有一个字符串，有两种操作：
- 询问第 x 个字符。
-
把最左边的 x 个字符搬到最右边或把最右边 x 个字符搬到最左边。
官方题解：
想像成字符串是头尾接在一起的 ，只需维护一个指针指向当前第一个字符 的位置，就能以 O(1) 的时间复杂度进行每个操作。
• 以 Sample 为例 •
初始时指针在 n 的前面 |nowcoder •
操作 1 询问指针右边第 1 个字符，答案是 n •
操作 2 把 4 个字符搬到右边，相当于把指针向右移 4 个字符 nowc|oder •
操作 3 询问指针右边第 6 个字符，答案是 o •
操作 4 把右边 3 个字符搬到右边，相当于把指针向左移 3 个字符 n|owcoder •
…
输入
nowcoder
6
A 1
M 4
A 6
M -3
M 1
A 1
输出
n
o
w
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(false);
int n,tmp,tip=0,len;
string s;
char c;
cin>>s>>n;
len=s.length();
while(n--)
{
cin>>c>>tmp;
if(c=='A') cout<<s[(tip+tmp-1)%len]<<endl;
else
{
if(tmp>0) tip=(tip+tmp)%len;
else tip=(tip+tmp+len)%len;
}
}
return 0;
}
C：Operation Love
图为某机器人右手手印的形状，左手为右手的对称图形，现在给你一个机器人 手印(可能经过平移及旋转，大小不变)，请判断是左手还右手(保证一定是其中一只手) 。
找出边长为6和9的两条边，判断顺逆，注意精度
#include<bits/stdc++.h>
using namespace std;
#define ll long long
double x[25],y[25];
const double eps=0.1; //偏差值，有时用1e-10
int sgn(double x)//判断x是否等于0
{
if(fabs(x)<eps) return 0;
return x<0? -1:1;
}
struct point
{
double x,y;
point(){}
point(double x,double y):x(x),y(y){}
point operator-(point B) {return point(x-B.x,y-B.y);} //向量减法
};
double dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
point a[25];
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
for(int i=0;i<20;i++)
cin>>a[i].x>>a[i].y;
int bo;
for(int i=0;i<20;i++)
{
if(sgn(dis(a[i],a[(i+19)%20])-36)==0&&sgn(dis(a[i],a[(i+1)%20])-81)==0)
{
bo=sgn(cross(a[(i+19)%20]-a[i],a[(i+1)%20]-a[i]));
break;
}
if(sgn(dis(a[i],a[(i+19)%20])-81)==0&&sgn(dis(a[i],a[(i+1)%20])-36)==0)
{
bo=sgn(cross(a[(i+1)%20]-a[i],a[(i+19)%20]-a[i]));
break;
}
}
if(bo==-1) cout<<"right"<<endl;
else cout<<"left"<<endl;
}
return 0;
}
D:Points Construction Problem
在无限大的格子盘面中，原本所有格子都是白色的，请把其中 n 个格 子涂黑，使得满足格子 x 和格子y 是上下左右相邻且 x , y 异色的 (x,y) 组数恰好为k 个((x,y)和(y,x) 视为相同)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(false);
int t,n,m,x,y,sum,tmp,res;
cin>>t;
while(t--)
{
cin>>n>>m;
if(m%2||m>4*n||m*m<16*n)//m为偶数，最大值4n，最小值m^2>=16n
cout<<"No"<<endl;
else
{
cout<<"Yes"<<endl;
int sum=2*n+2;//当n为一排过去时的边数
if(m>sum) //两种情况，一些在一排里，一些落单
{
tmp=(m-sum)/2;//
for(int i=1;i<=n-tmp;i++) //一排过去，每次边+2
cout<<1<<" "<<i<<endl;
for(int i=3;i<=3+tmp-1;i++) //斜线，每次边+4
cout<<i<<" "<<i<<endl;
}
else//L型，最佳情况，abs(x-y)<=1
{
//m=2(x+y),极值在abs(x-y)<=1处取到，所以x=m/4
x=m/4;y=m/2-x; //
for(int i=1;i<=x;i++)
cout<<i<<" "<<1<<endl;
for(int i=2;i<=y;i++)
cout<<1<<" "<<i<<endl;
//L型，往里填方格，边不变
res=n-(x+y-1);//已填x+y-1个
for(int i=2;i<=x&&res;i++)
for(int j=2;j<=y&&res;j++,res--)
cout<<i<<" "<<j<<endl;
}
}
}
return 0;
}
E：Two Matchings
详解
dp[i]=min(dp[i-4]+dp[i]-dp[i-3],dp[i-6]+dp[i]-dp[i-5]);
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[200100];
int main()
{
ios::sync_with_stdio(false);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>dp[i];
sort(dp+1,dp+n+1);
dp[4]-=dp[1];
dp[6]-=dp[1];
dp[8]=dp[8]-dp[5]+dp[4];
for(int i=10;i<=n;i+=2)
dp[i]=min(dp[i-4]+dp[i]-dp[i-3],dp[i-6]+dp[i]-dp[i-5]);
cout<<2*dp[n]<<endl;
}
return 0;
}
F: Fraction Construction Problem
详解
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b)
{
return b==0? a:gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1;y=0;return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int pri[2000100],cnt=0;
bool st[2000100];
int m[2000100];//数字i的最小因子（除了1）
void prime()
{
m[0]=m[1]=1;
for(int i=2;i<=2000000;i++)
if(m[i]==0)
{
for(int j=i;j<=2000000;j+=i)
if(m[j]==0)
m[j]=i;
}
}
int main()
{
ios::sync_with_stdio(false);
int t,a,b,g;
cin>>t;
prime();
while(t--)
{
cin>>a>>b;
g=gcd(a,b);
if(g>1)
cout<<a/g+b/g<<" "<<b/g<<" "<<1<<" "<<1<<endl;
else
{
//找b的两个互质因子
ll d=1,f=b,k=m[b];
while(k!=1&&f%k==0) d*=k,f/=k;
if(d==b&&f==1) cout<<-1<<" "<<-1<<" "<<-1<<" "<<-1<<endl;
else
{
ll e,c;
exgcd(d,f,e,c);//ed+cf=1
//-ed+cf=1
e*=-1;
//ax+by=gcd(a,b)的其他解为x=x0+k*b; y=y0-k*a
while(e<=0||c<=0) c+=d,e+=f;
e*=a;c*=a;
cout<<c<<" "<<d<<" "<<e<<" "<<f<<endl;
}
}
}
return 0;
}
G：Operating on a Graph
官方题解：
给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次 操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色， 于是所有和 oi 相邻的颜色全都变成 oi (若已没有颜色oi 已被侵略，则该次操作无效)，求最终每个点的颜色。
- 对于每个颜色都维护一个点的链表，储存该颜色中尚未把所有相邻点变为自己颜色的点。
- 用并查集纪录每个点属于哪个颜色。
- 每次操作就会把颜色 oi 的链表中所有相邻的点所属的颜色都变为 oi ， 就直接把对应的链表合并以及在并查集上做对应的操作、
#include<bits/stdc++.h>
using namespace std;
#define ll long long
list<int>G[800100];
int t,n,m,u,v,q,num,fa[800100],fx,fy;
int find(int x) //找到并更新最终结点
{
if(x!=fa[x])
x=fa[x]=find(fa[x]);
return x;
}
void merge(int x,int y) //
{
fx=find(x);
fy=find(y);
if(fx==fy) return; //本来就在一组，不用修改
fa[fy]=fx;
G[fx].splice(G[fx].end(),G[fy]);// 合并
G[fy].clear(); //删去
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=0;i<n;i++) //一开始指向自己+初始化
{
fa[i]=i;
G[i].clear();
}
for (int i=0;i<m;i++)//存入边
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
cin>>q;
while(q--)
{
cin>>num;
if(find(num)!=num)
continue;
//把相连的点归到自己一组
vector<int>v;
for(auto &j: G[num]) //相连的点
{
if(find(j)!=num) //需要修改的点
v.push_back(j);
}
G[num].clear(); //清空
for(auto &j:v) //修改
{
merge(num,j);
}
}
for (int i=0;i<n;i++)
cout<<find(i)<<" ";
cout<<endl;
}
return 0;
}
L：Problem L is the Only Lovely Problem
判断一个字符串是否为 lovely 开头，不分大小写。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(false);
string s;
cin>>s;
for(int i=0;i<6;i++)
if(s[i]>='A'&&s[i]<='Z')
s[i]=s[i]-'A'+'a';
if(s.length()>=6&&s.substr(0,6)=="lovely") cout<<"lovely"<<endl;
else cout<<"ugly"<<endl;
return 0;
}
![submodule集成第三方库[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)