题解 | #小竹与妈妈#
小竹与妈妈
https://ac.nowcoder.com/acm/contest/45670/A
A.
显然小竹的年龄为 #include<bits/stdc++.h>
using namespace std;
int a,b,x;
int main()
{
cin>>a>>b>>x;
cout<<(x-b)/a<<'\n';
return 0;
}
B.记录每个房间有多少个出口连接记为
#include<bits/stdc++.h>
using namespace std;
int cnt[100005];
int n,m,q;
int main()
{
cin>>n>>m>>q;
assert(1<=n&&n<=1e5);
assert(1<=m&&m<=1e5);
assert(1<=q&&m<=1e5);
for(int i = 1;i<=n;++i)
{
int x;
cin>>x;
assert(1<=x&&x<=m);
cnt[x]++;
}
while(q--)
{
int x;
cin>>x;
assert(1<=x&&x<=m);
cout<<(n-cnt[x])<<'\n';
}
return 0;
}
C.
用一个
设
很容易能列出 
。
由于允许 
通过,直接模拟该过程即。最后的答案为
。
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2005];
int dp[2005];
int ans;
int main()
{
cin>>n>>k;
assert(1<=n&&n<=2000);
assert(1<=k&&k<=n);
for(int i = 1;i<=n;++i)
{
cin>>a[i];
assert(a[i]<=2000&&a[i]>=1);
}
for(int i = 1;i<=n;++i)
for(int j = 0;j<=max(0,i-k-1);++j)
{
dp[i] = max(dp[j]+a[i],dp[i]);
ans = max(ans,dp[i]);
}
cout<<ans<<'\n';
return 0;
}
D.
从起点开始
时间复杂度
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,x;
ios::sync_with_stdio(false);
cin.tie(nullptr);
int sx,sy,ex,ey;
assert(cin>>n>>m>>x);
assert(cin>>sx>>sy>>ex>>ey);
vector<vector<int>> s(n,vector<int>(m));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
assert(cin>>s[i][j]);
sx--,sy--,ex--,ey--;
s[sx][sy]=0,s[ex][ey]=0;
vector<vector<int>> dista(n,vector<int>(m,1e9)),distb=dista;
function<void(vector<vector<int>>&,int,int)> bfs=[&](vector<vector<int>> &dist,int x,int y)->void{
array<int,4> dx ={-1,1,0,0},dy ={0,0,-1,1};
dist[x][y]=0;
using PII = pair<int,int>;
queue<PII> qe;
qe.push({x,y});
while(qe.size()){
PII var = qe.front();
qe.pop();
for(int i=0;i<4;i++){
int x= var.first+dx[i],y=var.second+dy[i];
if(x<0||y<0||x>=n||y>=m)continue;
if(s[x][y]==-1)continue;
if(dist[x][y] > dist[var.first][var.second]+1){
dist[x][y] = dist[var.first][var.second]+1;
qe.push({x,y});
}
}
}
};
bfs(dista,sx,sy),bfs(distb,ex,ey);
int ans = 1e9;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(s[i][j]>x)
ans = min(ans,dista[i][j]+distb[i][j]);
if(ans==1e9)
ans=-1;
cout << ans<<"\n";
}
E.相邻结点满足有至少两个不同的共同质因子,也就相当于,相邻两个结点的
我们可以把所有质数的幂次使用一个标记数组
设
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int f[5*maxn+5];
int p[5*maxn+5];
int dp[maxn+5];
int a[maxn+5];
int n;
int ans;
vector<int> edge[maxn+5];
void dfs(int x,int fa)
{
dp[x] = 1;
for(auto v:edge[x])
{
if(v==fa) continue;
dfs(v,x);
if(!f[(__gcd(a[v],a[x]))])
dp[x]+=dp[v];
}
ans = max(dp[x],ans);
}
int main()
{
f[1] = 1;
for(int i = 2;i<=5*maxn;++i)
if(!p[i])
{
for(int j = i+i;j<=5*maxn;j+=i)
p[j] = 1;
for(long long j = i;j<=5*maxn;j*=i)
f[j] = 1;
}
cin>>n;
assert(1<=n&&n<=1e6);
for(int i = 1;i<=n;++i)
{
cin>>a[i];
assert(a[i]<=5e6&&a[i]>=1);
}
for(int i = 1;i<n;++i)
{
int x,y;
cin>>x>>y;
assert(1<=x&&x<=n);
assert(1<=y&&y<=n);
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1,0);
for(int i = 1;i<=n;++i)
assert(dp[i]);
cout<<ans<<'\n';
return 0;
}
F.先考虑后面那一堆式子，考虑算出每一个区间的贡献，区间内每一个数作为
所以直接枚举区间长度
我们发现这个式子与排列无关所以原式可以写成:
我们可以计算每一对逆序对
共有
答案即为
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int n;
vector<int> js;
const int mod = 1e9+7;
ll fac[100006];
ll ifac[100006];
int maxn = 1e5+4;
ll ksm(ll x, ll y)
{
ll ret = 1;
do {
if ( y & 1 )
ret = ret * x % mod;
x = x * x % mod;
} while ( y >>= 1 );
return ret;
}
void init()
{
fac[0] = 1;
for ( int i = 1;i <= maxn;i++ ) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[maxn - 1] = ksm(fac[maxn - 1], mod - 2);
for ( int i = maxn - 1;i >= 1;i-- ) {
ifac[i - 1] = ifac[i] * i % mod;
}
}
ll C(int x, int y)
{
return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
void solve()
{
int n;
cin>>n;
assert(1<=n&&n<=100000);
ll ans = (((C(n+3,4))%mod*fac[(n-2)]%mod*(1ll*n*(n-1)/2)%mod*(1ll*n*(n-1)/2)%mod))%mod;
assert(0<=ans&&ans<=1e9+7);
cout<<ans<<'\n';
}
signed main()
{
init();
int t;
cin>>t;
assert(1<=t&&t<=100000);
while(t--)
solve();
return 0;
}
投递英伟达等公司10个岗位 >
