07月28, 2018

7.28 牛客网练习赛23

[比赛链接] (https://www.nowcoder.com/acm/contest/156#question)

知识点总结

  • A 暴力
  • B 记忆化搜索
  • C 暴力
  • D 离线O(m)查找长度为m的子序列
  • E 走马灯数,原根
  • F 树上随机删除子树问题

题解

A

直接贪心即可

#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
#define mem(a,x) memset(a,x,sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back

const ll MOD=1e9+7;
const ll N=1e5+50;
const db eps=1e-9;

inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;}
inline void addp(ll& x,ll y,ll p = MOD){x += y;if (x>=MOD) x-=MOD;}
inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

int num[13]{100,50,20,10,5,2,1,50,20,10,5,2,1};
int cnt[13];
int main(){
std::ios::sync_with_stdio(false);
  int T;cin>>T;
  while(T--){
    int a,b;
    cin>>a>>b;
    llp(i,0,7){
      cnt[i] = a/num[i];
      a%=num[i];
    }
    llp(i,7,13){
      cnt[i] = b/num[i];
      b%=num[i];
    }
    lp(i,13) {
      cout<<cnt[i];if (i!=12) cout<<" ";
    }
  }
}

B

显然是个递归,因此记忆化搜索一下就好。

#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
#define mem(a,x) memset(a,x,sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back

const ll MOD=1e9+7;
const ll N=1e5+50;
const db eps=1e-9;

inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;}
inline void addp(ll& x,ll y,ll p = MOD){x += y;if (x>=MOD) x-=MOD;}
inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

unordered_map<int,ll> ma;
ll dfs(int x){
  if (x == 1) return 0;
  if (ma.count(x)) return ma[x];
  else{
    int u = x/2;int v=x-u;
    return ma[x] = 1LL*u*v+dfs(u)+dfs(v);
  }
}
int main(){
std::ios::sync_with_stdio(false);
  int T,n;cin>>T;
  while(T--){
    cin>>n;
    cout<<dfs(n)<<endl;
  }
}

C

题意:

给n个数,选取任意个数,使得这些数的按位与的最低位1最高;在保证最低位1最高的情况下,选取的数尽量多。

解法:

一开始觉得是取所有数的最高位1的最大值,输出所有最高位1为该值的数。

但是很显然错了,因为最高位1同为该值未必按位与的结果就是该值,因为可能所有最高位1为该值的数都含有共同的更低位的1。

可以证明:若k个数的按位与含有某个位的1,那么它的任意非空子集的按位与也含有这个1.

因此,正解是,从高到低枚举每一位1,求所有含有该位1的数的按位与,若得到的结果的最低位1是该枚举值,则为答案。

小check是,如果所有数都是0,则输出所有数。

#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
#define mem(a,x) memset(a,x,sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back

const ll MOD=1e9+7;
const ll N=1e5+50;
const db eps=1e-9;

inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;}
inline void addp(ll& x,ll y,ll p = MOD){x += y;if (x>=MOD) x-=MOD;}
inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

ll a[N];
int main(){
  std::ios::sync_with_stdio(false);
  int n;cin>>n;
  lp(i,n) cin>>a[i];
  ll ans=0;
  int k=0;

  rlp(i,0,31){
    ll q = (1LL<<i);
    ll p = (1LL<<31)-1;
    k=0;
    lp(j,n){
      if (a[j]&q){
        p &= a[j];
        k++;
      }
    }
    if (p % q == 0) {
      ans = q;
      break;
    }
  }
  if (ans==0){
    cout<<n<<endl;
    lp(i,n) {
      cout<<a[i];if(i!=n-1) cout<<" ";
    }
    cout<<endl;
  }
  else{
    cout<<k<<endl;
    lp(i,n) {
      if (a[i]&ans) {
        cout<<a[i];
        if(--k) cout<<" ";
      }
    }
    cout<<endl;
  }
}

D

题意

给个长度为3000的由1..9组成的序列 s,求有多少个不同的1..9的排列为序列s的子序列。

解法

先考虑暴搜,再考虑优化。

搜子序列的复杂度太大了,因为一个长度为n的序列的长度为m的子序列有C(n,m)个。

而1..9的排列只有9!<4e5个, 因此应该枚举每一个排列,在序列s中找该排列。

暴力找的话复杂度是O(n)。因为字符集很小,我们想到如果预处理每个位置i的下一个数字c的位置,就可以O(m)查找。

m!O(m) = 99! ,这个复杂度是可以接受的。

预处理的方法就是倒过来扫一遍,O(n)。

#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
#define mem(a,x) memset(a,x,sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back

const ll MOD=1e9+7;
const ll N=3e3+50;
const db eps=1e-9;

inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;}
inline void addp(ll& x,ll y,ll p = MOD){x += y;if (x>=MOD) x-=MOD;}
inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));
int last[9];
char str[N];
int ss[10] = {0,1,2,3,4,5,6,7,8};
int nxt[N][9];
// string str;
// set<string> S;
bool check(int len){
  int pos=0;
  lp(i,9){
    pos = nxt[pos][ss[i]];
    if (pos>len) return false;
  }
  return true;
}
int main(){
  scanf("%s",str+1);
  int len = strlen(str+1);
  lp(j,9) last[j] = len+1;
  rlp(i,1,len+1){
    lp(j,9) nxt[i][j] = last[j];
    last[str[i]-'a'] = i;
  }
  lp(j,9) nxt[0][j] = last[j];
  int ans=0;
  do{
    if (check(len)) ans++;
  }while(next_permutation(ss,ss+9));
  printf("%d\n",ans);
}

E

题意

求拥有长度为n的走马灯数的小于x的最大进制b

解法

关于走马灯数,见 【链接】142857这个数为什么这么神秘呢?还有其他的 https://www.zhihu.com/question/19761522

所以答案就是n+1的小于x的最大原根。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000010
typedef long long ll;
ll n, x, cnt, len, pr[MAXN], prime[MAXN], isprime[MAXN];
ll gcd(ll a, ll b) {
    return !b ? a : gcd(b, a % b);
}
ll fast(ll a, ll b, ll mod) {
    ll sum = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) sum = sum * a % mod;
    return sum;
}
void get() {
    for (ll i = 2; i <= MAXN - 10; i++) {
        if (!isprime[i]) prime[++cnt] = i;
        for (ll j = 1; j <= cnt && prime[j] * i <= MAXN - 10; j++) {
            isprime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
void pre(ll p) {
    ll temp = p - 1;
    for (ll i = 1; i <= cnt; i++) {
        if (temp % prime[i] == 0) pr[++len] = prime[i];
        while (temp % prime[i] == 0) temp /= prime[i];
    }
    if (temp > 1) pr[++len] = temp;
}
bool check(ll d, ll p) {
    if (gcd(p, d) != 1) return 0;
    for (ll i = 1; i <= len; i++)
        if (fast(d, (p - 1) / (pr[i]), p) == 1) return 0;
    return 1;
}
int main() {
    scanf("%lld%lld", &n, &x);
    get();
    if (isprime[n + 1]) {
        printf("-1\n");
        return 0;
    }
    pre(n + 1);
    for (ll i = x - 1; i > 1; i--)
        if (check(i, n + 1)) {
            printf("%lld\n", i);
            return 0;
        }
    printf("-1\n");
    return 0;
}

F

题意

在树上随机选点u,删u为根的子树(u包括树根),求删完整颗树的操作次数的期望。

解法

【链接】Codeforces280CGameonTree概率dp树上随机删子树求删 https://blog.csdn.net/acmmmm/article/details/41688045

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define REP(i, x, n) for (int i = (x); i < (n); ++i)
#define PER(i, x, n) for (int i = (n) -1; i >= x; --i)
#define endl "\n"
#define DE puts("----------")
#define CASE(i, ans) cout << "Case #" << (i) << ": " << (ans) << "\n"
#define lowbit(x) ((x) & (-(x)))
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define PI acos(-1.0)
#define MOD 1000000007
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
__gnu_pbds::cc_hash_table<string, int> hash1;
__gnu_pbds::gp_hash_table<string, int> hash2;
__gnu_pbds::priority_queue<int> pq;
__gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag> rbtree;
typedef bitset<1005> Bitset;
const int maxn = 100050;
ll n, m, k;
const long long mod = 998244353;
int a[10000];
vector<int> e[maxn];
int sz[maxn];
vector<ll> ans1;
int inv[maxn];
ll ans2 = 1;
ll qmul(ll a, ll b, ll p = mod) { // return a*b %p
    ll t = 0;
    for (; b; a = a * 2 % p, b >>= 1) {
        if (b & 1) t = (t + a) % p;
    }
    return t;
}
inline long long pow_mod(long long a, long long n) {
    long long ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
long long getinv(long long n) {
    return pow_mod(n, mod - 2);
}
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b) {
        ll r = extgcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    } else {
        x = 1;
        y = 0;
        return a;
    }
}
ll solve(ll a, ll b, ll M) {
    ll x, y, r = extgcd(a, M, x, y);
    if (b % r)
        return -1;
    else
        x = (x + M) % M * b / r;
    return x % (M / r);
}
void dfs(int u, int fa, ll d) {
    sz[u] = 1;
    for (auto &x : e[u]) {
        if (x != fa) {
            dfs(x, u, d + 1);
            sz[u] += sz[x];
        }
    }
    ans1.push_back(d);
    ans2 = qmul(ans2, d);
}
ll ans3 = 0;
int main() {
    ios::sync_with_stdio(0);
    int x, y;
    cin >> n;
    inv[1] = 1;
    for (int i = 2; i <= 100005; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    REP(i, 0, n - 1) {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0, 1);
    for (auto &x : ans1) {
        ans3 = (ans3 + qmul(ans2, inv[x])) % mod;
    }
    cout << solve(ans2, ans3, mod) << endl;
    return 0;
}
`

本文链接:https://www.haolovej.com/post/nowcoder_practice23.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。