A
签到。按照题意模拟输出就好了。
#include<bits/stdc++.h>
using namespace std;
string s="I LOVE WIT";
int main(){
int len=s.size();
for(int i=0;i<len;i++){
for(int j=0;j<i;j++) cout<<' ';
cout<<s[i]<<endl;
}
return 0;
}B
签到。12 * 2.54 * 10=304.8 n是5的倍数结果就是整数 否则保留一位小数
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
if(n%5==0) cout<<n/5*1524<<endl;
else printf("%.1f",1.0*n*304.8);
return 0;
}
C
闪光率是1%，意味着非闪光率是99%。注意下这个就好
#include<bits/stdc++.h>
using namespace std;
int main(){
double a[36]={0};
for(int i=0;i<7;i++){
scanf("%lf%%",&a[i]);
}
int n,m;cin>>n>>m;
double q=a[n];
if(m==1) q=q*0.01;
else q*=0.99;
printf("%.2f%%",q);
return 0;
}
D
位运算，我的做法是直接模拟过程了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[36]={0};
long long n;cin>>n;
int cnt=0;
for(int i=0;i<=32;i++){
if(n>>i&1) cnt=i;
}
int m=0;
for(int i=0;i<cnt;i++){
if(!(n>>i&1)) m+=1ll<<i;
}
n=0;
for(int i=0;i<cnt;i++){
if(m>>i&1){
n+= 1ll<<(31-i);
}
}
cout<<n;
return 0;
}
E
算出来到达时间，比较一下即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
scanf("%d:%d:%d",&a,&b,&c);
if(a>=21) cout<<"too late"<<endl;
else{
c+=33;
b+=c/60;
c%=60;
b+=22;
a+=b/60;
a+=1;
b%=60;
//cout<<a<<" "<<b<<" "<<c<<endl;
if(a<19) cout<<"arrive on time";
else if(a<21) cout<<"arrive late"<<endl;
else cout<<"too late"<<endl;
}
return 0;
}F
等于每个人获得的鸽子肉只能从一只上面来，不能拼凑。
题意等价把n个数字拆分m个相同数字出来，数字最大是多少，数字不能拼凑。
答案具有单调性。二分即可
#include<bits/stdc++.h>
using namespace std;
int a[1<<17];
int n,m;
bool check(int x){
int num=0;
for(int i=1;i<=n;i++){
num+=a[i]/x;
}
return num>=m;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int l=0,r=2e9,mid;
while(l+1<r){
mid=l+r>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l<<endl;
return 0;
}
G
显然总和是个等比数列，等比数列前n个项和求一下，和n比一下大小。
注意一下奇数是凑不出来的，结果炸int
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll k,n;cin>>k>>n;
if((1ll<<(k+1))-2<n || n&1) cout<<"No";
else{
cout<<"Yes"<<endl;
ll q=0;
for(ll i=0;i<63;i++){
if(n>>i&1) q=i;
}
cout<<(1ll<<q);
}
return 0;
}
I
dfs暴力搜，注意剪枝
#include<bits/stdc++.h>
using namespace std;
int n,w;
int a[25],b[25];
int ans;
void dfs(int x,int num){
if(num>=ans) return ;
if(x>n) {
ans=min(ans,num);return ;
}
for(int i=1;i<=num;i++){
if(a[x]+b[i]<=w){
b[i]+=a[x],dfs(x+1,num),b[i]-=a[x];
}
}
b[num+1]+=a[x];
dfs(x+1,num+1);
b[num+1]-=a[x];
}
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n,greater<int>());
ans=n;
dfs(1,0);
cout<<ans;
return 0;
}J
就是模拟栈的过程，不用这个栈需要能访问栈内任意一个，所以不能用stl的栈，需要自己手写模拟一下。
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r;
int id;
}a[1<<20];
int ans[1<<20];
int vis[1<<20];
int sta[1<<20],tot=1;
bool cmp(node x,node y){
return x.l<y.l;
}
char s[15];
int main(){
// ios::sync_with_stdio(0);
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
if(s[0]=='i') vis[i]=1;
}
int q;scanf("%d",&q);
for(int i=1;i<=q;i++){
int x,y;scanf("%d%d",&x,&y);
a[i]={x,y,i};
}
sort(a+1,a+1+q,cmp);
int k=0,num=1;
for(int i=1;i<=q;i++){
while(a[i].l!=k){
if(vis[++k]) sta[tot++]=num++;
else tot--;
}
ans[a[i].id]=sta[a[i].r];
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
K
数学推公式。
n行m列。
枚举k即可，n行选k个 m列选k个
然后等于是在一个k阶的矩阵里，在选择k个，并且每行每列只能有一个 所以方案数是k!
预处理阶乘即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[1<<21];
const ll mod=1e9+7;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int main(){
int n,m,k;cin>>n>>m>>k;
f[0]=1;
for(int i=1;i<=1000000;i++) f[i]=f[i-1]*i%mod;
ll ans=0;
k=min(k,min(n,m));
for(int i=1;i<=k;i++){
ans+=(f[n]*qpow(f[n-i]*f[i]%mod,mod-2))%mod*(f[m]*qpow(f[m-i]*f[i]%mod,mod-2)%mod)%mod*f[i]%mod;
ans%=mod;
}
cout<<ans;
return 0;
}
L
这是一棵有根树，根据入度可以得到根节点。
亲缘关系就是树上两点的最近距离。
是否是直系血亲，计算两个人的lca是否是其中一个即可。
对于树上两点间的距离为 dis[x]+dis[y]-2 * dis[LCA(x,y)]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int head[N], tot, depth[N], fa[N][22], lg[N];
int du[N];
struct Node
{
int t, nex;
} e[N << 1];
void add(int x, int y)
{
e[++tot].t = y;
e[tot].nex = head[x];
head[x] = tot;
}
void dfs(int now, int fath)
{
fa[now][0] = fath;
depth[now] = depth[fath] + 1;
for (int i = 1; i <= lg[depth[now]]; ++i)
fa[now][i] = fa[fa[now][i - 1]][i - 1];
for (int i = head[now]; i; i = e[i].nex)
if (e[i].t != fath)
dfs(e[i].t, now);
}
int LCA(int x, int y)
{
if (depth[x] < depth[y])
swap(x, y);
while (depth[x] > depth[y])
x = fa[x][lg[depth[x] - depth[y]] - 1];
if (x == y)
return x;
for (int k = lg[depth[x]] - 1; k >= 0; --k)
if (fa[x][k] != fa[y][k])
x = fa[x][k], y = fa[y][k];
return fa[x][0];
}
void init()
{
tot = 0;
memset(head, 0, sizeof(head));
memset(fa, 0, sizeof(fa));
memset(depth, 0, sizeof(depth));
}
int main()
{
// ios::sync_with_stdio(false);
int n, m, s;
scanf("%d%d", &n, &m);
int root;
init();
for (int i = 1; i <= n - 1; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
du[y]++;
add(y,x);
}
for(int i=1; i<=n; i++)
{
if(!du[i])
{
root=i;
break;
}
}
for (int i = 1; i <= n; ++i)
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
dfs(root, root);
for (int i = 1; i <= m; ++i)
{
int x, y, p, z, ans;
scanf("%d%d", &x, &y);
p = LCA(x, y );
ans= depth[x] + depth[y] - 2 * depth[p];
if (x==p || y==p || ans<=4)
puts("NO");
else
puts("YES");
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号