A
solution:
入门的二维动态规划，每个点只会影响其右方和下方的位置，遍历输出答案即可
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
string s[55];
int dp[55][55];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
}
dp[0][0] = 1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char c = s[i][j];
if(c == 'R'){
dp[i][j+1] += dp[i][j] ;
dp[i][j+1] %= mod;
}
if(c == 'D'){
dp[i+1][j] += dp[i][j];
dp[i+1][j] %= mod;
}
if(c == 'B'){
dp[i+1][j] += dp[i][j];
dp[i][j+1] += dp[i][j];
dp[i+1][j] %= mod;
dp[i][j+1] %= mod;
}
}
}
cout<<dp[n-1][m-1]<<endl;
return 0;
}B
solution:
构造，和第一题要求相反，要求构造迷宫，考虑二进制,直接上图
左图是初始的矩阵，对角线是B，往下一行是R，其余全是D
右图是构造出n=13的矩阵 ，我们将13的二进制为1的位置的下标对应的位置的R都变成B即可
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
int a[55][55];
int main()
{
ll k;
cin>>k;
k %= mod;
cout<<"50 50"<<endl;
for(int i=1;i<=40;i++){
a[i][i] = 1;
a[i][i+1] = 2;
a[i+1][i] = 3;
for(int j=i+2;j<=49;j++){
a[j][i] = 2;
}
}
for(int i=1;i<=50;i++){
a[50][i] = 3;
}
for(int i=30;i>=1;i--)
{
int x = (1<<(i-1));
if(k >= x){
k -= x;
a[i+1][i] = 1;
}
if(k == 0){
break ;
}
}
for(int i=1;i<=50;i++){
for(int j=1;j<=50;j++){
if(a[i][j] == 1){
cout<<"B";
}
else if(a[i][j] == 2){
cout<<"D";
}
else if(a[i][j] == 3){
cout<<"R";
}
else{
cout<<"R";
}
}
cout<<endl;
}
return 0;
}C
solution:
题目长，但是题简单，题目明确说明“无论是否发生数组越位或者非法访问，输入数据都要完整读入",所以不要中途break，按照题目写应该没什么问题
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1004;
int a[maxn][maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
ll n,m,x,y;
int p;
int flag = 0,val;
cin>>n>>m>>p;
ll maxx = n*m - 1;
while(p--)
{
cin>>x>>y>>val;
if(flag == 2){
continue ;
}
ll pos =m*x + y;
if(pos > maxx || pos < 0){
flag = 2;
continue ;
}
if(x < 0 || x >= n || y < 0 || y >= m){
flag = 1;
int xx = (int)pos/m;
int yy = (int)pos%m;
a[xx][yy] = val;
continue ;
}
a[x][y] = val;
}
//cout<<"yes"<<flag<<endl;
if(flag == 2){
printf("Runtime error\n");
continue ;
}
if(flag == 1){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j != 0)
printf(" ");
printf("%d",a[i][j]);
}
printf("\n");
}
printf("Undefined Behaviour\n");
continue ;
}
if(flag == 0){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j != 0)
printf(" ");
printf("%d",a[i][j]);
}
printf("\n");
}
printf("Accepted\n");
continue ;
}
}
return 0;
}D
solution:
按照题目意思写出来基本上就对了，记得先用牛客本地数据编译一遍
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
map<int , int> mp;
int a[maxn];
int main()
{
int sum = 0 ,n;
scanf("%d",&n);
memset(a, -1 ,sizeof(a));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i] != -1){
sum++;
mp[a[i]] = i;
}
}
printf("The size of the tree is %d\n",sum);
printf("Node %d is the root node of the tree\n",a[1]);
for(int i=1;i<=sum;i++)
{
printf("The father of node %d is %d, the left child is %d, and the right child is %d\n",i , a[mp[i]/2] , a[mp[i]*2] , a[mp[i]*2 + 1]);
}
return 0;
}
E
solution:
这个题确实可以考虑笨一点的办法
考虑二进制对答案的贡献，假设[l1,r1]中二进制第k位0的个数位cntx0，1的个数位cnty0；同样的[l2,r2]中二进制第k位0的个数位cntx1，1的个数位cnty1，那么产生的贡献就是2^k×(cntx0×cnty1 + cntx1×cnty0)，理解了这个式子，就可以有技巧的解决这一道题了，but如果想考虑少一点，用容斥的方法去做
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll pow_mod(ll a,ll b,ll mod){
ll ans = 1;
a%=mod;
while(b){
if(b&1)
ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
const ll mod = 1e9 + 7;
ll z = 1;
ll get(ll n,ll k)//从1到n的第k位2进制有多少1
{
ll cnt = 0;
n++;
cnt = n/(2ll<<k)*(z<<k);
n %= (2ll<<k);
if(n > (z<<k))
cnt += (z<<k);
else
cnt += n;
return cnt;
}
ll f(ll l ,ll r,ll k){
return ((get(r,k) - get(l-1,k))%mod + mod)%mod;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll l1,l2,r1,r2,ans1 = 0,ans2 = 0;
scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
ll len1 = (r1 - l1 + 1)%mod , len2 = (r2 - l2 + 1)%mod;
ans1 = pow_mod(len1*len2%mod, mod - 2,mod);
for(ll i=0;i<=62;i++){
ll x = f(l1 , r1 , i);
ll y = f(l2 , r2 , i);
ans2 = (ans2 + (z<<i)%mod*x%mod*(len2 - y)%mod)%mod;
ans2 = (ans2 + (z<<i)%mod*y%mod*(len1 - x)%mod)%mod;
}
ans1 = (ans1*ans2%mod + mod)%mod;
printf("%lld\n",ans1);
}
return 0;
}
F
solution:
前缀和，考虑新出现的一个点对答案的贡献，就等于新出现的点再重新和前n-1个点连n-1条边，每次只需记录上一个点的位置，维护前缀和
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
const int maxn = 100005;
char s[maxn];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s);
int pos = 0;
for(int i=0;i<n;i++){
if(s[i] == '1'){
pos = i;
break ;
}
}
ll ans = 0;
ll len = 0;
int pre = pos, k = 1;
for(int i = pos+1;i<n;i++)
{
if(s[i] == '1'){
len = len + k*(i - pre);
ans = ans + len;
len %= mod;
ans %= mod;
pre = i;
k++;
}
//cout<<ans<<endl;
}
cout<<ans;
return 0;
}G
solution:
待补
std：
H
solution:
先处理出来1e5内的所有质数，枚举1e5，记录每一个数的因子非质数的个数，O(1)输出答案即可
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 100010;
int a[maxx];
bool pri[maxx];
int cnt1 = 0,cnt2 = 0;
void prime()
{
for(int i=2;i<maxx;i++)
pri[i] = 1;
for(int i=2;i<maxx;i++)
{
if(pri[i])
a[cnt1++] = i;
for(int j=0;(j<cnt1 && i*a[j]<maxx);j++)
{
pri[i*a[j]] = 0;
if(i%a[j] == 0)
break;
}
}
}
int ans[maxx];
int n,m;
map<int ,int > mp;
void solve()
{
for(int i=3;i<=n;i++){
if(pri[i]){
continue ;
}else{
ans[i]++;
}
for(int j=2;j*j<=i;j++){
if(i%j == 0){
int x = i/j;
int y = j;
if(x != y){
if(!pri[x]){
ans[i]++;
}
if(!pri[y]){
ans[i]++;
}
}else{
if(!pri[x]){
ans[i]++;
}
}
}
}
}
for(int i=1;i<=n;i++){
mp[ans[i]]++;
}
}
int main()
{
cin>>n>>m;
prime();
solve();
int x;
while(m--){
scanf("%d",&x);
printf("%d\n",mp[x]);
}
return 0;
}I
solution:
递推，dp[i][j][k]表示在第i种情况下n层汉诺塔产生第k中操作的次数
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[7][70][7];// 第i种情况的j层汉诺塔产生第k种操作的次数
int main()
{
int n;
cin>>n;
for(int i=0;i<6;i++)
dp[i][1][i] = 1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<6;j++)
{
dp[j][i][j]++;
}
for(int j=0;j<6;j++) dp[0][i][j] += dp[1][i-1][j] + dp[5][i-1][j];
for(int j=0;j<6;j++) dp[1][i][j] += dp[0][i-1][j] + dp[3][i-1][j];
for(int j=0;j<6;j++) dp[2][i][j] += dp[3][i-1][j] + dp[4][i-1][j];
for(int j=0;j<6;j++) dp[3][i][j] += dp[2][i-1][j] + dp[1][i-1][j];
for(int j=0;j<6;j++) dp[4][i][j] += dp[5][i-1][j] + dp[2][i-1][j];
for(int j=0;j<6;j++) dp[5][i][j] += dp[4][i-1][j] + dp[0][i-1][j];
}
printf("A->B:%lld\n", dp[1][n][0]);
printf("A->C:%lld\n", dp[1][n][1]);
printf("B->A:%lld\n", dp[1][n][2]);
printf("B->C:%lld\n", dp[1][n][3]);
printf("C->A:%lld\n", dp[1][n][4]);
printf("C->B:%lld\n", dp[1][n][5]);
printf("SUM:%lld\n", 1ll*(1ll*1<<1ll*n) - 1);
return 0;
}
京公网安备 11010502036488号