牛客寒假算法集训 1

<h1>A题</h1> <h2>小a的计算器（水题）</h2> 链接：<a href="https://ac.nowcoder.com/acm/contest/317/A" target="_blank">https://ac.nowcoder.com/acm/contest/317/A</a> 来源：牛客网 小a的数学基础实在太差了，以至于他只会用计算器算数。他的计算器比较特殊，只有<mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">+,−,×,/+,−,×,/(即加减乘除)四种运算。 经过一番周折，小a终于算出了他想要的数，但是他却忘记了最初的数是什么。不过幸运的是他记下了整个操作序列，他想请你帮他算出最初的数 <h2><mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">思路</h2> <mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">就是用个数组，将操作序列记录下来，然后逆序进行求解，这里对乘的运算的逆是除，但是，要排除除以0的情况，进行下特判 <h2><mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">代码</h2> <div class="cnblogs_code"> <pre>#include <bits/stdc++.h> using namespace std; int main() { long long n,m; cin>>n>>m; long long op[105],x[105]; for(int i=1;i<=n;i++) cin>>op[i]>>x[i]; for(int i=n;i>=1;i--){ if(op[i]==1) m-=x[i]; else if(op[i]==2)m+=x[i]; else if(op[i]==3) { if(x[i]==0) m=0; else m=m/x[i]; } else m=m*x[i]; } cout<<m<<endl; return 0; }</pre> </div>   <h1>B题</h1> <h2>小a与204</h2> 链接：<a href="https://ac.nowcoder.com/acm/contest/317/B" target="_blank">https://ac.nowcoder.com/acm/contest/317/B</a> 来源：牛客网 小a非常喜欢<mn>204</mn></math>">204204这个数字，因为<msup><mi></mi><mo>&#x2032;</mo></msup><msup><mi>a</mi><mo>&#x2032;</mo></msup><msup><mo>+</mo><mo>&#x2032;</mo></msup><msup><mi>k</mi><mo>&#x2032;</mo></msup><mo>=</mo><mn>204</mn></math>">′a′+′k′=204′a′+′k′=204。 现在他有一个长度为<mi>n</mi></math>">nn的序列，其中只含有<mn>2</mn><mo>,</mo><mn>0</mn><mo>,</mo><mn>4</mn></math>">2,0,42,0,4这三种数字 设<msub><mi>a</mi><mi>i</mi></msub></math>">aiai为序列中第<mi>i</mi></math>">ii个数，你需要重新排列这个数列，使得<munderover><mo>&#x2211;</mo><mrow class="MJX-TeXAtom-ORD"><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo stretchy="false">(</mo><msub><mi>a</mi><mi>i</mi></msub><mo>&#x2212;</mo><msub><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>i</mi><mo>&#x2212;</mo><mn>1</mn></mrow></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup></math>">∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和) 注意：我们默认<msub><mi>a</mi><mn>0</mn></msub><mo>=</mo><mn>0</mn></math>">a0=0a0=0 <h2><mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">思路</h2> <mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">贪心，我们需要对一个序列进行排序，是的两两之差的平方，要尽可能的大。 <mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">这里我们只需要先将2 0 4这三个数的次数统计一下，然后从1开始，对于前一个数进行判断然后放值进行就行了 <mo>+</mo><mo>,</mo><mo>&#x2212;</mo><mo>,</mo><mo>&#x00D7;</mo><mo>,</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow></math>">如果前一个数是0，那优先放4，如果4没了，就放2，如果2也没了，就放0，其他数也同理。 <h2>代码</h2> <div class="cnblogs_code"> <pre>#include <bits/stdc++.h> using namespace std; int main() { int n,m; long long ans=0; int a=0,b=0,c=0; cin>>n; for(int i=0;i<n;i++){ cin>>m; if(m==0) a++; if(m==2) b++; if(m==4) c++; } int t=0; for(int i=0;i<n;i++){ if(t==0){ if(c>0) c--,ans+=16,t=4; else if(b>0) b--,ans+=4,t=2; else a--; } else if(t==2){ if(c>0) c--,ans+=4,t=4; else if(a>0) a--,ans+=4,t=0; else b--; } else if(t==4){ if(a>0) a--,ans+=16,t=0; else if(b>0) b--,ans+=4,t=2; else c--; } } cout<<ans<<endl; return 0; }</pre> </div> <h1>C题</h1> <h2>小a与星际探索</h2> 链接：<a href="https://ac.nowcoder.com/acm/contest/317/C" target="_blank">https://ac.nowcoder.com/acm/contest/317/C</a> 来源：牛客网 小a正在玩一款星际探索游戏，小a需要驾驶着飞船从<mn>1</mn></math>">11号星球出发前往<mi>n</mi></math>">nn号星球。其中每个星球有一个能量指数<mi>p</mi></math>">pp。星球<mi>i</mi></math>">ii能到达星球<mi>j</mi></math>">jj当且仅当<msub><mi>p</mi><mi>i</mi></msub><mo>&gt;</mo><msub><mi>p</mi><mi>j</mi></msub></math>">pi>pjpi>pj。 同时小a的飞船还有一个耐久度<mi>t</mi></math>">tt，初始时为<mn>1</mn></math>">11号点的能量指数，若小a前往星球<mi>j</mi></math>">jj，那么飞船的耐久度会变为<mi>t</mi><mo>&#x2295;</mo><msub><mi>p</mi><mi>j</mi></msub></math>">t⊕pjt⊕pj(即<mi>t</mi></math>">tt异或<msub><mi>p</mi><mi>j</mi></msub></math>">pjpj，关于其定义请自行百度) 小a想知道到达<mi>n</mi></math>">nn号星球时耐久度最大为多少 <div> 注意：对于每个位置来说，从它出发可以到达的位置仅与两者的 <mi>p</mi></math>">pp有关，与下标无关 </div> <h2>思路</h2> 背包问题的dp 首先我们队这个能量指数进行排序，使得对于每个星球，在他之后的所有星球都可以从这个星球到达。 然后就开始dp呗，我自己的代码好像不是正确的。所以再贴一份官方的代码 <h2>代码</h2> <div class="cnblogs_code"> <pre>#include <bits/stdc++.h> using namespace std; int n; struct node{ int a,b; }num[3005]; int cmp(node x,node y){ if(x.b==y.b) return x.a<y.b; return x.b>y.b; } int main() { std::ios::sync_with_stdio(false); cin>>n; for(int i=0;i<n;i++){ cin>>num[i].b; num[i].a=i; } sort(num,num+n,cmp); int s,t; //for(int i=0;i<n;i++) cout<<num[i].a<<' '<<num[i].b<<endl; for(int i=0;i<n;i++){ if(num[i].a==0) s=i; if(num[i].a==n-1) t=i; } //cout<<s<<' '<<t<<endl; if(s>t) cout<<-1<<endl; else{ int dp[3005]; memset(dp,0,sizeof(dp)); dp[s]=num[s].b; for(int i=s+1;i<=t;i++){ for(int j=s;j<i;j++){ dp[i]=max(dp[i],dp[j]^num[i].b); } } if(!dp[t]) cout<<-1<<endl; else cout<<dp[t]<<endl; } return 0; }</pre> </div> <div class="cnblogs_code"> <pre>#include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 10003, INF = 1e9 + 10; void chmin(int &a, int b) {a = (a a : b);} void chmax(int &a, int b) {a = (a > b ? a : b);} int sqr(int x) {return x * x;} inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, mx; bool f[MAXN][MAXN]; struct Node { int id, val; bool operator < (const Node &rhs) const { return val > rhs.val; } }a[MAXN]; signed main() { //freopen("a2.in", "r", stdin); //cout << (457 ^ 23); N = read(); for(int i = 1; i <= N; i++) a[i].id = i, a[i].val = read(); mx = 6001; sort(a + 1, a + N + 1); for(int i = 1, flag = 1; i <= N; i++) { if(a[i].id == 1) {flag = 0, f[i][a[i].val] = 1; continue;} if(flag) continue; if(a[i].id == N) { int k = i - 1; while(k && a[i].val == a[k].val) k--; if(!k) break; for(int j = mx; j >= 0; j--) { f[i][j] |= f[k][j ^ a[i].val]; if(f[i][j]) {printf("%d", j); return 0;} } break; } else if(a[i].val == a[i - 1].val) { memcpy(f[i], f[i - 1], sizeof(f[i])); } else { for(int j = 0; j <= mx; j++) f[i][j] |= (f[i - 1][j ^ a[i].val] | f[i - 1][j]); } } puts("-1"); return 0; }</pre> </div> <h1>D题</h1> <h2>小a与黄金街道</h2> 链接：<a href="https://ac.nowcoder.com/acm/contest/317/D" target="_blank">https://ac.nowcoder.com/acm/contest/3***> 来源：牛客网 小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。 游戏规则是这样的： 假设道路长度为<mi>n</mi></math>">nn米(左端点为<mn>0</mn></math>">00，右端点为<mi>n</mi></math>">nn)，同时给出一个数<mi>k</mi></math>">kk(下面会提到<mi>k</mi></math>">kk的用法) 设小a初始时的黄金数量为<mi>A</mi></math>">AA，小b初始时的黄金数量为<mi>B</mi></math>">BB 小a从<mn>1</mn></math>">11出发走向<mi>n</mi><mo>&#x2212;</mo><mn>1</mn></math>">n−1n−1，小b从<mi>n</mi><mo>&#x2212;</mo><mn>1</mn></math>">n−1n−1出发走向<mn>1</mn></math>">11，两人的速度均为<mn>1</mn><mi>m</mi><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mi>s</mi></math>">1m/s1m/s 假设某一时刻(必须为整数)小a的位置为<mi>x</mi></math>">xx，小b的位置为<mi>y</mi></math>">yy，若<mi>g</mi><mi>c</mi><mi>d</mi><mo stretchy="false">(</mo><mi>n</mi><mo>,</mo><mi>x</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></math>">gcd(n,x)=1gcd(n,x)=1且<mi>g</mi><mi>c</mi><mi>d</mi><mo stretchy="false">(</mo><mi>n</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></math>">gcd(n,y)=1gcd(n,y)=1，那么小a的黄金数量<mi>A</mi></math>">AA会变为<mi>A</mi><mo>&#x2217;</mo><msup><mi>k</mi><mi>x</mi></msup><mo stretchy="false">(</mo><mi>k</mi><mi>g</mi><mo stretchy="false">)</mo></math>">A∗kx(kg)A∗kx(kg)，小b的黄金数量<mi>B</mi></math>">BB会变为<mi>B</mi><mo>&#x2217;</mo><msup><mi>k</mi><mi>y</mi></msup><mo stretchy="false">(</mo><mi>k</mi><mi>g</mi><mo stretchy="false">)</mo></math>">B∗ky(kg)B∗ky(kg) 当小a到达<mi>n</mi><mo>&#x2212;</mo><mn>1</mn></math>">n−1n−1时游戏结束 小a想知道在游戏结束时<mi>A</mi><mo>+</mo><mi>B</mi></math>">A+BA+B的值 答案对<msup><mn>10</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></math>">109+7109+7取模 <h2>思路</h2> 首先我们需要理解一个知识点，对于gcd（n，x）=1 时，x<n，gcd（n，n-x）=1，这个是满足的 那这个问题就转换成我们要求在n以内有多少个与n互质的个数，也就是欧拉函数。 当然只求个数是不行的，我们需要知道这些数的和，就为<mi>&#x03D5;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math>">ϕ(n)*n/2，这个可以推一下 <h2>代码</h2> <div class="cnblogs_code"> <pre>#include <bits/stdc++.h> using namespace std; const int mod=1e9+7; int phi(int n) { int ans = n; for(int i = 2;i*i <= n;i++)if(n % i == 0) { ans -= ans/i; while(n % i == 0) n /= i; } if(n != 1) ans -= ans/n; return ans; } long long power_mod(long long a,long long b){ long long ans=1; a=a%mod; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { int n; long long k,a,b; ios::sync_with_stdio(false); cin>>n>>k>>a>>b; long long x=(long long)phi(n)*n/2; a=a%mod; b=b%mod; long long ans=(a+b)*power_mod(k,x)%mod; cout<<ans<<endl; return 0; }</pre> </div>