这篇文章上次修改于 285 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
2024.1.25模拟赛总结
T1
一天有 $h$ 小时，$m$ 分钟。求出一天分钟数大于小时数的时间占比。
rz题，一眼题。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
inline int read();
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen("relax.in","r",stdin);
freopen("relax.out","w",stdout);
#endif
int h=read(),m;
m=read();
int xiang=std::min(m,h);
int lst=(m-xiang+1);
int a=((m+lst)*xiang);
int b=2*h*m;
int gg=std::__gcd(a,b);
a/=gg;
b/=gg;
printf("%lld/%lld",a,b);
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
T2
从 $[1,n]$ 选任意多个数，重新排列，使得任意相邻数 $gcd$ 大于 $2$ 。最大化选择数的数量，并且构造方案并输出。
构造题，我们考虑把所有最小质因子数相同的数放一起，开头结尾分别放一个能被 $2$ 整除的数和能被 $3$ 整除的数，交替放即可，一头一尾要特判。最后放置所有偶数，因为最后放的是能被 $3$ 整除的，可能与 $2$ 互质，放个 $18$ 即可，对于 $n\leq 18$ ,我们乱搞打表即可。
#include <iostream>
#include <cstdio>
#include <queue>
inline int read();
bool prime[3000005];
int lst[3000005];
int cho[3000005];
std::deque<int>deq;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
#endif
int n=read();
int cnt=0;
if(n<=18){
if(n==4) std::cout<<"2\n2 4";
if(n==5) std::cout<<"2\n2 4";
if(n==6) std::cout<<"4\n2 4 6 3";
if(n==7) std::cout<<"4\n2 4 6 3";
if(n==8) std::cout<<"5\n8 2 4 6 3";
if(n==9) std::cout<<"6\n2 4 8 6 3 9";
if(n==10) std::cout<<"8\n5 10 2 4 8 6 3 9";
if(n==11) std::cout<<"8\n5 10 8 2 4 6 3 9";
if(n==12) std::cout<<"9\n5 10 12 8 2 4 6 3 9";
if(n==13){
std::cout<<"9\n5 10 6 3 9 12 2 4 8";
}
if(n==14){
std::cout<<"11\n7 14 6 3 9 12 2 4 8 10 5";
}
if(n==15){
std::cout<<"12\n7 14 10 5 15 6 3 9 12 2 4 8";
}
if(n==16){
std::cout<<"13\n7 14 10 5 15 6 3 9 12 2 4 8 16";
}
if(n==17){
std::cout<<"13\n7 14 10 5 15 6 3 9 12 2 4 8 16";
}
if(n==18){
std::cout<<"14\n7 14 10 5 15 6 3 9 18 12 2 4 8 16\n";
}
return 0;
}
for(int i=2;i<=n;i++){
if(!prime[i]){
lst[++cnt]=i;
cho[i*3]=1;
}
for(int j=1;j<=cnt;j++){
if((1ll*i*lst[j])>n){
break;
}
prime[i*lst[j]]=1;
if(i%lst[j]==0){
continue;
}
}
}
int pian1=0;
int pian2=0;
int asns=0;
int cntt=0;
int oo=0;
for(int i=3;i<=n;i+=2){
int ans=0;
for(int j=i;j<=n;j+=2*i){
if(cho[j]){
continue;
}
cho[j]=i;
ans++;
}
if(ans==0){
continue;
}
if((i*2)<=n&&(i*3)>n){
cntt++;
if(cntt==1){
pian1=ans;
asns++;
deq.push_front(i*2);
cho[i*2]=1;
for(int j=i;j<=n;j+=2*i){
if(cho[j]==i){
deq.push_front(j);
asns++;
}
}
}else if(cntt==2){
pian2=ans;
cho[i*2]=1;
asns++;
if(n>=18&&!cho[18]){
cho[18]=1;
asns++;
deq.push_back(18);
}
for(int i=2;i<=n;i+=2){
if(cho[i]==0){
deq.push_back(i);
asns++;
cho[i]=1;
}
}
deq.push_back(i*2);
for(int j=i;j<=n;j+=2*i){
if(cho[j]==i){
deq.push_back(j);
}
}
}
}else if((i*2)<=n&&(i*3)<=n){
asns+=ans;
if(oo){
deq.push_back(i*2);
cho[i*2]=1;
}else{
if(i==3){
deq.push_back(i*4);
cho[i*4]=1;
}
deq.push_back(i*3);
cho[i*3]=1;
}
asns+=2;
for(int j=i;j<=n;j+=2*i){
if(cho[j]==i){
deq.push_back(j);
}
}
if(!oo){
deq.push_back(i*2);
cho[i*2]=1;
}else{
if(i==3){
deq.push_back(i*4);
cho[i*4]=1;
}
deq.push_back(i*3);
cho[i*3]=1;
}
oo^=1;
}
}
asns+=pian1;
asns+=pian2;
if(n>=18&&!cho[18]){
cho[18]=1;
asns++;
deq.push_back(18);
}
for(int i=2;i<=n;i+=2){
if(cho[i]==0){
deq.push_back(i);
asns++;
cho[i]=1;
}
}
printf("%d\n",int(deq.size()));
for(int i=0;i<deq.size();i++){
printf("%d ",deq[i]);
}
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
T3
原！大模拟！
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
#define mod 1000000007
#define inv2 500000004
inline int read();
int pow(int x,int y){
if(y==0){
return 1;
}
if(y%2==0){
int temp(pow(x,y/2));
return (temp*temp)%mod;
}
return (pow(x,y-1)*x)%mod;
}
class node{
public:
int l,r;
int id;
node(int x,int y,int z){
l=x;
r=y;
id=z;
return ;
}
};
bool operator< (node x,node y){
return x.l>y.l;
}
class tim{
public:
std::vector<node>bef;
int l=2000000000;
int gnow;
}aa[300005];
int kk[300005];
int add[300005];
int plu[300005];
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
#endif
int Q=read();
int g=0;
int now=1;
int curadd=0;
int pp=1;
int lstgggg=0;
kk[g]=0x3f3f3f3f;
plu[g]=1;
while(Q--){
int op=read();
switch(op){
case 1:{
int k=read();
g++;
kk[g]=k;
if(k==0){
pp*=2;
curadd*=2;
curadd%=mod;
pp%=mod;
aa[now].gnow=g;
now++;
}else{
lstgggg=g;
curadd+=k;
curadd%=mod;
aa[now].bef.push_back(node(aa[now].l-k,aa[now].l-1,g));
aa[now].l-=k;
}
add[g]=mod-curadd;
plu[g]=pow(pp,mod-2);
break;
}
case 2:{
int g=read();
int x=read();
if(kk[g]==0){
x=2*x-1;
}else{
x--;
}
x%=mod;
x*=pp;
x%=mod;
x*=plu[g];
x%=mod;
x+=curadd;
x%=mod;
x+=((add[g]*pp)%mod*plu[g])%mod;
x%=mod;
printf("%lld\n",x);
break;
}
case 3:{
int x=read();
if(x==0){
printf("%lld\n",lstgggg);
break;
}
int nw=now;
bool yes=0;
auto idd=std::lower_bound(aa[nw].bef.begin(),aa[nw].bef.end(),node(aa[nw].l+x,0,0));
if(aa[nw].bef.size()>0&&idd!=aa[nw].bef.end()&&(*idd).l-aa[nw].l<=x&&x<=(*idd).r-aa[nw].l&&(*idd).id!=0){
printf("%lld\n",(*idd).id);
yes=1;
}
if(aa[nw].bef.size()>0)
x-=2000000000-aa[nw].bef[aa[nw].bef.size()-1].l;
while(nw&&yes==0){
nw--;
if(x%2==1){
printf("%lld\n",aa[nw].gnow);
yes=1;
break;
}else{
x/=2;
auto idd=std::lower_bound(aa[nw].bef.begin(),aa[nw].bef.end(),node(aa[nw].l+x,0,0));
if(aa[nw].bef.size()>0&&idd!=aa[nw].bef.end()&&(*idd).l-aa[nw].l<=x&&x<=(*idd).r-aa[nw].l&&(*idd).id!=0){
printf("%lld\n",(*idd).id);
yes=1;
}
if(aa[nw].bef.size()>0)
x-=2000000000-aa[nw].bef[aa[nw].bef.size()-1].l;
}
}
if(!yes){
printf("0\n");
}
break;
}
}
}
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/T4
还是原！
给定两颗树，节点数相同，对所有的 $i$ 求 $\min \limits _{i\neq j}\{ dis1_{i,j}+dis2_{i,j}\}$
点分树后，枚举所有两颗树祖先的组合，然后你发现剩下的一个点可以从枚举的LCA的子树里选，淀粉质时预处理即可。
时间复杂度 $O(n\log^2n)$
#include <iostream>
#include <cstdio>
#define int long long
inline int read();
int fir[10000005];
int nxt[10000005];
int v[10000005];
int w[10000005];
int now;
int afa[10000005];
bool vis[10000005];
void add(int x,int y,int z){
v[++now]=y;
nxt[now]=fir[x];
fir[x]=now;
w[now]=z;
return ;
}
int siz[10000005];
int maxx[10000005];
int nx;
int sum;
void calcsiz(int now,int fa){
siz[now]=1;
maxx[now]=0;
for(int i=fir[now];i!=-1;i=nxt[i]){
if(v[i]==fa||vis[v[i]]){
continue;
}
calcsiz(v[i],now);
maxx[now]=std::max(maxx[now],siz[v[i]]);
siz[now]+=siz[v[i]];
}
maxx[now]=std::max(maxx[now],sum-maxx[now]);
if(maxx[now]<=maxx[nx]||nx==0){
nx=now;
}
return ;
}
int facnt[1000005];
int dis[1000005][30];
int mn[1000005];
int ans[1000005];
void addfa(int now,int fa,int dep){
dis[now][++facnt[now]]=dep;
for(int i=fir[now];i!=-1;i=nxt[i]){
if(v[i]==fa||vis[v[i]]){
continue;
}
addfa(v[i],now,dep+w[i]);
}
return ;
}
int fa[1000005];
int dep=0;
void dfs1(int now,int fa){
vis[now]=1;
::fa[now]=fa;
for(int i=fir[now];i!=-1;i=nxt[i]){
if(v[i]==fa||vis[v[i]]){
continue;
}
addfa(v[i],now,w[i]);
}
for(int i=fir[now];i!=-1;i=nxt[i]){
if(fa==v[i]||vis[v[i]]){
continue;
}
nx=0;
calcsiz(v[i],now);
sum=siz[v[i]];
nx=0;
calcsiz(v[i],now);
calcsiz(nx,nx);
afa[nx]=now;
dfs1(nx,now);
}
return ;
}
class node{
public:
int p,dis;
node(int x=0,int y=0){
p=x;
dis=y;
return ;
}
}vv[1000006];
int tp;
void aans(){
if(tp==1){
return ;
}
for(int i=1;i<=tp;i++){
int &tt=vv[i].p;
int &tt2=vv[i].dis;
ans[tt]=std::min(ans[tt],tt2+mn[tt]);
for(int j=facnt[tt],now=fa[tt];j>0;j--,now=fa[now]){
ans[tt]=std::min(ans[tt],tt2+dis[tt][j]+mn[now]);
}
mn[tt]=std::min(mn[tt],tt2);
for(int j=facnt[tt],now=fa[tt];j>0;j--,now=fa[now]){
mn[now]=std::min(mn[now],tt2+dis[tt][j]);
}
}
for(int i=1;i<=tp;i++){
int tt=vv[i].p;
mn[tt]=0x3f3f3f3f3f3f3f3f;
for(int j=facnt[tt],now=fa[tt];j>0;j--,now=fa[now]){
mn[now]=0x3f3f3f3f3f3f3f3f;
}
}
for(int i=tp;i>=1;i--){
int &tt=vv[i].p;
int &tt2=vv[i].dis;
ans[tt]=std::min(ans[tt],tt2+mn[tt]);
for(int j=facnt[tt],now=fa[tt];j>0;j--,now=fa[now]){
ans[tt]=std::min(ans[tt],tt2+dis[tt][j]+mn[now]);
}
mn[tt]=std::min(mn[tt],tt2);
for(int j=facnt[tt],now=fa[tt];j>0;j--,now=fa[now]){
mn[now]=std::min(mn[now],tt2+dis[tt][j]);
}
}
for(int i=tp;i>=1;i--){
int tt=vv[i].p;
mn[tt]=0x3f3f3f3f3f3f3f3f;
for(int j=facnt[tt],now=fa[tt];j>0;j--,now=fa[now]){
mn[now]=0x3f3f3f3f3f3f3f3f;
}
}
tp=0;
return ;
}
void addfa2(int now,int fa,int dep){
vv[++tp]=node(now,dep);
for(int i=fir[now];i!=-1;i=nxt[i]){
if(v[i]==fa||vis[v[i]]){
continue;
}
addfa2(v[i],now,dep+w[i]);
}
return ;
}
void dfs2(int now,int fa){
vis[now]=1;
tp=0;
for(int i=fir[now];i!=-1;i=nxt[i]){
if(v[i]==fa||vis[v[i]]){
continue;
}
addfa2(v[i],now,w[i]);
}
vv[++tp]=node(now,0);
aans();
for(int i=fir[now];i!=-1;i=nxt[i]){
if(v[i]==fa||vis[v[i]]){
continue;
}
nx=0;
calcsiz(v[i],now);
nx=0;
sum=siz[v[i]];
calcsiz(v[i],now);
calcsiz(nx,nx);
dfs2(nx,now);
}
dep--;
return ;
}
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen("a23.in","r",stdin);
freopen(".out","w",stdout);
#endif
int n=read();
for(int i=1;i<=n;i++){
fir[i]=-1;
}
maxx[0]=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<n;i++){
int x=read();
int y=read();
int z=read();
add(x,y,z);
add(y,x,z);
}
nx=0;
sum=n;
calcsiz(1,1);
calcsiz(nx,-1);
dfs1(nx,nx);
now=0;
for(int i=1;i<=n;i++){
fir[i]=-1;
vis[i]=0;
}
for(int i=1;i<=n;i++){
mn[i]=ans[i]=0x3f3f3f3f3f3f3f3f;
}
for(int i=1;i<n;i++){
int x=read();
int y=read();
int z=read();
add(x,y,z);
add(y,x,z);
}
nx=0;
sum=n;
calcsiz(1,1);
calcsiz(nx,-1);
dfs2(nx,nx);
for(int i=1;i<=n;i++){
printf("%lld\n",ans[i]);
}
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/