概述
数学场，我只写了四题没想到rank都有121，和我一起打的帅辉四题居然rank38 orz，强巨三小时5题rank18（膜啊膜）
A 小a的计算器
链接：https://ac.nowcoder.com/acm/contest/317/A
来源：牛客网
小a的数学基础实在太差了，以至于他只会用计算器算数。他的计算器比较特殊，只有+,−,×,/+,−,×,/(即加减乘除)四种运算。
经过一番周折，小a终于算出了他想要的数，但是他却忘记了最初的数是什么。不过幸运的是他记下了整个操作序列，他想请你帮他算出最初的数
输入描述:
第一行两个整数n,Xn,X，分别表示操作次数和最终的数
接下来nn行表示操作序列，每行两个数opt,xopt,x
若opt=1opt=1，则表示将当前数加xx
若opt=2opt=2，则表示将当前数减xx
若opt=3opt=3，则表示将当前数乘xx
若opt=4opt=4，则表示将当前数除以xx
输出描述:
一个整数表示最初的数
示例1
输入
4 6
1 3
2 1
3 3
4 2
输出
2
签到，直接暴力模拟就行，加减互换，乘除互换即可。
#include<stdio.h>
int main(){
int n,opt[101],i;
long long k,x[101],ans;
scanf("%d %lld",&n,&k);
//ans=0;
for(i=0;i<n;i++) scanf("%d %lld",&opt[i],&x[i]);
for(i=n-1;i>=0;i--){
if(opt[i]==1) k=k-x[i];
else if(opt[i]==2) k=k+x[i];
else if(opt[i]==3) k=k/x[i];
else if(opt[i]==4) k=k*x[i];
//printf("%lldn",k);
}
printf("%lld",k);
return 0;
}
B 小a与’204’
链接：https://ac.nowcoder.com/acm/contest/317/B
来源：牛客网
小a非常喜欢204204这个数字，因为′a′+′k′=204′a′+′k′=204。
现在他有一个长度为n的序列，其中只含有2,0,4这三种数字
设ai为序列中第i个数，你需要重新排列这个数列，使得∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0a0=0
输入描述:
第一行一个整数nn
接下来一行nn个整数，第ii个数表示aiai
输出描述:
输出一个整数，表示∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2的最大值
示例1
输入
2
2 4
输出
20
运用贪心的思想，显然，用0来间隔2，4是能使结果最大的，所以我们在排列时应该先间隔的排4，0（例如40404……），再排4242……或者402020……，这都取决于0，2，4的个数，因此分别计数再分类讨论即可。
#include<stdio.h>
int SQ(int x,int y){
return (x-y)*(x-y);
}
int main(){
int n,aa[100001]={0},i,j,a=0,b=0,c=0;
long long ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&aa[i]);
if(aa[i]==0) a++;
else if(aa[i]==2) b++;
else if(aa[i]==4) c++;
}
//printf("a=%d,b=%d,c=%dn",a,b,c);
if(a>=(b+c-1)) ans=16*(2*c)+4*(2*b-1);
else{
if(a>=c) ans=16*2*c+(2*(a-c+1)-1)*4;
else if(a<c){
if(b>(c-a-1)) ans=16*(2*(a+1)-1)+4*(2*c-2*a-1);//
else ans=16*(2*(a+1)-1)+8*b;
}
}
printf("%lld",ans);
return 0;
}
C 小a的星际旅行
链接：https://ac.nowcoder.com/acm/contest/317/C
来源：牛客网
小a正在玩一款星际探索游戏，小a需要驾驶着飞船从11号星球出发前往nn号星球。其中每个星球有一个能量指数pp。星球ii能到达星球jj当且仅当pi>pj。
同时小a的飞船还有一个耐久度tt，初始时为11号点的能量指数，若小a前往星球jj，那么飞船的耐久度会变为t⊕pjt⊕pj(即t异或pj，关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关
输入描述:
第一行一个整数n，表示星球数
接下来一行有n个整数，第i个整数表示pi
输出描述:
一个整数表示到达n号星球时最大的耐久度
若不能到达n号星球或到达时的最大耐久度为0则输出−1
示例1
输入
3
457 456 23
输出
478
显然暴力搜索时会TLE，那么我考虑dp，并写了如下dp代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
int max(int x,int y){
return x>y?x:y;
}
int dp[3001];
int main(){
int n,p[3001],i,j,t;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&p[i]),dp[i]=-1;
dp[1]=p[1];
if(p[1]<=p[n]) printf("-1");
else {
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
if(p[i]<p[j]) dp[i]=max(dp[j]^p[i],dp[i]);
}
}
if(dp[n]==0) printf("-1");
else printf("%d",dp[n]);
}
return 0;
}
提交上去牛客也显示ac，但是被泽神和凯巨的hack了，后来想了想，发现这是个写成dp的贪心，而实际问题应该是一个背包问题，因此提供如下线性基做法：
#include <bits/stdc++.h>
#define lld I64d
using namespace std ;
inline long long Readin() {
long long K = 0 , F = 1 ; char C = ' ' ;
while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ;
return F * K ;
}
const int Bit = 12 ;
int N , A[3005] , Base[Bit+5] ;
inline void Insert( int Num ) {
for(register int i = Bit ; --i >= 0 ; )
if( 1 << i & Num )
if( not Base[i] ) {
Base[i] = Num ;
break ;
}
else Num ^= Base[i] ;
}
inline int Query( int Num ) {
for(register int i = Bit ; --i >= 0 ; )
Num = max( Num , Num ^ Base[i] ) ;
return Num ;
}
int main() {
N = Readin() ;
for(register int i = 0 ; ++i <= N ; A[i] = Readin() ) ;
if( A[1] < A[N] ) return not printf( "-1n" ) ;
for(register int i = 1 ; ++i < N ; )
if( A[1] >= A[i] and A[i] >= A[N] )
Insert( A[i] ) ;
return not printf( "%dn" , Query( A[1] ^ A[N] ) ) ;
}
C 小a与黄金街链接：https://ac.nowcoder.com/acm/contest/317/D
来源：牛客网
小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。
游戏规则是这样的：
假设道路长度为nn米(左端点为0，右端点为n)，同时给出一个数k(下面会提到k的用法)
设小a初始时的黄金数量为A，小b初始时的黄金数量为B
小a从1出发走向n−1，小b从n−1出发走向1，两人的速度均为1m/s
假设某一时刻(必须为整数)小a的位置为x，小b的位置为y，若gcd(n,x)=1gcd且gcd(n,y)=1，那么小a的黄金数量A会变为A∗kx，小b的黄金数量B会变为B∗ky
当小a到达n−1时游戏结束……
小a想知道在游戏结束时A+B值
答案对10^9+7取模
输入描述:
一行四个整数n,k,A,B
输出描述:
输出一个整数表示答案
示例1
输入
4 2 1 1
输出
32
首先不难发现，若gcd(n,x)=1,则gcd(n,n-x)=1.反证法：若gcd(n,x)=1,gcd(n,n-x)=k,那么n=kp,n-x=kq,则x=k*(p-q),则n与x有共同约数k，与已知不符，故结论成立。
那么小a小b的总贡献是相同的
小a单独的贡献是Aka*k(n-a)kb*k(n-b)……=Ak^Rn,R为系数，
如何求R的值呢，通过题目描述发现，能产生答案的数一定是与n互质的数，这与欧拉函数的定义相同！记P(x)为x的欧拉函数值(欧拉函数的符号不知道怎么打QAQ），又因为前n个数的欧拉函数之和为n/2P(n)，当然，不知道这个结论也可以用容斥原理来算约数的贡献，所以最终答案就是(A+B)K^(P(n)/2n),注意，指数幂比较大，需要用快速幂来算 我的代码如下(那是没想到欧拉函数，直接找超哥要的O(根号n)容斥的板子:
#include<stdio.h>
#include<vector>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll A,B,k;
int solve (int n, int r) { //1~r,容斥原理的板子
vector<int> p;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
p.push_back (i);
while (n % i == 0)
n /= i;
}
if (n > 1)
p.push_back (n);
int sum = 0;
for (int msk=1; msk<(1<<p.size()); ++msk) {
int mult = 1,
bits = 0;
for (int i=0; i<(int)p.size(); ++i)
if (msk & (1<<i)) {
++bits;
mult *= p[i];
}
int cur = r / mult;
if (bits % 2 == 1)
sum += cur;
else
sum -= cur;
}
return r - sum;
}
ll mod_pow(ll x,ll n){
ll res=1;
while(n){
if(n&1) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
int main(){
int n,gg;
scanf("%d %d %d %d",&n,&k,&A,&B);
gg=solve(n,n)/2*n%mod;
printf("%lld",(A+B)*mod_pow(k,gg)%mod);
return 0;
}
这是后来推出公式的做法：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9+7;
long long Euler(long long n) {
long long res = n;
for(int i = 2; i*i <=n; i++){
if(n%i == 0) {
res -= res/i;
while(n%i == 0)
n /= i;
}
}
if(n>1)
return res -= res/n;
return res;
}
ll quickpow(ll k, ll m) {
ll res = 1;
while (m) {
if (m & 1) {
res *= k;
res %= mod;
}
k *= k;
k %= mod;
m >>= 1;
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
ll n, k, A, B;
cin >> n >> k >> A >> B;
cout << ((A+B)*quickpow(k, Euler(n)/2*n)) % mod << endl;
return 0;
}
H 小a的学期
链接：https://ac.nowcoder.com/acm/contest/317/H
来源：牛客网
小a是一个健忘的人，由于他经常忘记做作业，因此老师对他很恼火。
小a马上就要开学了，他学期一共2n天，对于第i天，他有可能写了作业，也可能没写作业，不过他自己心里还有点B数，因此他会写恰好n天的作业
现在，小a需要安排他的学期计划，如果小a的学期中存在一天x，在这之前的x天中，他没写作业的天数 - 写作业的天数⩾k，那么老师就会把它开除，我们称这是一种不合法的方案
小a想知道他有多少种合法的方案
输入描述:
第一行三个整数n,k,p表示对p取模
输出描述:
一个整数表示答案
示例1
输入
2 1 100007
输出
2
运用卡特兰数证明思想的题，如果我们会catalan数的证明，那么这道题会很容易证出结论，证明如下
长度为2?的序列，?个−1，?个+1，问不存在一个前缀值≥ ?的方案数有多少 首先，若存在一个不合法的前缀≥?，那么一定存在一个位置=?。 ?=1显然是经典的Catalan数 考虑其证明过程 若数列不合法，则一定存在一个位置，在这之前有?+?个+1，?个−1 我们把之后的1变为−1，−1变为1 则该序列含有?+?个+1，?−?个 −1 也就是说，一种不合法的方案进行上述转化后，一定唯一对应了长度为2?且含?+?个1的序列 那么转化后序列的方案数为 C(2n,n+k) ，用总的 C(2n,n) 减去即可 注意模数可能不为素数，我们可以考虑每个质因子的贡献，也就是把公式C(n,m)中的阶乘展开，同时用 线性筛预处理出每个数的最小质因子，对于每个数将其分解成质数乘积的形式，最后统计每个质数的贡献即可 复杂度：?(?????)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,cot=0,k,mod,a[100005];
bool vis[2000005];
void init(ll x)
{
a[cot++]=2;
for(ll i=3;i<=x;i+=2)
{
if(!vis[i])
{
a[cot++]=i;
for(int j=i;j<=x;j+=i)
vis[j]=true;
}
}
}
ll qpow(ll a,ll n)
{
ll ans=1;
while(n)
{
if(n&1) ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
ll cal(ll x,ll p)
{
ll ans=0,t=p;
while(x>=p)
{
ans+=x/p;
p*=t;
}
return ans;
}
ll c(ll n,ll m)
{
ll ans=1,num;
for(int i=0;i<cot;i++)
{
num=cal(n,a[i])-cal(m,a[i])-cal(n-m,a[i]);
ans=ans*qpow(a[i],num)%mod;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld",&n,&k,&mod);
init(2*n);
printf("%lldn",(c(2*n,n)+mod-c(2*n,n-k))%mod);
}
待补充
最后
以上就是义气巨人为你收集整理的牛客j寒假算法训练营一（待补充）的全部内容，希望文章能够帮你解决牛客j寒假算法训练营一（待补充）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复