A.Exchange
模拟
#include <iostream> #include<cstdio> typedef long long ll; using namespace std; int main() { ll a,b,k;scanf("%lld%lld%lld",&a,&b,&k); ll cnt=0; while(k--){ cnt++; if(cnt%2){ if(a%2) a--; b+=a/2; a=a/2; } else{ if(b%2) b--; a+=b/2; b=b/2; } } printf("%lld %lld ",a,b); return 0; }
B.Align
公式
#include <iostream> #include<cstdio> #include<algorithm> typedef long long ll; using namespace std; ll a[100005]; int main() { ll n;scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); if(n==1){ printf("0 "); return 0; } sort(a+1,a+1+n); ll ans=0; if(n%2==0){ ll num=(n-2)/2; ll tmp1=0; for(ll i=n;i>=n-num+1;i--) tmp1+=a[i]; ll tmp2=0; for(ll i=1;i<=num;i++) tmp2+=a[i]; ll tmp3=a[n-num]-a[num+1]; ans=2*(tmp1-tmp2)+tmp3; } else{ ll num=(n-1)/2; ll tmp1=0; for(ll i=n;i>=n-num+1;i--) tmp1+=a[i]; ll tmp2=0; for(ll i=1;i<=num-1;i++) tmp2+=a[i]; ll tmp3=a[num]+a[num+1]; ll ans1=2*(tmp1-tmp2)-tmp3; tmp1=0,tmp2=0,tmp3=0; for(ll i=n;i>=n-num+2;i--) tmp1+=a[i]; for(ll i=1;i<=num;i++) tmp2+=a[i]; tmp3=a[num+1]+a[num+2]; ll ans2=2*(tmp1-tmp2)+tmp3; ans=max(ans1,ans2); } printf("%lld ",ans); return 0; }
C.Crossing
构造
#include <iostream> #include<cstdio> using namespace std; bool ok[100005]; void init(){ ok[1]=1,ok[2]=0,ok[3]=1; int now=3; for(int t=3;now+t<=100000;t++){ ok[now+t]=1; now=now+t; } } int main() { init(); int n;scanf("%d",&n); if(ok[n]) puts("Yes"); else puts("No"); return 0; }
B.滑动窗口
单调队列
#include <iostream> #include<cstdio> using namespace std; int a[1000005],ans_max[1000005],ans_min[1000005],q[1000005]; int main() { int n,k;scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int head=1,tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&a[q[tail]]<=a[i]) tail--; q[++tail]=i; while(head<=tail&&i-q[head]+1>k) head++; ans_max[i]=a[q[head]]; } head=1,tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&a[q[tail]]>=a[i]) tail--; q[++tail]=i; while(head<=tail&&i-q[head]+1>k) head++; ans_min[i]=a[q[head]]; } for(int i=k;i<=n;i++){ if(i!=k) printf(" "); printf("%d",ans_min[i]); } puts(""); for(int i=k;i<=n;i++){ if(i!=k) printf(" "); printf("%d",ans_max[i]); } puts(""); return 0; }
C.发财兔fbi树
dfs
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char s[2005]; int dfs(int l,int r){ if(l==r){ if(s[l]=='0') {printf("B");return 0;} else {printf("I");return 1;} } int mid=(l+r)>>1; int tl=dfs(l,mid); int tr=dfs(mid+1,r); if(tl!=tr) {printf("F");return 2;} else{ if(tl==0) {printf("B"); return 0;} else if(tl==1) {printf("I"); return 1;} else {printf("F"); return 2;} } } int main() { int n;scanf("%d",&n); scanf("%s",s+1); n=strlen(s+1); int t=dfs(1,n); puts(""); return 0; }
D.医院设置
暴力+LCA
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f3f3f3f3f typedef long long ll; using namespace std; ll num[105],pre[105],depth[105],fa[105][105]; int main() { ll n;scanf("%lld",&n); for(ll i=1;i<=n;i++){ ll l,r;scanf("%lld%lld%lld",&num[i],&l,&r); pre[l]=i,pre[r]=i; } depth[1]=0; for(ll i=2;i<=n;i++){ ll x=i; while(x!=1){ depth[i]++; x=pre[x]; } } for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ ll x=i,y=j; while(depth[x]>depth[y]) x=pre[x]; while(depth[y]>depth[x]) y=pre[y]; while(x!=y){ x=pre[x]; y=pre[y]; } fa[i][j]=x; } } ll ans=inf; for(ll i=1;i<=n;i++){ ll tot=0; for(ll j=1;j<=n;j++){ ll f=fa[i][j]; ll l=depth[i]+depth[j]-2*depth[f]; tot+=l*num[j]; } ans=min(ans,tot); } printf("%lld ",ans); return 0; }
E.加分二叉树
dp
#include <iostream> #include<cstdio> typedef long long ll; using namespace std; ll a[35],dp[35][35],ans[35][35]; ll DP(ll l,ll r){ if(l>r) return 1; else if(l==r) return dp[l][r]=a[l]; else{ if(dp[l][r]) return dp[l][r]; for(ll i=l;i<=r;i++){ ll tmp=DP(l,i-1)*DP(i+1,r)+a[i]; if(tmp>dp[l][r]){ dp[l][r]=tmp; ans[l][r]=i; } } return dp[l][r]; } } void print(ll l,ll r){ if(l>r) return; else if(l==r) printf(" %lld",l); else{ printf(" %lld",ans[l][r]); print(l,ans[l][r]-1); print(ans[l][r]+1,r); } } int main() { ll n;scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); printf("%lld ",DP(1,n)); printf("%lld",ans[1][n]); print(1,ans[1][n]-1); print(ans[1][n]+1,n); return 0; }