A.牛牛的DRB迷宫I
题解：这道最签到的题目，裸dp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 205;
int n,m;
const int mod = 1e9+7;
char a[maxn][maxn];
ll dp[maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
memset(dp,0,sizeof(dp));
dp[1][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i>1&&(a[i-1][j]=='B'||a[i-1][j]=='D'))
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
if(j>1&&(a[i][j-1]=='B'||a[i][j-1]=='R'))
dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
}
}
printf("%lld\n",dp[n][m]);
}B.牛牛的DRB迷宫II
题解：这道题真的是一道非常好的思维题，我们可以知道dp[1][1]=1,通过讲mp[1][1]='B',mp[1][2]='D',mp[2][1]='R',我们可以算出dp[2][2]=2,同样可以通过这个构造方法可以使得对角线上的值变为dp[i][i]=
。而i位二进制可以表示 -1内的任意数。而题目要求的1e9+7我们可以发现
因此我们只要用30列就可以构造出1e9+7内的任意数。而我们怎么选取哪一列要哪一列不要呢。我们可以将最下面那一行全部设为'R',而在不要的那一列下面将mp[i+1][i]='R',因为一共有30列，所以i最大会取到30，那么为了使mp[i+1][i]能取到，而又不影响最后一行，那么需要32行。这样就能控制那一列向下转移了，所以一共需要32行，30列即可。可以结合图片理解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
char mp[55][55];
int main()
{
int n=32,m=30;
int k;
scanf("%d",&k);
for(int i=1;i<=m;i++)mp[1][i]=(i<=2)?'B':'R';
for(int i=2;i<=n-1;i++)
{
for(int j=1;j<=m;j++)
{
if(j<i-1)mp[i][j]='D';
else if(j<i+2)mp[i][j]='B';
else mp[i][j]='R';
}
}
for(int i=1;i<=m;i++)
{
if(!(k&(1<<(i-1))))mp[i+1][i]='R';
mp[n][i]='R';
}
printf("%d %d\n",n,m);
for(int i=1;i<=n;i++)
printf("%s\n",mp[i]+1);
return 0;
}C.牛牛的数组越位
题解：一道简单模拟题，照着题意来即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int a[maxn][maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
int f1=1,f2=1;
while(p--)
{
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
if(!f2)continue;
if(x<0||y<0||x>=n||y>=m)
f1=0;
int sum = x * m + y;
if(sum<0||sum>=n*m)
{
f2=0;
continue;
}
int tx = sum / m;
int ty = sum % m;
a[tx][ty]=val;
}
if(!f1&&!f2)
printf("Runtime error\n");
else
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
printf("%d%c",a[i][j],j==m-1?'\n':' ');
if(!f1)printf("Undefined Behaviour\n");
else printf("Accepted\n");
}
}
return 0;
}D.牛牛与二叉树的数组存储
题解：同样是一道简单模拟。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
int t[maxn],id[maxn];
set<int>s;
int main()
{
memset(id,-1,sizeof(id));
memset(t,-1,sizeof(t));
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
id[t[i]]=i;
if(t[i]!=-1)
s.insert(t[i]);
}
printf("The size of the tree is %d\n",s.size());
printf("Node %d is the root node of the tree\n",t[1]);
for(auto i:s)
{
printf("The father of node %d is %d, ",i,id[i]==1?-1:t[id[i]/2]);
printf("the left child is %d, ",t[id[i]*2]);
printf("and the right child is %d\n",t[id[i]*2+1]);
}
return 0;
}E.牛牛的随机数
题解:一道很好的数位dp，官方题解讲的很好我就直接贴过来了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll INF = 1ll << 60;
ll cnta[70], cntb[70], dp[70][70][2], a[70];
ll dfs(int len, bool maxi, int k, bool f)
{
if (dp[len][k][f] != -1 && maxi == 0)
return dp[len][k][f];
ll cnt = 0;
if (!len)
return f;
int maxn = maxi ? a[len] : 1;
for (int i = 0; i <= maxn; i++)
cnt += dfs(len - 1, maxi && i == a[len], k, f || k == len && i);
return maxi ? cnt : dp[len][k][f] = cnt;
}
ll div(ll tmp, int k) //求0~tmp之间第k位为1的个数
{
memset(a, 0, sizeof(a));
int p = 0;
while (tmp)
a[++p] = tmp % 2, tmp /= 2;
return dfs(p, 1, k, 0);
}
ll inv(ll x, ll mod)
{
ll k = mod - 2, ans = 1;
while (k)
{
if (k & 1)
ans = ans * x % mod;
x = x * x % mod;
k >>= 1;
}
return ans;
}
int main()
{
int T;
memset(dp, -1, sizeof(dp));
scanf("%d", &T);
while (T--)
{
ll l1, r1, l2, r2, p = 1, ans = 0;
scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
l1--, l2--;
for (int i = 1; i <= 60; i++, p *= 2)
{
cnta[i] = div(r1, i) - div(l1, i);
cntb[i] = div(r2, i) - div(l2, i);
ans += (cnta[i] % mod * ((r2 - l2 - cntb[i]) % mod) % mod + cntb[i] % mod * ((r1 - l1 - cnta[i]) % mod) % mod) * (p % mod) % mod;
ans %= mod;
}
ans = ((ans % mod) + mod) % mod;
ans = ans * inv(((r1 - l1) % mod) * ((r2 - l2) % mod) % mod, mod) % mod;
printf("%lld\n", ans);
}
return 0;
}官方题解还给出了另一种不借助数位dp的做法，通过观察数字二进制下的特点来写，也很好。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
ll get_sum_1(ll limit,int bits)
{
limit++;
ll ans=limit/(2ll<<bits)*(1ll<<bits);
ans+=((limit/(1ll<<bits))&1)*(limit%(1ll<<bits));
return ans%mod;
}
ll get_sum_0(ll limit,int bits)
{
limit++;
ll ans=limit/(2ll<<bits)*(1ll<<bits);
if((limit/(1ll<<bits))&1)
ans+=(1ll<<bits);
else
ans+=(limit%(1ll<<bits));
return ans%mod;
}
ll get_val(ll limit1,ll limit2)
{
ll ans=0;
for(int i=0;i<=62;i++)
{
ll val=(1ll<<i)%mod;
ans=(ans+get_sum_0(limit1,i)*get_sum_1(limit2,i)%mod*val+get_sum_1(limit1,i)*get_sum_0(limit2,i)%mod*val)%mod;
ans%=mod;
}
return ans;
}
ll quickpow(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=(x*ans)%mod;
x=(x*x)%mod;
y>>=1;
}
return ans;
}
ll get_inv(ll x)
{
return quickpow(x,mod-2);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll l1,r1,l2,r2;
scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
ll ans=0;
ans+=get_val(r1,r2);
ans-=get_val(l1-1,r2);
ans-=get_val(r1,l2-1);
ans+=get_val(l1-1,l2-1);
ans=((ans%mod)+mod)%mod;
ans=ans*get_inv(((r1-l1+1)%mod)*((r2-l2+1)%mod)%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}F.牛牛的Link Power I
题解：扫描一遍，记录前面所有点的贡献和点数，每移动一位则贡献加上所有点的点数，就是每个点的贡献都加一。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
const long long mod=1e9+7;
char s[MAXN];
int n;
long long sum,cnt,ans;
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;++i)
{
sum=(sum+cnt)%mod;
if(s[i]=='1')
{
ans=(ans+sum)%mod;
++cnt;
}
}
printf("%lld\n",ans);
return 0;
}G.牛牛的Link Power II
这题就是在上一题的基础上增加了单点的修改，不难想到用线段树，操作1我们只需要加上单点的贡献，操作2我们只需要减去单点的贡献。而一个点的贡献我们可以通过将区间划分为以该点的分界的左右两部分算出，左边贡献为左边点数该点位置-左边坐标和，右边贡献为右边坐标和-右边点数该点位置算出即可。因为要取模，不要忘记取模后可能变负的情况，((ans%mod)+mod)%mod,我比赛时就是错在这了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int maxn = 1e5+5;
const int mod = 1e9+7;
char s[maxn];
struct node{
ll val;
int cnt;
}tr[maxn<<2];
void pushup(int rt)
{
tr[rt].val=(tr[rt<<1].val+tr[rt<<1|1].val)%mod;
tr[rt].cnt=(tr[rt<<1].cnt+tr[rt<<1|1].cnt);
}
void update(int rt,int l,int r,int pos,int op)
{
if(l==r)
{
tr[rt].val=(tr[rt].val+1ll*pos*op)%mod;
tr[rt].cnt+=op;
return;
}
int mid = (l+r)>>1;
if(pos<=mid)
update(rt<<1,l,mid,pos,op);
else update(rt<<1|1,mid+1,r,pos,op);
pushup(rt);
}
pli merge(pli a, pli b) {
return{(a.first+b.first)%mod,a.second+b.second};
}
pli query(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return {tr[rt].val,tr[rt].cnt};
}
int mid = (l+r)>>1;
if(R<=mid)return query(rt<<1,l,mid,L,R);
else if(L>mid)return query(rt<<1|1,mid+1,r,L,R);
else return merge(query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R));
}
int main()
{
int n;
vector<int>v;
scanf("%d",&n);
getchar();
scanf("%s",s+1);
for(int i=1;i<=n;i++)
if(s[i]=='1')
{
v.push_back(i);
update(1,1,n,i,1);
}
ll ans=0;
if(v.size()<=1)
printf("0\n");
else
{
int cnt=1;
ll now = 0;
for(int i=v.size()-2;i>=0;i--)
{
now = (now + 1ll*cnt*(v[i+1]-v[i]))%mod;
ans = (ans+now)%mod;
cnt++;
}
printf("%lld\n",ans);
}
int m;
scanf("%d",&m);
while(m--)
{
int q,pos;
scanf("%d%d",&q,&pos);
if(q==1)
{
pli a =query(1,1,n,1,pos);
pli b =query(1,1,n,pos,n);
ans = (ans+((1ll*a.second*pos%mod)-(1ll*a.first%mod)+(1ll*b.first%mod)-(1ll*b.second*pos%mod)))%mod;
update(1,1,n,pos,1);
}
else
{
pli a =query(1,1,n,1,pos);
pli b =query(1,1,n,pos,n);
ans = (ans-((1ll*a.second*pos%mod)-(1ll*a.first%mod)+(1ll*b.first%mod)-(1ll*b.second*pos%mod)))%mod;
update(1,1,n,pos,-1);
}
ans=((ans%mod)+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}H.牛牛的k合因子数
题解:埃式筛筛出质数，然后对于合数再筛一遍，然后统计每个数字被筛到的次数。桶排序一下即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
int vis[maxn];
int cnt[maxn],ans[maxn];
int main()
{
memset(cnt,0,sizeof(cnt));
int n,m;
scanf("%d%d",&n,&m);
for(int i=2;i<=n/2;i++)
{
if(vis[i])continue;
for(int j=2*i;j<=n;j+=i)
{
vis[j]=1;
}
}
for(int i=1;i<=n;i++)
{
if(!vis[i])continue;
for(int j=i;j<=n;j+=i)
cnt[j]++;
}
for(int i=1;i<=n;i++)
ans[cnt[i]]++;
while(m--)
{
int k;
scanf("%d",&k);
printf("%d\n",ans[k]);
}
return 0;
}I.牛牛的汉诺塔
题解：发现n只有60，首先想到能不能打表，发现直接打到60好像要很久，就打了10组找规律。其实也很好找和4有关＋i、+2i总结一下就行。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100;
ll res=0;
ll res1[maxn],res2[maxn],res3[maxn],res4[maxn];
void init(){
res1[1]=1,res2[1]=1,res3[1]=2,res4[1]=1;
for(int i=2;i<=35;i++){
res1[i]=res1[i-1]*4-i+2;
res2[i]=res2[i-1]*4-2*i+3;
res3[i]=res3[i-1]*4+2*i;
res4[i]=res4[i-1]*4+i;
}
}
int main(){
int n;
cin>>n;
init();
if(n==1) {
printf("A->B:%d\n", 0);
printf("A->C:%d\n", 1);
printf("B->A:%d\n", 0);
printf("B->C:%d\n", 0);
printf("C->A:%d\n", 0);
printf("C->B:%d\n", 0);
cout<<"SUM:1\n";
return 0;
}
if(n==2) {
printf("A->B:%d\n", 1);
printf("A->C:%d\n", 1);
printf("B->A:%d\n", 0);
printf("B->C:%d\n", 1);
printf("C->A:%d\n", 0);
printf("C->B:%d\n", 0);
cout<<"SUM:3\n";
return 0;
}
if(n==3) {
printf("A->B:%d\n", 1);
printf("A->C:%d\n", 3);
printf("B->A:%d\n", 1);
printf("B->C:%d\n", 1);
printf("C->A:%d\n", 0);
printf("C->B:%d\n", 1);
cout<<"SUM:7\n";
return 0;
}
printf("A->B:%lld\n", res1[n/2]);
res+=res1[n/2];
printf("A->C:%lld\n", res2[(n+1)/2]);
res+=res2[(n+1)/2];
printf("B->A:%lld\n", res4[(n+1)/2-1]);
res+=res4[(n+1)/2-1];
printf("B->C:%lld\n", res1[n/2]);
res+=res1[n/2];
printf("C->A:%lld\n", res3[n/2-1]);
res+=res3[n/2-1];
printf("C->B:%lld\n", res4[(n+1)/2-1]);
res+=res4[(n+1)/2-1];
cout<<"SUM:"<<res<<endl;
return 0;
}J.牛牛的宝可梦Go
通过Floyd可以算出所有的距离，后面显然是按时间排序，可以发现这道题是道dp题。对于每一步我们肯定要找前面所有点里能走里面的最大值加上它，可是这样的话时间复杂度为O(m²)。然后我们注意到题目里面n<=200,而且设计不存在任何一个时刻同时刷出两只及以上的宝可梦。这就说明图中最大的距离不会超过200并且每两个点的时间差肯定大于等于1。所以说我们每次统计[0，i-200]之间的最大值，因为当前点肯定可以到达这里面的所有点。对于[i-200,i]我们暴力找即可。将复杂度降到了O(200m)就可以顺利算出来了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int maxp = 505;
const ll INF = 1ll<<60;
ll premax,dp[maxn],ans,dis[maxp][maxp];
int n,m,N,u,v;
struct node{
int p,t;
ll val;
bool operator<(node const & C)const{
return t<C.t;
}
}a[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=(i==j)?0:INF;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
dis[u][v]=dis[v][u]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d%d%lld",&a[i].t,&a[i].p,&a[i].val);
sort(a+1,a+N+1);
a[0].p=1;
for(int i=1;i<=N;i++)
{
if(i>200)
{
premax=max(premax,dp[i-200]);
dp[i]=a[i].val+premax;
}
else
dp[i]=-INF;
for(int j=1;j<=200&&i-j>=0;j++)
if(a[i].t-a[i-j].t>=dis[a[i].p][a[i-j].p])\
dp[i]=max(dp[i],a[i].val+dp[i-j]);
ans=max(ans,dp[i]);
}
printf("%lld\n",ans);
return 0;
}官方题解
这真的是一套很好的题目，出题人题解也写得非常好。
京公网安备 11010502036488号