前置扯淡
真是神了，我半个小时切前三题（虽然还是很菜）
然后就开始看\(D\)，不会；
接着看\(E\)，\(dp\)看了半天，交了三次还不行
然后看\(F\)：一眼\(LCA\)瞎搞，然后\(15min \space A\)掉
幸亏加时了\(10min\)，否则\(F\)题\(AC\)不掉啥没有了
送我自闭，如果先全看一遍，发现\(D\)题和\(E\)题都不可做，直接刚\(F\)，新年就上蓝了（然而还是菜）
题目&&解答
A.Collecting Coins
思路
这水题吧，就是需要特判一下是不是有一个人的个数多于平均数了
CODE：
#include<bits/stdc++.h>
using namespace std;
inline void work()
{
int a,b,c,n;
cin>>a>>b>>c>>n;
int sum=a+b+c+n;
if(sum%3!=0) return puts("NO"),void();
sum/=3; if(c>sum||a>sum||b>sum) return puts("NO"),void();
return puts("YES"),void();
}
int main()
{
int T; cin>>T; while(T--) work();
return 0;
}
B. Collecting Packages
思路
一眼贪心，\(sort+check\)一波
有一些细节（可能是我代码能力太差）
CODE:
（直接放代码了）
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=1010;
struct node{
int x,y;
}p[N];
int n;
inline bool cmp(node a,node b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
inline void work()
{
n=read(); for(int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
if(p[i].x<p[j].x&&p[i].y>p[j].y) return puts("NO"),void();
}
}puts("YES");
int nx=0,ny=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=p[i].x-nx;++j) putchar('R');
for(int j=1;j<=p[i].y-ny;++j) putchar('U');
nx=p[i].x,ny=p[i].y;
}
return puts(""),void();
}
signed main()
{
int T=read(); while(T--) work();
return 0;
}
}
signed main(){yspm::main(); return 0;}
C. Product of Three Numbers
思路
一眼可能会比较复杂，但是当你发现这个题放\(O(\sqrt n)\)算法就很可做了吧，
就是分解一下\(n\)，然后就是合并你分解出来的结果（有些奇怪的情况，代码可懂）
CODE：
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
inline void work()
{
int n=read(),ans[10010],tot=0;
for(int i=2;i*i<=n;++i)
{
if(n%i==0) ans[++tot]=i,n/=i;
}
if(n!=1)
{
bool flag=0;
for(int i=1;i<=tot;++i) if(n==ans[i]){ans[i]*=n; flag=1;} if(!flag) ans[++tot]=n;
}
if(tot<=2) return puts("NO"),void();
if(tot>3) for(int i=4;i<=tot;++i) ans[3]*=ans[i];
puts("YES");
cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;;
return ;
}
signed main()
{
int T=read(); while(T--) work();
return 0;
}
}
signed main(){yspm::main(); return 0;}
D.MEX maximizing
woc 比赛的时候看错题了！！！没看出来可以操作任意次可还行！！！
这要是翻译出来正确题意，再想不出来用同余就退赛吧……（反正有qjjh）
思路
记录关于\(x\)同余下各个数字的结果，然后桶一波，还是模拟就可以了……
外语水平严重不足（其实就是依赖百度翻译），导致这个题只能补了2444
CODE:
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=4e5+10;
int n,x,y,p,q,cnt[N],app[N];
signed main()
{
n=read(); x=read(); app[0]=x;
for(int i=1;i<=n;++i)
{
y=read()%x;
app[cnt[y]]--; cnt[y]++; app[cnt[y]]++;
if(!app[p]) ++p,q=0;
while(cnt[q]>p) ++q;
printf("%lld\n",p*x+q);
}
return 0;
}
}
signed main(){return yspm::main();}
E.Obtain a Permutation
思路
首先有每一列都是无关的，单独处理就行（这要是行列相关就很复杂了）
然后就变成了一个\(dp\)做\(m\)遍？
同是\(O(n * m)\)的复杂度，我死活比赛过不去
（现在知道了，\(memset\)的复杂度是\(O(n)\)的，循环套\(memset\)卡到\(O(n^2)\)现场）
思路其实跟正解一样，但是不知道为啥不行2444
写法就是我们看每一个列上的数是不是符合“不改”的要求，这个取模就可以办到，如果不行，肯定要修改（无论在什么位置）
然后看每个数转几次就可以到它应该在的位置（这个求两个位置的移动次数很简单，画下图就可以）
然后开桶，看哪个最多就选择转哪个，最后统计答案
CODE：
#include<bits/stdc++.h>
#define reg register
using namespace std;
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=2e5+10;
int n,m,app[N],ans;
vector<int> vec[N];
signed main()
{
n=read(); m=read();
for(reg int i=1;i<=n;++i)
{
vec[i].push_back(0);
for(reg int j=1;j<=m;++j) vec[i].push_back(read());
}
for(reg int j=1;j<=m;++j)
{
int tmp=2e9+10; for(int i=0;i<n;++i) app[i]=0;
for(reg int i=1;i<=n;++i)
{
if(vec[i][j]<j||vec[i][j]>n*m||(vec[i][j]-j)%m!=0) continue;
int k=(vec[i][j]-j)/m+1; app[(i-k+n)%n]++;
}
for(reg int i=0;i<n;++i) tmp=min(tmp,i+n-app[i]); ans+=tmp;
} printf("%d\n",ans);
return 0;
}
}
signed main(){return yspm::main();}
F.Three Paths on a Tree
思路
题意就是树上任意三个点，求三个点的各自路径上的边数总和最大（这里点还是边无所谓，反正\(lca\)求\(dis\)的时候卡一下就好）
首先，三个点其中必有两个点是直径
这个结论显然吧（应该贪心地想一下就完事）
之后我们发现数据放了\(O(nlog \space n)\)
所以第三个点枚举算就好
其实这个地方还有一个重要的定理：树的叶节点只有连向其父节点的一条边（显然是废话）
我们两遍\(dfs\)算直径的时候就可以把直径的一个端点“拎”起来，当做根节点
所以我们每次算第三点的路径的时候，可以直接算\(lca(p_3,p _ {max})\) 和\(p _ 3\)的深度差
\(lca\)倍增求吧，还方便一点点
CODE:
可读性不太强的样子
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=2e5+10;
struct node{
int nxt,to;
}e[N<<1];
int head[N],cnt,n;
inline void add(int u,int v)
{
e[++cnt].nxt=head[u]; e[cnt].to=v;
return head[u]=cnt,void();
}
int fa[N][40],dep[N];
inline void dfs1(int x,int fat)
{
fa[x][0]=fat; dep[x]=dep[fa[x][0]]+1;
for(int i=head[x];i;i=e[i].nxt)
{
int t=e[i].to; if(t==fat) continue;
dfs1(t,x);
}
return ;
}int lg[500010];
inline void dfs2(int x,int fat)
{
fa[x][0]=fat; dep[x]=dep[fa[x][0]]+1;
for(int i=1;(1<<i)<=dep[x];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].nxt) if(fa[x][0]!=e[i].to) dfs2(e[i].to,x);
return ;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(int k=lg[dep[x]]-1; k>=0;--k) if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
signed main()
{
n=read(); for(int i=1,v,u;i<n;++i) u=read(),v=read(),add(u,v),add(v,u);
int rt=1; dfs1(1,0); for(int i=1;i<=n;++i) rt=dep[i]>dep[rt]?i:rt;
dfs1(rt,0); int ans=0,ed=1; for(int i=1;i<=n;++i) ed=dep[i]>dep[ed]?i:ed; ans+=dep[ed]-1;
for(int i=1;i<500010;++i) lg[i]=lg[i-1]+((1<<lg[i-1])==i);
dfs2(rt,0);
int maxx=-1,num;
for(int i=1;i<=n;++i)
{
if(i==ed||i==rt) continue;
int anc=lca(ed,i);
if(maxx<dep[i]-dep[anc]) maxx=dep[i]-dep[anc],num=i;
}
if(dep[num]==dep[rt]+1) cout<<ans<<endl;
else cout<<ans+maxx<<endl;
cout<<num<<" "<<rt<<" "<<ed<<endl;
return 0;
}
}
signed main(){return yspm::main();}
赛后总结
感觉好像这个\(F\)题一出，我就有\(AK\)的实力了
但是还是不可以在打外文题的时候过度依赖翻译机
还有要记得在循环内清空数组时能用\(for\)就换掉\(memset\)
这俩\(sb\)事坑掉了我的\(AK\)
加油！ 冲向开学前\(Rating 1650\)的目标！