一.闲话
太菜了，又被各位神仙吊打qwq
二.题解
A.L1-1 I LOVE WIT
签到题，没啥技巧，模拟即可~
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string x="I LOVE WIT";
int len=x.size();
for(int i=0;i<len;++i){
for(int j=1;j<=i;++j){
putchar(' ');
}
cout<<x[i]<<'\n';
}
return 0;
} B.L1-2 单位换算
由题，直接输出即可，若答案为整数输直接输出，否则保留小数
有个小技巧，我们可以直接用double存答案，然后比较下double的值与double转int后的值即可判断是否为整数
代码:
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-3;
int main(){
int n;
scanf("%d",&n);
double res=1.0*n*12*25.4;
int ret=res;
if(fabs(ret-res)<=eps){
printf("%d",ret);
}else{
printf("%.1lf",res);
}
return 0;
} C.L1-3 Pokémon
又是签到题,若f=1,输出,否则输出
烦的地方主要是输入带%，小技巧就是，先把值输入进double里面，再输入一个char，就可以无视%了
代码:
#include<bits/stdc++.h>
using namespace std;
double p[7];
int main(){
char s;
for(int i=0;i<=6;++i){
cin>>p[i]>>s;
}
int tp,opt;
cin>>tp>>opt;
if(opt==1){
p[tp]*=0.01;
}else{
p[tp]*=0.99;
}
printf("%.2lf",p[tp]);putchar('%');
return 0;
} D.L1-4 颠倒阴阳
模拟即可，需要注意的是，题目要求的是从从左到右第一个为1的位置到最低位（就是最后那个2^0的位置）反转。。。题目有点不明确，多试几次就行了
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
scanf("%lld",&n);
if(n==0){
puts("0");
return 0;
}
int l=0,r=0;
for(int i=0;i<=31;++i){
if((n>>i)&1){
l=min(l,i),r=max(r,i);
}
}
for(int i=l;i<=r;++i){
n^=(1<<i);
}
int ans=0;
for(int i=31;~i;--i){
if((n>>i)&1){
ans+=(1LL<<(31-i));
}
}
printf("%lld",ans);
return 0;
} E.L1-5 演唱会
直接算可能有点麻烦(真的只有一点)，我们可以考虑把所有单位化为相同的，这样就好比较了，为了避免精度问题，我直接把所有时间换算成秒，这样就可以直接比较大小了
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int h,m,s;
char ss;
cin>>h>>ss>>m>>ss>>s;
int tot=h*3600+m*60+s;
tot+=3600+22*60+33;
int al=19*3600,ed=21*3600;
if(tot<al){
puts("arrive on time");
}else if(tot<ed){
puts("arrive late");
}else{
puts("too late");
}
return 0;
} F.L1-6 分鸽子
一道标准的二分题（貌似就是一种版本的小木棍那题？）
读题可以发现，答案明显满足二分性，所以我们二分答案，然后算出最多可以分出多少分鸽子肉（看出出题人对鸽子的愤怒了/x），把这个值和m比较一下就行了
代码:
#include<bits/stdc++.h>
using namespace std;
int w[100001];int n,m;
inline bool check(int x){
int res=0;
for(int i=1;i<=n;++i){
res+=(w[i]/x);
}
return res>=m;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
}
int l=1,r=1e9,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid,l=mid+1;
}else{
r=mid-1;
}
}
printf("%d",ans);
return 0;
} G.L1-7 拼接梯子
一道结论题，类比二进制拆分即可，（注意没有2^0）
我们从大到小枚举能分则分，最后看剩余的值是否为0即可
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long k,n;
cin>>k>>n;
long long ans1=1;
for(int i=k;i;--i){
if((n>>i)&1){
n-=(1LL<<i);
ans1=max(ans1,(1LL<<i));
}
}
if(!n){
puts("Yes");
printf("%lld",ans1);
}else{
puts("No");
}
return 0;
} H. L1-8 幻想乡炼金学
发现是个码农模拟题,emmmm反正也没啥知识点，打的又麻烦就不填坑辣！（qwq）
I. L2-1 特殊的沉重球
由于是15点50多才开始打比赛，所以做到这题时只有10多分钟了qwq，草草打了个dfs，居然出锅了！（我:???）
于是，考场中就没做出来，后面debug发现是个sb错误（新建一组时没把当前的值加进去），然后改了下70points,怎么办呢？
卡时优化天下第一！
然后。。。就A了，2333
（dfs怎么打应该不用说吧？）
一个小技巧，因为我们装精灵的顺序对背包剩余空间没有影响，所以我们可以规定每个背包优先装编号小的，这样可以加速不少时间（简单来说就是枚举组合而不是排列）
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=21,T=10000000;//卡时常数
int c[N];int n,w,ans;
int tp[N],po=T;
inline void dfs(int now,int res){
if(res>=ans){
--po;
if(!po){
printf("%d",ans);
exit(0);
}
return;
}
if(now==n+1){
ans=res;
return;
}
for(int i=1;i<=res;++i){
if(tp[i]+c[now]<=w){
tp[i]+=c[now];
dfs(now+1,res);
tp[i]-=c[now];
}
}
tp[res+1]=c[now];
dfs(now+1,res+1);
}
int main(){
ans=2e9;
scanf("%d%d",&n,&w);
for(int i=1;i<=n;++i){
scanf("%d",&c[i]);
}
dfs(1,0);
printf("%d",ans);
return 0;
} J.L2-2 又见火车入栈
直接做的话可能不太好做，但是，我们可以将询问离线下来做，这样，我们把询问按x排序后，就可以直接动态模拟入栈出栈的过程同时更新答案了。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
struct node{
int x,y,w;
}t[N];
int ans[N];
int sta[N],top;
bool opt[N];
inline bool kkk(node x,node y){
return x.x<y.x;
}
int main(){
int n;
scanf("%d",&n);
char ss[4];
for(int i=1;i<=n;++i){
scanf("%s",ss);
opt[i]=(ss[0]=='i');
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d%d",&t[i].x,&t[i].y);
t[i].w=i;
}
sort(t+1,t+q+1,kkk);
int now=1,cnt=0;
for(int i=1;i<=n;++i){
if(opt[i]){
sta[++top]=++cnt;
}else{
--top;
}
while(now<=q&&t[now].x==i){
ans[t[now].w]=sta[t[now].y];
++now;
}
if(now==q+1){
break;
}
}
for(int i=1;i<=q;++i){
printf("%d\n",ans[i]);
}
return 0;
} K. L2-3 新旷野地带
简单数论题，相当于棋盘放车，假设我们在棋盘中放i个"车"，那么方案数如下：
我们先从n行中选i行放车，再从j列中选i列放车，这样每行每列一定最多只有一个车，然后把这个i个列分别分配个i个行，进行组合，分配方式有i!种，所以方案数就是
直接预处理组合数和阶乘即可O(1)计算贡献，O(n)枚举i即可
代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=1e6+1;
int C1[N],C2[N],f[N],g[N];
int main(){
f[0]=f[1]=g[0]=g[1]=1;
for(int i=2;i<N;++i){
f[i]=(1LL*f[i-1]*i)%mod;
g[i]=(1LL*g[mod%i]*(mod-mod/i))%mod;
}
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
C1[1]=n,C2[1]=m;
for(int i=2;i<=k;++i){
C1[i]=(1LL*C1[i-1]*(n-i+1))%mod;
C1[i]=(1LL*C1[i]*g[i])%mod;
C2[i]=(1LL*C2[i-1]*(m-i+1))%mod;
C2[i]=(1LL*C2[i]*g[i])%mod;
}
k=min(k,min(n,m));
int ans=0;
for(int i=1;i<=k;++i){//枚举放几个
//选i行放,选i列放,然后每行放的顺序乱序
//ans+=C i,n*C i.m*i!
ans+=(1LL*((1LL*C1[i]*C2[i])%mod)*f[i])%mod;
ans%=mod;
}
printf("%d",ans);
return 0;
} L.2-4 缘之空
简单的lca模板，但需要注意的是，题目并没有说根节点为1（这也是坑点所在），但是题目明确了每个点的父亲，所以，我们只要找到没有被指定父亲的那个节点，那个节点就是根，其他的就是个lca模板了。。。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
struct node{
int v,nex;
}t[N<<1];
int fa[N][18];
int dep[N];
int len,las[N];
bool is_not_fa[N];
inline void add(int u,int v){
t[++len]=(node){v,las[u]},las[u]=len;
}
inline void dfs(int now){
for(int i=1;i<=17;++i){
fa[now][i]=fa[fa[now][i-1]][i-1];
}
for(int i=las[now];i;i=t[i].nex){
int v=t[i].v;
dep[v]=dep[now]+1;fa[v][0]=now;
dfs(v);
}
}
inline int lca(int x,int y){
if(dep[x]>dep[y]){
x^=y^=x^=y;
}
int cha=dep[y]-dep[x];
for(int i=17;~i;--i){
if(cha>=(1<<i)){
cha-=(1<<i);
y=fa[y][i];
}
}
if(x==y){
return x;
}
for(int i=17;~i;--i){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i],y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);is_not_fa[v]=1;
}
int rt;
for(int i=1;i<=n;++i){
if(!is_not_fa[i]){
rt=i;
}
}
dep[rt]=1;
dfs(rt);
while(q--){
int u,v;
scanf("%d%d",&u,&v);
int x=lca(u,v);
int dis=dep[u]+dep[v]-2*dep[x];
if(dis<=4||x==u||x==v){
puts("NO");
}else{
puts("YES");
}
printf("%d\n",dis);
}
return 0;
} 
京公网安备 11010502036488号