A - Collecting Coins
首先把少的那两个补到与最大的那个相等，然后再判剩下的$n$是不是3的倍数就行了。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
ll n,a[3];
int main()
{
int T;cin>>T;
while(T--)
{
cin>>a[0]>>a[1]>>a[2]>>n;
sort(a,a+3);
n-=a[2]-a[0];
n-=a[2]-a[1];
if(n<0){puts("NO");continue;}
if(n%3){puts("NO");continue;}
else puts("YES");
}
return 0;
}
B - Collecting Packages
按照$x$排序，然后有解的条件就是$y$单调不减就行。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
int n;
struct point
{
int x;
int y;
}a[1050];
bool cmp(const point &x,const point &y)
{
return x.x<y.x||(x.x==y.x&&x.y<y.y);
}
int main()
{
int Test;cin>>Test;
while(Test--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a+1,a+n+1,cmp);
a[n+1].x=1010,a[n+1].y=1010;
bool exist=true;
for(int i=1;i<=n;++i)
{
if(a[i].y<a[i-1].y){exist=false;break;}
}
if(!exist){puts("NO");continue;}
point now;now.x=now.y=0;
puts("YES");
for(int i=1;i<=n;++i)
{
int dx=a[i].x-now.x;
int dy=a[i].y-now.y;
for(int j=1;j<=dx;++j)printf("R");
for(int j=1;j<=dy;++j)printf("U");
now.x=a[i].x;now.y=a[i].y;
}
puts("");
}
return 0;
}
C - Product of Three Numbers
这题我还疯狂wa...
方法其实很多，我的方法就是令a为最小的质因子，c为最大的质因子，b就是原数除以a和c就行。
就是只有一种质因子的时候要特判一下，然后特判地有些复杂......
嘛，还是自己写丑了。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
int n;
int pri[40050];
int a,b,c;
vector <int> v;
//
int main()
{
int T;cin>>T;
while(T--)
{
cin>>n;int num=n;a=b=c=0;
v.clear();
memset(pri,0,(sqrt(num)+5)*sizeof(int));
for(int i=2;i<=sqrt(num);++i)
{
while(n%i==0){pri[i]++;n/=i;}
}
for(int i=2;i<=sqrt(num);++i)
{
if(pri[i])v.push_back(i);
}
if(v.size()==0){puts("NO");continue;}
if(v.size()==1)
{
if(pri[v[0]]<6&&(v[0]*v[0]*v[0]>=sqrt(num)))
{puts("NO");continue;}
else if(pri[v[0]]<3){puts("NO");continue;}
else
{
a=v[0];b=v[0]*v[0];c=num/(a*b);
}
}
else
{
a=v[0];c=v[v.size()-1];
b=num/(a*c);
if(a==b||b==c){puts("NO");continue;}
}
puts("YES");
printf("%d %d %d\n",a,b,c);
}
return 0;
}
D - MEX maximizing
这题因为那个$x$可以随便加减，所以我们只关心$y_i \mod x$的mex值就行，
然后mex值可能会超过$x$，然后我们也只需要集合中某个元素出现过，那就把相同的余数加上$x$，比如说现在有两个$0$，那么我可以让其中一个$0$变为$x$，可以保证原mex值不会减小，可能会增大。
然后就考虑怎么维护mex值。实际上只需要按照定义来，开一个set或者树状数组之类的就行，转化为经典问题了。
#include <bits/stdc++.h>
using namespace std;
const int N=400050;
#define ll long long
int t[N<<1];
int q,X;
inline int lowbit(int x){return x&(-x);}
inline void upd(int x,int val){while(x<=q+5){t[x]+=val;x+=lowbit(x);}}
inline int query(int x){int ret=0;while(x){ret+=t[x];x-=lowbit(x);}return ret;}
int cnt[N];
bool check(int x)
{
int sum=query(x);
if(sum==x)return true;
else return false;
}
int work()
{
int ret=0;
int L=1,R=q+2;
while(L<=R)
{
int mid=(L+R)>>1;
if(check(mid))L=mid+1,ret=mid;
else R=mid-1;
}
return ret;
}
int main()
{
cin>>q>>X;
for(int i=1;i<=q;++i)
{
int num;
scanf("%d",&num);
num%=X;
cnt[num]++;
if((ll)num+(ll)(cnt[num]-1)*1LL*(ll)X<=q)
upd(1+num+(cnt[num]-1)*X,1);
int ans=work();
printf("%d\n",ans);
}
return 0;
}
E - Obtain a Permutation
这题实际上就是一个贪心。
首先，题目中只能单点修改和对一列操作，所以实际上子问题就是把一列变回去所需要的最少步数，
而我们可以记录一下本不属于这一列应有的数字的那些一定只能单点修改，然后还有一个轮换操作，我们只需要记录一下当前元素经过多少次轮换可以到原位，然后它到了的话其他有些数可能就需要单点修改一下。对所有的轮换贪心一下即可。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n,m;
vector <int> a[N];
int cnt[N];
int ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)a[i].push_back(0);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
int num;
scanf("%d",&num);
a[j].push_back(num);
}
}
for(int j=1;j<=m;++j)
{
int tmp2=0;
memset(cnt,0,(n+3)*sizeof(int));
for(int i=1;i<=n;++i)
{
int yu=a[j][i]%m;
if(yu==0)yu=m;
if(yu!=j||a[j][i]>n*m)tmp2++;
else
{
int f=a[j][i]/m+(a[j][i]%m>0);
int shift=(i-f+n)%n;
cnt[shift]++;
}
}
int sum=0;
int tmp=INT_MAX;
for(int i=0;i<=n;++i)sum+=cnt[i];
for(int i=0;i<n;++i)
{
tmp=min(tmp,sum-cnt[i]+tmp2+i);
}
ans+=tmp;
}
printf("%d\n",ans);
return 0;
}
F - Three Paths on a Tree
实际上这三个点中，一定有两个点是这棵树的一条直径上的两个端点......
接下来就只需要再找一个点就行，那个点就是除直径外的子树上深度最大的点。
注意树退化为一条链的数据......不然会WA39.
Code by HeRaNO
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
struct link
{
int to,nxt;
};
link e[MAXN<<1];
int head[MAXN],cnt;
int n,u,v,a,b,c,dep[MAXN],pre[MAXN],ans;
bool vis[MAXN],d[MAXN];
inline void add(int u,int v)
{
e[cnt]=(link){v,head[u]};head[u]=cnt++;
e[cnt]=(link){u,head[v]};head[v]=cnt++;
}
inline void dfs1(int x,int f,int deep)
{
dep[x]=deep;if (dep[x]>dep[a]) a=x;
for (int i=head[x];~i;i=e[i].nxt)
if (e[i].to!=f) dfs1(e[i].to,x,deep+1);
return ;
}
inline void dfs2(int x,int f,int deep)
{
dep[x]=deep;if (dep[x]>dep[b]) b=x;
for (int i=head[x];~i;i=e[i].nxt)
if (e[i].to!=f)
{
dfs2(e[i].to,x,deep+1);
pre[e[i].to]=x;
}
return ;
}
inline void dfs3(int x,int f,int deep)
{
vis[x]=true;
if (deep>ans)
{
ans=deep;c=x;
}
for (int i=head[x];~i;i=e[i].nxt)
if (e[i].to!=f&&!vis[e[i].to]&&!d[e[i].to])
dfs3(e[i].to,x,deep+1);
return ;
}
int main()
{
scanf("%d",&n);memset(head,-1,sizeof head);
for (int i=1;i<n;i++) scanf("%d %d",&u,&v),add(u,v);
dfs1(1,-1,0);memset(dep,0,sizeof dep);dfs2(a,-1,0);
for (int x=b;x!=a;x=pre[x]) d[x]=true;d[a]=true;
for (int i=1;i<=n;i++) if (d[i]) dfs3(i,-1,0);
printf("%d\n",ans+dep[b]);
printf("%d %d",a,b);
if(c==0)
{
for(int i=1;i<=n;++i)
{
if(i!=a&&i!=b){printf(" %d",i);break;}
}
}
else printf(" %d\n",c);
return 0;
}
Comments NOTHING