A. Dalton the Teacher
询问把一个排列变成 pi=i 的最小操作次数。
直接记录 pi=i 的个数即可,然后除二向上取整。
B. Longest Divisors Interval
询问一个数最多能被多少个连续的数字整除
如果一个数能被 x 个连续的数字整除,那么根据鸽巢原理,一定可以被 1,2,3,4,...,x 整除。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<bits/stdc++.h> #define int long long
using namespace std;
const int maxn=100100;
int T,n;
signed main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; int ans=0,tans=0; for(int i=1;i<=min(n,1000ll);i++) { if(n%i==0) { tans++; ans=max(ans,tans); } else tans=0; } cout<<ans<<'\n'; } return 0; }
|
C. Dual
给你一个序列,每次可以把 ai 操作为 ai=ai+aj,你需要把他弄成不下降序列,最多 31 步 ,输出方案。
假设我们构造出绝对值最大的负数需要 x1 步 ,然后把所有正数变成负数需要 x2 布,同理对正数定义 y1,y2 那么一定有不等式
x1+x2+y1+y2≤25 因为 x1+y1≤5,x2+y2≤20
换句话说 x1+x2,y1+y2 有一个必定小于等于 12
然后如果去全为非负或者非正,我们最多需要进行 n−1=19 次 ,总共操作次数 ≤31 次
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
| #include<bits/stdc++.h>
using namespace std;
const int maxn=55;
int T,n,a[maxn],cnt,b[maxn]; int mmx,mmn;
struct que{ int x,y; }q[maxn];
void sol1() { while(abs(b[mmx])<abs(b[mmn])) { q[++cnt].x=mmx; q[cnt].y=mmx; b[mmx]*=2; } for(int i=1;i<=n;i++) { if(b[i]<0) { q[++cnt].x=i; q[cnt].y=mmx; } } for(int i=1;i<n;i++) { q[++cnt].x=i+1; q[cnt].y=i; } cout<<cnt<<'\n'; for(int i=1;i<=cnt;i++) { cout<<q[i].x<<" "<<q[i].y<<'\n'; } }
void sol2() { while(abs(b[mmn])<abs(b[mmx])) { q[++cnt].x=mmn; q[cnt].y=mmn; b[mmn]*=2; } for(int i=1;i<=n;i++) { if(b[i]>0) { q[++cnt].x=i; q[cnt].y=mmn; } } for(int i=n-1;i;i--) { q[++cnt].x=i; q[cnt].y=i+1; } cout<<cnt<<'\n'; for(int i=1;i<=cnt;i++) { cout<<q[i].x<<" "<<q[i].y<<'\n'; } }
void solve() { mmx=1,mmn=1; int cnt0=0,cnt1=0; for(int i=1;i<=n;i++) b[i]=a[i]; for(int i=1;i<=n;i++) { if(b[mmx]<b[i]) mmx=i; if(b[mmn]>b[i]) mmn=i; if(b[i]>0) cnt1++; if(b[i]<0) cnt0++; } if(b[mmx]<=0) { cout<<n-1<<'\n'; for(int i=n-1;i;i--) { cout<<i<<' '<<i+1<<'\n'; } } else if(b[mmn]>=0) { cout<<n-1<<'\n'; for(int i=1;i<n;i++) { cout<<i+1<<' '<<i<<'\n'; } } else { if(abs(b[mmx])>=abs(b[mmn])) { if(cnt0>12) sol2(); else sol1(); } else { if(cnt1>12) sol1(); else sol2(); } } }
int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } cnt=0; solve(); } }
|
D. Earn or Unlock
显然可以转化为一个背包问题,因为到了 x 位置的花费和获得都是固定的,bitset 背包考虑能到哪些位置就可了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| #include<bits/stdc++.h> #define int long long
using namespace std;
const int maxn=200100;
bitset <maxn> b,t; int n,a[maxn],ans=0; int sum[maxn];
signed main() { ios::sync_with_stdio(false); cin>>n; t.set(); for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } for(int i=n+1;i<=n*2;i++) sum[i]=sum[i-1]; ans=a[1]; b[1]=1; for(int i=1;i<=n*2;i++) { if(i<=n)b=b|((b&t)<<a[i]); if(b[i])ans=max(ans,sum[i]-i+1); t[i]=0; } cout<<ans<<"\n"; }
|